CSC 2/458: Parallel and Distributed Systems

Spring 2019.

Assignment 2: The “Drinking (or Dining) Philosophers”

The purpose of this assignment is to expand your knowledge of multithreaded programming by solving a classic problem in synchronization.  Many of you will have heard of the Dining Philosophers Problem, introduced by Edsger Dijkstra in 1972 as a pedagogical exercise.  Paraphrasing, five philosophers sit around a circular table.  Each has a plate of spaghetti.  Each philosopher repeatedly thinks for a while and then eats for a while, at intervals of his or her own choosing.  On the table between each pair of adjacent philosophers is a single fork.  To eat, a philosopher requires both adjacent forks:  the one on the left and the one on the right.  Because they share a fork, adjacent philosophers cannot eat simultaneously. 

The task of the programmer is to implement the philosophers as threads, in a way that maximizes concurrency while enforcing the fork-utilization (synchronization) rule and, ideally, treating all philosophers fairly.  A solution in which each philosopher picks up the fork to the right and then the fork to the left is prone to deadlock:  if they all pick up their right-hand forks before attempting to pick up the left, they all may wait forever.  An alternative solution, in which the forks are numbered 1–5 and each philosopher first attempts to pick up the lower-numbered adjacent fork ends up being unfair: some philosopher P inevitably ends up stuck between two peers who both first attempt to pick up the fork they share with P; over time this poor soul ends up eating less than everyone else.

In 1984, Chandy and Misra published an elegant solution to the problem that satisfies all the desired goals.  They also generalized their solution to arbitrary conflict graphs—not just the 5-node cycle of Dijkstra’s original problem.  They call their generalization the “Drinking Philosophers Problem.” Each drinking session requires some (randomly chosen) subset of the bottles represented by adjacent edges.  The key idea is to add directions to the edges of the graph that indicate which philosopher has priority access to the bottle.  Initial directions are chosen to make the graph acyclic.  After successfully drinking, a philosopher reorients the used edges away from itself—giving priority to its neighbors for the next round while ensuring that the graph remains acyclic. 

If you are in CSC 258, you are required to implement a solution to Dijkstra’s original Dining Philosophers Problem using the approach of Chandy and Misra.  If you are in CSC 458, you are required to solve the full Drinking Philosophers Problem.  As in assignment 1, 258 students can undertake the 458 version for extra credit.  In either case, you will need to read the Chandy and Misra article.  You’ll discover that their solution is not presented in shared-memory terms; rather, philosophers send messages to one another to coordinate their activities.  Part of the challenge of the assignment is to adapt the solution to shared memory.  You’ll want to represent each fork (bottle) as a data structure accessible to each adjacent philosopher.  You’ll probably want to protect the fork (bottle) with a lock, but you will not want to hold that lock while eating (drinking).  Rather, you should hold it only long enough to update the state of the fork (bottle) atomically, and use a separate condition_variable associated with the lock for each potentially waiting philosopher. 

Assignment Details

To simplify testing of your code, please name your program philosophers.  For the basic 258 (dining) solution, your program should accept a single command-line parameter, specified with “-s num”, that specifies the number of times that each philosopher should engage in a meal (eating session).  For the 458 (drinking) solution, this same parameter will indicate the number drinking sessions per philosopher.  If the parameter is not specified, use 20 as a default. 

For the 458 (drinking) solution, an additional filename parameter should indicate the name of a file from which to read the problem configuration.  Specifying a single hyphen character (e.g., “philosophers -s 10 -”) should cause your program to read the configuration from standard input.  If no configuration is specified, the program should use Dijkstra’s original five-philosopher cycle. 

You may find the standard getopt library helpful to parse command-line parameters.  (Much better packages are available on the web, but getopt should suffice for this project.)  To generate pseudo-random numbers, I recommend the random_r library routine.  To better test your probram, you may want to arrange for it to use a different “seed” for the random number generator on every run, either by passing something like the time of day to srandom_r or by taking a seed as an optional command-line parameter.

A correctly formatted configuration file should begin with a number n (in ASCII) that indicates the number of philosophers, followed by a series of number pairs, all separated by whitespace.  If philosophers are numbered from 1 to n, the pair “i j” indicates an edge between philosophers i and j.  The default Drinking Philosophers configuration might be specified as

5
1  2
2  3
3  4
4  5
5  1
Edges can be specified in any order, but there should be no repeats, and the graph should be connected (you should check these properties, and print a helpful message and stop if they aren’t satisfied).  Note that the rules imply that the number of pairs should be between n−1 and n(n−1)/2.

Your program should generate an output steam in which each philosopher announces its state transitions:

philosopher 3 drinking
philosopher 5 drinking
philosopher 7 drinking
philosopher 5 thinking
...
To avoid interleaving of output messages, you’ll need to use a lock to protect your access to stdout.  During testing, you may find it helpful to redirect stdout to a file. 

To generate arbitrary interleavings, a thinking or eating (drinking) philosopher should call the linux usleep function with a randomly chosen argument.  I suggest values in the range of 1–1,000 microseconds (1,000–1,000,000 nanoseconds).  If you make the sleeps too short, you’ll serialize on the output lock, and execution will get much less interesting.  For simplicity and for ease of grading, each drinking session should employ all adjacent bottles (not the arbitrary subset allowed by Chandy and Misra). 

As in assignment 1, you should use a global flag to maximize the odds that your threads will all start working simultaneously.  Also as in assignment 1, please employ a Makefile to compile and link your code.  Be sure that clean” and “make philsophers” work correctly. 

Given that your goal in this assignment is “merely” to generate correct behavior while permitting concurrency and ensuring fairness, we will not be measuring any sort of parallel speedup. We will be checking your code to make sure you haven’t overly constrained the possible interleavings or disadvantaged any particular philosopher(s). 

To turn in your code, follow the turnin directions.  Be sure to include a good README.pdf file.  Among other things, you’ll probably want to explain how you adapted Chandy and Misra’s algorithm to hared memory.  If you have questions, post to the discussion board

Due Date: Sunday, February 17, 11:59 pm.


Last Change: 04 February 2019 / Michael Scott's email address