new sync primitives

[phw <P.H.Welch@xxxxxxxxx>]

Dear All,

The KRoC 0.8beta release included four new primitives: SEMAPHOREs, RESOURCEs,
EVENTs and BUCKETs.  An example program for each was included but, otherwise,
no documentation.

Enclosed is an extract from the start of this documentation -- it grew too
large (about 100 Kbytes of folded plain text) to email blindly.  It's actually
grown into a draft paper rather than straightforward documentation, but I'm
not going to prune it back again!  To get a copy you have to fetch it from
the Internet Parallel Computing Archive (or ftp) at page:

  <URL:http://www.hensa.ac.uk/parallel/occam/projects/occam-for-all/hlps/>
  <URL:ftp://unix.hensa.ac.uk/pub/parallel/occam/projects/occam-for-all/hlps/>

Please have a go with these new ways of synchronising processes.  They shortcut
lots of tricky code that we have to write if all we have for synchronisation
are channels, plus heaps of execution time.  Please let us know how you get
on with them!

Cheers,

Peter Welch.

PS.  The document is plain text, but `folded'.  It is quite readable as
     plain text; but, for viewing on-line, it was designed for browsing
     with a `folding' editor such as Origami or F.

PPS. KRoC 0.8 and 0.81 beta (and all earlier releases) contain a bug that
     prevents EVENTs and BUCKETs from working reliably.  This is because
     their implementation uses a transputer instruction (SAVEL) never
     previously exercised -- you can't generate it from ordinary occam!
     This will be fixed in the KRoC 0.9 beta release.  Meanwhile, the
     full documentation explains how to work around it for the current
     (and earlier) releases.

(cut here)
-------------------------------------------------------------------------------

--{{{  Title

Higher Levels of Process Synchronisation in occam

--}}}

--{{{  Authors

P.H.Welch and D.C.Wood
Computing Laboratory
The University
Canterbury
KENT -- CT2 7NF
ENGLAND

{P.H.Welch, D.C.Wood}@ukc.ac.uk

Copyright (1996) P.H.Welch and D.C.Wood.

--}}}

--{{{  Introduction

This document details the extra synchronisation primitives introduced in the
KRoC 0.8beta release of occam for SPARC (SunOS/Solaris) and Alpha (OSF/1) UNIX
workstations [1, 2].

The new primitives are experimental -- we would like feedback on their use.
They are designed to support higher-level mechanisms of SHARING between
parallel processes that give us greater powers of expression.  They will
also let greater levels of concurrency be safely exploited from future
parallel architectures, such as those providing (virtual) shared-memory.
They demonstrate that occam is neutral in any debate between the merits of
message-passing versus shared-memory parallelism, enabling applications to
take advantage of whichever paradigm (or mixture of paradigms) is the most
appropriate.

The new primitives could be (but are not) implemented in terms of traditional
channels, but only at the expense of increased complexity and computational
overhead.  The primitives are immediately useful even for uni-processors --
for example, the cost of a `fair' ALT can be reduced from O(n) to O(1).
In fact, all the operations associated with new primitives have constant
space and time complexities; and the constants are very low.

Direct use of these primitives enables the user to misuse them.  They must be
used in the ways prescribed below else their semantics become unpredictable.
No tool is provided to check correct usage at this level.

The intention is to bind those primitives found to be useful into higher
level versions of occam.  Some of the primitives (e.g. SEMAPHOREs) may never
themselves be made visible in the language, but may be used to implement
bindings of higher-level paradigms (such as SHARED channels and BLACKBOARDs).
The compiler will perform the relevant usage checking on all new language
bindings, closing the security loopholes opened by raw use of the primitives.

--}}}

--{{{  Channels are not enough ...

An occam channel is a primitive combining communication and synchronisation.
As a synchronisation primitive, it applies to two processes at a time.  Some
applications require many processes to synchronise before any can continue --
for example, the barrier synchronisations used by common shared-memory parallel
algorithms.

Multi-way synchronisation is a fundamental idea in CSP, but is not implemented
in occam.  The computational arrangements for allowing any of the synchronising
processes to back off (which CSP allows) is even more costly than allowing
both parties to back off during channel synchronisation.  However, just as
allowing only the receiver to back off an offer to communicate enabled an
efficient channel implementation in occam, a similarly drastic rule -- allowing
no parties to back off a multi-way synchronisation -- makes possible an
efficient implementation of the (CSP) EVENT.  Does such a restriction still
leave a useful primitive?  Just as for occam channels, the answer seems to be
yes, but we would like to hear from potential users.

Another way of looking at channels is that they provide a peg on which to hang
a blocked process.  If we have lots of processes we wish to suspend for some
common reason (e.g. they are waiting on a common event or for some shared
resource, access to which is restricted by some rules), we either have to have
lots of channels on which to hang them (and, later, organise their release)
or we put them on a timer queue.  Neither of these may be convenient or
computationally light.

What are needed are different kinds of peg on which we may hang arbitrary
numbers of processes ... plus the ability to retrieve them one at a time
(SEMAPHOREs and RESOURCEs) ... or all at once (EVENTs and BUCKETs) ... or
some other way ...

--}}}

--{{{  Abstract Data Types

Each new primitive is presented as an Abstract Data Type.  Each is implemented
as an occam2.1 DATA TYPE, together with a set of operations defined through
INLINEd occam2.1 PROCs and FUNCTIONs.  Full source code is provided for each
primitive in a separate #INCLUDE file.

Although users have visibility of the data structures used for each primitive,
advantage must *not* be taken of this visibility.  Components of the data
structures must *not* be accessed directly by user programs.  Instances of
the primitives may *only* be operated on by calling the PROCs and FUNCTIONs
provided.

--}}}

--{{{  SEMAPHOREs

...  SEMAPHORE Abstract Data Type (documentation)
...  Normal pattern of use
...  occam3 SHARED channels (via SEMAPHOREs)
...  Dining Philosophers (via SEMAPHOREs)
...  Instrumenting parallel systems (via SEMAPHOREs)

--}}}

--{{{  RESOURCEs

...  RESOURCEs and SHARED channels
...  RESOURCE Abstract Data Type (documentation)
...  Implementation of CLAIM and GRANT
...  Example client-server application
...  Differences between this prototype and T9000 RESOURCEs
...  RESOURCEs versus SEMAPHOREs for SHARED channels

--}}}

--{{{  EVENTs

...  Barrier synchronisation
...  EVENT Abstract Data Type (documentation)
...  Implementation of proposed barriers
...  A simple example
...  A shared accumulator (and implicitly parallel recursive lazy functional occam)

--}}}

--{{{  BUCKETs

...  Bucket synchronisation
...  BUCKET Abstract Data Type (documentation)
...  A simple example
...  Discrete event simulation

--}}}

--{{{  Implementation overview and platform independence

...  SEMAPHOREs
...  RESOURCEs
...  EVENTs
...  BUCKETs

...  Transputer restrictions

--}}}

--{{{  Postscript

...  Summary
...  Performance and optimisation
...  Virtual transputers
...  Microcode, methods and objects
...  Java threads and occam
...  If only ...

--}}}