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.THREAD_H/THREAD_C/THREAD_O
in
Makefile.common
accordingly.
Concurrent programming and synchronization:
If you examine threads/main.cc
, you will see that the program
is executing the ThreadTest
function in
threads/threadtest.cc
. 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.
Stack overflow:
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[1000]
) 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
modifying the #define
in threads/thread.h
.
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 Thread::Sleep
and Scheduler::ReadyToRun
primitives).
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 Thread::Sleep
,
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 BoundedBuffer
class,
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.
Each 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
consumers.
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 Read
and Write
requests when multiple producers or consumers share
the same 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.
Implement an 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 machine/timer.h
). When
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
interval (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
stats->totalTicks
.
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
Timer
class itself.
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
to use AlarmClock
in completing this part.
Turn-in:
You are asked to electronically turn in a copy of the complete Nachos source tree.
Include the test programs (e.g., threads/threadtest.cc
you
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.
Grading guideline:
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.