Date: Tue, 05 Nov 1996 20:57:12 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 31 Oct 1996 21:38:53 GMT Content-length: 22123
Discussion of synchronization in operating systems is often
couched in metaphor. We have
the Sleeping Barber problem,
the Cigarette Smoker's problem,
the Bakery problem,
and perhaps the most venerable of all, the Dining Philosophers. Each
of these scenarios in essence models how multiple processes are able to
access shared resources without leading to deadlock. The better solutions to
the problem will even guarantee fairness: All processes will be
guaranteed some access to the resources, so they cannot be ``starved.''
For this project, you will be required to implement two solutions
to a generalization of the Dining Philosophers problem, using
the multithreading
and synchronization capabilities of Java to simulate the action
of multiple processes competing for shared resources.
Tanenbaum
offers two solutions.
The first one, outlined in Figure 2-19 (p. 57) is subject to deadlock
(there is
an animated demonstration of this solution in the
Java
Tutorial).
The second one, spelled out in complete detail in C
in Figure 2-20, is the solution given by Edsger Dijkstra, the person
who made up the problem in the first place.
It avoids deadlock by putting the states of all the philosophers in
a public place and using a global mutex semaphore to inspect it.
You will be implementing two other solutions.
Generalized Dining Philosophers
The original dining philosophers problem as posed by Dijkstra involved five philosophers sitting around a table with a fork between each pair of philosophers. The philosophers were eating spaghetti that was so tangled, it required two forks to eat it. Subsequent authors generally assume that the number N of philosophers is a fixed constant, but not necessarily five. (Some authors also realized that the story would be much more believable if the forks were replaced with chopsticks).
Chandy and Misra
1
further generalized the problem to allow arbitrary pairs of philosophers
to share forks. For example, the following diagram shows ten philosophers
numbered 0 through 9. Each line represents a fork shared by a pair of
philosophers.
The 15 forks are indicated by fork identifiers which are
the numbers 0 through 14.
Thus each philosopher shares forks with three others.
For example, philosopher 0 shares fork 0 with philosopher 1,
fork 10 with philosopher 5, and
fork 4 with philosopher 4.
(This picture is known in graph theory as the Peterson graph).
The simplest algorithm for the diners problem is for a hungry philosopher
to grab all the forks she needs (i.e. all the forks surrounding her) in some
order and then start eating.
If a fork is not available, she simply waits for it before asking for the next
one. This algorithm can lead to deadlock, but
if each philosopher always picks up forks in increasing order by
fork identifiers, deadlock cannot occur
(you should be able to prove this statement).
For example, philosopher 0 should grab forks in the order 0, 4, 10.
It does not matter how the forks are numbered, so long as no two of
them have the same number.
Algorithm II
Chandy and Misra call this algorithm a "hygienic" solution to the diners problem.
Chandy and Misra show that this algorithm is deadlock-free provided the initial placement of forks is acyclic in the following sense: Draw an arrow head on each edge of the graph G so that it points towards the process currently holding the fork. If it is possible to start at some process and follow edges around the graph returning to the starting point while always obeying the directions of the arrow heads, then deadlock is possible. Otherwise it is not. Because a philosopher can ask for all of his forks at once, he may not have to wait as long to eat as in Algorithm I. For example, here is one possible placement of forks.
The specification of the philosopher graph (that is, the number of philosophers and forks and an indication of which which forks are shared by which pairs of philosophers) is given in a file. The graph file also indicates an initial placement of forks. We will give you some graph files as well as a library class to parse them, so you don't have to worry about the their format. The library class which is to be supplied has the following interface.
class Graph { Graph(String fileName) throws FileNotFoundException; // Constructor: reads the graph from a file public int numberOfPhilosophers(); public int numberOfForks(); public int numberOfNeighbors(int phil); // How many neighbors does phil share forks with? public int forkId(int phil, int n); // What is the nth fork shared by phil? public int neighborId(int phil, int n); // Who does phil share his nth fork with? public boolean hasForkInitially(int phil, int n); // Does phil initially hold his nth fork? }The first four methods should be self-explanatory. The last three each take two arguments, a philosopher id phil (a number in the range 0 ... numberOfPhilosophers() - 1), and a number n in the range 0 ... numberOfNeighbors(phil) - 1, and return, respectively, the fork id of phil's nth fork, the philosopher id of the philosopher he shares it with, and an indication of whether phil holds that fork initially. The forks are arranged around each philosopher in increasing order of fork id so that forkId(phil,0) is always the lowest-numbered fork shared by phil. For example, in the above figure, numberOfNeighbors(4) = 3 and
n | forkId(4,n) | neighborId(4,n) | hasForkInitially(4,n) |
---|---|---|---|
0 | 3 | 3 | true |
1 | 4 | 0 | true |
2 | 14 | 9 | false |
Your program will be invoked as java Project2 peterson 10000 where ``peterson'' is the name of a graph file and 10000 indicates the number of iterations. In both solutions, each philosopher will be represented by a thread (an instance of a class that extends Thread or implements Runnable). The run method of this class will look something like this
public void run() { for (int i = 0; i < numberOfIterations; i++) { think(); takeForks(); eat(); putForks(); } }where think() and eat() simply sleep() for a random amount of time, and numberOfIterations is specified on the command line. Use the Random class in java.util and Thread.sleep() to implement think() and eat().
For the first solution, you should define a Semaphore class and create an instance of this class to represent each fork.
class Semaphore { Semaphore(int initialValue); public synchronized void down(); public synchronized void up(); }The method takeForks simply does a down operation on each of the forks (in the order returned by Graph.forkId()) and pubForks does an up operation on them (in any order). The method Graph.hasForkInitially is not used for this solution.
Your main() function will look something like this:
public static void main (String[] args) { // Make sure we have the correct number of arguments if (args.length != 2) { System.err.println ("Usage: Command Filename Iterations"); return; } // Read in the file containing the graph information try { Graph graph = new Graph(args[0]); } catch (FileNotFoundException e) { System.err.println(args[0] + ": " + e); System.exit(1); } // Get the number of iterations (cycles) from the second argument int iterations = Integer.parseInt(args[1]); // Create an array of forks Semaphore[] forks = new Semaphore[graph.numberOfForks()]; for (int i = 0; i < graph.numberOfForks(); i++) forks[i] = new Semaphore(1); // Create an array of philosophers Philosopher[] phil = new Philosopher[graph.numberOfPhilosophers()]; // For Solaris, create a scheduler do keep us honest ThreadScheduler sched = new ThreadScheduler(); sched.start(); // Start the processes for (int id = 0; id < graph.numberOfPhilosophers(); id++) { phil[id] = new Philosopher(iterations); phil[id].start(); sched.registerThread(phil[id]); } // Wait for the philosophers to die for (int id = 0; id < graph.numberOfPhilosophers(); id++) phil[id].join(); sched.stop(); }
The coding for the second algorithm is going considerably more complicated than the first. In this program forks are not represented by separate objects, but rather by variables in the Philosopher objects. Instead of grabbing each of the forks in order, a hungry philosopher will repeatedly cycle through all of his forks, politely requesting those he doesn't have, until he gets them all. He is always willing to respond to requests for forks, even while eating, but depending on his state (thinking, hungry, or eating) and the state of the requested fork (clean or dirty), he may respond by giving the requested fork, or he may respond negatively and remember the request. When a philosopher finishes eating, he goes through his records of requests he refused earlier and sends those forks to their requesters.
Each philosopher will need to remember (in a field of class Philosopher) his own state, as well as several pieces of information about each fork he shares: whether he has it, whether it's clean or dirty, whether it has been requested by his neighbor, and perhaps more.
/** Called by this philosopher when he gets hungry to get his forks. ** Doesn't return until he has them. **/ private synchronized void takeForks() { state = HUNGRY; while (I don't have all my forks) { for (i = 0; i < my number of neighbors; i++) { if (I don't have my ith fork) { f = theGraph.forkId(myId, i); p = theGraph.forkNeighborId(myId, i); if (p.requestFork(f)) record that I have my ith fork, and it is clean } } if (I still don't have all my forks) wait(); } state = EATING; } /** Called when this philosopher finishes eating. */ private synchronized void putForks() { state = THINKING; for (i = 0; i < my number of neighbors; i++) { mark my ith fork as dirty if (I previously rejected a request for my ith fork) { // I previously refused a request for this fork f = theGraph.forkId(myId, i); p = theGraph.forkNeighborId(myId, i); p.giveFork(f); remember that I don't have that fork any more } } } /** Called by another philosopher to request a fork. ** Returns true if the request is granted immediately, and false ** if it has been deferred. **/ public synchronized boolean requestFork(int f) { find i such that theGraph.forkId(myId, i) == f; if (it is ok to give up my ith fork right now) { record that I no longer have my ith fork; return true; } else { remember that my ith fork has been requested return false; } } /** Called by another philosopher to give me a fork I previously ** requested (by calling his requestFork method). **/ public synchronized void giveFork(int forkId) { find i such that theGraph.forkId(myId, i) == f; record that "this" philosopher has his ith fork and that it is clean; notify(); }
You should give a lot of thought to the design of the data structures
used to record the state of a philosopher and his forks.
Note that information about each fork is stored in two places:
Each philosopher that shares the fork has his idea of its state.
There is no separate ``fork'' object.
If your program is correct, this information should always be consistent.
For example, exactly one of the two philosophers should think he has the
fork at any given time.
For debugging, it is useful to check for conditions that ``can't happen''
(such as receiving a request for a fork you don't have) and print an
error message (or throw an exception).
Turn In
You are to turn in copies of all the .java files you used for
this project as well as a script file showing your program in
action (both algorithms) on both of the supplied graph files (peterson and
star).
You must use our
ThreadScheduler
class for the runs you hand in.
Run each test for 20 iterations (each philosopher eats 20 times). The maximum thinking time should be one second and the maximum eating time should be 1/2 second. Print a message each time a philosopher changes state (eating to thinking, thinking to hungry, or hungry to eating). Use ThreadScheduler.elapsed() to timestamp each message:
private Random rand = new Random(); private static final int MAXTHINK = 1000; private static final int MAXEAT = 500; private void think() { try { Thread.sleep((int)(rand.nextFloat() * MAXTHINK)); } catch (InterruptedException) {} System.out.println(ThreadScheduler.elapsed() + ": philosopher " + myId + " becomes hungry"); } private void eat() { System.out.println(ThreadScheduler.elapsed() + ": philosopher " + myId + " starts eating"); try { Thread.sleep((int)(rand.nextFloat() * MAXEAT)); } catch (InterruptedException) {} System.out.println(ThreadScheduler.elapsed() + ": philosopher " + myId + " finishes eating"); }As always, your code should be clearly written with good internal structure, meaningful variable names, helpful comments, etc. Code that is incomprehensible will not be given the benefit of the doubt.
The Windows and Solaris versions of Java have different scheduling policies for threads. The Windows version is preemptive--it periodically switches among all the read threads--while the Solaris version runs one thread until it blocks for some reason. We have created for you a class that simulates preemptive scheduling so that you can see your ``concurrent'' threads really running concurrently under Solaris. To use it, copy ~cs537-1/public/src/ThreadScheduler.java to the directory containing the rest of your source files and compile it:
javac -g ThreadScheduler.javaIn your main method (or wherever you start your threads) create an instance of ThreadScheduler
ThreadScheduler scheduler = new ThreadScheduler(); scheduler.start();and after starting each new thread, ``register'' it with the scheduler
Thread t = new Thread(); t.start(); scheduler.registerThread(t);
Here's how it works:
ThreadScheduler extends Thread, so it is itself a thread.
It raises its own priority to a high level, so it is guaranteed to run
whenever it is not blocked.
It keeps a circular list of all the threads you register with it
and blocks all but one of them from running by calling Thread.suspend().
In a cyclical fashion, it awakens an individual thread
(using Thread.resume())
and sleeps itself for a short period (thereby giving the resumed thread a chance
to run). When the ThreadScheduler wakes, it regains control
due to its high priority, suspends the previous thread, and resumes
a new one. It continues to cycle through all registered threads, giving each
a slice of time in which to execute.
Copyright © 1996 by Marvin Solomon. All rights reserved.
2 K. M. Chandy and J. Misra, op. cit. page 637.