Date: Wed, 2 Oct 96 16:39:25 BST From: Peter Welch P.H.Welch@ukc.ac.uk To: java-threads@ukc.ac.uk Subject: occam version of the Java College (SHARED channels) Cc: occam-com@ukc.ac.uk Status: RO
Dear All,
Here is the occam version of the Non-Starving Philosophers system mailed yesterday in Java. The Java implementation exactly follows the occam process/channel methodolgy, so there is a 1-1 correspondence between this occam model and the Java one.
This occam model uses an (occam3) SHARED channel-pair for the client-server connection between the Philosophers and the Canteen. The standard screen output channel is also SHARED by all processes in the system.
Not having occam3, these SHARED channels are implemented in occam2 as ordinary channels for which the sharers have explicitly to claim and release SEMAPHOREs. SEMAPHOREs are implemented as occam2.1 data types with the initialisation, claim and release methods programmed by in-lined transputer assembler (ASM). We haven't yet benchmarked the semaphores, but doubt that their overheads (which include context-switching) exceed a microsecond (using KRoC on SPARCs or Alphas).
The SEMAPHOREs are very useful in that they give us queues on which to hang processes. Channels give us a peg to hang just a single process.
SEMAPHOREs guarding channels give us SHARED channels (in much the same way as SEMAPHOREs guarding procedures gave monitors). In the occam-for-all project, we have devised ways of distributing SEMAPHOREs so as to obtain SHARED channels that stretch across processors (for example, a workstation cluster). This is different to the RESOURCE CHANNEL mechanism of the T9000 (which we have also implemented for KRoC) and has several benefits (but one disadvantage). For information, we have also implemented bulk synchronisation primitives that are dynamic and hierarchical ... but probably not useful until we have an SMP (or virtual-SMP) implementation for KRoC. Details on this will appear on occam-com@ukc.ac.uk and on the occam Web pages in the (HENSA) IPCA archive ... eventually!
SEMAPHOREs, RESOURCEs and EVENT synchronisations will be in the next release of the KRoC system. SEMAPHOREs, giving us FIFO-queued (i.e. fair) sharing (in constant and sub-microsecond time), are immediately useful.
Would anyone like a pre-release?
NOTE: See "Higher Levels of Process Synchronisation in occam" at
<URL:/parallel/occam/projects/occam-for-all/hlps/>
SHARED channels, even when implemented via ordinary channels guarded by explicit SEMAPHOREs, give better performance and a higher-level way of expressing certain things.
For example, see how easy it is now for any process to have access to the screen (or keyboard, file system, ...) in the College example below.
For fair-ALTing (with no pre-conditions) over a large number of channels, a single SHARED channel provides constant-time (and tiny) overheads plus reduced memory requirements and an increase in system simplicity.
However, we do need to tie down the concepts into the language in order to remove the need for programmer-explicit guards and close that security loophole. For instance, all the SEMAPHORE declarations and sharing PRAGMAs disappear in the occam3 version of the College.
The important comparison is how similar (and simple) are the guts of the codes.
Comparing the codes, the Java program is slightly shorter (306 lines against 328 lines). But a lot of those Java lines are a distracting syntactic overhead (e.g. constructor declaration, run declaration ... the occam PROCs just get on with it). The occam PROCs also contain information about their parameters in the obvious place -- not as private declarations within the class body that get set up by the class constructor!
If we compare the bodies of the Java run methods against the bodies of the occam PROCs, the Java is a fair bit smaller. This is chiefly because the program consists mainly of writing strings and numbers to the screen. Java does this in one `System.out.println' statement (two lines), but occam takes around eight. This is because occam treats printing as a communication, just like any output, and this needs guarding since its destination channel is SHARED. The sharing is automatically managed by some ad hoc mechanism in the Java run-time system. Java also gets times returned by method calls, which is dangerous -- because of the usual confusion in most imperative languages between expression evaluation and system update (that leads to very complex semantics).Note also that all processes in the occam system explicitly share the same timer (which is not necessarilly guaranteed if they each declared their own timers).
Finally, Java wins because its operator overloading allows numeric and string data to be concatenated as a string.
Of course, with a folding editor, the Java two lines and the occam eight lines look just the same -- one fold!
occam wins, by a wide margin, on the performance front. The timestamps from the Java output are in milliseconds, whilst those from the occam output are in microseconds. The start-up times recorded between the first-process- starting and all-the-processes-started-plus-Phil-0-announcing-gotta-eat (which comprises all program activity that can take place before the first time-out, set for two seconds) are:
Java : 116 msecs occam : 8.8 msecs
I would bet good money that around 8.3 msecs of the occam time is time spent by Unix in outputting the characters. That leaves around 500 microseconds time spent by the actual user code. The dominant activity in this program is context-switching. The dominant context-switches are caused by screen output -- one context-switch per character -- everything else is just noise! That's about 500 context-switches for this start-up, so that 500 micro-seconds is probably an overestimate. [Future versions of KRoC will stop all this context-switch-per-screen-character-output business!]
Peter
#USE "utils"
#INCLUDE "semaphore.inc"
PROC College (CHAN OF BYTE keyboard, screen, error)
--{{{
--{{{ COMMENT documentation
--|
--| This program is an occam version of the Java model of the Non-Starving
--| Philosophers (the one that used the occam model of processes and channels).
--|
--| This program also shows the use of SHARED channels (between the Canteen
--| and the Philosophers and between everyone and the external Screen).
--|
--| Note that, in occam, we have to be precise about that SHARED screen channel.
--| In Java, its shared use is implicit and restricted to multi-plexing on a
--| single-line basis. Here is the College:
--|
--|
--| ---------->-------------->----------------->------------------------>
--| | | | | | | | screen
--| 0 1 2 3 4 | |
--| :) :) :) :) :) _____|_____ ____|___
--| | | | | | | | | |
--| ---------------------<->--| Canteen |------<------| Chef |
--| service/deliver |_________| supply |______|
--|
--|
--|
--| The College consists of 5 Philosophers, a Chef and the Canteen. 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.
--|
--}}}
--{{{ screen sharing
#PRAGMA SHARED screen
--}}}
--{{{ timing
VAL INT seconds IS 1000000:
--}}}
--{{{ Canteen
PROC Canteen (CHAN OF INT service, deliver, supply,
CHAN OF BYTE screen, SEMAPHORE screen.s,
TIMER tim)
--{{{
--{{{ COMMENT documentation
--
--The Canteen is a pure SERVER process for its `supply' and `service'/`deliver'
--channels, giving priority to the former.
--
--Philosophers 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 until this has happened.
--
--}}}
INT n.chickens:
SEQ
n.chickens := 0
--{{{ starting
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Canteen : starting ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
WHILE TRUE
PRI ALT
--{{{ new batch of chickens from the Chef
INT value:
supply ? value
SEQ
--{{{ bring in the tray
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Canteen : ouch ... make room ... this dish is very hot ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
--{{{ take 3 seconds to set down the dish (a queue may be developing)
INT t:
SEQ
tim ? t
tim ? AFTER t PLUS (3*seconds)
--}}}
n.chickens := n.chickens + value
--{{{ announce arrival of more chickens
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Canteen : more chickens ... ", 0, screen)
out.number (n.chickens, 0, screen)
out.string (" now available ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
supply ? value -- let the Chef get back to cooking
--}}}
--{{{ (n.chickens > 0) & Philosopher wants a chicken
INT dummy:
(n.chickens > 0) & service ? dummy
SEQ
--{{{ thanks
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Canteen : one chicken coming down ... ", 0, screen)
out.number (n.chickens - 1, 0, screen)
out.string (" left ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
deliver ! 1 -- serve one chicken
n.chickens := n.chickens - 1
--}}}
--}}}
:
--}}}
--{{{ Chef
PROC Chef (CHAN OF INT supply,
CHAN OF BYTE screen, SEMAPHORE screen.s,
TIMER tim)
--{{{
--{{{ COMMENT documentation
--
--The Chef 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.
--
--}}}
SEQ
--{{{ starting
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Chef : starting ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
WHILE TRUE
INT n.chickens:
SEQ
--{{{ cook 4 chickens
SEQ
--{{{ say we're cooking
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Chef : cooking ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
--{{{ cook for around 2 seconds
INT t:
SEQ
tim ? t
tim ? AFTER t PLUS (2*seconds)
--}}}
n.chickens := 4
--{{{ ready-to-go
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Chef : ", 0, screen)
out.number (n.chickens, 0, screen)
out.string (" chickens, ready-to-go ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
--}}}
supply ! n.chickens -- supply the chickens
supply ! 0 -- wait till they're set down
--}}}
:
--}}}
--{{{ Phil
PROC Phil (VAL INT id, CHAN OF INT service, deliver, SEMAPHORE service.s,
CHAN OF BYTE screen, SEMAPHORE screen.s,
TIMER tim)
--{{{
--{{{ 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 Philosophers are just kept
--waiting in the service queue. The greedy Philosopher cannot lose his place
--through getting in before the food is cooked and doesn't starve.
--
--}}}
SEQ
--{{{ starting
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Phil ", 0, screen)
out.number (id, 0, screen)
out.string (" : starting ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
WHILE TRUE
INT chicken:
SEQ
--{{{ everyone, bar Philosopher 0, has a little think
IF
id > 0
--{{{ think for around 3 seconds
INT t:
SEQ
tim ? t
tim ? AFTER t PLUS (3*seconds)
--}}}
TRUE
SKIP
--}}}
--{{{ want chicken
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Phil ", 0, screen)
out.number (id, 0, screen)
out.string (" : gotta eat ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
claim.semaphore (service.s)
--{{{ client transaction on service/deliver
SEQ
service ! 0
deliver ? chicken
--}}}
release.semaphore (service.s)
--{{{ consume chicken
INT t:
SEQ
claim.semaphore (screen.s)
tim ? t
screen ! '('
out.number (t, 0, screen)
out.string (") Phil ", 0, screen)
out.number (id, 0, screen)
out.string (" : mmm ... that*'s good ... *c*n", 0, screen)
release.semaphore (screen.s)
--}}}
--}}}
:
--}}}
--{{{ network
--{{{ VAL INT n.philosophers IS 5:
VAL INT n.philosophers IS 5:
--}}}
--{{{ TIMER tim:
TIMER tim:
--}}}
--{{{ SHARED [CHAN OF INT, CHAN OF INT] [service, deliver]:
CHAN OF INT service, deliver:
#PRAGMA SHARED service
#PRAGMA SHARED deliver
SEMAPHORE service.s:
#PRAGMA SHARED service.s
--}}}
--{{{ CHAN OF INT supply:
CHAN OF INT supply:
--}}}
--{{{ SEMAPHORE screen.s
SEMAPHORE screen.s:
#PRAGMA SHARED screen.s
--}}}
SEQ
--{{{ initialise the semaphores
SEQ
initialise.semaphore (service.s, 1)
initialise.semaphore (screen.s, 1)
--}}}
PAR
Canteen (service, deliver, supply, screen, screen.s, tim)
Chef (supply, screen, screen.s, tim)
PAR i = 0 FOR n.philosophers
Phil (i, service, deliver, service.s, screen, screen.s, tim)
--}}}
--}}}
:
Script started on Wed Oct 2 12:31:50 1996 mint.ukc.ac.uk% College (-1507231166) Canteen : starting ... (-1507225827) Chef : starting ... (-1507225381) Phil 0 : starting ... (-1507224993) Phil 1 : starting ... (-1507224603) Phil 2 : starting ... (-1507223642) Phil 3 : starting ... (-1507223203) Phil 4 : starting ... (-1507222771) Chef : cooking ... (-1507222344) Phil 0 : gotta eat ... (-1505219920) Chef : 4 chickens, ready-to-go ... (-1505217251) Canteen : ouch ... make room ... this dish is very hot ... (-1504220279) Phil 1 : gotta eat ... (-1504217677) Phil 2 : gotta eat ... (-1504217222) Phil 3 : gotta eat ... (-1504216831) Phil 4 : gotta eat ... (-1502210547) Canteen : more chickens ... 4 now available ... (-1502207819) Chef : cooking ... (-1502207366) Canteen : one chicken coming down ... 3 left ... (-1502206733) Phil 0 : mmm ... that's good ... (-1502206309) Canteen : one chicken coming down ... 2 left ... (-1502205856) Phil 0 : gotta eat ... (-1502205450) Phil 1 : mmm ... that's good ... (-1502205037) Canteen : one chicken coming down ... 1 left ... (-1502204531) Phil 2 : mmm ... that's good ... (-1502204108) Canteen : one chicken coming down ... 0 left ... (-1502203598) Phil 3 : mmm ... that's good ... (-1500200186) Chef : 4 chickens, ready-to-go ... (-1500193255) Canteen : ouch ... make room ... this dish is very hot ... (-1499200244) Phil 1 : gotta eat ... (-1499197644) Phil 2 : gotta eat ... (-1499197187) Phil 3 : gotta eat ... (-1497190569) Canteen : more chickens ... 4 now available ... (-1497187826) Chef : cooking ... (-1497187374) Canteen : one chicken coming down ... 3 left ... (-1497186739) Phil 4 : mmm ... that's good ... (-1497186315) Canteen : one chicken coming down ... 2 left ... (-1497185807) Phil 0 : mmm ... that's good ... (-1497185387) Canteen : one chicken coming down ... 1 left ... (-1497184935) Phil 0 : gotta eat ... (-1497184526) Phil 1 : mmm ... that's good ... (-1497184114) Canteen : one chicken coming down ... 0 left ... (-1497183605) Phil 2 : mmm ... that's good ... (-1495180508) Chef : 4 chickens, ready-to-go ... (-1495177844) Canteen : ouch ... make room ... this dish is very hot ... (-1494180461) Phil 4 : gotta eat ... (-1494177324) Phil 1 : gotta eat ... (-1494176867) Phil 2 : gotta eat ... (-1492170628) Canteen : more chickens ... 4 now available ... (-1492167893) Chef : cooking ... (-1492167441) Canteen : one chicken coming down ... 3 left ... (-1492166806) Phil 3 : mmm ... that's good ... (-1492166387) Canteen : one chicken coming down ... 2 left ... (-1492165875) Phil 0 : mmm ... that's good ... (-1492165457) Canteen : one chicken coming down ... 1 left ... (-1492164997) Phil 0 : gotta eat ... (-1492164597) Phil 4 : mmm ... that's good ... (-1492164186) Canteen : one chicken coming down ... 0 left ... (-1492163674) Phil 1 : mmm ... that's good ... (-1490160554) Chef : 4 chickens, ready-to-go ... (-1490157872) Canteen : ouch ... make room ... this dish is very hot ... (-1489159659) Phil 3 : gotta eat ... (-1489157075) Phil 4 : gotta eat ... (-1489156624) Phil 1 : gotta eat ... (-1487150657) Canteen : more chickens ... 4 now available ... (-1487147934) Chef : cooking ... (-1487147483) Canteen : one chicken coming down ... 3 left ... (-1487146850) Phil 2 : mmm ... that's good ... (-1487146428) Canteen : one chicken coming down ... 2 left ... (-1487144425) Phil 0 : mmm ... that's good ... (-1487143525) Canteen : one chicken coming down ... 1 left ... (-1487142570) Phil 0 : gotta eat ... (-1487141682) Phil 3 : mmm ... that's good ... (-1487140672) Canteen : one chicken coming down ... 0 left ... (-1487139665) Phil 4 : mmm ... that's good ... (-1485140597) Chef : 4 chickens, ready-to-go ... (-1485137917) Canteen : ouch ... make room ... this dish is very hot ... (-1484140618) Phil 2 : gotta eat ... (-1484120637) Phil 3 : gotta eat ... (-1484119711) Phil 4 : gotta eat ... (-1482130531) Canteen : more chickens ... 4 now available ... (-1482127865) Chef : cooking ... (-1482127420) Canteen : one chicken coming down ... 3 left ... (-1482126721) Phil 1 : mmm ... that's good ... (-1482126302) Canteen : one chicken coming down ... 2 left ... (-1482125798) Phil 0 : mmm ... that's good ... (-1482125386) Canteen : one chicken coming down ... 1 left ... (-1482124928) Phil 0 : gotta eat ... (-1482124527) Phil 2 : mmm ... that's good ... (-1482124118) Canteen : one chicken coming down ... 0 left ... (-1482123600) Phil 3 : mmm ... that's good ... (-1480120622) Chef : 4 chickens, ready-to-go ... (-1480118006) Canteen : ouch ... make room ... this dish is very hot ... (-1479120670) Phil 1 : gotta eat ... (-1479118078) Phil 2 : gotta eat ... (-1479117620) Phil 3 : gotta eat ... (-1477110775) Canteen : more chickens ... 4 now available ... (-1477108056) Chef : cooking ... (-1477107607) Canteen : one chicken coming down ... 3 left ... (-1477106980) Phil 4 : mmm ... that's good ... (-1477106558) Canteen : one chicken coming down ... 2 left ... (-1477104370) Phil 0 : mmm ... that's good ... (-1477103466) Canteen : one chicken coming down ... 1 left ... (-1477102500) Phil 0 : gotta eat ... (-1477101620) Phil 1 : mmm ... that's good ... (-1477100711) Canteen : one chicken coming down ... 0 left ... (-1477100182) Phil 2 : mmm ... that's good ... (-1475100040) Chef : 4 chickens, ready-to-go ... (-1475097376) Canteen : ouch ... make room ... this dish is very hot ... (-1474100703) Phil 4 : gotta eat ... (-1474080689) Phil 1 : gotta eat ... (-1474079761) Phil 2 : gotta eat ... (-1472090821) Canteen : more chickens ... 4 now available ... (-1472086727) Chef : cooking ... (-1472086256) Canteen : one chicken coming down ... 3 left ... (-1472085625) Phil 3 : mmm ... that's good ... (-1472085209) Canteen : one chicken coming down ... 2 left ... (-1472084702) Phil 0 : mmm ... that's good ... (-1472084289) Canteen : one chicken coming down ... 1 left ... (-1472083830) Phil 0 : gotta eat ... (-1472083421) Phil 4 : mmm ... that's good ... (-1472083012) Canteen : one chicken coming down ... 0 left ... (-1472082496) Phil 1 : mmm ... that's good ... (-1470080752) Chef : 4 chickens, ready-to-go ... (-1470078078) Canteen : ouch ... make room ... this dish is very hot ... (-1469080704) Phil 3 : gotta eat ... (-1469078099) Phil 4 : gotta eat ... (-1469077641) Phil 1 : gotta eat ... (-1467070834) Canteen : more chickens ... 4 now available ... (-1467068115) Chef : cooking ... (-1467067663) Canteen : one chicken coming down ... 3 left ... (-1467067032) Phil 2 : mmm ... that's good ... (-1467066610) Canteen : one chicken coming down ... 2 left ... (-1467066102) Phil 0 : mmm ... that's good ... (-1467065691) Canteen : one chicken coming down ... 1 left ... (-1467065231) Phil 0 : gotta eat ... (-1467064824) Phil 3 : mmm ... that's good ... (-1467064413) Canteen : one chicken coming down ... 0 left ... (-1467063895) Phil 4 : mmm ... that's good ... (-1465060790) Chef : 4 chickens, ready-to-go ... (-1465058121) Canteen : ouch ... make room ... this dish is very hot ... (-1464060546) Phil 2 : gotta eat ... (-1464057964) Phil 3 : gotta eat ... (-1464057507) Phil 4 : gotta eat ... (-1462050881) Canteen : more chickens ... 4 now available ... (-1462048174) Chef : cooking ... mint.ukc.ac.uk% ^D script done on Wed Oct 2 12:32:56 1996