CSE 120 Nachos Project 1: Threads

Winter 2007

Due: Monday, February 5 at Midnight

Sharing Files

Submission Instructions

In this assignment, we will give you part of a working thread system. Your job is to complete it and then use it to solve several synchronization problems.

The first step is to read and understand the partial thread system we've provided. This thread system implements thread fork, thread completion, and semaphores for synchronization.

Properly synchronized code should work no matter what order the scheduler chooses to run the threads on the ready list. In other words, we should be able to put a call to Thread::Yield() (which causes the scheduler to pick another thread to run) anywhere in your code where interrupts are enabled without changing the correctness of your code. You will be asked to write properly synchronized code as part of later assignments, so understanding how to do this is crucial to being able to do the project.

To aid you in this task, code linked in with Nachos will cause Thread::Yield() to be called in a repeatable but unpredictable way. Nachos code is repeatable in that if you call it repeatedly with the same arguments, it will do exactly the same thing each time. However, if you invoke Nachos with "nachos -rs #" with a different number each time, calls to Thread::Yield() will be inserted in different places in the code.

Warning: In our implementation of threads, each thread is assigned a small, fixed-size execution stack. This may cause bizarre problems (such as segmentation faults at strange lines of code) if you declare large data structures to be automatic variables (e.g., "int buf[1000];"). You will probably not notice this during the term, but, if you do, you may change the size of the stack by modifying the StackSize #define in switch.h.

Although the solutions can be written as normal C routines, you will find organizing your code to be easier if you structure your code as C++ classes. Also, there should be no busy-waiting in any of your solutions to this assignment.

Don't worry if you don't have to write much code for each of these: the assignment is largely conceptual and not a programming chore. For some hints on getting started, here are some suggestions.

  1. [15 pts] Implement condition variables using interrupt enable and disable to provide atomicity. The file code/threads/synch.h defines the classes "Lock" and "Condition", and it is your task to implement the functions defined by those classes in synch.cc. The file badtest.cc is an example program that demonstrates how race conditions can happen inside of Nachos. It is similar in spirit to the withdraw() example from lecture. [Sample Output]

    [10 pts] You should write your code "defensively" in the sense that you should make an attempt to detect error conditions and react appropriately. For error conditions that could result in a race condition or deadlock, your library routines should exit -- there is no way to recover from these errors, so they should be fatal to the program. There is a convenient macro ASSERT() that you can use to check for error conditions and abort if necessary (grep through the Nachos source code files for examples of how to use it).

    To help motivate you to get into the habit of testing for error conditions, write test programs that test that your code correctly deals with the following situations: (1) acquiring the same Lock twice, (2) releasing a Lock that isn't held, (3) deleting a Lock that is held, (4) waiting on a condition variable without holding a Lock, (5) signaling a condition variable wakes only one thread and broadcasting wakes up all threads, (6) signaling and broadcasting to a condition variable with no waiters is a no-op, and future threads that wait will block (i.e., the signal/broadcast is "lost"), and (7) a thread calling Signal holds the Lock passed in to Signal. These are the minimal set of error conditions for which we'll test your Lock and Condition implementations. For an example of how to start writing test programs, see the testing section of the hints.

  2. [15 pts] Implement synchronous send and receive of one word messages using condition variables. Create a "Mailbox" class with the operations Mailbox::Send(int message) and Mailbox::Receive(int * Message). Send atomically waits until Receive is called on the same mailbox, and then copies the message into the receive buffer. Once the copy is made, both can return. Similarly, Receive waits until Send is called, at which point the copy is made and both calls return. Your solution should work even if there are multiple senders and receivers for the same mailbox. (Hint: this is equivalent to a zero-length bounded buffer.) Note that you cannot use explicit wait queues, Sleep, or disable/enable interrupts to implement Mailbox; the condition variables will do all of that for you. Also, it is not necessary to "match" sending and receiving threads -- a receiver does not care which sender it gets a message from, only that it does get a message if a sender is trying to send one. If you do match them, though, that is fine.

    You can implement the "Mailbox" class in synch.h and sync.cc, or in new files. If you create new files, be sure to update the dependency information in the Makefile; see Installing and Building Nachos from the Duke equivalent of this course for directions on how to do this.

    [5 pts] Write test cases that demonstrate that your implementation of the Mailbox class is faithful to the semantics described above: a receiver will only return when a sender sends, and blocks otherwise (and vice-versa); only one receiver and sender synchronize at a time, even when there are multiple senders and receivers.

  3. [15 pts] Implement Thread::Join(). Two threads are involved in Join; for the sake of intuition, let's call them the parent and the child. At a high level, Join enables the parent thread to wait for the child thread to finish. To do this, the parent thread is the one that invokes Join, and it invokes it on the child:
    (executing as the parent thread)
    
    Thread *child = new Thread("child", 1);
    child->Fork(SomeProcedure, SomeArgument);
    ...
    child->Join();  // parent blocks until child terminates
    

    To implement Join, start by adding a parameter to the thread constructor to indicate whether or not Join will be called on this thread, and then implement the new Join method using one of the high-level synchronization primitives (Locks/CVs or Semaphores); do not create another "wait queue" and Sleep the waiting thread directly (i.e., do not do anything that requires you to add code to disable/enable interrupts).

    Use the following signatures for the updated constructor and Join method:

    Thread(char* debugName, int join = 0);
    
    void Join();
    

    Your implementation should properly delete the thread control block (1) whether or not Join is to be called, and (2) whether or not the thread being Joined finishes before the Join is called. For (1), if Join will not be called on the thread, you can delete the TCB immediately when the thread exits (as currently implemented). If Join will be called on the thread, you must wait until after Join has been called and returns before you can delete the TCB (you can assume that Join will eventually be called in this case). For (2), you do not know whether the thread to be Joined will finish before another thread calls Join on that thread -- i.e., the TCB for the child cannot be deleted even if the child terminates before the parent calls Join on it. If the child finishes before the parent calls Join, you must wait to delete the child's TCB until the parent calls Join.

    The file join-example.cc is an example program where one thread calls Join() on another [Sample Output]. It should help make the semantics and use of Join more concrete. Be sure to note the use of the "-rs" switch to the nachos executable to randomizes context switches.

    [5 pts] Write test cases that test that (1) a thread that will be joined only is destroyed once Join has been called on it, (2) if a parent calls Join on a child and the child is still executing, the parent waits, (3) if a parent calls Join on a child and the child has finished executing, the parent does not block, (4) a thread does not call Join on itself, (5) Join is only invoked on threads created to be joined, (6) Join is only called on a thread that has forked, and (7) Join is not called more than once on a thread (if it is, then this could easily lead to a segmentation fault because the child is likely deleted).

  4. [15 pts] Implement preemptive priority scheduling in Nachos. Priority scheduling is a key building block for real-time systems. Add calls to the Thread class to set and get the priority of the thread. When a thread is added to the ready list that is a higher priority than the currently running thread, the thread should insert into the front of the ready list and be the next thread to run on the next context switch. When a thread is added to the ready list that is the same priority as another thread in the list (including the currently running thread), the thread should insert after the threads at that same priority (so that they will all get a chance to run). On a context switch, if there is a higher priority thread at the head of the ready list, the higher priority thread should run. If the thread at the head of the ready list has the same priority, still perform the context switch so that threads of equal priority share the CPU. If a thread is already on the ready (or a wait) list when setPriority changes the priority, you do not have to re-sort it (although you can if you want). When threads are waiting for a lock, semaphore, or condition variable, the highest priority waiting thread should be woken up first.

    Use the following signatures for the methods:

    void setPriority(int newPriority);
     int getPriority();
    

    NOTE: You need to use these names (including capitalization) and obey these signatures so that our test programs will compile to your code.

    The range of valid priorities is the entire range of an "int". Assume that all threads are created with priority 0. Roughly speaking, threads set to have a negative priority have "less priority", and threads set to have a positive priority have "more priority". Compare thread priorities directly to determine higher priority (e.g., a priority of 1 is lower than a priority of 2).

    An issue with priority scheduling is "priority inversion". If a high priority thread needs to wait for a low priority thread, such as for a lock held by a low priority thread or for a Join 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. Implement this fix separately for both situations: (1) the Lock class and (2) the Join method.

    [10 pts] Write test programs that (1) demonstrate that threads with higher priority get service first in the cases outlined above (both when added to the ready list, and when woken up when waiting on a synchronization variable), and (2) demonstrate that you solve the priority inversion problem for Locks and Join().

  5. [10 pts] You have been hired by Greenpeace to help the environment. Because unscrupulous commercial interests have dangerously lowered the whale population, whales are having synchronization problems in finding a mate. The trick is that, to have children, three whales are needed, one male, one female, and one to play matchmaker -- literally, to push the other two whales together (I'm not making this up!).

    Your job is to save the whales using either semaphores or condition variables. Create a "Whale" class with the operations Whale::Male(), Whale::Female(), and Whale::Matchmaker(). We will represent each whale as a separate thread. A male whale calls Male(), which waits until there is a waiting female and matchmaker; similarly, a female whale calls Female() and must wait until a male whale and a matchmaker are present, and a matchmaker calls Matchmaker() and must wait until a male and female are present. Once all three are present, all three return out of the methods (representing that a match has been made). Note that there can be many whales mating at the same time, and so your solution must correctly handle the various cases that could potentially arise (single male, female, matchmaker; multiple of each; only some of each; etc.). If there are multiple whales of a given kind, when there is a mating it does not matter which one mates, just that only one of them mates. Further, until whales of all three kinds arrive, the whales of the other kinds must wait.

    Structurally, this problem is similar to the "Mailbox" problem above. You can implement the "Whale" class in synch.{h,cc} or in another file. You will write test programs in threadtest.cc (or another test file of your creation) that create a Whale instance and then multiple threads to play the roles of male, female, and matchmater by synchronizing through the Whale instance. Be sure to write test cases for the various combinations of whale situations.

Sharing Files

We recommend that you use a source code control system like CVS to manage and share group files. We will create CVS repositories for each of the groups. We will also create Unix groups so that you can set group permissions on files.

Submitting The Project

All the code you write should be well commented so we can understand what you changed. However, your grade on the project fundamentally depends upon how well your solutions will pass the test cases. As a result, it is important that (1) your code compiles cleanly, (2) the nachos executable will run, and (3) you write test cases to test your solutions to the problems.

As a final step, create a file named README in the code/threads directory listing the members of your group, and providing a short write-up describing what changes you made, how well they worked, how you tested your changes, and how each group member contributed to the project. The idea is to make it easier for us to understand what you did as we grade, not to burden you with a lot more work. Do not agonize over wording or anything, it does not have to be poetic. But it should be informative. For a skeleton outline, see http://www-cse.ucsd.edu/classes/fa02/cse120/projects/example-writeup.html .

Remove compiled files from your code directory, create a tar file of the code directory, and use turnin to submit.

$ cd nachos-3.4/code
$ gmake clean
$ cd ..
$ tar cvf project1.tar code
$ gzip project1.tar
$ turnin project1.tar.gz



voelker@cs.ucsd.edu, marzullo@cs.ucsd.edu