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;''). 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.
[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 for the following errors: (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) signalling a condition variable wakes only one thread and broadcasting wakes up all threads, (6) signalling 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"). These are the minimal set of error conditions for which we'll test your Lock and Condition implementations.
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.
[5 pts] Write test cases that test for the requirements outlined above for the semantics of the Join method. Be sure to test for both possibilites of each requirement.Thread(char* debugName, int join = 0); void Join();
void setPriority(int newPriority);
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().
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.
You should hand in the entire threads directory, including your test cases, as well as a file named "README" containing your group name and the members of the team. In addition, we would like a short paper 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. An example of writing up a problem is shown in this skeleton.
To turn in your project, create a tar file of your threads directory and Mail it to Rishi, Kuo-Wen, and me. If you were group 57, use the following sequence of commands to minimize the size of the file you send:
% cd nachos-3.4/code % gmake clean % tar cvf group57.tar threads % gzip group57.tar % [mail group57.tar.gz using your favorite method of email attachments]
Look on the project groups list if you do not remember your group number.