RE: ALTs on inputs and outputs

["Gerald Hilderink" <g.h.hilderink@xxxxxxxxxxxxx>]

John and Barry,

As I understood, the primary reason is that an efficient implementation for
an Occam ALT with input guards AND output guards was a real problem.
Furthermore, this was even harder to realize on silicon, i.e., on the
transputer. The secundary reason is that having input guards and output
guards at the same time can be VERY dangerous, as Barry mentioned, and Occam
must be a safe language!
Geraint Jones [1] and Bill Roscoe suggested a workaround that allows us to
eliminate output guards by using strictly input guards. Thus, eliminating
output guards seem to be a simple and safe solution.

In Java there is no way to detect 'meeting' conflicts between an input guard
and an output guard at compile-time. The programmer must be aware of this
situation and he/she must avoid this conflict at any time.

CTJ supports both input guards and output guards!

The symmetric implementations of the CTJ ALTs provide efficient input guards
and output guards. Thus, technically, having both output guards and input
guards is possible with very low overhead on modern processors.

In our paper, which will be presented at the CPA-2000, we explain new ALTs
with notion of priority. In this paper, we explain five major reasons for
having output guards when desired:
1. simplifying coding;
2. increasing performance;
3. adapting to priorities of client processes for better real-time behavior;
4. reducing or avoiding priority inversion problems;
5. more design freedom.

The workaround, as suggested by Geraint Jones [1] and Bill Roscoe [2], by
translating an ALT with output guards to an ALT with input guards
accomplishes safety, but calls for an extra channel with an extra protocol.
These extras make coding more complex and the extra channel communication
will slow-down the performance.
The new ALTs can adapt their choices dependent on the priority of the client
processes. This provides an efficient throughput of higher priority
(real-time) processes. This will not work efficiently with the above
mentioned workaround.
In case of a priority inversion situation, the extra channel communication
calls for an extra priority inversion problem resulting in a significant
performance penalty.
CSP allows input guards and output guards, and gives us some freedom in
design. After that, the CSP-checker notifies us of any failures, including
'meeting' conflicts. Similar, the compiler or design tool could notify us of
any failures in the code or design. The problem is that we don't have such a
Java compiler or Java design tool! Hmmm, we present another paper at the
CPA-2000 that introduces a prototype CSP design tool that can detect
'meeting' conclicts.

Gerald.


PS. join the CPA-2000 conference!
    http://wotug.ukc.ac.uk/cpa2000/

[1] Jones, G. (1987), On Guards, 7th Occam User Group & International
Workshop on Parallel Programming of Transputer based Machines, Grenoble,
LGI-IMAG.

[2] Roscoe, A.W. (1987), Routing messages through networks: an excercise in
deadlock avoidance, 7th Occam User Group & International Workshop on
Parallel Programming of Transputer based Machines, Grenoble, LGI-IMAG.

> -----Original Message-----
> From: B.M. Cook [mailto:b.m.cook@xxxxxxxxxxxxxx]
> Sent: Tuesday, August 15, 2000 4:01 PM
> To: Campbell, John
> Cc: java-threads@xxxxxxxxx
> Subject: Re: ALTs on inputs and outputs
>
>
> John,
>
> > I understand that at one time the merits of ALTs on
> > output channels as well as input channels in Occam
> > was debated.  CSP is even handed on the issue,
> > can anyone explain why Occam isn't? -jc
>
> A matter of ease of implementation.
>
> There is no problem with an ALT containing an output sending to a simple
> input, when the ALT commits to that channel there is something at
> the other
> end to receive the communication.
>
> BUT when a channel appears as an output in one ALT and an input in another
> ALT (instant deadlock if they are the same ALT!) there is a problem of
> commitment.  The outputting ALT may have chosen that channel while the
> inputting ALT has committed to another channel and we get into all sorts
> of problems. We can do this only if we are able to withdraw from a
> commitment - and that is possible, but a slow and possibly messy business.
>
> HOWEVER, having said that I find I have a need for output guards in an ALT
> driving input guards in another ALT for a network routing switch design.
> So, I WILL be providing them in my occam to hardware compiler. It would be
> nice if JCSP could provide them too :-)
>
> 	   Barry.
> --
> /-----------------------------------------------------------------
> -----------\
> | Barry M Cook, BSc, PhD, CEng, MBCS
>            |
> | Senior Lecturer,                           Department of
> Computer Science, |
> | Chartered Information Systems Engineer.    Keele University,
>            |
> |                                            Keele,
>            |
> | Phone: +44 1782 583411                     Staffordshire,
>            |
> | FAX:   +44 1782 713082                     ST5 5BG,
>            |
> | email: barry@xxxxxxxxxxxxxx                UK.
>            |
> \-----------------------------------------------------------------
> -----------/