Phase 1: Build a thread system
Stock Nachos has an incomplete thread system. In this assignment,
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 have
written for you. This thread system implements thread fork,
thread completion, and semaphores for synchronization. It also provides locks
and condition variables built on top of semaphores.
After installing the Nachos distribution, run the program nachos
(in the proj1 subdirectory) for a simple test of our code. This causes the
methods of nachos.threads.ThreadedKernel to be called in the order
listed in threads/ThreadedKernel.java:
- The ThreadedKernel constructor is invoked to create the Nachos
kernel.
- This kernel is initialized with initialize().
- This kernel is tested with selfTest().
- This kernel is finally "run" with run(). For now, run()
does nothing, since our kernel is not yet able to run user programs.
Trace the execution path (by hand) for the simple test cases we provide.
When you trace the execution path, it is helpful
to keep track of the state of each thread and which procedures
are on each thread's execution stack. You will notice that when
one thread calls TCB.contextSwitch(), that thread
stops executing, and another thread starts running.
The first thing the new thread does is to return from
TCB.contextSwitch(). We realize this comment will
seem cryptic to you at this point, but you will understand
threads once you understand why the TCB.contextSwitch()
that gets called is different from the TCB.contextSwitch()
that returns.
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 KThread.yield()
(causing the scheduler to choose another thread to run) anywhere in your code
where interrupts are enabled, and your code should still be correct.
You will be asked to write properly synchronized code
as part of the later assignments, so understanding how to do this is
crucial to being able to do the project.
To aid you in this, code linked in with Nachos will cause
KThread.yield() to be called on your
behalf in a repeatable (but sometimes 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 -s <some-long-value>",
with a different number each time,
calls to KThread.yield() will be inserted at
different places in the code.
You are encouraged to add new classes to your solution as you see fit; the
code we provide you is not a complete skeleton for the project.
Also, there should be no busy-waiting in any
of your solutions to this assignment.
Your project code will be automatically graded. There are two reasons for this:
- An autograder can test your code a lot more thoroughly than a TA can,
yielding more fair results.
- An autograder can test your code a lot faster than a TA can.
Of course, there is a downside. Everything that will be tested needs to have a
standard interface that the autograder can use, leaving slightly less room for
you to be creative. Your code must strictly follow these interfaces (the
documented *Interface classes).
In order for you to verify that your code is compatible with the autograder,
there are some simple compatibility tests you can run before you submit.
Since your submissions will be processed by a program, there are some very
important things you must do, as well as things you must not do.
For all of the projects in this class...
- Do not modify Makefile, except to add source files.
You will not be submitting this file (javac automatically finds
source files to compile, so we don't need you to submit Makefile).
- Only modify nachos.conf according to the project specifications.
You will not be submitting this file either. Do not rely on any additional keys
being in this file.
- Do not modify any classes in the nachos.machine package,
the nachos.ag package, or the nachos.security package.
You will not be submitting any of these classes.
- Do not add any new packages to your project.
All the classes you submit must reside in the packages we provide.
- Do not modify the API for methods that the autograder uses. This is
enforced every time you run Nachos by Machine.checkUserClasses().
If an assertion fails there, you'll know you've modified an interface that
needs to stay the way it was given to you.
- Do not directly use Java threads (the java.lang.Thread
class). The Nachos security manager will not permit it. All the threads you
use should be managed by TCB objects (see the documentation for
nachos.machine.TCB).
- Do not use the synchronized keyword in any of your code. We
will grep for it and reject any submission that contains it.
- Do not directly use Java File objects (in the
java.io package). In later projects, when we start dealing with files,
you will use a Nachos file system layer.
When you want to add source files to your project, simply add entries to your
Makefile.
In this project,
- The only package you will submit is nachos.threads, so don't add
any source files to any other package.
- The autograder will not call ThreadedKernel.selfTest()
or ThreadedKernel.run(). If there is any kernel initialization you
need to do, you should finish it before
ThreadedKernel.initialize() returns.
- There are some mandatory autograder calls in the KThread code.
Leave them as they are.
Submission:
To submit your code (which should include your test cases), run the
command submit proj1-code from within the nachos
directory. It will only take files from the threads directory. We will
grade only the last submission by any member of your group (though the
autograder will mail you test results from all submissions).
Tasks:
-
(5%, 5 lines) Implement KThread.join(). Note that another thread
does not have to call join(), but if it is called, it must be
called only once. A thread must finish executing normally
whether or not it is joined.
-
(5%, 20 lines) Implement condition variables directly, by using
interrupt enable and disable to provide atomicity.
We have provided a sample implementation that uses
semaphores; your job is to provide an equivalent implementation
without directly using semaphores (you may of course still use locks, even
though they indirectly use semaphores). Once you are done, you will
have two alternative implementations that provide the exact same
functionality. Your second implementation of condition variables
must reside in class nachos.threads.Condition2.
-
(10%, 40 lines) Complete the implementation of the Alarm class,
by implementing the waitUntil(int x) method.
A thread calls waitUntil
to suspend its own exeuction until time has advanced to at least now + x.
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
in the timer interrupt handler after they have waited
for at least the right amount of time. Do not fork any additional threads to
implement waitUntil(); you need only modify waitUntil() and
the timer interrupt handler. waitUntil is not limited to
one thread; any number of threads may call it and be suspended at any
one time.
-
(15%, 40 lines) Implement synchronous send and receive of one word
messages (also known as Ada-style rendezvous), using
condition variables (don't use semaphores!). Implement
the Communicator class with operations,
void speak(int word) and int listen().
speak() atomically waits until listen() is called on the same
Communicator object, and then transfers the word over to listen().
Once the transfer is made, both can return.
Similarly, listen() waits until speak() is called,
at which point the transfer is made, and both can return
(listen() returns the word).
Your solution should work even if there are multiple speakers and
listeners for the same Communicator
(note: this is equivalent to a zero-length bounded buffer;
since the buffer has no room, the producer and consumer
must interact directly, requiring that they wait for one another).
Each communicator should only use exactly one lock. If you're using
more than one lock, you're making things too complicated.
-
(25%, 125 lines) Implement priority scheduling in Nachos by completing the
PriorityScheduler class. Priority scheduling is a key building block
in real-time systems. Note that in order to use your priority
scheduler, you will need to change a line in nachos.conf that
specifies the scheduler class to use. The ThreadedKernel.scheduler
key is initially equal to nachos.threads.RoundRobinScheduler. You
need to change this to nachos.threads.PriorityScheduler when you're
ready to run Nachos with priority scheduling.
Note that all scheduler classes extend the abstract class
nachos.threads.Scheduler. You must implement the methods
getPriority(), getEffectivePriority(), and
setPriority(). You may optionally also implement
increasePriority() and decreasePriority() (these are not
required). In choosing which thread to dequeue, the scheduler should always
choose a thread of the highest effective priority.
An 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), and another high 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 the priority scheduler so that it donates priority, where possible.
Be sure to implement Scheduler.getEffectivePriority(), which returns
the priority of a thread after taking into account all the donations it is
receiving.
You will probably find that there are two completely different ways to
implement priority donation; one is extraordinarily simple and extraordinarily
slow, and the other is much faster but a little more complicated. You will not
receive full points on your design if you choose the easy route here. However,
you will also not receive full points on your design if your solution is
unnecessarily complicated, because it's better to do things correctly and
slowly than to do them incorrectly and quickly.
-
(25%, 300 lines) Putting all of this together, you are to implement a
controller for a bank of elevators, such as in Soda Hall.
See nachos.machine.ElevatorBank for details on the hardware interface,
and nachos.threads.ElevatorController for details on what you are to
implement. Create a thread for each elevator; these threads
talk to the elevator hardware (through the interface defined
in nachos.machine.ElevatorControls) to
open and close the elevator doors, move the
elevator between floors, etc. The elevator threads should coordinate
with each other to make sure that exactly one elevator goes to pick up each
set of passengers. For synchronizing the elevator threads, you are free to use
semaphores, condition variables, or even the Communicator
if you want (though in my experience, using a Communicator only makes
things harder). You will also need to use Alarm.waitUntil()
to hold open the doors for a fixed amount of time (you should hold them open
for timeDoorsOpen ticks).
-
(15%, 100 lines) Since you will need to test out your code before you
turn it in, you will also be required to implement elevator riders. See
nachos.threads.Rider for details on what you are to implement. This
part is considerably easier, because each rider is independent of all other
riders, and each rider gets its own nachos.machine.RiderControls
object (as opposed to the elevator controller, which has one controls object
for all the elevators, and requires synchronization).
Of course, the only communication possible between the elevator riders
and the elevator controller is via the physical elevator device.
The elevator threads should not share any memory
or synchronization variables with the rider threads.
To test your riders and elevators, you must first call
Machine.bank().init(). Then call Machine.bank().addRider()
once for each rider. Finally, call Machine.bank().run() to run the
simulation (this method returns when the simulation is complete).
We have provided a GUI to help you to test your elevators and riders together.
To enable it, simply call Machine.bank().enableGui() before
Machine.bank().run().