Package ptolemy.domains.csp.demo.DiningPhilosophers

Class DiningPhilosophers

java.lang.Object

ptolemy.domains.csp.demo.DiningPhilosophers.DiningPhilosophers

public class DiningPhilosophers
extends java.lang.Object

Five philosophers are seated at a table with a large bowl of food in the middle. Between each pair of philosophers is one chopstick, and to eat a philosopher must use both chopsticks beside him. Each philosopher spends his life in the following cycle: He thinks for a while, gets hungry, picks up one of the chopsticks beside him, then the other, eats for a while and puts the chopsticks down on the table again. If a philosopher tries to grab a chopstick but it is already being used by another philosopher, then the philosopher waits until that chopstick becomes available. This implies that no neighbouring philosophers can eat at the same time and at most two philosophers can eat at a time.

The Dining Philosophers problem was first dreamt up by Edsger W. Dijkstra in 1965. It is a classic concurrent programming problem that illustrates the two basic properties of concurrent programming:

1. Liveness. How can we design the program to avoid deadlock, where none of the the philosophers can make progress because each is waiting for someone else to do something?
2. Fairness. How can we design the program to avoid starvation, where one of the philosoph ers could make progress but does not because others always go first?

This demo uses an algorithm that lets each philosopher randomly chose which chopstick to pick up first, and all philosophers eat and think at the same rates. This algorithm is fair as any time a chopstick is not being used and both philosophers try to use it, they both have an equal chance of succeeding. However this algorithm does not guarantee the absence of deadlock, and if it is let run long enough this will eventually occur. The probability that deadlock occurs sooner increases as he thinking times are decreased relative to the eating times.

Since:

Ptolemy II 0.3

Version:

$Id$

Author:

Neil Smyth

Pt.AcceptedRating:

Red (cxh)

Pt.ProposedRating:

Red (cxh)

Constructor Summary

Constructors

Constructor	Description
DiningPhilosophers()	Create an instance of the Dining Philosophers demo.

Method Summary

Modifier and Type	Method	Description
static void	connect(TypedCompositeActor univ, Philosopher p1, Philosopher p2, Philosopher p3, Philosopher p4, Philosopher p5)	Connect up the actors.
static void	main(java.lang.String[] args)	The application code.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DiningPhilosophers

public DiningPhilosophers()

Create an instance of the Dining Philosophers demo.

Method Detail

main

public static void main(java.lang.String[] args)

The application code.

connect

public static void connect(TypedCompositeActor univ,
                           Philosopher p1,
                           Philosopher p2,
                           Philosopher p3,
                           Philosopher p4,
                           Philosopher p5)
                    throws IllegalActionException,
                           NameDuplicationException

Connect up the actors.

Parameters:

univ - The container.

p1 - Philosopher 1.

p2 - Philosopher 2.

p3 - Philosopher 3.

p4 - Philosopher 4.

p5 - Philosopher 5.

Throws:

IllegalActionException - If thrown while creating the chopsticks.

IllegalActionException - If thrown while creating the chopsticks.

NameDuplicationException