Re: Conflicting Priorities in occam

[tjoccam@xxxxxxxxxxxxx (Lawrence Dickson)]

All,
   I don't understand all the formal semantics here, but I think perhaps
a different point of view may offer some light.
   The PRI PAR, as I always used it with Transputers, modeled interrupts
versus normal instructions (with no interrupting of interrupts allowed).
It amounts to two different instruction streams, one having priority over
the other on a uniprocessor with asynchronous hardware interrupts.
   The PRI ALT simply determined the ordering of the disables once the
ALT came ready. There was always a PRI ALT even in a standard ALT (the
disables were in SOME order even if only the compiler knew). It was
certainly not true that there was a PRI PAR in a standard PAR. The PRI
ALT was more like the ordering of the initialization of each branch of
the PAR - a far "weaker" influence than a PRI PAR which practically
broke the processor into two processors.
   In my version of occam for the 8086, I intend (I haven't gotten to it
yet) to treat all PRI PAR code as interrupt code - normally activated by
hardware events such as traditionally generate interrupts.

>Subject: Conflicting Priorities in occam
>To: occam-com@xxxxxxxxx
>Date: Sat, 27 Feb 1999 00:36:58 +0000 (GMT)
>From: Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
>
>I was under the impression---for no very good reason, I now realize---that
>conflicting priorities cannot arise in occam. But playing with CSSP led me
>to construct this example: I don't know how I could have missed it. :-(
>{Another triumph for formal methods: drawing attention to the blindingly
>obvious....}
>
>Consider:
>PAR
>  PRI PAR
>    b ! 2
>    a ! 1
>  PRI ALT
>    a ? x                             (I corrected the Ps and Qs
>      Q                                here - Larry)
>    b ? y
>      P
>
>My intuition is that implementations will communicate 2 on b and then execute
>P. But that intuition is strongly informed by a lack of symmetry between
>input and output. And that lack of symmetry is not really captured by CSP
>or even CSPP.
>
>....
>
>Subject: Conflicting Priorities in occam
>To: occam-com@xxxxxxxxx
>Date: Sat, 27 Feb 1999 09:18:32 +0000 (GMT)
>From: Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
>
>Is occam defined?
>~~~~~~~~~~~~~~~~~
>"Lower priority processes may only continue when all higher priority processes
>\emph{are unable to}."
>PRI PAR: from occam 2 Reference Manual, page 71. My \emph.
>
>Questions.
>~~~~~~~~~
>1) Am I right? Is occam undefined here? AFAICS, the question is not left
>   open -- unspecified -- but ambiguously "defined" by the reference manual.
>   [Probably because CSPP hadn't been invented? :-) ]
>
>2) Should we define occam? And if so, should it be specified in CSPP?
>
>3) What should the definition be? If we go for the hard semantics which seems
>   to me to be the *right* answer, does that make a software implementation
>   on a sequential processor too heavy? Particulary as efficiency in this
>   area is likely to be critical.
>
>4) Is the answer a usage rule: we just ban conflicting priority? Then the
>   implementation can be simpler. Could such a usage rule be automatically
>   checked? Statically? Would that ban any useful programs?
>
>5) What do KRoK, SPOC et al do?
>
>6) Does this arise in Java?
>
>7) Is there any coffee ready?
>
>Adrian

The problem goes away if you treat the ALT as a select or server
mechanism - i.e. it fires when someone communicates and is a slave of
external conditions - that's why ALTs are ? and not !, because a
transmission ACTUALLY TAKES PLACE to make a hardware ALT fire, even
though the received byte may be hidden in the local hardware till
someone picks it up.

>
>From: P.H.Welch@xxxxxxxxx
>Date: Sun, 28 Feb 1999 19:15:28 GMT
>To: adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx, occam-com@xxxxxxxxx
>Subject: Re: Conflicting Priorities in occam
>
>OK - the output guards aren't kosher occam, but semantically it makes
>sense.  By semantically, I mean formally semantically!
>
>In which case, your original example transforms to:
>
>  PAR
>    PRI ALT
>      b ! 2
>        a ! 1
>      a ! 1
>        b ! 2
>    PRI ALT
>      a ? x
>        SKIP
>      b ? y
>        SKIP
>
>and ... we are back to your original dilemma.  The above code certainly
>requires semantic sorting out into "hard"-PAR (==> deadlock) or "soft"-PAR
>(==> non-deterministic choice between either communication).
>
>....
>
>Cheers,
>
>Peter.
>
>Subject: Re: Conflicting Priorities in occam
>To: adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Adrian Lawrence)
>Date: Mon, 1 Mar 1999 15:21:52 +0000 (GMT)
>From: "B.M. Cook" <b.m.cook@xxxxxxxxxxxxxx>
>
>Adrian,
>
>> >   -- This compiles in SPoC, communicates over b fine,
>> >   -- sends on a, but there is no receiver and the queue
>> >   -- is empty, so SPoC issues a critical error.
>
>Referring to the program that does not have a loop around the ALT.  Two
>values are sent but the ALT runs only once and receives one of them.

The above problem is why there aren't both output and input ALTs. Any
output ALT would have to receive a signal from the other side before it
fired - a practical problem. Otherwise you certainly do get deadlock.

>
>Date: Mon, 01 Mar 1999 17:40:11 +0000
>From: Rick Beton <rdb@xxxxxxxxxx>
>Organization: Roke Manor Research Ltd
>To: occam-com@xxxxxxxxx
>Subject: Re: Conflicting Priorities in occam
>
>"B.M. Cook" wrote:
>
>> > Continuing on this theme for a moment: processes versus events:
>>
>> 1) PRI ALT is a way of declaring an "urgent" channel
>>
>> 2) Except that if the process receiving the message is low priority, then
>>   "urgent" may take a long time to be received.
>>
>
>Here's my tuppence-worth... [Forgive me for repeating what you no doubt know
>already.]
>
>It occurred to me that there is a qualitative difference between processes on the
>late transputer. Lo-pri processes timesliced in a round-robin manner. Hi-pri
>processes did not timeslice between each other, but did pre-empt the current lo-pri
>process, if any. The only way to define that a process was lo-pri or hi-pri was to
>use a PRI PAR; PRI ALT did not do this.
>
>It's interesting to wonder whether PRI PAR is actually redundant, possibly even
>harmful, in the light of the recent conversation! If so, how would a latter-day
>transputer support process priority levels, based on message priority levels?
>
>Just thinking aloud...
>Rick

The PRI PAR isn't redundant! I need to be able to do interrupt code - and
PRI PAR is a beautiful formalization of interrupt code - so much better
than "256 interrupt priorities" and all that junk that the RTOS's are
always talking about. But PRI PAR is naturally a master construct and
ALT is a slave construct from the information passing point of view.

Here's another possible red herring: what about the fact that PRI ALT is
dependent on interrupt latency, i.e. up to a certain time interval, the
priority communication wins even though it comes in after the lesser
priority one, but beyond a certain (short) interval, it misses the boat
during the disables and loses?

Larry Dickson