Due by 11:59pm, Thursday, March 1.
The managing TA for this assignment is Daniel Mullowney. All email inquiries about this assignment should be addressed to the TA and the instructor.
This is the first in a series of four assignments based on Nachos. If you haven't done so, please read the Nachos introduction page now. In this assignment, we give you part of a working thread system; your job is to complete it, and then to use it to solve several synchronization problems.
This is a group assignment. You should form a group of two to complete this assignment. Groups of three may also be acceptable under rare circumstances (e.g., there are odd number of students in the class) and you must contact the instructor if you plan to work in a group of three. As in all group programming assignments, you are encouraged to use CVS or other version control software to manage your source code. Discuss with your group members early to establish safe and flexible policies for managing your code. Again, you are encouraged to help (and seek help from) people in other groups (except sharing code, of course). Note that we will not distinguish grades within a group.
Read this carefully! We ask you to take full advantage of the TA (Daniel Mullowney)'s office hours. It is sometimes very hard to explain problems and provide answers through email. Face-to-face contact with the TA is usually much more efficient. In addition to asking questions, you are also encouraged to explain your designs to the TA and ask for feedback. If you have trouble making any of the scheduled office hours with the TA, it is possible to set up a meeting at a different time. Please contact the TA for such an arrangement.
Before working on this assignment, you must understand why we need synchronization primitives to support concurrent programming. This assignment also assumes that you understand the basic behaviors of interrupt enable/disable, sleep/wakeup, locks/mutexes, and condition variables from class and from readings. If you don't understand them, study up the lecture notes and ask us or your classmates if necessary.
In this assignment, you will build and test your nachos executable in the
threads/ directory. As the first step, please read and
understand the partial thread system given to you. This thread system implements
thread fork and thread completion, along with semaphores for synchronization.
Run the program
nachos for a simple test of the code given to
you. Everything you do in this assignment is within the Nachos kernel, which means
you do not need to deal with any user programs.
The files for this assignment are:
threads/main.cc, threadtest.cc a simple test of thread routines.
threads/thread.h, thread.cc thread data structures and thread operations such as thread fork, thread sleep, and thread finish.
threads/scheduler.h, scheduler.cc manages the list of threads that are ready to run.
threads/synch.h, synch.cc synchronization routines such as semaphores, locks, and condition variables (some are not implemented).
threads/boundedbuffer.h, boundedbuffer.cc synchronization routines for a bounded buffer (to be implemented by you).
threads/list.h, list.cc generic list management.
threads/synchlist.h, synchlist.cc synchronized access to lists using locks and condition variables (useful as an example of the use of synchronization primitives).
threads/system.h, system.cc Nachos kernel data structures and startup/shutdown routines.
threads/utility.h, utility.cc some useful definitions and debugging routines.
threads/switch.h, switch.s assembly language magic for starting up threads and context switching between them.
machine/interrupt.h, interrupt.cc manage enabling and disabling interrupts as part of the machine emulation.
machine/timer.h, timer.cc emulates a clock that periodically causes an interrupt to occur.
machine/stats.h, stats.cc collect interesting statistics.
Concurrent programming and synchronization:
If you examine
threads/main.cc, you will see that the program
is executing the
ThreadTest function in
ThreadTest is a
simple example of a concurrent program. You can create new versions of this
function to test various new features you will be implementing in this assignment.
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 (causing the scheduler to choose another
thread to run) anywhere in your code (where interrupts are enabled), and your code
should still be correct. To aid you in this, the Nachos code will cause
Thread::Yield to be called in a repeatable but unpredictable
way. Nachos 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 -rs #, with a different number each time, calls to
Thread::Yield will be inserted at different places in the code.
You will be asked to write properly synchronized code as part of later assignments,
so a good understanding on concurrent programming and synchronization is crucial.
Warning: Each Nachos thread is assigned a small, fixed-size execution stack (4K bytes by default). This may cause bizarre problems (such as segmentation faults at strange lines of code) if you declare large data structures (e.g.,
int buf) to be automatic variables (local
variables or procedure arguments). You will probably not notice this during
the semester, but if you do, you may increase the size of the stack by
This assignment contains three parts: (1) mutex and condition variables;
(2) bounded buffer; (3) alarm clock. There is also an additional CSC456 part.
For each part, make sure to run various test cases
against your solution. You can create test cases by replacing
ThreadTest and other functions in
threads/threadtest.cc with something else.
For instance, here is a very simple test case for
testing the mutex lock synchronization primitive.
Part I: mutex lock and condition variables.
Your task is to fill in the implementation of mutexes and condition variables. The public interface to mutexes and condition variables is defined in
threads/synch.h. Look at
threads/synchlist.h, synchlist.cc to see how the
synchronization primitives for mutexes and condition variables are used.
You need to define private data for these classes in
threads/synch.h and implement the interfaces in
threads/synch.cc. Implement your locks and condition
variables using the sleep/wakeup primitives (the
Note that you are not allowed to use the Nachos
semaphore in your implementation.
It will be necessary to disable interrupts temporarily, to eliminate the
possibility of an ill-timed interrupt or involuntary context switch. For example,
you must disable interrupts before calling
to avoid a missed wakeup race. However, note that disabling interrupts is a
blunt instrument and it should be avoided unless absolutely necessary. You
may lose points for holding interrupts disabled when it is unnecessary to do so.
Part II: bounded buffer.
You are asked to implement a thread-safe
based on the definitions in
threads/boundedbuffer.h. You are
allowed to use any combination of semaphores, mutexes, and/or condition variables.
The semantics of
BoundedBuffer are defined below. As always, if the
specification is incomplete you are free to resolve the ambiguity as you see fit.
BoundedBuffer is a flow-controlled channel for passing
an ordered stream of bytes from one or more producer threads to one or more
consumer threads. The producers call
Write to push bytes into
the stream. The consumers call
Read, which extracts bytes
from the buffer and copies them to memory specified by the consumer. Each byte
written is delivered at most once, and bytes are delivered to the consumers in the
order they were written by the producers. The channel is flow-controlled in the
following sense: If producers generate data faster than the consumers consume it,
then the buffer fills up, and any call to
Write blocks until
some of the bytes in the buffer are consumed, freeing up space in the buffer. If
the consumers read data faster than the producers can write it, then the buffer
empties, and any call to
Read blocks until the producers write
more bytes. By limiting the space (
maxsize) reserved for the
buffer, the system can automatically synchronize the speed of the producers and
BoundedBuffer can be used to implement pipes, an inter-process
communication (IPC) mechanism fundamental to Unix systems. You should have a good
clue about it if you did the CSC456 part of assignment #1.
You should take care to preserve the atomicity of
Write requests when multiple producers or consumers share
BoundedBuffer. That is, data written by a given
Write should never be delivered to a reader interleaved with
data from other
Write operations. This invariant should hold
even if writers and/or readers are forced to block because the buffer fills up or
drains. Note further that any producer may also act as a consumer, and vice versa.
You should also take care that no producer sleeps while there is space in the buffer
for it, and no consumer sleeps while there are bytes in the buffer for it.
Part III: alarm clock.
AlarmClock class for your Nachos kernel. Threads
will call your
AlarmClock::Pause(int howLong) to go to sleep
for a period of time. The alarm clock can be implemented using the simulated
Timer device (see
the timer interrupt goes off, the
Timer interrupt handler in
threads/system.cc must wake up any thread sleeping in
AlarmClock::Pause whose interval has expired. There is no
requirement that an awakened thread starts running immediately after the interval
expires; just wake them up after they have waited for at least the specified
howLong). We have not created a header file for
AlarmClock, so you may define the rest of the class interface
as you see fit. The unit for
howLong should be a machine
tick. The number of machine ticks since bootstrap is maintained at
A couple of things to pay attention to when implementing the alarm clock:
AlarmClock. You may modify the timer interrupt handler in
threads/system.cc, but do not modify the
CSC456 Part: elevator (for disk scheduling).
Implement an elevator controller for a building with F floors. You are allowed to use any combination of semaphores, mutexes, and/or condition variables. The elevator is represented as a thread; each person is also represented by a thread. Your elevator needs to support a routine called by each arriving person
Elevator::Goto(int atFloor, int toFloor). This should wait
for the elevator to arrive. It then continues to block until the elevator takes
the person to
toFloor. When multiple requests arrive at the
same time, try to design an efficient elevator scheduling scheme that can complete
all pending requests quickly. The is where we will consider performance in
assigning points. The elevator takes 100 ticks to go from one floor to the next.
For simplicity, you can assume there's only one elevator, and that it holds an
arbitrary number of people. We have not created a header file for
Elevator, so you may define the rest of the class interface
as you see fit. Include test cases for serving concurrent requests. You may need
AlarmClock in completing this part.
You are asked to electronically turn in a copy of the complete Nachos source tree. Include the test programs (e.g.,
created) you used in testing. Note that your test programs
are an important part of your turn-in.
Do not turn in any executables, object files, or
things like that. We expect that all changes/additions you made are within the
threads/ subdirectory except
Makefile.common. Add enough comments in your code
to make your changes easy to understand. Attach a README file describing the
files you changed/added and anything else special you want us to know. The
README file should be in plain text format. Instructions for electronic
turn-ins can be found on the class Web page.
Below is a tentative grading guideline. Note that we will actually read your code. Your turn-in will be graded not only on its correctness, but also on the completeness and clarity of your comments.
Late turn-in policy:
Late turn-ins will be accepted for up to three days, with 10% penalty for each late day. No turn-ins more than three days late will be accepted.