/OU=CCTA452/%idem.hmg.gold-400.gb@NSS.CS.UCL.AC.UK (10/27/88)
OCCAM NEWSLETTER 9 DEADLOCK ARTICLE
This is in response to Alan Chambers' article in the Occam User Group
Newsletter 9, and to the article 373(a)istop.ist.CO.UK from
Tom Parke. I have already responded to a reponse from Geraint Jones
on the 'Fair ALT' problem on the occam net, and have added a copy of that
to this posting for those not on both nets.
My TEDIOUS demonstration system, running under TDS, consists of a keyboard
fan-out process (1 in, n out), a screen-driver multiplexor (n in, 1 out),
and a floating population of intermediate processes, some of which display
in windows on the screen through the s-d m. The following are the rules
I have devised for the intermediate processes to ensure that the whole
system will terminate on a single keystroke command.
1. Every channel type has a defined 'abort' signal.
2. Within each process, every input is tested for 'abort'.
3. When a process detects 'abort' on any input channel:
a) it does not read that channel again
b) as soon as it conveniently can it ceases all activity, except
for a routine in which IN PARALLEL it:
sends 'abort' on all output channels (except to screen)
reads all input channels until 'abort' has been read
c) it sends 'abort' to the screen and terminates.
Making the screen a special case helps diagnosis. The screen multiplexor
follows a different plan, simply counting the number of 'abort's received,
and then terminating.
An example of a process which can communicate with another copy of itself,
if necessary:
PROC active(CHAN OF INT inchan, outchan, up, down)
-- inchan from kbd, outchan towards screen)
-- up from, down to, other active procs
BOOL run :
INT key, char :
VAL abort IS ft.refresh : -- 'ESC' key
SEQ
... initialise run:=TRUE; key:= char:= 0;
WHILE run
SEQ
ALT
inchan ? key
SKIP -- it's actually more complex of course
up ? char
SKIP
-- end ALT
IF
(key = abort) OR (char = abort)
run := FALSE
(key <> abort) AND (char <> abort)
SEQ
... rest of action
-- end SEQ
-- end WHILE
PAR -- start of termination routine
down ! abort
WHILE char <> abort
up ? char
WHILE key <> abort
inchan ? key
-- end PAR
outchan ! abort -- close window
-- end SEQ
: -- end of PROC
If rule 2 seems to impose too great an overhead, it may be possible to
treat groups of inputs as "messages", and only test each message.
ROUND ROBIN SCHEDULING
The trouble with an 'obvious' numerical rotation round robin is that if
channel B follows channel A in simple sequence, then if there are
10 channels, it will follow it in 9 out of 10 rotated sequences. If
A is 100% busy, B will get only 1/10th of the cake.
The following is a simplified version of the multiplexor from my screen
windowing system. It has been posted to the occam board and has found some
favour there. [Close-down mechanism not shown].
VAL n IS number-of-channels :
[n] CHAN OF BYTE c :
[n] BOOL mask :
[n] BYTE x :
BOOL reset, busy :
SEQ
... busy := TRUE; reset := FALSE; mask[] := TRUE
WHILE busy
PRI ALT
ALT i = 0 FOR n
mask[i] & c[i] ? x[i]
SEQ
mask[i] := FALSE
reset := TRUE
P(i)
-- end ALT
reset & SKIP
SEQ
reset := FALSE
SEQ i = 0 FOR n
mask[i] := TRUE
-- end PRI ALT
This will not let any channel have a second go until there are no other
channels waiting for a first go - sort of round robin but with some
(inevitable?) quantum uncertainty of exact sequencing.
Harold J Curnow +44 1 217 3209
Advanced Technology Group
Central Computer & Telecommunications Agency
Riverwalk House
157-161 Millbank, London SW1P 4RT
e.mail: CCTA452%GB.GOLD-400.hmg.idem.ccta452@uk.ac.ucl.cs
or : CCTA452@GB.GOLD-400.hmg.idem.ccta452paul@unisoft.UUCP (n) (10/28/88)
In article <8810261709.AA18143@uk.ac.oxford.prg.inessa> /OU=CCTA452/%idem.hmg.gold-400.gb@NSS.CS.UCL.AC.UK writes: > > ROUND ROBIN SCHEDULING >.... > > This will not let any channel have a second go until there are no other > channels waiting for a first go - sort of round robin but with some > (inevitable?) quantum uncertainty of exact sequencing. It robs from the rich and gives to the poor - seems to me to actually be "Round Robin Hood Scheduling" ..... sorry, I couldn't resist ... Paul -- Paul Campbell, UniSoft Corp. 6121 Hollis, Emeryville, Ca ..ucbvax!unisoft!paul Nothing here represents the opinions of UniSoft or its employees (except me) "Where was George?" - Nudge, nudge say no more