You may do this project individually or in 2-person teams. Be sure to tell the TA who your partner is if you go that route.


An angry mob goes after the five dining philosophers, who escape into a dark alley in an unfrequented part of the town. They found an old soup kitchen, 5 bowls, and a coin. They decide to adopt to a new lifestyle and put the bowls on a table. A philosopher now goes through the sequence:

        result = coin->flip();
        if(result = COIN_HEAD){

Where coin (of type Coin) and table (of type Table) are shared objects that encapsulate the system's shared state. Only one philosopher can flip the shared coin at a time; flipping the coin results in either COIN_HEADS or COIN_TAILS. As a result of the function Table::work(), the philosopher makes enough soup to fill a bowl. Similarly, the result of the function Table::eat() is that a philosopher picks a bowl and consumes all the soup in it. Note that there is no correspondence between bowls and philosophers, i.e. a philosopher will eat from any available bowl that contains soup, and will fill any available empty bowl. If all the bowls are full, work blocks until at least one is empty; if all of the bowls are empty, eat blocks until at least one is full. Think() just yields the processor or sleeps.

Working with threads

Before you begin the assignment, read Coding Standards for Programming with Threads. You are required to follow these standards for this project. Because it is impossible to determine the correctness of a multithreaded programming via testing, grading on this project will primarily be based on reading your code not by running tests. Your code must be clear and concise. If your code is not easy to understand, then your grade will be poor, even if the program seems to work. In the real world, unclear multi-threaded code is extremely dangerous -- even if it "works" when you write it, how will the programmer who comes after you debug it, maintain it, or add new features? Feel free to sit down with the TA or instructor during office hours for code inspections before you turn in your project.

You should also look at these hints for avoiding common pitfalls.

To simplify your task, we have developed a simple thread package on top of the standard pthread package for your use. The idea is to shield you from the irrelevant detail that inevitably is part of dealing with pthreads. This way, you use the standard package but you also focus on the project at hand.

The files are sthread.h and sthread.cc. The package provides threads, mutex locks, and condition variables as well as some other utility functions that you may need (such as a random number generator). This package is built on the posix thread library. For more information, see the man pages for the library functions used in the sthread.cc code.

Exercise 1

Download the code from hw4.tar and untar this file to create the subdirectory hw4. Running "make" should produce the executable file main with no errors or warnings.

We have provided skeleton files for the Table object as well as a Barrier object we will use to aid testing. The Table object is as described above -- it holds the bowls shared by the philosophers and has the public methods Table::work() (which increases the number of full bowls) and Table::eat() (which reduces the number of full bowls). For debugging and testing, we also have given it the public method Table::dbgCountFull() (which returns the number of full bowls; this number should always be between 0 and NBOWLS.) The shared Barrier object is initialized with a count. A call to Barrier::waitUntilDone() does not return until there have been at least count calls to Barrier::done(). Thus, a barrier allows a thread to wait for count other threads to complete their work.

Complete the code for Barrier and Table. Once you have done this, the two simple tests in mikesTest() should succeed. Feel free to add any additional tests to moreTests().

Exercise 2

Complete the philosophers simulation by creating a shared Coin object and writing the runPhilosophers() method in main.cc.

As noted above, the Coin has one public method: flip() which returns HEADS or TAILS. The philosophers share a single coin (only one philosopher can flip the coin at a time.) Just to make it interesting, the coin is charmed: it has a "bias" towards "evening out" the working and the eating of the philosophers. In particular, the coin "remembers" the result of its last flip; if the last flip was HEADS, then there is a 3/4 chance that the current flip will return TAILS and if the last flip was TAILS, then there is a 3/4 chance that the current flip will return HEADS.

The runPhilosophers() method creates nPhilosophers threads, each of which executes code corresponding to the pseudo-code above. Recall that the pseudocode for _start (the "stub" for the "main" thread of a process) is roughly:


So, you will need to make sure that the process continues to exist after spawning off the philosopher threads.

A philosopher thread should print "E(x)" when it eats (with x replaced by the number of full bowls left after the philosopher eats.) And, it should print "W(x)" when it works (with x replaced by the number of full bowls left after the philosopher works.) Notice that if you simply print out the value returned by eat() or work(), the output to the screen may not quite be what you expect. That's OK -- we could make the project more complex and require that you structure your code so that the output is more what you would epect. You don't need to do this for the lab -- just do the simple thing and proint out the values returned by eat() and work(). But, think about what is happening and how you would structure the code to avoid such issues.

The philosophers hope that their new life is in harmony with nature and that they can sustain their existence indefinitely. Can they? (More to the point: is this system free from deadlock?) You don't need to turn in an answer to this question, but think about the deadlock properties of the system.

This completes the lab.

Turn-in procedure.

Running "make turnin" should create a file containing all of the .h and .cc files you have modified or created. Please do not include any other files in hw4-done.tar. Turn in this file using the command

turnin --submit indrajit GradOS-hw4 hw4-done.tar