Project 1: Threads
******************

In this assignment, we give you a minimally functional thread system. Your job is to extend the functionality of this system to gain a better understanding of synchronization problems. Additionally, you will use at least part of this increased functionality in future assignments.

You will be working in the threads and devices directories for this assignment.  Compilation should be done in the threads directory.

Understanding Threads
=====================

The first step is to read and understand the initial thread system. Pintos, by default, implements thread creation and thread completion, a simple scheduler to switch between threads, and synchronization primitives (semaphores, locks, and condition variables). However, there's a lot of magic going on in some of this code, so you should compile and run the base system to see a simple test of the code.  You should trace the execution using your favorite debugger to get a sense for what's going on.

When a thread is created, you are creating a new context to be scheduled. You provide a function to be run in this context as an argument to thread_create(). The first time the thread is scheduled and runs, it will start from the beginning of that function and execute it in the context. When that function returns, that thread completes. Each thread, therefore, acts like a mini-program running inside Pintos, with the function passed to thread_create() acting like main().

At any given time, Pintos is running exactly one thread, with the others switched out.  The scheduler decides which thread to run next when it needs to switch between them.  (If no thread is ready to run at any given time, then the special ``idle'' thread runs.)  The synchronization primitives are used to force context switches when one thread needs to wait for another thread to do something.

The exact mechanics of a context switch are pretty gruesome and have been provided for you in switch.S (this is 80X86 assembly; don't worry about understanding it). It involves saving the state of the currently running thread and restoring the state of the thread we're switching to. Slowly trace through a context switch to see what happens.  Be sure to keep track of each thread's address and state, and what procedures are on the call stack for each thread. You will notice that when one thread calls switch_threads(), another thread starts running, and the first thing the new thread does is to return from switch_threads(). We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand why the switch_threads() that gets called is different from the switch_threads() that returns.

Warning: In Pintos, each thread is assigned a small, fixed-size execution stack just under 4 kB in size.  The kernel does try to detect stack overflow, but it cannot always succeed.  You ma cause bizarre problems, such as mysterious kernel panics, if you declare large data structures as non-static local variables, e.g. int buf[1000];.  Alternatives to stack allocation include the page allocator in threads/palloc.c and the block allocator in threads/malloc.c.  Note that the page allocator doles out 4 kB chunks and that malloc() has a 2 kB block size limit.  If you need larger chunks, consider using a linked structure instead.

Debugging versus Testing
========================

When you're debugging code, it's useful to be able to be able to run a program twice and have it do exactly the same thing.  On second and later runs, you can make new observations without having to discard or verify your old observations.  This property is called ``reproducibility.''  The simulator we use, Bochs, can be set up for reproducibility.  If you use the Bochs configuration files we provide, which specify ips: N where N is a number of simulated instructions per second, your simulations can be reproducible.

Of course, a simulation can only be reproducible from one run to the next if its input is the same each time.  For simulating an entire computer, as we do, this means that every part of the computer must be the same.  For example, you must use the same disks, the same version of Bochs, and you must not hit any keys on the keyboard (because you could not be sure to hit them at exactly the same point each time) during the runs.

While reproducibility is useful for debugging, it is a problem for testing thread synchronization, an important part of this project.  In particular, when Bochs is set up for reproducibility, timer interrupts will come at perfectly reproducible points, and therefore so will thread switches.  That means that running the same test several times doesn't give you any greater confidence in your code's correctness than does running it only once.

So, to make your code easier to test, we've added a feature to Bochs that makes timer interrupts come at random intervals, but in a perfectly predictable way.  In particular, if you put a line ips-jitter: SEED, where SEED is an integer, into your Bochs configuration file, then timer interrupts will come at irregularly spaced intervals.  Within a single SEED value, execution will still be reproducible, but timer behavior will change as SEED is varied.  Thus, for the highest degree of confidence you should test your code with many seed values.

Tips
====

There should be no busy-waiting in any of your solutions to this assignment.  Furthermore, resist the temptation to directly disable interrupts in your solution by calling intr_disable() or intr_set_level(), although you may find doing so to be useful while debugging.  Instead, use semaphores, locks and condition variables to solve synchronization problems.  Hint: read the comments in threads/synch.h if you're unsure what synchronization primitives may be used in what situations.

Given some designs of some problems, there may be one or two instances in which it is appropriate to directly change the interrupt levels instead of relying on the given synchroniztion primitives.  This must be justified in your DESIGNDOC file.  If you're not sure you're justified, ask!

While all parts of this assignment are required if you intend to earn full credit on this project, keep in mind that Problem 2 (Join) will be needed for future assignments, so you'll want to get this one right.  We don't give out solutions, so you're stuck with your Join code for the whole quarter.  Problem 1 (Alarm Clock) could be very handy, but not strictly required in the future.  The upshot of all this is that you should focus heavily on making sure that your implementation of Join works correctly, since if it's broken, you will need to fix it for future assignments.  The other parts can be turned off in the future if you find you can't make them work quite right.

Also keep in mind that Problem 4 (the MFQS) builds on the features you implement in Problem 3, so to avoid unnecessary code duplication, it would be a good idea to divide up the work among your team members such that you have Problem 3 fully working before you begin to tackle Problem 4.

Problem 1-2: Alarm Clock
========================

Improve the implementation of the timer device defined in devices/timer.c by reimplementing timer_msleep(0. Threads call timer_msleep(X) to suspend execution until time has advanced by at least X milliseconds.  This is useful for threads that operate in real-time, for example, for blinking the cursor once per second.  There is no requirement that threads start running immediately after waking up; just put them on the ready queue after they have waited for approximately the right amount of time.

A working implementation of this function is provided.  However, the version provided is poor, because it ``busy waits,'' that is, it spins in a tight loop checking the current time until the current time has advanced far enough.  This is undesirable because it wastes time that could potentially be used more profitably by another thread.  Your solution should not busy wait.

The argument to timer_msleep() is expressed in milliseconds. You must convert it into timer ticks, rounding up.  The code provided does this acceptably; there is no need to change it.

Problem 1-2: Join
=================

Implement thread_join(struct thread *) in threads/thread.c.  There is already a prototype for it in threads/thread.h, which you should not change.  This function causes the currently running thread to block until thread passed as an argument exits.  If A is the running thread and B is the argument, then we say that ``A joins B'' in this case.

The model for thread_join() is the wait system call in Unix-like systems.  (Try reading the manpages.)  That system call can only be used by a parent process to wait for a child's death.  You should implement thread_join() to have the same restriction. That is, a thread may only join on its immediate children.

A thread need not ever be joined.  Your solution should properly free all of a thread's resources, including its struct thread, whether it is ever joined or not, and regardless of whether the child exits before or after its parent.  That is, a thread should be freed exactly once in all cases.

Joining a given thread is idempotent.  That is, joining a thread T multiple times is equivalent to joining it once, because T has already exited at the time of the later joins.  Thus, joins on T after the first should return immediately.

The behavior of calling thread_join() on an thread that is not the caller's child is undefined.  You need not handle this case gracefully.

Consider all the ways a join can occur: nested joins (A joins B when B is joined on C), multiple joins (A joins B, then A joins C), and so on.  Does your join work if thread_join() is called on a thread that has not yet been scheduled for the first time?  You should handle all of these cases.  Write test code that demonstrates the cases your join works for.  Don't overdo the output volume, please!

Be careful to program this function correctly.  You will need its functionality for project 2.

Problem 1-3 Priority Scheduling
===============================

Implement priority scheduling in Pintos.  Priority scheduling is a key building block for real-time systems.  Implement functions thread_set_priority() to set the priority of a thread and thread_get_priority() to get the priority of a thread.  There are already prototypes for these functions in threads/thread.h, which you should not change.

When a thread is added to the ready list that has a higher priority than the currently running thread, the current thread should immediately yield the processor to the new thread.  Similarly, when threads are waiting for a lock, semaphore or condition variable, the highest priority waiting thread should be woken up first.  A thread's priority may be set at any time, including while the thread is waiting on a lock, semaphore, or condition variable.

One issue with priority scheduling is ``priority inversion'': if a high priority thread needs to wait for a low priority thread (for instance, for a lock held by a low priority thread, or in thread_join() for a thread to complete), and a middle priority thread is on the ready list, then the high priority thread will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is to have the waiting thread ``donate'' its priority to the low priority thread while it is holding the lock, then recall the donation once it has acquired the lock. Implement this fix.

You will need to account for all different orders that priority donation and inversion can occur.  Be sure to handle multiple donations, in which multiple priorities are donated to a thread.  You must also handle nested donation: given high, medium, and low priority threads H, M, and L, respectively, and supposing H is waiting on a lock that M holds and M is waiting on a lock that L holds, both M and L should be boosted to H's priority.

You only need to implement priority donation when a thread is waiting for a lock held by a lower-priority thread. You do not need to implement this fix for semaphores, condition variables or joins. However, you do need to implement priority scheduling in all cases.

Problem 1-4 Advanced Scheduler
==============================

Implement Solaris's multilevel feedback queue scheduler (MFQS), as explained below, to reduce the average response time for running jobs on your system.

Demonstrate that your scheduling algorithm reduces response time relative to the original Pintos scheduling algorithm (round robin) for at least one workload of your own design (i.e. in addition to the provided test).

You may assume a static priority for this problem. It is not necessary to ``re-donate'' a thread's priority if it changes (although you are free to do so).

FAQ
===

 1. General FAQs

      1. I am adding a new .h or .c file.  How do I fix the Makefiles?

          To add a .c file, edit the top-level Makefile.build. You'll want to add your file to variable DIR_SRC, where DIR is the directory where you added the file.  For this project, that means you should add it to threads_SRC, or possibly devices_SRC if you put in the devices directory.  Then run make.  If your new file doesn't get compiled, run make clean and then try again.

          There is no need to edit the Makefiles to add a .h file.

      2. If a thread finishes, should its children be terminated immediately, or should they finish normally?

          You should feel free to decide what semantics you think this should have. You need only provide justification for your decision.

      3. Why can't I disable interrupts?

          Turning off interrupts should only be done for short amounts of time, or else you end up losing important things such as disk or input events.  Turning off interrupts also increases the interrupt handling latency, which can make a machine feel sluggish if taken too far. Therefore, in general, setting the interrupt level should be used sparingly.  Also, any synchronization problem can be easily solved by turning interrupts off, since while interrupts are off, there is no concurrency, so there's no possibility for race condition.

          To make sure you understand concurrency well, we are discouraging you from taking this shortcut at all in your solution.  If you are unable to solve a particular synchronization problem with semaphores, locks, or conditions, or think that they are inadequate for a particular reason, you may turn to disabling interrupts.  If you want to do this, we require in your design document a complete justification and scenario (i.e. exact sequence of events) to show why interrupt manipulation is the best solution.  If you are unsure, the TAs can help you determine if you are using interrupts too haphazardly.  We want to emphasize that there are only limited cases where this is appropriate.

      4. Where might interrupt-level manipuation be appropriate?

          You might find it necessary in some solutions to the Alarm problem.

          You might want it at one small point for the priority scheduling problem.  Note that it is not required to use interrupts for these problems.  There are other, equally correct solutions that do not require interrupt manipulation.  However, if you do manipulate interrupts and correctly and fully document it in your design document, we will allow limited use of interrupt disabling.

 2. Alarm Clock FAQs

      1. Why can't I use most synchronization primitives in an interrupt handler?

          As you've discovered, you cannot sleep in an external interrupt handler.  Since many lock, semaphore, and condition variable functions attempt to sleep, you won't be able to call those in timer_interrupt().  You may still use those that never sleep.

          Having said that, you need to make sure that global data does not get updated by multiple threads simultaneously executing timer_msleep().  Here are some pieces of information to think about:

           a. Interrupts are turned off while timer_interrupt() runs.  This means that timer_interrupt() will not be interrupted by a thread running in timer_msleep().

           b. A thread in timer_msleep(), however, can be interrupted by a call to timer_interrupt(), except when that thread has turned off interrupts.

           c. Examples of synchronization mechanisms have been presented in lecture. Going over these examples should help you understand when each type is useful or needed.

      2. What about timer overflow due to the fact that times are defined as integers? Do I need to check for that?

          Don't worry about the possibility of timer values overflowing.  Timer values are expressed as signed 63-bit numbers, which at 100 ticks per second should be good for almost 2,924,712,087 years.

 3. Join FAQs

      1. Am I correct to assume that once a thread is deleted, it is no longer accessible by the parent (i.e. the parent can't call thread_join(child))?

          A parent joining a child that has completed should be handled gracefully and should act as a no-op.

 4. Priority Scheduling FAQs

      1. Doesn't the priority scheduling lead to starvation? Or do I have to implement some sort of aging?

          It is true that strict priority scheduling can lead to starvation because thread may not run if a higher-priority thread is runnable. In this problem, don't worry about starvation or any sort of aging technique.  Problem 4 will introduce a mechanism for dynamically changing thread priorities.

          This sort of scheduling is valuable in real-time systems because it offers the programmer more control over which jobs get processing time.  High priorities are generally reserved for time-critical tasks. It's not ``fair,'' but it addresses other concerns not applicable to a general-purpose operating system.

      2. After a lock has been released, does the program need to switch to the highest priority thread that needs the lock (assuming that its priority is higher than that of the current thread)?

          When a lock is released, the highest priority thread waiting for that lock should be unblocked and put on the ready to run list.  The scheduler should then run the highest priority thread on the ready list.

      3. If a thread calls thread_yield() and then it turns out that it has higher priority than any other threads, does the high-priority thread continue running?

          Yes.  If there is a single highest-priority thread, it continues running until it blocks or finishes, even if it calls thread_yield().

      4. If the highest priority thread is added to the ready to run list it should start execution immediately.  Is it immediate enough if I wait until next timer interrupt occurs?

          The highest priority thread should run as soon as it is runnable, preempting whatever thread is currently running.

      5. What happens to the priority of the donating thread?  Do the priorities get swapped?

          No.  Priority donation only changes the priority of the low-priority thread.  The donating thread's priority stays unchanged.  Also note that priorities aren't additive: if thread A (with priority 5) donates to thread B (with priority 3), then B's new priority is 5, not 8.

      6. Can a thread's priority be changed while it is sitting on the ready queue?

          Yes.  Consider this case: low-priority thread L currently has a lock that high-priority thread H wants.  H donates its priority to L (the lock holder).  L finishes with the lock, and then loses the CPU and is moved to the ready queue.  Now L's old priority is restored while it is in the ready queue.

      7. Can a thread's priority change while it is sitting on the queue of a semaphore?

          Yes.  Same scenario as above except L gets blocked waiting on a new lock when H restores its priority.

      8. Why is pubtest3's FIFO test skipping some threads! I know my scheduler is round-robin'ing them like it's supposed to!  Our output is like this:

               Thread 0 goes.
               Thread 2 goes.
               Thread 3 goes.
               Thread 4 goes.
               Thread 0 goes.
               Thread 1 goes.
               Thread 2 goes.
               Thread 3 goes.
               Thread 4 goes.

          which repeats 5 times and then

               Thread 1 goes.
               Thread 1 goes.
               Thread 1 goes.
               Thread 1 goes.
               Thread 1 goes.

          This happens because context switches are being invoked by the test when it explicitly calls thread_yield().  However, the time slice timer is still alive and so, every tick (by default), thread 1 gets switched out (caused by timer_interrupt() calling intr_yield_on_return()) before it gets a chance to run its mainline.  It is by coincidence that Thread 1 is the one that gets skipped in our example.  If we use a different jitter value, the same behavior is seen where a thread gets started and switched out completely.

          Solution: Increase the value of TIME_SLICE in devices/timer.c to a very high value, such as 10000, to see that the threads will round-robin if they aren't interrupted.

      9. What happens when a thread is added to the ready list which has higher priority than the currently running thread?

          The correct behavior is to immediately yield the processor.  Your solution must act this way.

      10. What range of priorities should be supported and what should the default priority of a thread be?

          Your implementation should support priorities from 0 through 59 and the default priority of a thread should be 29.

 5. Advanced Scheduler FAQs

      1. What is the interval between timer interrupts?

          Timer interrupts occur TIMER_FREQ times per second.  You can adjust this value by editing devices/timer.h.  The default is 100 Hz.

      2. Do I have to modify the dispatch table?

          No, although you are allowed to. It is possible to complete this problem (i.e. demonstrate response time improvement) without doing so.

      3. When the scheduler changes the priority of a thread, how does this affect priority donation?

          Short (official) answer: Don't worry about it. Your priority donation code may assume static priority assignment.

          Longer (unofficial) opinion: If you wish to take this into account, however, your design may end up being ``cleaner.''  You have considerable freedom in what actually takes place. I believe what makes the most sense is for scheduler changes to affect the ``original'' (non-donated) priority.  This change may actually be masked by the donated priority.  Priority changes should only propagate with donations, not ``backwards'' from donees to donors.

      4. What is meant by ``static priority''?

          Once thread A has donated its priority to thread B, if thread A's priority changes (due to the scheduler) while the donation still exists, you do not have to change thread B's donated priority. However, you are free to do so.

      5. Do I have to make my dispatch table user-configurable?

          No.  Hard-coding the dispatch table values is fine.