CS 537 Assignment 2 CS 537 Assignment 2 The Drinking Philosophers NotesWatch this space for corrections, clarifications, implementation hints, etc. October 4 I have added two more graph files: k5.graph (five philosphers with every pair of philosophers sharing a bottle) and c10.graph (ten philosophers sitting in a circle). I also added a comment to the graph files explaining their format in case anyone wants to create their own graphs. September 30 There is now a Frequently Asked Questions (FAQ) page for this project. Check it frequently. September 30 I have released a new version of the files DrinkingException.java, Party.java, and Project2.java. The most imporant difference is that the methods Party.think and Party.drink are no longer synchronized. This change should allow much more concurrency (and more opportunity for race conditions!). For debugging, you may wish to make these methods synchronized in your copy, but the final version of your program should work correctly with these classes exactly as they are in ~cs537/public/project2. There is also a new command-line option -q which turns off all debugging output from class Party except for the summary statistics at the end, and those statistics are better formatted. Important: You must grab new versions of all three of these files. New versions of some will not work together with old versions of others. September 27 Warning It is not safe to call Party.getNeighbor from the Philsopher constructor. The main program creates philosophers one at a time. Consider the call party.getNeighbor(0,0). With the Peterson graph, the result should be a reference to philosopher 1. But if this method is called from philosopher 0's constuctor, philosopher 1 has not been created yet. The original version of Party.java would return null in this case. I have installed a new version that throws an exception. September 27 The due date has been changed. This project will be due at 9:30 am on Tuesday, October 12, 1999. September 25 The previous version of this page gave incorrect instructions for getting a copy of the source files. The instructions have been corrected. Introduction Several philosophers are having a party. When at a party, a philosopher does only two things: he thinks or he drinks. Scattered around the room are various bottles of liquor and mixers. Each bottle is between exactly two philosophers. Only those two philosophers can use that bottle. Each pair of philosophers shares at most one bottle. Philosophers that share a bottle are called neighbors. When a thinking philosopher gets thirsty, he grabs the bottles he needs to mix a drink, mixes the drink, drinks it, and releases the bottles (in that order). He then goes back to thinking. Only one philosopher may use a bottle at a time. Each time a philosopher gets thirsty, he may decide to mix a different drink. He only needs the bottles necessary to mix that drink. For example, if the philosopher gets a craving for a Brandy Alexander, he grabs the bottles of cream, creme de cacao, and brandy, releasing them after he's done drinking. The next time he gets thirsty, he may decide to mix a Sidecar, which requires brandy, cointreau, and lemon juice. A philosopher only tries to mix a drink if he shares all the required bottles (he never gets up and walks across the room to get a bottle), but if, after choosing a drink, he finds that one of the bottles he needs is in use, he may have to wait. At any one time, a bottle is either in use, or it is sitting on the floor next to one of the pair of neighbors that share it. The party is so smoky that a philosopher can only see his neighbors, and it is so noisy that he can only communicate by hand signals. When a philosopher wants to mix a drink and he doesn't have one of the bottles he needs, he signals his request to the appropriate neighbor, who eventually gives it to him, either immediately, or after using it himself. Chandy and Misra's Algorithm K. M. Chandy and J. Misra devised a solution to this problem in their classic paper "The Drinking Philosophers Problem" (ACM Transactions on Programming Languages and Systems, Vol. 6, No. 4, October 1984, pp. 632-646). They came up with the clever idea of using the Dining Philosophers problem as a subroutine to help in solving the Drinking Philosophers problem. Each pair of philosophers that share a bottle also share a fork. When a philosopher gets thirsty, he grabs all his forks and then starts asking for bottles he needs and doesn't yet have. When a philosopher gets a request for a bottle, he hands it over immediately unless he is currently using the bottle, or he is thirsty, he needs the bottle for his chosen drink, and he holds the corresponding fork. In either of these cases, he gives the bottle to his neighbor when he is done using it. Once a Philosopher has all the bottles he needs, he releases the forks. Implementing the Drinking Philosophers in Java You must write a class
public class Philosopher implements Runnable { ... }
We will provided classes Project2 (which contains the main method) and Party. Class Philosopher must have a constructor
Philosopher(int id, int iterations, boolean[] initialBottles, Party party)
id is an integer that uniquely identifies each instance of Philosopher. The method Project2.main creates several instances of Philosopher, each with a different id, and starts each running in a separate thread. iterationsIndicates the number of drinks the Philosopher should mix and drink. The method Philosopher.run() should complete that many think/getBottles/drink/releaseBottles cycles, and then return. initialBottles Indicates which bottles this Philosopher starts out with. The value N = intialialBottles.length is the number of neighbors. Different Philosophers may have different numbers of neighbors. If this philosopher starts out with his ith bottle next to him, initialBottles[i] is true. Otherwise, he has to ask his neighbor for the bottle before he can use it. Each Philosopher must keep track of which bottles he has at any time. In a correct implementation, neighbors will always agree who has the bottle. party is the unique instance of class Party, which is created before any of the Philosophers is started. Class Party has a think method, which the Philosopher should call at the start of each cycle, and a drink method, which it should call after it has gathered all the necessary bottles. Class Party has several other useful public methods. They are summarized below. See the online documentation for more details. Source FilesWe have written three classes for you. Grab copies of all the source files from ~cs537/public/project2:
cd private
mkdir project2
cp ~cs537-2/public/project2/*.* project2
cd project2
WARNING: These classes may need to be updated from time to time. Check the Notes section above frequently to see if you need to fetch a fresh copy. You should not modify any of these files without express permission. Project2.javaThis is the main program. It accepts two command line arguments: the name of a graph file that describes the arrangement of Philosophers and bottles and the number of drinks consumed by each Philosopher before it terminates. The source directory contains a graph file peterson.graph indicating the following arrangement of philosophers: We may be providing additional graph files later. The main program also accepts an optional command-line argument of -v, meaning "verbose", which calls Party.setDebugLevel(10). A sample run might be
jikes *.java # or javac *.java
java -Djava.compiler=NONE Project2 -v peterson.graph 10
Party.javaThe Party class contains the following public methods. See the online documentation for more details. debug(Object message) prints the given message, together with a timestamp and an indication which Philosopher called it. setDebugLevel(int level) Various methods of class Party print their own debugging information. This method controls how verbose the output will be. Higher levels generate more output. Philosopher getNeighbor(int philosopherId, int i) returns a reference to the ith neighbor of the indicated philosopher. getNeighborIndex(int philId, int neighborId) indicates which neighbor a given philosopher is. If getNeighbor(philId, i) = p and unique id of philosopher p is id, then getNeighborIndex(philId, id) == i. int[] think(int philosopherId) simulates a philosopher thinking. It should only be called by the thread of the indicated Philosopher. The caller is delayed for a random amount of time and then gets back an indication of which bottles it should use for its next drink. The result is coded as an array of distinct integers in the range 0 ... N-1, where N is the number of neighbors of the indicated Philosopher. int[] think(int philosopherId) simulates a philosopher thinking. drink(int philosopherId) simulates a philosopher drinking. As with think, philosopherId should be the identifier of the calling Philosopher. This method performs a variety of checks, such as verifying that none of the bottles needed for this drinking session (as indicated by the return value of the previous thinking session) are in use by other Philosophers. getForks(int philosopherId) and releaseForks(int philosopherId) provide a simple solution to the Dining Philosophers problem. In their paper, Chandy and Misra provide a very clever distributed algorithm for Dining Philosophers, but for the purpose of this project we use a simple algorithm using semaphores. (The algorithm "cheats" and uses information about the ordering of neighbors to prevent starvation or deadlock). DrinkingException.javaThis exception is thrown by various methods of Party to indicate a violation of the rules. Hints Your Philosopher class will need private methods getBottles and releaseBottles, which the run method calls before and after calling Party.drink. According to Chandy and Misra's algorithm, getBottles will call party.getForks before trying to get its bottles and party.releaseForks() before it returns. Each Philosopher will need to keep track of which bottles it currently holds. To get a bottle that it doesn't have, it will call the public method requestBottle of the appropriate neighbor. That method will either return the bottle immediately or indicate that the requested bottle is not currently available. In the latter case, it must remember the request, so that when the Philosopher finishes its next drink, it can send the bottle to its neighbor (by calling another public method giveBottle). Remember the cardinal rule of concurrent programming: Any variable that may be accessed by more than one process should only be accessed inside a critical section. In the context of this project, that means that fields of class Philosopher should only be accessed inside synchronized methods. (All fields should be private). On the other hand, there's another rule that will help you avoid deadlocks: A synchronized method should never call a synchronized method of another object. In the context of this project, that means that Philosopher.getBottles will probably not be synchronized, but will instead call other private synchronized methods to access and modify the fields. There will undoubtedly be more hints provided by your fellow students. Watch the Notes section above for more information. What to turn inTurn all .java files you wrote or modified. Do not turn in .class files. No transcript is necessary. GradingPlease carefully consider all the grading criteria discussed in class. Correctness will be 70% of your grade, and style will be 30% of your grade. Last modified: Mon Oct 4 09:31:15 CDT 1999 by Marvin Solomon
