<- back
CS 153: Project 1: Threads
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. Just as in
Project 0, 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.
Your session should match the following:
$ cd nachos/proj1
$ make
$ ./../bin/nachos
nachos 5.0j initializing... config interrupt timer user-check grader
*** thread 0 looped 0 times
*** thread 1 looped 0 times
*** thread 0 looped 1 times
*** thread 1 looped 1 times
*** thread 0 looped 2 times
*** thread 1 looped 2 times
*** thread 0 looped 3 times
*** thread 1 looped 3 times
*** thread 0 looped 4 times
*** thread 1 looped 4 times
Machine halting!
Ticks: total 2130, kernel 2130, user 0
Disk I/O: reads 0, writes 0
Console I/O: reads 0, writes 0
Paging: page faults 0, TLB misses 0
Network I/O: received 0, sent 0
Trace the execution path (by hand) for the startup test case
provided. 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. Be
careful to add any additional classes to the packages (directories)
permitted. See the list of "do not"s below.
There should be no busy-waiting in any of your solutions to this
assignment.
Your project code will be automatically graded.
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).
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 non-java source files (useful in later projects).
We will be using our own Makefile. (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. We will also being using our own nachos.conf
file. 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. Also do
not add any classes to these packages. They will not be used during grading.
- 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 non-java source files to your project, simply add entries to your
Makefile.
In this project.
- The only package that we will really look at 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.
Tasks:
-
(20%) Implement KThread.join(). Note that another thread does not have
to call join(), but if it is called, it must be called only once. The
result of calling join() a second time on the same thread is
undefined, even if the second caller is a different thread than the
first caller. To clarify, the callee thread may or may not get a join
call (i.e. no thread calls calleeThread.join()). Also, there is no
requirement to support multiple join calls on the same thread. For
example, say threads a, b, & c exist and all have references to each
other. If a calls b.join() then you don't need to support the case
where c also calls b.join(). A thread must finish executing normally
whether or not it is joined.
-
(30%) 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.
Note: there are subtleties
here! Make sure you exactly understand all the design choices in the
provided implementation.
-
(20%) Complete the implementation of the Alarm class, by implementing
the waitUntil(long x) method. A thread calls waitUntil to suspend its
own execution 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. Note however that only one instance of Alarm may exist at a time
(due to a limitation of Nachos).
- (30%) 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). In this
case, a message is still passed between one speaker and one
listener -- the other visitors are queued. Note that there exists a very
simple implementation using exactly one lock! If you have more, you
should wonder..
Code Submission:
As with all projects, you will submit it using iLearn. For this
project, you are to work in groups of 2.
Be sure to include a README file containing the names, student ids
and email addresses of both members of the group.
Due Date: May 3rd, 2011
Hints
- You can add additional member objects/data structures to help keep track of stuff.
- Understand the code you changed in project 0
- This will help you test your new implementations
- Create two threads that do different things
- Consider three KThreads: threads A, B and C. If thread A calls
B.join(), thread A will stop at that point and wait for thread B to
finish before continuing. This means that the join() method should
alter the state of thread A so that it doesn't get scheduled
anymore. Further, when thread B finishes, it should change the state
of A again so that it will be allowed to run (hint: look at the
finish() method). Now, when you've figured that out, consider the
case where B calls C.join() during its execution.
- Here's how to test Condition variables:
- Create two threads a Waker thread and a Sleeper thread.
- In your threads, use your condition variable to wake and sleep
(respectively). Make sure you are using the same condition and
lock object instance in both threads. Also, make sure to aquire the lock
before and release the lock after performing the sleep and wake
methods.
- Make sure that your sleeper executes before the waker wakes it
up.