Programming assignment #3 - Threads and Synchronization

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.

Assignment background

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:

You might also need to add more files for this assignment. When you do so, make sure you also update 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.

Assignment requirements in detail

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:

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.

Administrative policies

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.