Re: Conflicting Priorities in occam

[Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

Lawrence Dickson writes:
> 
> 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.

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.

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.

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.

> 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