CS3431 - Programming Assignment

Overview

For this assignment, you are to implement, using pthreads on Solaris, a simulation of the "Dining Philosophers" problem, as discussed in detail in pages 175-177 of the textbook. For your simulation, assume there are 5 philosophers numbered 0 - 4, and 5 chopsticks also numbered 0 - 4. For philosopher "n", the left hand chopstick is chopstick "n", and the right hand chopstick is chopstick (n+1) mod 5.

Which system to use

We should all use system "elvis.cc.gatech.edu" for compilations and test runs. You can log into any system on the CoC network, and then telnet to elvis by entering "telnet elvis" (from a unix system), or using the telnet window on WindowsNT and opening a connection to "elvis". Elvis has 4 CPU's and lots of memory, so it should not be a bottleneck for us getting our work done.

Getting Started

To make the task simpiler, I have provided a Makefile which you can use to build your simulation. I have also provided a set of useful subroutines in miscsubs.c, (and a corresponding header file miscsubs.h) which are described in more detail below. Finally I created a skeleton C program, dining.c which you can use as a starting point.

Before doing anything, your code should call "InitializeChecking", which is in miscsubs.c (this call is already present in the skeleton dining.c I provided). Continue by creating 5 threads using pthread_create, one for each philopsopher. Each philosopher should start out in the "thinking" state. When thinking, your code should call "RandomDelay" (which is in miscsubs.c) to wait for a short, random interval. After the random interval, each philosopher should enter "hungry" state. When hungry, the philosopher should attempt to pick up both the left and right chopsticks. Use a "mutex" to represent the chopsticks, which will prevent more than one philosopher from using the same chopstick at the same time. Once he has obtained both chopsticks, the philosopher enters "eating" state. In the eating state, you should first call "StartEating" (which is in miscsubs.c). Then, you should again call "RandomDelay" to give a short delay, call "DoneEating" (also in miscsubs.c), and then put down both chopsticks (release the mutex for each one), and return to thinking state. All threads should exit when global variable "TotalEats" (defined in miscsubs.h and maintained by miscsubs.c) reaches or exceeds the value "MAX_EATS" (also defined in miscsubs.h). When all threads have exited, the main program should call "LogResults" (also in miscsubs.c and also in the skeleton dining.c I provided).

More Details

Your main program MUST NOT just burn CPU time waiting for the philosophers (threads) to exit. Instead, you must use a condition variable which the philosophers use to inform the main program they are exiting. You should also "desk check" your code carefully to be sure that you don't have a possible deadlock situation, since just running the program for a while with no problems does not mean there are not potential problems. In my solution, I intentially introduced a potential deadlock, but yet the program still ran to completion!

One other detail that you must attend to. We want to insure that each philosopher thread will get scheduled and begin some execution before the next philosopher thread is created. This is not necessary at all to solve the dining philosophers problem, but it helps us understand better some inter-thread communication techniques. Again, the main thread MUST NOT just burn CPU time waiting for each thread to start up.

Turning In Your Program

Email your "dining.c" program (not as an attachment, but just as the body of the message) to namgeun@cc. One way to do this is (on unix):

mail namgeun@cc < dining.c

Contact Information:

riley@cc.gatech.edu

College of Computing

Georgia Institute of Technology

Atlanta, GA 30332-0280