... also during these days resources are rare, especially spoons are out, but anyway philosophers have to eat beside thinking. Our five philosophers can take their seat in the room below and eat at their place spaghetti, if they can get both forks around the plate. During eating it is not allowed due to hygienic restrictions to share any forks. This is the scenario of “The Dining Philosophers” [Dij71], an example to verify the capabilities of concurrent programming language features and synchronization methods.

It will show how the state pattern can be re-implemented by a multi-user, thread safe and more readable approach (with little loss of flexibility). On the other side it is possible to solve the philosopher’s problem with this implementation. For accessing the resources (forks), assertions will be defined, no explicit synchronization mechanism to hand over control to another thread (philosopher) is used (no notify, wait). In detail: if an assertion in a single user environment is not valid, the program can raise an exception. There is nobody else who can set the assertion in between to true. Now it is possible that another philosopher releases a fork, so the right choice for an assertion is to wait (maybe until a reasonable time limit).

At most two philosophers can eat in parallel, a third would need a sixth fork. An assertion object for the room is used which raises immediately an exception if it is not valid.

ASSERT.cond(0 <= pareatcount && pareatcount <= 2);

The room with two eating philosophers (1, 4) looks like:

Inside the table class counters (for statistics) and the forks are defined according to the picture:

class Table {

int pareatcount = 0;

int pareatcountsum = 0;

int eatcountsum = 0;

class Fork {

void use() {

// …

}

}

Fork[] forks = new Fork[5];

boolean[] isForkOnTable = new boolean[5];

// …

}

The variables isForkOnTable are defined to control the requests for forks. The precondition for eating is defined with the help of these variables. The table is implemented as a “state machine” with two main states: dinner and lunch terminated. During dinner it controls access to eat on a seat, leave, or terminate the dinner.

The definition of the entries looks like:

class Table {

// …

class PreConditions extends SelectE2 {

final SelectE2.Entry[] eatsE = new SelectE2.Entry[5];

final SelectE2.Entry releaseE = newEntry();

final SelectE2.Entry terminateE = newEntry();

PreConditions() {

super();

for (int i = 0; i < eatsE.length; i++) {

eatsE[i] = newEntry();

}

}

// …

}

// …

}

To express the preconditions, a class for the enumeration type Precondition is defined by extending a class SelectE2. The name Select is used as a hint to the select statement of the programming language Ada, which allows to define named “entries” as enumeration values. The number 2 denotes to an optimized version of the state machine without a run method for a separate thread. Instead a method nextSelect is used for the state transitions, which gains a factor 3.3 in calculation time (on a single processor) due to eliminated thread waiting conditions.

class Table {

// …

class PreConditions extends SelectE2 {

// …

void nextSelect() {

try {

// state dinner

for (int i = 0; i < 5; i++) {

if (isForkOnTable[i] && isForkOnTable[(i + 1) % 5]) {

this.eatsE[i].accept();

}

}

this.releaseE.accept();

this.terminateE.accept();

this.request();

ASSERT.cond(0 <= pareatcount && pareatcount <= 2);

}

catch (Sync.TerminationException e) {

// state termination

ASSERT.trace("Average parallel lunches "

+((float) pareatcountsum / (float) eatcountsum));

}

}

}

// …

}

According to the values of isForkOnTable the five entries to eat are set. In any case the release of the two forks is allowed and also the termination of the lunch. The request method call is used to tell the preconditions that it is time for a choice.

The Table class initializes and uses the preconditions for controlling access to the eats, getsUp, and terminate methods.

class Table {

// …

PreConditions SELECT = new PreConditions();

Table() {

for (int i = 0; i < 5; i++) {

forks[i] = new Fork();

isForkOnTable[i] = true;

}

SELECT.nextSelect();

}

// …

}

Before an action on the table is possible, it will be tested if the precondition is fulfilled. If not it is not allowed to raise any exception instantly (beside the case lunch is finished). Maybe forks are not available, but the philosopher can start eating after another getsUp.

class Table {

// …

void eats(int seatnum) throws Sync.TerminationException {

SELECT.eatsE[seatnum].pre();

isForkOnTable[seatnum] = false;

isForkOnTable[(seatnum + 1) % 5] = false;

pareatcount++;

pareatcountsum += pareatcount;

eatcountsum++;

SELECT.end();

forks[seatnum].use();

forks[(seatnum + 1) % 5].use();

}

void getsUp(int seatnum) throws Sync.TerminationException {

//forks are stolen when termination happens during eating

SELECT.releaseE.pre();

ASSERT.pre(!isForkOnTable[seatnum]

&& !isForkOnTable[(seatnum + 1) % 5]);

isForkOnTable[seatnum] = true;

isForkOnTable[(seatnum + 1) % 5] = true;

pareatcount--;

SELECT.end();

}

void terminate() throws Sync.TerminationException {

SELECT.terminateE.pre();

SELECT.terminate("Lunch finished!");

SELECT.end();

}

}

The eats method calls first the precondition. If it is fulfilled the method blocks the forks, sets the counters, and tells the SELECT object to evaluate the next state by calling end. Then any other method can be executed in parallel to the use calls of the forks, depending on the philosophers behavior. If the terminate method was executed, all preconditions will raise exceptions and free waiting philosophers. If a philosopher wants to wait only a fixed time .pre(millisecs) can be used.

A philosopher can be implemented this way:

class Phil implements Runnable {

Table table;

int seatnum;

long eatcount = 0;

Phil(Table t, int sn) {

table = t;

seatnum = sn;

new Thread(this).start();

}

void thinks() {

// …

}

public void run() {

try {

while (true) {

thinks();

table.eats(seatnum);

table.getsUp(seatnum);

eatcount++;

}

}

catch (Sync.TerminationException e) {

ASSERT.trace("" + seatnum + " eats " + eatcount + " times.");

}

}

}

A thread is used to describe a simple behavior with a counter to show how successful eating was (not talking about thinking).

The surrounding class Room starts and terminates the example:

public class Room {

// …

Table table = new Table();

Phil[] phils = new Phil[5];

void run() {

for (int i = 0; i < 5; i++) {

phils[i] = new Phil(table, i);

}

ASSERT.sleep(10000); // ten seconds for lunch

try {

table.terminate();

}

catch (Sync.TerminationException e) {

e.printStackTrace();

}

}

public static void main(String[] args) {

Room room = new Room ();

room.run();

}

}

Remark: access modifiers, setters, getters, interfaces, singletons, and additional assertions are not used in the example to keep it short. Also the implementation of the select statement with notify, wait operations is not shown.

Test Results

For a 10 seconds lunch duration and a fork usage time of 10 milliseconds the number of lunches of the philosophers are

194, 196, 204, 199, 203

and the average parallel lunches 1.998998.

If the fork usage time is skipped we have the following numbers:

113739, 112911, 115165, 111800, 151747

and for the average parallel lunches 1.9698743 in a test run.

If the state transitions are defined by a separate thread and not by nextSelect

public void run() {

try {

while (true) {

for (int i = 0; i < 5; i++) {

if (isForkOnTable[i] && isForkOnTable[(i + 1) % 5]) {

SELECT.eatsE[i].accept();

}

}

SELECT.releaseE.accept();

SELECT.terminateE.accept();

SELECT.request();

ASSERT.cond(0 <= pareatcount && pareatcount <= 2);

}

}

catch (Sync.TerminationException e) {

ASSERT.trace("Average parallel lunches "

+ ((float) pareatcountsum / (float) eatcountsum));

}

}

the numbers of lunches reduce to

46042, 27645, 39968, 37234, 30422

and the average parallel lunches to 1.9492536.

There are additional task-switches, which are enforced by the waiting condition in the request method. But the advantage is that the run method can hold the state and no additional variables have to be defined for the next request in more complicate state machines.

Termination

Instead of aborting threads by signals in any state, the example above uses exceptions for a controlled end of a state machine. The method terminate can be called during the dinner state. If termination can happen during any state, terminate may be defined without checking an entry at the beginning.

Deadlock

Deadlock may happen if all philosophers can take the left fork in parallel and wait to get the right. But here using the forks is controlled by the preconditions: an entry is accepted if the left AND the right fork is available, so the number of used forks is always at most 4 and someone is eating or all forks are available.

Fairness and Starvation

Starvation of a philosopher does not happen if the operating system guarantees a minimum of processing time for a thread and Select uses a fair strategy. By overriding the selection method for entries any priority scheme can be implemented.

CSP – Communicating Sequential Processes

Using the mathematical calculus CSP [Hoa85, 75-81] there is a solution for the Dining Philosophers with processes, events, alphabets, traces, and laws:

PHILS=(PHIL0||PHIL1||PHIL2||PHIL3||PHIL4)

FORKS=(FORK0||FORK1||FORK2||FORK3||FORK4)

ROOM=(PHILS||FORKS)

and for example the life of a FORK0 as a process with a sequence of events

FORK0=(0.picks_up_fork.0->0.puts_down_fork.0->FORK0 OR

4.picks_up_fork.0->4.puts_down_fork.0->FORK0)

With a footman who offers at most four philosophers a seat in parallel, the absence of deadlocks is proofed. But the number of traces that must be examined by a computer to proof the absence is two raised to the power of 1.8 millions!

The example shows that it makes sense to insert into the entries preconditions a time constraint to detect deadlocks at runtime (the precondition is forever invalid).

Threads are expensive in implementation, so only threads for tasks are defined. Only philosophers are active and fulfill a task. The table and forks are passive. The role of the footman is implicit defined by the preconditions of the table. These implement the fact that a philosopher takes the forks if both are free. The selection process is sequential. Forks as processes allow parallel selections.

The separate approach for a concurrent version of Eiffel [Mey93] uses multiple resource locking for forks which in fact is a similar implementation but with a different focus and naming. Here entries are used because of the extension to the useful concept of assertions and the more declarative way. Additionally the evaluation of the entries can be defined by a separate programmable state machine (nextSelect).

The State Pattern

The state transitions can be described by the following picture:

It shows the implementation of the method nextSelect. Depending on post-conditions the flow of control may switch to a different state (due to termination).

Comparing with the state pattern defined in [GHJV95] the following differences are found:

all states are defined by one method. It can be divided in sub-methods and overridden by a subclass. The state pattern uses a class per state and a common super class which allows more flexibility in state changes but with a significant overhead in class definitions and complexity in understanding the transitions. In nextSelect the states are more implicit (Dinner) and sub-states (fork used, on table) are defined by variables. The evaluation is done at a central point and the new values for the next state are defined in the eats, getsUp methods. Select is also capable to handle multi user access and blocks the method until the state is reached. This prevents users (philosophers) from polling the state they need.

Preconditional Selection Statement

For the entries inside the precondition class, the enumeration pattern [Blo01] is used in a slightly modified way. Furthermore it would be nice if there is a statement supported by the language. In fact select is an extension of an assertion and also of the synchronize statement. On a first view it can be combined with a try statement since the methods can raise termination exceptions (but it seems to be difficult to define a statement without losing the flexibility of overriding by sub-classing):

void eats(int seatnum) throws Sync.TerminationException {

try (SELECT.eatsE[seatnum]) {

isForkOnTable[seatnum] = false;

isForkOnTable[(seatnum + 1) % 5] = false;

pareatcount++;

pareatcountsum += pareatcount;

eatcountsum++;

}

finally {

forks[seatnum].use();

forks[(seatnum + 1) % 5].use();

}

}

The eatsE entry blocks until it is accepted and the part down to finally will be evaluated under mutual exclusion (like with synchronize). Then the finally part is called which may run in parallel with another method called by another philosopher.

Hereby wait and notify(All) is not necessary in combination with the synchronize statement to schedule another process. There is no explicit jump within the control flow to another point in another thread (implicit goto statement). Code-quality can be enhanced in the same way as by defining assertions, to detect runtime errors in the concurrent program flow locally and as soon as possible.

Bibliography

[Blo01] Joshua Bloch. Effective Java. Programming Language Guide. Addison-Wesley, Reading, MA, 2001.

[Dij71] E. W. Dijkstra. Hierarchical Ordering of Sequential Processes. Acta Informatica 1, 1971, 115-138.

[GHJV95] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Reading, MA, 1995.

[Hoa85] C. A. R. Hoare. Communicating Sequential Processes. Prentice Hall, 1985.

[Mey88] Bertrand Meyer. Object-Oriented Software Construction. Series in Computer Science. Prentice Hall, Englewood Cliffs, NJ, 1988.

[Mey93] Bertrand Meyer. Systematic Concurrent Object-Oriented Programming. Communications of the ACM, 36, 9, September 1993, 56-80.