http:^^www.cs.wisc.edu^~cs537-1^project2.html

This data set contains WWW-pages collected from computer science departments of various universities

        public synchronized void down();
        public synchronized void up();
    }
</font></pre>
The method <samp><font color="0f0fff">takeForks</font></samp> simply does a <samp><font color="0f0fff">down</font></samp> operation on
each of the forks (in the order returned by <samp><font color="0f0fff">Graph.forkId()</font></samp>)
and <samp><font color="0f0fff">pubForks</font></samp> does an <samp><font color="0f0fff">up</font></samp> operation on them (in any order).
The method <samp><font color="0f0fff">Graph.hasForkInitially</font></samp> is not used for this solution.
<p>
Your <samp><font color="0f0fff">main()</font></samp> function will look something like this:
<pre><font color="0f0fff">
    public static void main (String[] args)                    
    {    
        // Make sure we have the correct number of arguments     
        if (args.length != 2) {                             
            System.err.println (&quot;Usage: Command Filename Iterations&quot;);
            return;                                            
        }                                                     

        // Read in the file containing the graph information       
        try {
            Graph graph = new Graph(args[0]);                                 
        }
        catch (FileNotFoundException e) {
            System.err.println(args[0] + &quot;: &quot; + 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 &lt; 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 &lt; 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 &lt; graph.numberOfPhilosophers(); id++)
            phil[id].join();
        sched.stop();
    }
</font></pre>

<h3>Algorithm 2</h3>
<p>
The coding for the second algorithm is going considerably more
complicated than the first.
In this program forks are <em>not</em> represented by separate objects,
but rather by variables in the <samp><font color="0f0fff">Philosopher</font></samp> 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.
<p>
Each philosopher will need to remember (in a field of class <samp><font color="0f0fff">Philosopher</font></samp>)
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.
<pre><font color="0f0fff">
    /** 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 &lt; 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 &lt; 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 &quot;this&quot; philosopher has his ith fork and that it is clean;
        notify();
    }
</font></pre>
<p>
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.
<strong>There is no separate ``fork'' object.</strong>
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).

<a name="turnin"> <h2>Turn In</h2> </a>
You are to turn in copies of all the <samp><font color="0f0fff">.java</font></samp> 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
<!WA16><a href="#scheduler">
ThreadScheduler
</a>
class for the runs you hand in.
<p>
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 <samp><font color="0f0fff">ThreadScheduler.elapsed()</font></samp> to timestamp each message:
<pre><font color="0f0fff">
    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()
            + &quot;: philosopher &quot; + myId + &quot; becomes hungry&quot;);
    }
    private void eat() {
        System.out.println(ThreadScheduler.elapsed()
            + &quot;: philosopher &quot; + myId + &quot; starts eating&quot;);

        try { Thread.sleep((int)(rand.nextFloat() * MAXEAT)); }
        catch (InterruptedException) {}

        System.out.println(ThreadScheduler.elapsed()
            + &quot;: philosopher &quot; + myId + &quot; finishes eating&quot;);
    }
</font></pre>
As always,
your code should be clearly written with good internal structure, meaningful
variable names, helpful comments, etc.   Code that is incomprehensible will
<b>not</b> be given the benefit of the doubt.

<a name="scheduler"> <h2>The ThreadScheduler</h2> </a>
<p>
The Windows and Solaris versions of Java have different scheduling policies
for threads.
The Windows version is <em>preemptive</em>--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
<!WA17><a href="http://www.cs.wisc.edu/~cs537-1/src/ThreadScheduler.java">
~cs537-1/public/src/ThreadScheduler.java</a>
</a>
to the directory containing the rest of your source files and compile it:
<pre><font color="0f0fff">
    javac -g ThreadScheduler.java
</font></pre>
In your <samp><font color="0f0fff">main</font></samp> method (or wherever you start your threads)
create an instance of <samp><font color="0f0fff">ThreadScheduler</font></samp>
<pre><font color="0f0fff">
    ThreadScheduler scheduler = new ThreadScheduler();        
    scheduler.start();                                     
</font></pre>
and after starting each new thread, ``register'' it with the scheduler
<pre><font color="0f0fff">
    Thread t = new Thread();                                                
    t.start();                                                              
    scheduler.registerThread(t);
</font></pre>
<p>
Here's how it works:
<samp><font color="0f0fff">ThreadScheduler</font></samp> extends <samp><font color="0f0fff">Thread</font></samp>, 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 <samp><font color="0f0fff">Thread.suspend()</font></samp>.
In a cyclical fashion, it awakens an individual thread
(using <samp><font color="0f0fff">Thread.resume()</font></samp>)
and sleeps itself for a short period (thereby giving the resumed thread a chance
to run).  When the <samp><font color="0f0fff">ThreadScheduler</font></samp> 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.
<br>
<br>
Copyright &#169; 1996 by Marvin Solomon.  All rights reserved.
<hr>
<a name="footnote">
<sup>1</sup>
K. M. Chandy and J. Misra, ``The Drinking Philosophers 
Problem,'' <i>ACM Trans. on Programming Languages and Systems</i>, Vol. 6, 
No. 4, October 1984, pp. 632-646. 
<p>
<sup>2</sup>
K. M. Chandy and J. Misra, <em>op. cit.</em> page 637.
</a>
</body>
</html>