SWEN-342 Engineering of Concurrent & Distributed Software Systems
The Dining Philosophers

Overview

For this activity your team will implement the Dining Philosopher's problem. You'll be able to test it under conditions leading to deadlock as well as those that prevent deadlock.

Note:

You are not allowed to use the synchronized keyword in any code for this activity.

Classes

Fork Class

Create a passive (non-threaded) Fork class; below is the interface to be implemented by Fork.

public interface IFork {
/*
     * A philosopher (attempts to) acquire the fork.
     */
    public void acquire() ;

    /*
     * A philosopher releases the fork.
     */
    public void release() ;
}

There is only a default Fork constructor. Note that a Philosopher acquiring the Fork may have to wait if the Fork is already allocated; when the Fork is released, any waiting Philosopher must be notified. Add state as necessary to the Fork class to support these operations; the initial state is unallocated.

Philosopher Class

The Philosopher class (should be useable in a thread):

public Philosopher(int id, Fork left, Fork right, int nTimes, long thinkMillis, long eatMillis): Initialize the new Philosopher thread object. The id, left and right arguments are self-explanatory and nTimes represents the number of think / eat cycles before the Philosopher exits (0 means run forever). The thinkMillis and eatMillis represent the maximum think time and eating time, respectively, for each cycle.
public void run(): Enter a loop executed nTimes (or infinitely if nTimes is 0). On each iteration:

Select a random integer t from 0 through thinkMillis.
Print a message Philosopher id thinks for t time units, and sleep the selected time.
Print Philosopher id goes for right fork, acquire the right fork, and when this returns print
Philosopher id has right fork.
Yield to another thread using Thread.yield( ).
Print Philosopher id goes for left fork, acquire the left fork, and when this returns print
Philosopher id has left fork.
Yield to another thread using Thread.yield( ).
Select a random integer t from 0 through eatMillis.
Print a message Philosopher id eats for t time units, and sleep the selected time.
Release the right fork and print Philosopher id releases right fork.
Release the left fork and print Philosopher id releases left fork.

Driver Class

The driver class contains the public static void main( ... ) method; your program will be executed with a command of the form:

java Driver [np] [nt] [tm] [em]

np, nt, tm and em are non-negative integers.

As written, all philosophers are right handed.
np is the number of philosophers (and forks); if omitted the default is 4.
nt is the number of the think / eat cycles; the default is 10.
tm is the think time in milliseconds; the default is 0.
em is the eat time in milliseconds; the default is 0.
Command line arguments will be provided in the order shown above. Trailing arguments that are not specified will receive the default value.

The driver first creates an array of np Forks. Next, np Philosopher threads are created, where Philosopher i's right fork is i and left fork is
(np + i - 1) % np - note that i ranges from 0 to np - 1.

Execution

You should execute your program with different parameters, capture the output, and create one long file Trace.txt from the results. The different traces in Trace.txt should be separated from each other so as to make them easy to distinguish. Add comments to the ends of lines in the trace that illustrate interesting states of the system.

In particular, you should have at least one trace with all right handed philosophers that results in a deadlock. I'd suggest running the program as follows (though other combinations may work better for you):

java Driver 2 0 0 0

You need only show the output from the first fork acquisition leading to the deadlock occurs to the deadlock itself.

Once deadlock has been demonstrated, make sure to commit your code. After successfully committing, modify the code to remove the deadlock. This can be accomplished by breaking any of the four necessary and sufficient requirements for deadlock (see class slides). Run your program again (multiple times) do demonstrate the deadlock no longer occurs. Record at least one of these runs in the Trace.txt file along with a description of what you changed to avoid the deadlock.

Deliverables

Submit your solution by pushing all files to the course repo by the deadline.

SWEN-342 Engineering of Concurrent & Distributed Software Systems The Dining Philosophers