📄 http:^^www.cs.wisc.edu^~cs537-1^project2.html
字号:
Date: Tue, 05 Nov 1996 20:57:12 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 21:38:53 GMTContent-length: 22123<html><head><title>CS 537 - Programming Assignment II</title></head><body bgcolor="#ffffff"><h1>CS 537<br>Programming Assignment II <BR>Process Synchronization<br>Corrected: 9/19/96</h1><h2> Due: </h2> October 10 at the <strong>start</strong> of class<hr><h2>Contents</h2><ul><li> <!WA0><a href="#intro"> Introduction</a><li> <!WA1><a href="#generalized"> Generalized Dining Philosophers</a><li> <!WA2><a href="#algorithmI"> Algorithm I</a><li> <!WA3><a href="#algorithmII"> Algorithm II</a><li> <!WA4><a href="#graph"> Specifying the Graph</a><li> <!WA5><a href="#details"> Programming Details</a><li> <!WA6><a href="#turnin"> Turn In</a><li> <!WA7><a href="#scheduler"> ThreadScheduler</a></ul><hr><a name="intro"> <h2> Introduction </h2> </a><p>Discussion of synchronization in operating systems is oftencouched in metaphor. We havethe 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 tothe 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 solutionsto a generalization of the Dining Philosophers problem, usingthe multithreadingand synchronization capabilities of Java to simulate the actionof multiple processes competing for shared resources.<!WA8><a href="http://www.cs.wisc.edu/~cs537-1/cs537.html#tanenbaum">Tanenbaum</a>offers two solutions.The first one, outlined in Figure 2-19 (p. 57) is subject to deadlock(there isan animated demonstration of this solution in the <!WA9><a href="http://www.cs.wisc.edu/~cs537-1/java/tutorial/java/threads/deadlock.html">JavaTutorial</a>).The second one, spelled out in complete detail in Cin Figure 2-20, is the solution given by Edsger Dijkstra, the personwho made up the problem in the first place.It avoids deadlock by putting the states of all the philosophers ina public place and using a global <samp><font color="0f0fff">mutex</font></samp> semaphore to inspect it.You will be implementing two other solutions.<a name="generalized"> <h2> Generalized Dining Philosophers </h2> </a><p>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, itrequired two forks to eat it. Subsequent authors generally assume that the number <i>N</i> 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). <p>Chandy and Misra<!WA10><a href="#footnote"><sup>1</sup></a>further generalized the problem to allow arbitrary pairs of philosophersto 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 <em>fork identifiers</em> which arethe 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, andfork 4 with philosopher 4.(This picture is known in graph theory as the Peterson graph).<BR><center><!WA11><img src = "http://www.cs.wisc.edu/~cs537-1/peterson1.gif"> </center><a name="algorithmI"> <h2> Algorithm I </h2> </a><p>The simplest algorithm for the diners problem is for a hungry philosopherto 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 nextone. This algorithm can lead to deadlock, butif each philosopher always picks up forks in increasing order byfork 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 ofthem have the same number.<a name="algorithmII"> <h2> Algorithm II </h2> </a><p>Chandy and Misra call this algorithm a"hygienic"solution to the diners problem.<ol>``A fork is either<i>clean</i>or<i>dirty</i>.A fork being used to eat with is dirty and remains dirty until it is cleaned.A clean fork remains clean until it is used for eating.A philosopher cleans a fork when mailing it (he is hygienic).A fork is cleaned only when it is mailed.An eating philosopher does not satisfy requests for forks until he has finished eating.The key issue is:which requests should a non-eating philosopher defer?In our algorithm, a non-eating philosopher defers requests for forks thatare clean and satisfies requests for forks that aredirty.''<!WA12><a href="#footnote"><sup>2</sup></a></ol>For example, suppose Aristotle and Berkeley are neighbors and Berkeley iseating.When Berkeley finishes eating, he continues to hold on to their shared forkunless Aristotle asks for it.If Berkeley gets hungry again, he can simply reuse the fork and starteating again (provided he can get the rest of his forks).But if Aristotle wants the fork before Berkeley starts eating again, hecan take it<i>even if Berkeley is hungry</i> (but not yet eating).However, once Aristotle grabs the fork he does not give it up again untilhe has eaten at least once.<p>Chandy and Misra show that this algorithm is deadlock-free provided theinitial placement of forks is<i>acyclic</i>in the following sense:Draw an arrow head on each edge of the graph <i>G</i> so that it points towards the process currently holding the fork.If it is possible to start at some process and follow edges around thegraph returning to the starting point while always obeying the directionsof 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 nothave to wait as long to eat as in Algorithm I.For example, here is one possible placement of forks.<center><!WA13><img src = "http://www.cs.wisc.edu/~cs537-1/peterson2.gif"> </center>Philosopher 8 has all his forks (so he can eat right now if he is hungry),while poor philosopher 0 has none of hers.Fork 11, which is shared by philosophers 6 and 1, is currently held byphilosopher 1.This placement is <em>not</em> acyclic (and hence could lead to deadlock)because of the cycle from 3 to 4 to 9 to 7 to 2 and back to 3.<a name="graph"> <h2>Specifying the Graph</h2> </a><p>The specification of the philosopher graph (that is,the number of philosophers and forks and an indication of which whichforks 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 classto parse them, so you don't have to worry about the their format.The library class which is <em>to be supplied</em> has the followinginterface.<pre><font color="0f0fff"> 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? }</font></pre>The first four methods should be self-explanatory.The last three each take two arguments, a <em>philosopher id</em> <samp><font color="0f0fff">phil</font></samp>(a number in the range <samp><font color="0f0fff">0 ... numberOfPhilosophers() - 1</font></samp>),and a number <samp><font color="0f0fff">n</font></samp> in the range <samp><font color="0f0fff">0 ... numberOfNeighbors(phil) - 1</font></samp>,and return, respectively, the <em>fork id</em> of phil's <samp><font color="0f0fff">n</font></samp><sup>th</sup>fork, the <em>philosopher id</em> 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<em>fork id</em> so that <samp><font color="0f0fff">forkId(phil,0)</font></samp> is always the lowest-numberedfork shared by phil.For example, in the above figure,<samp><font color="0f0fff">numberOfNeighbors(4) = 3</font></samp> and<center><table bgcolor="#e0e0ff" border=3 cellpadding=1 cellspacing=1><tr align="center"> <th>n <th>forkId(4,n) <th>neighborId(4,n) <th>hasForkInitially(4,n)<tr align="center"> <td>0 <td>3 <td>3 <td>true<tr align="center"> <td>1 <td>4 <td>0 <td>true<tr align="center"> <td>2 <td>14 <td>9 <td>false</table></center><a name="details"> <h2>Programming Details</h2> </a><h3> General Outline </h3><p>Your program will be invoked as<samp><font color="0f0fff"> java Project2 peterson 10000</font></samp>where ``peterson'' is the name of a graph file and 10000 indicatesthe number of iterations.In both solutions, each philosopher will be represented by a thread(an instance of a class that extends <samp><font color="0f0fff">Thread</font></samp> or implements<samp><font color="0f0fff">Runnable</font></samp>).The <samp><font color="0f0fff">run</font></samp> method of this class will look something like this<pre><font color="0f0fff"> public void run() { for (int i = 0; i < numberOfIterations; i++) { think(); takeForks(); eat(); putForks(); } }</font></pre>where <samp><font color="0f0fff">think()</font></samp> and <samp><font color="0f0fff">eat()</font></samp> simply <samp><font color="0f0fff">sleep()</font></samp> for a randomamount of time, and <samp><font color="0f0fff">numberOfIterations</font></samp> is specified on thecommand line.Use the <!WA14><a href = "http://www.cs.wisc.edu/~cs537-1/java/api/java.util.Random.html">Random</a>class in java.util and<!WA15><a href = "http://www.cs.wisc.edu/~cs537-1/java/api/java.lang.Thread.html#44520">Thread.sleep()</a>to implement <samp><font color="0f0fff">think()</font></samp> and <samp><font color="0f0fff">eat()</font></samp>.<h3>Algorithm I</h3><p>For the first solution, you should define a <samp><font color="0f0fff">Semaphore</font></samp>class and create an instance of this class to represent each fork.<pre><font color="0f0fff"> class Semaphore { Semaphore(int initialValue);⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -