Nachos Project 1: Threads
Due: Thursday, October 20th, at Midnight.
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
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
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.
- [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.
[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
- [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.
- [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->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
Use the following signatures for the updated constructor and Join
Thread(char* debugName, int join = 0);
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
[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
- [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 current thread gives
up the processor to the new thread (a thread with the same priority as
the current thread does not preempt it). If it is already on the
ready list, you do not have to re-sort it (although you can if you
want). Similarly, 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);
NOTE: You need to use these names (including capitalization) and
obey these signatures so that our test programs will compile to your
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().
- [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 in order
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 write the three procedures
Male(), Female(), and Matchmaker(). Each whale is represented by a
separate thread. A male whale calls Male(), which waits until there is
a waiting female and matchmaker; similarly, a female whale must wait
until a male whale and a matchmaker are present. Once all three are
present, all three return.
Note that you cannot use explicit wait queues, Sleep, or
disable/enable interrupts to implement the Whale procedures. The
Whale problem is similar in spirit to the synchronization problems we
discussed in class (e.g., BoundedBuffer, ProducerConsumer, etc.). You
will use synchronization primitives (either Locks and CVs, or
Semaphores) to coordinate the threads.
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.
Turning in the project will be done via CVS. Add a file named README
to your CVS repository containing the members of your group, and 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. The idea of this is to make it easier to
grade, not to burden you with a lot more work. Don't agonize over
wording or anything, it doesn't have to be poetic, but should be
Put this file in the root of your copy of the cvs repository, and do:
% cvs add README
% cvs commit README
Next, label the current version of the code in CVS as project1, this is
important as this is how we get your files. To do this, type the
% cvs rtag -F project1 nachos-3.4
The -F flag tells it to set the tag even if it's already been set. This
will be useful if you need to make changes to what you turned in.
Essentially any time you make a change that you want turned in, you'll
have to re-label it.
If you've forgotten all the CVS commands, there is a quick and dirty reference
for most of the commands you will need here.