Nachos Assignment #1: Build a thread system

CS 42
Due Oct. 23

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 a 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, along with semaphores for synchronization. Run the program `nachos' for a simple test of our code. Trace the execution path (by hand) for the simple test case 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 SWITCH, another thread starts running, and the first thing the new thread does is to return from SWITCH. We realize this comment will seem cryptic to you at this point, but you will understand threads once you understand why the SWITCH that gets called is different from the SWITCH that returns. (Note: because gdb does not understand threads, you will get bizarre results if you try to trace in gdb across a call to SWITCH.)

The files for this assignment are:

main.cc, threadtest.cc --- a simple test of our thread routines.

thread.h, thread.cc --- thread data structures and thread operations such as thread fork, thread sleep and thread finish.

scheduler.h, scheduler.cc --- manages the list of threads that are ready to run.

synch.h, synch.cc --- synchronization routines: semaphores, locks, and condition variables.

list.h, list.cc --- generic list management (LISP in C++).

synchlist.h, synchlist.cc --- synchronized access to lists using locks and condition variables (useful as an example of the use of synchronization primitives).

system.h, system.cc --- Nachos startup/shutdown routines.

utility.h, utility.cc --- some useful definitions and debugging routines.

switch.h, switch.s --- assembly language magic for starting up threads and context switching between them.

interrupt.h, interrupt.cc --- manage enabling and disabling interrupts as part of the machine emulation.

timer.h, timer.cc --- emulate a clock that periodically causes an interrupt to occur.

stats.h -- collect interesting statistics.

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 without changing the correctness of your code. 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 Thread::Yield to be called on your behalf in a repeatable but 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 -rs #'', with a different number each time, calls to Thread::Yield will be inserted at different places in the code.

Make sure to run various test cases against your solutions to these problems; for instance, for part two, create multiple producers and consumers and demonstrate that the output can vary, within certain boundaries.

Warning: in our implementation of threads, each thread is assigned a small, fixed-size execution stack. This may cause bizarre problems (such as segmentation faults at strange lines of code) if you declare large data structures to be automatic variables (e.g., ``int buf[1000];''). You will probably not notice this during the semester, but if you do, you may change the size of the stack by modifying the StackSize define in switch.h.

Although the solutions can be written as normal C routines, you will find organizing your code to be easier if you structure your code as C++ classes. Also, there should be no busy-waiting in any of your solutions to this assignment.

The following is a sample assignment. The actual assignment will be made soon.

1. Correct the semaphore class so that bounded waiting is satisfied. The key to this is in safely removing the while loop in Semaphore::P(). Coupled with this, it is important to maintain the correctness of value. The key is in understanding what value's value should be if a waiting thread is released by a signaling thread.

2. Implement locks and condition variables. You may either use semaphores as a building block, or you may use more primitive thread routines (such as Thread::Sleep). We have provided the public interface to locks and condition variables in synch.h. You need to define the private data and implement the interface. Note that it should not take you very much code to implement either locks or condition variables.

3. Implement producer/consumer communication through a bounded buffer, using locks and condition variables. (A solution to this bounded buffer problem is described in Silberschatz, Peterson, and Galvin in the Mach chapter.)

The producer places characters from the string "Hello world" into the buffer one character at a time; it must wait if the buffer is full. The consumer pulls characters out of the buffer one at a time and prints them to the screen; it must wait if the buffer is empty. Test your solution with a multi-character buffer and with multiple producers and consumers. Of course, with multiple producers or consumers, the output display will be gobbledygook; the point is to illustrate.

4. The local laundromat has just entered the computer age. As each customer enters, he or she puts coins into slots at one of two stations and types in the number of washing machines he/she will need. The stations are connected to a central computer that automatically assigns available machines and outputs tokens that identify the machines to be used. The customer puts laundry into the machines and inserts each token into the machine indicated on the token. When a machine finishes its cycle, it informs the computer that it is available again. The computer maintains an array available[NMACHINES] whose elements are non-zero if the corresponding machines are available (NMACHINES is a constant indicating how many machines there are in the laundromat), and a semaphore nfree that indicates how many machines are available.

The code to allocate and release machines is as follows:

int allocate()	/* Returns index of available machine.*/
{
  int i;

  P(nfree);	/* Wait until a machine is available */
  for (i=0; i < NMACHINES; i++)
    if (available[i] != 0) {
      available[i] = 0;
      return i;
    }
}

release(int machine)	/* Releases machine */
{
  available[machine] = 1;
  V(nfree);
}

The available array is initialized to all ones, and nfree is initialized to NMACHINES.

(a) It seems that if two people make requests at the two stations at the same time, they will occasionally be assigned the same machine. This has resulted in several brawls in the laundromat, and you have been called in by the owner to fix the problem. Assume that one thread handles each customer station. Explain how the same washing machine can be assigned to two different customers.

(b) Modify the code to eliminate the problem.

(c) Re-write the code to solve the synchronization problem using locks and condition variables instead of semaphores.