Spring 2019.
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.
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
5Edges 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.
1 2
2 3
3 4
4 5
5 1
Your program should generate an output steam in which each philosopher announces its state transitions:
philosopher 3 drinkingTo avoid interleaving of output messages, you’ll need to use a lock to protect your access to
philosopher 5 drinking
philosopher 7 drinking
philosopher 5 thinking
...
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.