Date: Wed, 25 Sep 96 23:33:48 BST From: Peter Welch P.H.Welch@ukc.ac.uk To: java-threads@ukc.ac.uk Subject: wot, no chickens? Status: RO
Dear All,
Enclosed is a demonstration that shows that notified threads do get put on the *back* of the queue in order to regain the monitor. Before the `wait' method returns, the thread is made to queue up again on the monitor (behind threads that arrived long after it first went through that queue!). This can result in infinite overtaking and, hence, thread starvation.
This makes the CubbyHole buffer from the Sun tutorial unsafe to use ...
At least, these are the semantics of the `wait/notify' method as implemented on Version 1.0.2 of the JDK for Sun/SPARCs. Since there are no formal semantics and the informal explanation in the tutorial is so vague, it may work differently for other versions or on other platforms ...
Cheers,
Peter.
This demonstration shows a college consisting of five philosophers, a chef and a canteen. The chef and the philosophers are "active" objects. The canteen is a "passive" object through which the philosophers and the chef interact. The canteen is implemented in the style of the CubbyHole.
The philosophers think for a while and then go to the canteen for food. Except for one of them ... who is plain greedy, never thinks and just keeps going to the canteen.
The chef cooks in batches of four, replenishing the canteen when each batch is ready. The greedy philosopher always misses out! He gets there too early the first time (no food yet) and is put on hold. When released, he is put on the *back* of the canteen queue again ... behind his colleagues who arrived whilst he was on hold. His colleagues take the whole batch just arrived from the kitchen and he gets put on hold again. He never gets out of this cycle.
Moral: this shows the danger of programming with these waits and notifies! Why not just use our channels and buffers ...
Note: this scenario was inspired by actions in the canteen queue for the final lunch at the workshop. The reason we didn't starve was that we barged back in to the *front* of the canteen queue when we were notified that the chickens were ready ... luckilly, we weren't being managed by the Java run-time system!
Below is a script session showing a run of the "Starving_Philosophers.java" program. The numbers in parantheses at the start of each line are timestamps in microseconds. The run was stopped with a ctl<C>:
Script started on Wed Sep 25 22:49:24 199 mint.ukc.ac.uk% javac Starving_Philosophers.java mint.ukc.ac.uk% java College (843688193132) Chef : starting ... (843688193158) Chef : cooking ... (843688193173) Phil 0: starting ... (843688193182) Phil 0: gotta eat ... (843688193192) Phil 0: wot, no chickens? I'll WAIT ... (843688193207) Phil 1: starting ... (843688193218) Phil 2: starting ... (843688193230) Phil 3: starting ... (843688193241) Phil 4: starting ... (843688195157) Chef : 4 chickens, ready-to-go ... (843688195167) Chef : ouch ... make room ... this dish is very hot ... (843688196177) Phil 1: gotta eat ... (843688196217) Phil 2: gotta eat ... (843688196225) Phil 3: gotta eat ... (843688196232) Phil 4: gotta eat ... (843688198197) Chef : more chickens ... 4 now available ... NOTIFYING ... (843688198209) Phil 1: those chickens look good ... one please ... (843688198216) Chef : cooking ... (843688198224) Phil 2: those chickens look good ... one please ... (843688198248) Phil 1: mmm ... that's good ... (843688198249) Phil 2: mmm ... that's good ... (843688198238) Phil 3: those chickens look good ... one please ... (843688198291) Phil 4: those chickens look good ... one please ... (843688198304) Phil 3: mmm ... that's good ... (843688198305) Phil 0: wot, no chickens? I'll WAIT ... (843688198305) Phil 4: mmm ... that's good ... (843688200247) Chef : 4 chickens, ready-to-go ... (843688200255) Chef : ouch ... make room ... this dish is very hot ... (843688201277) Phil 1: gotta eat ... (843688201284) Phil 2: gotta eat ... (843688201377) Phil 4: gotta eat ... (843688201385) Phil 3: gotta eat ... (843688203257) Chef : more chickens ... 4 now available ... NOTIFYING ... (843688203267) Phil 1: those chickens look good ... one please ... (843688203279) Chef : cooking ... (843688203280) Phil 2: those chickens look good ... one please ... (843688203280) Phil 1: mmm ... that's good ... (843688203370) Phil 4: those chickens look good ... one please ... (843688203370) Phil 2: mmm ... that's good ... (843688203460) Phil 3: those chickens look good ... one please ... (843688203461) Phil 4: mmm ... that's good ... (843688203549) Phil 0: wot, no chickens? I'll WAIT ... (843688203550) Phil 3: mmm ... that's good ... (843688205387) Chef : 4 chickens, ready-to-go ... (843688205395) Chef : ouch ... make room ... this dish is very hot ... (843688206427) Phil 1: gotta eat ... (843688206527) Phil 2: gotta eat ... (843688206617) Phil 3: gotta eat ... (843688206624) Phil 4: gotta eat ... (843688208417) Chef : more chickens ... 4 now available ... NOTIFYING ... (843688208427) Phil 1: those chickens look good ... one please ... (843688208438) Chef : cooking ... (843688208439) Phil 2: those chickens look good ... one please ... (843688208440) Phil 1: mmm ... that's good ... (843688208530) Phil 3: those chickens look good ... one please ... (843688208531) Phil 2: mmm ... that's good ... (843688208619) Phil 4: those chickens look good ... one please ... (843688208620) Phil 3: mmm ... that's good ... (843688208708) Phil 0: wot, no chickens? I'll WAIT ... (843688208709) Phil 4: mmm ... that's good ... (843688210557) Chef : 4 chickens, ready-to-go ... (843688210565) Chef : ouch ... make room ... this dish is very hot ... (843688211567) Phil 1: gotta eat ... (843688211667) Phil 2: gotta eat ... (843688211767) Phil 4: gotta eat ... (843688211774) Phil 3: gotta eat ... (843688213577) Chef : more chickens ... 4 now available ... NOTIFYING ... (843688213587) Phil 1: those chickens look good ... one please ... (843688213598) Chef : cooking ... (843688213599) Phil 2: those chickens look good ... one please ... (843688213600) Phil 1: mmm ... that's good ... (843688213690) Phil 4: those chickens look good ... one please ... (843688213691) Phil 2: mmm ... that's good ... (843688213779) Phil 3: those chickens look good ... one please ... (843688213780) Phil 4: mmm ... that's good ... (843688213867) Phil 0: wot, no chickens? I'll WAIT ... (843688213868) Phil 3: mmm ... that's good ... (843688215717) Chef : 4 chickens, ready-to-go ... (843688215725) Chef : ouch ... make room ... this dish is very hot ... (843688216787) Phil 1: gotta eat ... (843688216817) Phil 2: gotta eat ... (843688216917) Phil 3: gotta eat ... (843688216924) Phil 4: gotta eat ... (843688218737) Chef : more chickens ... 4 now available ... NOTIFYING ... (843688218747) Phil 1: those chickens look good ... one please ... (843688218761) Phil 1: mmm ... that's good ... (843688218761) Phil 2: those chickens look good ... one please ... (843688218760) Chef : cooking ... (843688218834) Phil 2: mmm ... that's good ... (843688218833) Phil 3: those chickens look good ... one please ... (843688218918) Phil 4: those chickens look good ... one please ... (843688218932) Phil 3: mmm ... that's good ... (843688218933) Phil 0: wot, no chickens? I'll WAIT ... (843688218933) Phil 4: mmm ... that's good ... ^Cmint.ukc.ac.uk% ^D script done on Wed Sep 25 22:50:23 199
Below is the source code of the file "Starving_Philosophers.java". This text is `folded', but is not too bad to read plain:
//{{{ Starving_Philosophers.java
//{{{ class Canteen {
class Canteen {
//{{{
//{{{ COMMENT documentation
//
//Philosphers eat chickens. They queue up at the canteen to use the `get'
//method. Inside the `get' method, they get served straight away so long
//as there are some chickens ready. Otherwise they `wait' on stand-by.
//
//The chef cooks chickens. When he has a batch ready, he also queues up
//at the canteen in order to use the `put' method. This involves setting
//down the batch -- which takes around 3 seconds -- and clearing the stand-by
//queue (of philosophers waiting for chickens) by calling `notifyAll'.
//
//{{{ note 1
//
//Clearly, the Chef should not have to queue up with the Philosophers to
//get into the Canteen. The Philosophers should have their own queue and
//the Chef should only have to contend with one Philospher when dealing with
//the chickens in the canteen. Such a separate queue for the Philosophers is
//just like the seperate queues for readers/writers that we needed for the
//securely shared Channel or Buffer class. However, we are modelling this
//Canteen on the CubbyHole class (to show the danger of starvation it contains)
//and CubbyHole has its queue shared by both readers and writers.
//
//}}}
//
//{{{ note 2
//
//All methods, apart from the `run' method, are executed as part of the thread
//of control of their calling objects. This is particularly clear here, where
//we see them speaking *as* those calling objects. For instance, the `get'
//method is part of the life of the calling Philosopher and `put' is part of
//the life of the Chef. So, this Canteen "object" has bits of Philosopher-
//algorithm and bits of Chef-algorithm for its methods -- a somewhat confused
//set of roles for something that's supposed to be a Canteen. There's nothing
//in these methods that are oriented towards the life of the Canteen.
//
//So, alongside the semantic imprecision of `wait/notify' and alongside the
//non-compositional (or, if you prefer, non-referentially-transparent) semantics
//of methods in general, we have to come to terms with the idea that no methods
//(apart from `run') are oriented towards the "objects" of which they are
//supposed to be a part. So much for "object-orientation" in the formal, and
//quite arbitrary, definition of the term! I believe that the first two
//problems referenced in this paragraph are a direct consequence of the third.
//These problems are not special to this Canteen, but are universal across
//all passive objects.
//
//The Canteen should, of course, be implemented as an active object connected
//to the Philosophers and the Chef via simple channels or buffers. Then, we
//wouldn't have the problems arising from this design. This is left as an
//exercise!
//
//}}}
//
//}}}
private int n_chickens = 0;
//{{{ synchronized get (no chickens ==> wait)
public synchronized int get (int id) {
//{{{
while (n_chickens == 0) {
//{{{ moan
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Phil " + id + ": wot, no chickens? I'll WAIT ... ");
//}}}
//{{{ get on stand-by queue, letting in the next philosopher (or chef)
try {wait();} catch (InterruptedException e){}
//}}}
}
//{{{ thanks
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Phil " + id + ": those chickens look good ... one please ...");
//}}}
n_chickens--;
return 1;
//}}}
}
//}}}
//{{{ synchronized put (takes at least 3 seconds)
public synchronized void put (int value) {
//{{{
//{{{ bring in the tray
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Chef : ouch ... make room ... this dish is very hot ... ");
//}}}
//{{{ take 3 seconds to set down the dish (meanwhile a queue may be developing)
try {Thread.sleep (3000);} catch (InterruptedException e) {}
//}}}
n_chickens += value;
//{{{ announce arrival of more chickens
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Chef : more chickens ... " +
n_chickens + " now available ... NOTIFYING ...");
//}}}
//{{{ put any waiting philosophers back on the main queue
notifyAll ();
//}}}
//}}}
}
//}}}
//}}}
}
//}}}
//{{{ class Chef extends Thread {
class Chef extends Thread {
//{{{
//{{{ COMMENT documentation
//
//A chef is an active object. He cooks chickens in batches of four -- taking
//around 2 seconds per batch -- and then takes then to the canteen.
//
//This cycle continues indefinitely.
//
//}}}
private Canteen canteen;
//{{{ constructor
public Chef (Canteen canteen) {
this.canteen = canteen;
start ();
}
//}}}
//{{{ run
public void run () {
//{{{
int n_chickens;
//{{{ starting
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Chef : starting ... ");
//}}}
while (true) {
//{{{ cook 4 chickens
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Chef : cooking ... ");
//{{{ cook for around 2 seconds
try {sleep (2000);} catch (InterruptedException e) {}
//}}}
n_chickens = 4;
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Chef : " + n_chickens + " chickens, ready-to-go ... ");
//}}}
canteen.put (n_chickens);
}
//}}}
}
//}}}
//}}}
}
//}}}
//{{{ class Phil extends Thread {
class Phil extends Thread {
//{{{
//{{{ COMMENT documentation
//
//A philosopher thinks for a while -- around 3 seconds -- and then goes to the
//canteen for food, consuming what he gets straight away. This cycle continues
//indefinitely.
//
//Except, that is, for philosopher 0 ... who refuses to think and just keeps
//going to the canteen. He will get his come-uppance shortly.
//
//}}}
private int id;
private Canteen canteen;
//{{{ constructor
public Phil (int id, Canteen canteen) {
this.id = id;
this.canteen = canteen;
start ();
}
//}}}
//{{{ run
public void run () {
//{{{
int chicken;
//{{{ starting
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Phil " + id + ": starting ... ");
//}}}
while (true) {
//{{{ everyone, bar philosopher 0, has a little think
if (id > 0) {
//{{{ think for around 3 seconds
try {sleep (3000);} catch (InterruptedException e) {}
//}}}
}
//}}}
//{{{ want chicken
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Phil " + id + ": gotta eat ... ");
//}}}
chicken = canteen.get (id);
//{{{ consume chicken
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Phil " + id + ": mmm ... that's good ... ");
//}}}
}
//}}}
}
//}}}
//}}}
}
//}}}
//{{{ class College {
class College {
//{{{
//{{{ COMMENT documentation
//
//The College consists of 5 Philosophers, a Chef and the Canteen. The Chef and
//the Philosophers are "active" objects. The Canteen is a "passive" object
//through which the Philosophers and the Chef have to interact.
//
//The Canteen is implemented in the style of the CubbyHole example from Sun's
//Java Tutorial. As such, it exposes each Philosopher to the danger of
//starvation (by infinite overtaking by fellow Philosophers). Sadly, this
//does happen with the particular timing circumstances set up in this
//demonstration. Happily, it's the greedy Philosopher that starves -- he
//never even gets one meal, despite being in the Canteen the whole time!
//
//}}}
//{{{ main
public static void main (String argv[]) {
//{{{
int n_philosophers = 5;
Canteen canteen = new Canteen ();
Chef chef = new Chef (canteen);
Phil[] phil = new Phil[n_philosophers];
for (int i = 0; i < n_philosophers; i++) {
phil[i] = new Phil (i, canteen);
}
//}}}
}
//}}}
//}}}
}
//}}}