Re: Conflicting Priorities in occam

[tjoccam@xxxxxxxxxxxxx (Lawrence Dickson)]

All,
   Wait, I wasn't meaning to change the subject or dismiss the importance
of formal methods - but every formalism has to be critiqued by its
implementations. There is cross-fertilization here in that you learn
from the absolute, ruthless, necessity of getting something to work
and be useful.
   The Transputer was successfully gotten to work and was a tremendous
technical success. This fact tends to be forgotten now that it has
proved to be a marketing failure. That was mostly due IMHO to the T9000
fiasco which, mind you, flopped because the connection to pure occam
was BROKEN by trying to design in C-driven bloat like protected mode.
Otherwise we'd probably have 500 MHz transputers with 32 links...
   Anyway, forget the dreaming, the technical success of the
transputer means every aspect of its design needs to be pondered.
Otherwise you may throw out the baby with the bathwater.

>Subject: Re: Conflicting Priorities in occam
>To: tjoccam@xxxxxxxxxxxxx (Lawrence Dickson)
>Date: Mon, 1 Mar 1999 23:36:19 +0000 (GMT)
>Cc: occam-com@xxxxxxxxx,
>        adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx (Adrian Lawrence)
>From: Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
> ....
>
>occam was designed as an implementation of CSP. And almost all of the
>features that we so cherish derive from that. The underlying mathematical
>theory gives denotational, algebraic and operational semantics. To a subset
>of occam. Areas that were not covered were assignments and related aspects
>of state. And priority. Some of the assignment stuff is captured by
>algebraic semantics like
>
>(x := a)    = (c ! a  || c ? x) \{c}     -- roughly
>
>So we absolutely must require that implementations conform to these semantics.
>But the trouble is (was) that CSP did not capture priority, so there was no
>proper treatment of this area. Now that we do have such a formal theory in
>CSPP, it is not surprising that it throws into sharp focus questions that we
>have not really noticed before. It is a great tribute to occam that so far
>we have only had this one issue. And the natural reading of the Manual is
>for soft priority. Also not surprising considering that the focus in those
>days was on software. Although Inmos people talked of using occam for hardware
>design from the earliest days: I remember reading an article by Steven Brain.
>I think David also covered it in some of his early papers. And they were
>using it in earnest in the transputer hardware design, although I think
>primarily in the firmware.
>
>It is not clear to me that we should be too influenced by what current
>implementations do. Except, of course, we don't want to invalidate anything
>unless it is clearly wrong. And we must learn from experience and question
>whether we have the right primitives, or perhaps, very cautiously add a
>very small number of new ones.

Exactly.

>
>It does seem to be generally agreed that real time multiple priorities are
>tricky. I am not clear how far this is influenced by the severe limitations
>of the transputer implementation. You could not pre-empt a high priority
>process: that is far from the spirit of occam. And there were only two
>levels of priority. If you had 100 priority levels (or better, bounded only
>by dynamic system resources) and all context switching was permitted
>subject to the prioritized semantics, would there still be a problem?
>I wonder how far the difficulties were really implementation restrictions,
>or were they language problems. *I* don't really know that answer to that.
>I hope that these discussions will clear the fog.

The RTOSs that use multiple priority levels run into endless problems,
and gain very little. The fact of the matter is that if you can't do
interrupts Transputer-style - just round robin them - because of
excessive interrupt density, then it is very unlikely that multiple
priorities can save you. This is exactly analogous to the problem with
dynamic memory allocation. If you are so short on memory that a static
memory allocation a la occam doesn't suffice, then very shortly thereafter
you choke on problems with dynamic memory.

I think the real problem is one of terminology. What the transputer
implemented wasn't really priority. High priority transputer occam is
different IN KIND from low priority. It was interrupts.

>
>I remember some sessions with Roger Shepherd at a WoTUG meeting [Aberdeen?]
>in the days of the H1=T9000 design. I was only on the periphery, but I think
>Andy was involved. As I understood it, there was much feedback from real time
>people asking for special facilities on the T9 for priority|real time
>scheduling  control and such. Was there any discussion then about language
>issues? As far as I know, it was primarily about hardware facilities. How were
>these to be controlled from occam. Any one know about 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.
>
>I am with you here. Fortunately we have to keep PRI PAR just for legacy code.
>Even if we come up with some wonderful new primitive.
>
>> But PRI PAR is naturally a master construct and
>> ALT is a slave construct from the information passing point of view.
>
>Ah, well, no. Even from an information passing viewpoint. Even in occam when
>we restrict (PRI) ALT to input guards: there is no such restriction in
>CSP|CSPP which are of wider application than just occam. Even in occam,
>we pass information from the receiver to the transmitter: "ready|not ready".
>And maybe, in hard semantics, a priority or set of offers and acceptances.
>The MASTER-SLAVE aspect is a quirk of occam: it is absent in CSP and CSPP.

But somebody has to go first in any real communication. Output ALTs talking
to input ALTs can always lead to deadlock. You can have output ALTs if you
are sure the other side has committed inputs - then the inputting side is
the master, as you say, by using the ready/not ready signal (the ack).

Another very important issue: the fact that all these entities, like
channels, can be presented as formal parameters - they can even be
parameters of independent program calls which allows real hot-swapping.
I don't know if that was intended, but it sure is a very valuable side
effect which we don't want to lose! If we start having to worry about
what goes on inside a module (i.e. is this channel used in ALTs or can
we rely on its inputs always being unconditional) that will at least
complicate things tremendously.

>
>> 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?
>
>I mentioned in another note that we really need timed versions of CSP(P)
>to deal with such matters. But these are implementation details.
>The first thing is to tie done the semantics at the level of abstraction of
>CSP(P).
>
>Thanks for the response. Hope this didn't sound dismissive! But I am worried
>that we don't get into hacking and making empirical changes driven by
>particular implementation problems. That is how C got into the quagmire.
>But I know you had no such intention!
>
>Adrian
>--
>A E Lawrence, MA., DPhil.   adrian.lawrence@xxxxxxxxxxxxxx
>MicroProcessor Unit, 13, Banbury Road, Oxford. OX2 6NN. UK.
>Voice: (+44)-1865-273274,  Fax: (+44)-1865-273275

You present it as an either/or. It's not! Otherwise we would still be
doing epicycles, ignoring Copernicus's empirical hack! You have to cross
fertilize your theory with news from the world of practice. You also have
to avoid doing it BADLY as C (and worse yet, OOP) have done.

Example (I've already mentioned this to Peter Welch): multiple programs
running on a non-occam operating system, but communicating with each other
in a way that makes them (considered as a whole) a valid occam program
complex? That is a fun abstract problem with uses in voice/reply
computing and embedded (but reconfigurable) systems like robotics that
C and OOP can't match.

>Date: Tue, 2 Mar 1999 09:29:54 +0000 (GMT)
>From: Denis A Nicole <dan@xxxxxxxxxxxxxxx>
>To: occam-com@xxxxxxxxx
>Subject: Re: Priorities in SPoC
> ....
>Anyway, the real reason for the message was to discuss SPoC's
>implementation of PRI.  The SPoC scheduler essentially uses coroutines; it
>is not preemptive.  When it gains control, which includes every
>communication and PAR, it uses two queues, high and low priority, as in
>the transputer. The high priority queue is always run if possible.
>Without external communication, a high priority process can _only_ become
>ready at a scheduling point, so this model ensures that there is never a
>high priority process waiting on a low priority one.  The scheduler has no
>preemption, so this guarantee cannot be provided for _external_
>communications triggering a high priority process.
>
>ALTs are all PRI ALTs of the transputer sort, complete with the famous
>three-way PRI ALT bug (feature).  SPoC goes to great lengths to ensure
>transputer compatibility...
>
>Denis A Nicole                      WWW:   http://www.hpcc.ecs.soton.ac.uk/~dan
>High Performance Computing Centre   Email: dan@xxxxxxxxxxxxxxx
>University of Southampton           Phone: +44 1703 592703
>UK.                                 Fax:   +44 1703 593903

This is one example of drifting away from the Transputer's successful
model, it seems. If

 > this guarantee [that a high priority process never waits on a low
 > priority one] cannot be provided for _external_
 > communications triggering a high priority process

then that destroys the main utility of high priority - which is
interrupt response to asynchronous events. The Transputer would have
been a complete flop without it.

We've got to stop treating asynchronous IO as an unwanted stepchild in
post-Transputer occam.

>Subject: Conflicting Priorities in occam
>To: occam-com@xxxxxxxxx
>Date: Tue, 2 Mar 1999 11:29:34 +0000 (GMT)
>From: Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>
>
>Here's another fish to throw in with the hares.
>
>An interrupt operator is sometimes defined in CSP.
>
>So P EEK(i) Q is a process that behaves as P unless the (interrupt) event
>i happens when process P is completely dumped, and the subsequent behaviour
>is that of Q.
>
>Maybe the occam would look like this?
>
>EEK
>  i ? x
>    Q
>  P
>
>Never used it myself. Not sure that I want it. Not very happy with throwing
>P away completely.

I can't blame you! When the Transputer-style high priority (call it by
another name maybe) works so much better... Surely someone can formalize
the round-robin interrupt structure without "throwing P away completely".

Larry Dickson