Assignment #1
Working with Threads

This is an individual assignment.  

In this assignment you get a working thread system; your job is to use the system to solve one of the synchronization problems specified below.

Getting the Code

The code you need can be found at ~icss544/pub/threads.tar.gz.  You should be able to copy this code directly into your own directory.  To make sure that all the pieces are in place and you can build Nachos execute the following sequence of instructions:

gunzip threads.tar.gz
tar xvf threads.tar
cd nachos
make threadsdep
make threadscode
cd threads
nachos

This should run Nachos's small thread test program.  You'll see output indicating that two threads have been started, run and terminated.

Getting Started

The first step is to gain an understanding of the structure of the code provided to you.  This thread system implements thread fork, thread completion, semaphores and condition variables for synchronization, and an alarm class. Run the program nachos for a simple test of the code. Trace the execution path (by hand) for the simple 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 SWITCH, another thread starts running, and the first thing the new thread does is to return from SWITCH. 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.

The Nachos code must be compiled with g++. This is set in the Makefile's provided to you.  You can not use workshop to debug the nachos program.  You will need to use gdb, a GNU text-based debugger.  Even though gdb understands threading you will not be able to use any of gdb's thread support.  The nachos threads are implemented internal to the running application following nachos's own threading model.  This differs from the threads that are supported by gdb.  It is strongly urged that you get familiar with gdb.  For some exercises it may turn out that gdb is the only tool that can show you what your program is really doing.  For a very quick overview of gdb's capabilities you can look at this short gdb tutorial.

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.

Nachos exits when there are no kernel threads in the ready-to-run state and no interrupts pending other than the timer daemon interrupt.  A pending interrupt is the only thing that could move a thread to the ready-to-run state.  Due to the way alarms are implemented in the base system there is always a periodic interrupt pending.  This will prevent the default exit mechanism from being triggered.  You will have to explicitly call interrupt->Halt() to stop Nachos when your program determines it is appropriate.

Warning: as provided, each kernel 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 -- for example, int buf[1000];. You will probably not notice this during the term, but if you do, you may change the size of the stack by modifying the StackSize define in switch.h.

Nachos is implemented in C++ and each of your assignments are expected to maintain the object-oriented design paradigm.  Also, there should be no busy-waiting loops in any of your solutions to this assignment.  Choose one of the following problems to solve.  You can probably find code solutions for these in texts or on the net.  The challenge for you will be determining how to incorporate a solution into the Nachos system.

1. You have been hired by the Department of Public Works to synchronize traffic over a narrow light-duty bridge on a public highway.  Traffic may only cross the bridge in one direction at a time, and if there are ever more than 3 vehicles on the bridge at one time, it will collapse under their weight.  In this system, each car is represented by an object (Car class) that executes the crossing operation in its own thread.  There are three steps involved with crossing the bridge: arriving, crossing and exiting.  These three operations should be encapsulated in a Bridge class as member functions:
   

   • ArriveBridge(int direction)
   • CrossBridge(int direction)
   • ExitBridge(int direction)
   
   You start each car's thread with the Thread::Fork member function.  Fork takes two parameters: a pointer to the function that the thread will start executing and a single parameter that will be passed to the start function.  All the functions associated with a car object should be encapsulated within the Car class.  Pay particular attention to the functions that control a car's operation as a result of forking the new thread.  This should primarily be handled by functions within the Car class.  Please do not interpret this to mean that Car class objects will not call functions on other objects.  They most certainly will use the Bridge object.  In the code above, direction is either 0 or 1; it gives the direction in which the vehicle will cross the bridge.
   
   In the discussion of your solution state how you ensure fairness of traffic flowing in both directions.
   
2. Implement a solution to the dining philosophers problem that is deadlock-free.  A statement of this classic problem in concurrency is:
   

   There are 5 philosophers sitting at a round table. Between each adjacent pair of philosophers is a chopstick. In other words, there are five chopsticks. Each philosopher does two things: think and eat. The philosopher thinks for a while, and then stops thinking and becomes hungry. When the philosopher becomes hungry, he/she cannot eat until he/she owns the chopsticks to his/her left and right. When the philosopher is done eating he/she puts down the chopsticks and begins thinking again. The challenge in the dining philosophers problem is to design a protocol so that the philosophers do not deadlock (i.e. every philosopher has a chopstick).

   You can find descriptions of deadlock-free solutions to this problem in almost any operating systems or concurrency textbook.
   
   In solving the dining philosophers problem be sure to treat each philosopher as an independent entity acting on his or her own schedule.  Your deadlock prevention solution should not be based on a higher-level supervisory entity that controls all of the philosophers at the table.  There are only 5 people in the room and, as philosophers often tend to be, each is in a world of their own more or less unaware of anything outside of their own immediate world.  Describe how your solution guarantees no deadlock.  In your discussion also consider the issue of starvation and fairness.  Specifically, does your solution provide fair access to all philosophers or can one or more of them suffer from starvation?  (In this case, it is starvation in both the literal and operating systems sense.) If yes, how is this accomplished with the constraint that each philosopher is independent?  If it is not fair, what would you have to change to create a fair solution?
   
3. Implement a solution to the sleeping barber problem.  The problem is as follows:
   

A small town barber shop is run by a single barber.  There is one chair for cutting hair and several chairs where customers can wait.  When there is no customer waiting the barber sits in the barber chair and usually takes a nap.  If a customer arrives and no one is waiting or getting a haircut, the customer wakes up the barber and the customer sits in the chair to get a haircut.  If someone is getting a haircut or there are customers waiting a newly arriving customer will take a seat in the waiting area.  If there are not seats in the waiting area the customer leaves the shop without a haircut.  When the barber finishes a haircut and the customer has left the chair, the barber will check for any waiting customers.  If there are waiting customers the barber will give haircuts in the order the customers arrived.  If there are no customers then the barber sits in the barber's chair and takes a nap.

Be sure that your solution demonstrates all of the possibilities of customers waiting, being served and leaving the shop.  There should be examples of when the barber is taking a nap.  This may require you to provide a method to adjust the arrival rate of customers and the number of waiting chairs.  The customers and the barber should be each be implemented as individual, independent threads.  There is no higher-level supervisory component providing coordination of the barber shop.  Your solution should not exhibit deadlock or starvation.  In your writeup explain how you ensure this.  Suppose the barber expanded the shop and hired more barbers.  Can this be easily accommodated in your system?  What would you have to change?