Date: Wed, 2 Oct 96 01:16:28 BST From: Peter Welch P.H.Welch@ukc.ac.uk To: java-threads@ukc.ac.uk Subject: ALTing ... Status: RO
Dear All,
Wow! I went away from my desk for three days plus a weekend and come back to an overflowing mail system ... better pitch in some more I guess ...
Rick asked whether we need ALTs, given that multiple writers to a channel are already (FIFO) queued in a fair (and constant time) way.
I believe we do still need ALTs because:
However, given the multiple writers FIFO mechanism, we may no longer need to worry about prividing a FAIR version of the ALT -- i.e. ALT and PRI ALT may be enough. Probably do need it though. Meanwhile, PRI ALT is a perfectly good way to implement an ALT, so that's all that's provided for now.
Enclosed is my version of how to do ALTing over our channels. I haven't had a chance to look seriously at what's been flying around so I don't know how different this is from Jeremy's and Gerald's? Except that I saw some discussion that Jeremy's ALT objects were active (i.e. contained a thread) and that Gerald's were passive but needed to be driven by busy polling loops ... in which case, the enclosed is different.
The Alternative class, below, has objects that are passive. Its state and algorithms are copied almost exactly from the mechanisms implemented by transputer micro-code (and copied by the KRoC and SPoC systems!).
The only differences from the transputer algorithm are the fixing of its bug when PRI ALTing from the same channel with different guards (which was identified many years ago by Michael Goldsmith of Formal Systems Ltd.) and a short-cut exit from the enabling sequence (if you find a ready channel).
There is no busy-waiting by the ALTing process and no new threads are needed to manage the ALT.
So, the enclosed implements a PRI ALT, but is a perfectly valid ALT as well, just as in the transputer. As with the transputer, these ALTs only allow input channels as guards and there may be pre-conditions. These input channels cannot be shared with other inputting processes -- but multiple outputting processes are fine. A simple variation would allow the ALTing guards to be output channels from the ALTing process -- but, of course, the process(es) at the other end could not be ALTing and would have to be committed inputters.
An interesting danger of deadlock arose in an earlier version of this scheme. This was when an ALTing process (having claimed the Alternative monitor) tries to disable a Channel (for which it needs to claim the Channel monitor). If this happens at a time when an outputting process writes to the Channel (having claimed the Channel monitor), discovers it is still enabled and tries to schedule the ALTing process (for which it has to claim the Alternative monitor), we will get deadlock!
This has been fixed by not making the disable method synchronised.
However, that lets in a potential race-hazard whereby the outputting process discovers an enabled channel and tries to schedule the ALTing process just after the ALTing process disables the channel. That would leave the outputting process trying to call the schedule method of a null object ... oh, dear ...
This race-hazard is avoided by making a temporary copy of the Alternative object pointer in a variable that is not volatile. An unnecessary schedule may result, but in the circumstances that won't actually do anything.
Cheers,
Peter.
// package occam; // I wish I knew how to make these packages work!
//{{{ public class Alternative {
public class Alternative {
//{{{ COMMENT documentation
//
//This mechanism is based upon the data structures and algorithms implemented
//by micro-code in the transputer. It is exactly the same algorithm as used
//by the KRoC kernel and by the SPoC translator.
//
//An Alternative object is part of the ALTing process and records the status
//of the Alt.
//
//It's `select' method is called by the ALTing process and returns an index
//for a ready Channel if-and-only-if one of the Channels becomes ready. If
//no Channel is ready, it waits (non-busilly) until one is. The parameters
//to `select' are an array of Channels over which to ALT (plus an optional
//array of boolean guards, settable at run-time).
//
//This `select' method operates exactly like similar routines for ALT provided
//in INMOS or 3L parallel C (e.g. `procAltList' or `alt_wait_vec' respectively).
//As with those, it is the programmer's responsibility to ensure that the
//Channel indicated by the selected index is actually used.
//
//An Alternative object is "passive", containing no threads of its own.
//
//For any Channel, there may only be one process ALTing on it, although there
//may be many processes sharing the other end.
//
//The `schedule' method is not public and is called only from an enabled
//Channel object (by the outputting process).
//
//}}}
//{{{ state
private static final int inactive = 0; // whatever happened to
private static final int enabling = 1; // enumerated types?
private static final int waiting = 2;
private static final int ready = 3;
private int state = inactive;
private int selected;
//}}}
//{{{ public synchronized int select (Channel[] c)
public synchronized int select (Channel[] c)
throws InterruptedException {
//{{{
int i;
state = enabling; // ALT START
for (i = 0; i < c.length; i++) {
if (c[i].enable(this)) { // ENABLE CHANNEL
state = ready;
selected = i;
break;
}
}
if (state == enabling) { // ALT WAIT
state = waiting;
wait ();
}
// assert : state == ready
for (i--; i >= 0; i--) {
if (c[i].disable()) { // DISABLE CHANNEL
selected = i;
}
}
state = inactive;
return selected; // ALT END
//}}}
}
//}}}
//{{{ public synchronized int select (Channel[] c, boolean[] guard) {
public synchronized int select (Channel[] c, boolean[] guard)
throws InterruptedException {
//{{{
int i;
state = enabling; // ALT START
for (i = 0; i < c.length; i++) {
if (guard[i] && c[i].enable(this)) { // ENABLE CHANNEL
state = ready;
selected = i;
break;
}
}
if (state == enabling) { // ALT WAIT
state = waiting;
wait ();
}
// assert : state == ready
for (i--; i >= 0; i--) {
if (guard[i] && c[i].disable()) { // DISABLE CHANNEL
selected = i;
}
}
state = inactive;
return selected; // ALT END
//}}}
}
//}}}
//{{{ synchronized void schedule () {
synchronized void schedule () {
if (state == waiting) {
state = ready;
notify ();
}
}
//}}}
}
//}}}
// package occam; // I wish I knew how to make these packages work!
//{{{ public class Channel {
public class Channel {
//{{{ COMMENT documentation
//
//Channel extends an occam CHAN OF INT for a single reader and multiple writers.
//
//It now allows ALTing by that single reader (multiple writers are allowed but
//cannot themselves ALT). This implementation follows closely the transputer
//implementation -- ALTing is passive (i.e. no busy-waits).
//
//There is full synchronisation between a reading and writing thread. Any
//thread may read or write on this Channel. Multiple writers are queued,
//allowing only one at a time to find a reader. Only a single reader is
//catered for and this may back off if it selects another Channel. Writers
//are not allowed to back off. A reader only completes when it finds a writer.
//A writer only completes when it gets to the front of its queue and finds
//a reader.
//
//There is no logical buffering of data in the Channel.
//
//Note: only the `read' and `write' methods are public. The `enable' and
//`disable' Channels are called only from an Alternative object (by the
//ALTing process). It is deliberate that `disable' is not synchronised.
//
//}}}
//{{{ local state
private int channel_hold; // buffer (not detectable to users)
private boolean channel_empty = true; // synchronisation flag
private Object write_monitor = // all writers multiplex through this
new Object ();
private Alternative alt; // state of reader
//}}}
//{{{ public synchronized int read () throws InterruptedException {
public synchronized int read () throws InterruptedException {
if (channel_empty) {
channel_empty = false; // first to the rendezvous
wait (); // wait for the writer thread
notify (); // schedule the writer to finish
} else {
channel_empty = true; // second to the rendezvous
notify (); // schedule the waiting writer thread
}
return channel_hold;
}
//}}}
//{{{ public void write (int n) throws InterruptedException {
public void write (int n) throws InterruptedException {
synchronized (write_monitor) {
synchronized (this) {
Alternative tmp_alt = alt; // avoid race-hazard on the volatile alt
channel_hold = n;
if (tmp_alt != null) { // a reader was ALTing on this Channel
channel_empty = false; // first to the rendezvous
tmp_alt.schedule (); // tell the reader we are here
wait (); // wait for the reader thread
} else if (channel_empty) {
channel_empty = false; // first to the rendezvous
wait (); // wait for the reader thread
} else {
channel_empty = true; // second to the rendezvous
notify (); // schedule the waiting reader thread
wait (); // let the reader regain this monitor
}
}
}
}
//}}}
//{{{ synchronized boolean enable (Alternative alt) {
synchronized boolean enable (Alternative alt) {
if (channel_empty) {
this.alt = alt;
return false;
} else {
return true;
}
}
//}}}
//{{{ boolean disable () {
boolean disable () {
alt = null;
return !channel_empty;
}
//}}}
}
//}}}
//{{{ COMMENT documentation
//|
//| This program shows a use of the ALT mechanism. It is a re-implementation
//| of the Starving Philosophers example but now has the Canteen programmed
//| properly as an active process. Here is the College:
//|
//|
//| 0 1 2 3 4
//| :) :) :) :) :) ___________ ________
//| | | | | | | | | |
//| ---------------------<->--| Canteen |------<------| Cook |
//| service/deliver |_________| supply |______|
//|
//|
//|
//| This time, although Philsopher 0 is just as greedy, no one starves.
//|
//}}}
// import occam.* // I wish I knew how to make these packages work!
//{{{ class Canteen extends Thread {
class Canteen extends Thread {
//{{{
//{{{ COMMENT documentation
//
//The Canteen is an active object -- a pure SERVER process for its `supply'
//and `service'/`deliver' Channels, giving priority to the former.
//
//Philosphers eat chickens. They queue up at the Canteen on its `service'
//Channel. They only get served when chickens are available -- otherwise,
//they just have to wait. Once they have got `service', they are dispensed
//a chicken down the `deliver' Channel.
//
//The Chef cooks chickens. When a batch ready is ready, he/she queues up at
//the Canteen on its `supply' Channel. Setting down the batch takes around
//3 seconds and the Chef is made to hang about this has happened.
//
//}}}
//{{{ channels
private Channel service; // shared from all Philosphers (many-1)
private Channel deliver; // shared to all Philosphers (but only used 1-1)
private Channel supply; // from the Chef (1-1)
//}}}
//{{{ constructor
public Canteen (Channel service, Channel deliver, Channel supply) {
this.service = service;
this.deliver = deliver;
this.supply = supply;
start ();
}
//}}}
//{{{ run
public void run () {
try {
//{{{
//{{{ alt channels and guards
Alternative alt = new Alternative ();
Channel[] c = {supply, service};
boolean[] guard = {true, false};
int supply_index = 0; // how do I declare this constant?
int service_index = 1; // how do I declare this constant?
//}}}
//{{{ state
int n_chickens = 0;
//}}}
//{{{ starting
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Canteen : starting ... ");
//}}}
while (true) {
guard[service_index] = (n_chickens > 0);
switch (alt.select (c, guard)) {
//{{{ supply
case 0: { // case supply_index: {
int value;
value = supply.read (); // new batch of chickens from the Chef
//{{{ bring in the tray
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Canteen : ouch ... make room ... this dish is very hot ... ");
//}}}
//{{{ take 3 seconds to set down the dish (meanwhile a queue may be developing)
try {sleep (3000);} catch (InterruptedException e) {}
//}}}
n_chickens += value;
//{{{ announce arrival of more chickens
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Canteen : more chickens ... " +
n_chickens + " now available ... ");
//}}}
value = supply.read (); // let the Chef get back to cooking
break;
}
//}}}
//{{{ service
case 1: { // case service_index: {
int dummy;
dummy = service.read (); // Philosopher wants a chicken
//{{{ thanks
System.out.println ("(" + System.currentTimeMillis() + ") " +
"Canteen : one chicken coming down ... " +
(n_chickens - 1) + " left ... ");
//}}}
deliver.write (1); // serve one chicken
n_chickens--;
break;
}
//}}}
}
}
//}}}
} catch (InterruptedException e) {}
}
//}}}
//}}}
}
//}}}
//{{{ class Chef extends Thread {
class Chef extends Thread {
//{{{
//{{{ COMMENT documentation
//
//The Chef is an active object. He/she cooks chickens in batches of four --
//taking around 2 seconds per batch -- and then sends them to the Canteen.
//The Chef is delayed in the Canteen, waiting for an acknowledge that the
//batch has been set down OK.
//
//This cycle continues indefinitely.
//
//}}}
//{{{ channels
private Channel supply;
//}}}
//{{{ constructor
public Chef (Channel supply) {
this.supply = supply;
start ();
}
//}}}
//{{{ run
public void run () {
try {
//{{{ 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 ... ");
//}}}
supply.write (n_chickens); // supply the chickens
supply.write (0); // wait till they're set down
}
//}}}
} catch (InterruptedException e) {}
}
//}}}
//}}}
}
//}}}
//{{{ 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.
//
//For this Canteen, when there's no chicken, the Philosphers are just kept
//waiting in the service queue. The greedy Philosopher no longer loses his
//place through getting in before the food is cooked and doesn't starve.
//
//}}}
//{{{ parameters
private int id;
//}}}
//{{{ channels
private Channel service;
private Channel deliver;
//}}}
//{{{ constructor
public Phil (int id, Channel service, Channel deliver) {
this.id = id;
this.service = service;
this.deliver = deliver;
start ();
}
//}}}
//{{{ run
public void run () {
try {
//{{{
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 ... ");
//}}}
service.write (0);
chicken = deliver.read ();
//{{{ consume chicken
System.out.println ("(" + System.currentTimeMillis() + ")" +
" Phil " + id + " : mmm ... that's good ... ");
//}}}
}
//}}}
} catch (InterruptedException e) {}
}
//}}}
//}}}
}
//}}}
//{{{ class College {
class College {
//{{{
//{{{ COMMENT documentation
//
//The College consists of 5 Philosophers, a Chef and the Canteen. All are
//"active" objects. The Canteen ALTs between a service Channel, shared by
//all the Philosophers, and a supply Channel from the Chef. Upon acceptance
//of a service request, chickens are dispensed through a delivery Channel.
//
//Despite the greedy behaviour of Philosopher 0, nobody starves. The Canteen
//guards the service Channel so that Philosophers cannot blunder in when there
//are no chickens, but are held waiting in the service queue. There is no
//concept now of a "stand-bye" queue to which they are sent, thereby losing
//their place in the main queue.
//
//}}}
//{{{ main
public static void main (String argv[]) {
//{{{
int n_philosophers = 5;
Channel service = new Channel ();
Channel deliver = new Channel ();
Channel supply = new Channel ();
Canteen canteen = new Canteen (service, deliver, supply);
Chef chef = new Chef (supply);
Phil[] phil = new Phil[n_philosophers];
for (int i = 0; i < n_philosophers; i++) {
phil[i] = new Phil (i, service, deliver);
}
//}}}
}
//}}}
//}}}
}
//}}}
and here is a script session of a run of the College. Notice nobody starves and that philosophers 1, 2, 3 and 4 eat in strict sequence -- but greedy 0 jumps into that sequence as often as possible:
Script started on Wed Oct 2 00:33:08 1996 mint.ukc.ac.uk% java College (844212797655) Canteen : starting ... (844212797690) Chef : starting ... (844212797704) Chef : cooking ... (844212797714) Phil 0 : starting ... (844212797724) Phil 0 : gotta eat ... (844212797736) Phil 1 : starting ... (844212797748) Phil 2 : starting ... (844212797759) Phil 3 : starting ... (844212797771) Phil 4 : starting ... (844212799722) Chef : 4 chickens, ready-to-go ... (844212799736) Canteen : ouch ... make room ... this dish is very hot ... (844212800752) Phil 1 : gotta eat ... (844212800760) Phil 2 : gotta eat ... (844212800767) Phil 3 : gotta eat ... (844212800776) Phil 4 : gotta eat ... (844212802772) Canteen : more chickens ... 4 now available ... (844212802782) Chef : cooking ... (844212802792) Canteen : one chicken coming down ... 3 left ... (844212802810) Phil 0 : mmm ... that's good ... (844212802821) Phil 0 : gotta eat ... (844212802806) Canteen : one chicken coming down ... 2 left ... (844212802840) Phil 1 : mmm ... that's good ... (844212802848) Canteen : one chicken coming down ... 1 left ... (844212802864) Phil 2 : mmm ... that's good ... (844212802872) Canteen : one chicken coming down ... 0 left ... (844212802883) Phil 3 : mmm ... that's good ... (844212804832) Chef : 4 chickens, ready-to-go ... (844212804843) Canteen : ouch ... make room ... this dish is very hot ... (844212805842) Phil 1 : gotta eat ... (844212805850) Phil 2 : gotta eat ... (844212805857) Phil 3 : gotta eat ... (844212807862) Canteen : more chickens ... 4 now available ... (844212807872) Chef : cooking ... (844212807881) Canteen : one chicken coming down ... 3 left ... (844212807892) Phil 4 : mmm ... that's good ... (844212807903) Canteen : one chicken coming down ... 2 left ... (844212807916) Phil 0 : mmm ... that's good ... (844212807924) Phil 0 : gotta eat ... (844212807930) Canteen : one chicken coming down ... 1 left ... (844212807945) Phil 1 : mmm ... that's good ... (844212807954) Canteen : one chicken coming down ... 0 left ... (844212807965) Phil 2 : mmm ... that's good ... (844212809892) Chef : 4 chickens, ready-to-go ... (844212809905) Canteen : ouch ... make room ... this dish is very hot ... (844212810915) Phil 4 : gotta eat ... (844212810956) Phil 1 : gotta eat ... (844212810964) Phil 2 : gotta eat ... (844212812902) Canteen : more chickens ... 4 now available ... (844212812912) Chef : cooking ... (844212812921) Canteen : one chicken coming down ... 3 left ... (844212812934) Phil 3 : mmm ... that's good ... (844212812943) Canteen : one chicken coming down ... 2 left ... (844212812956) Phil 0 : mmm ... that's good ... (844212812964) Phil 0 : gotta eat ... (844212812970) Canteen : one chicken coming down ... 1 left ... (844212812985) Phil 4 : mmm ... that's good ... (844212812992) Canteen : one chicken coming down ... 0 left ... (844212813004) Phil 1 : mmm ... that's good ... (844212814932) Chef : 4 chickens, ready-to-go ... (844212814943) Canteen : ouch ... make room ... this dish is very hot ... (844212815952) Phil 3 : gotta eat ... (844212815992) Phil 4 : gotta eat ... (844212816000) Phil 1 : gotta eat ... (844212817952) Canteen : more chickens ... 4 now available ... (844212817962) Chef : cooking ... (844212817970) Canteen : one chicken coming down ... 3 left ... (844212817985) Phil 2 : mmm ... that's good ... (844212817992) Canteen : one chicken coming down ... 2 left ... (844212818008) Phil 0 : mmm ... that's good ... (844212818016) Phil 0 : gotta eat ... (844212818022) Canteen : one chicken coming down ... 1 left ... (844212818037) Phil 3 : mmm ... that's good ... (844212818041) Canteen : one chicken coming down ... 0 left ... (844212818057) Phil 4 : mmm ... that's good ... (844212819982) Chef : 4 chickens, ready-to-go ... (844212819993) Canteen : ouch ... make room ... this dish is very hot ... (844212821002) Phil 2 : gotta eat ... (844212821042) Phil 3 : gotta eat ... (844212821050) Phil 4 : gotta eat ... (844212823002) Canteen : more chickens ... 4 now available ... (844212823012) Chef : cooking ... (844212823021) Canteen : one chicken coming down ... 3 left ... (844212823034) Phil 1 : mmm ... that's good ... (844212823042) Canteen : one chicken coming down ... 2 left ... (844212823057) Phil 0 : mmm ... that's good ... (844212823064) Phil 0 : gotta eat ... (844212823071) Canteen : one chicken coming down ... 1 left ... (844212823085) Phil 2 : mmm ... that's good ... (844212823092) Canteen : one chicken coming down ... 0 left ... (844212823105) Phil 3 : mmm ... that's good ... (844212825022) Chef : 4 chickens, ready-to-go ... (844212825032) Canteen : ouch ... make room ... this dish is very hot ... (844212826062) Phil 1 : gotta eat ... (844212826102) Phil 2 : gotta eat ... (844212826109) Phil 3 : gotta eat ... (844212828042) Canteen : more chickens ... 4 now available ... (844212828052) Chef : cooking ... (844212828060) Canteen : one chicken coming down ... 3 left ... (844212828073) Phil 4 : mmm ... that's good ... (844212828081) Canteen : one chicken coming down ... 2 left ... (844212828096) Phil 0 : mmm ... that's good ... (844212828103) Phil 0 : gotta eat ... (844212828109) Canteen : one chicken coming down ... 1 left ... (844212828124) Phil 1 : mmm ... that's good ... (844212828133) Canteen : one chicken coming down ... 0 left ... (844212828144) Phil 2 : mmm ... that's good ... Cmint.ukc.ac.uk% ^D script done on Wed Oct 2 00:33:51 1996