Priority revisited: a new primitive

[A E Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

In occam and HCSP we have two primitives:
  PRI PAR
and
  PRI ALT
The purpose of this note is to suggest the addition of a 3rd primitive:
  PAR PRI  .

{Eh, is this too much like a maze of little twisty passages?}

As the occam community has observed, neither PRI PAR nor PRI ALT gives a
simple way to assign an enduring priority to particular events. PRI ALT
gives priority to events rather than processes, but only to initial
events. PRI PAR gives enduring priority to the set of events performed
by a process, but a process almost always must perform events of lower
priority as well. This side effect of raising the priority of less
important events leads to pathologies like priority inversion.

A new primitive: PAR PRI
~~~~~~~~~~~~~~~~~~~~~~~~

I therefore propose a very simple new form of parallel constructor

  PAR PRI [S] .

S is the set of events with raised priority. I am not sure whether we
need to specify that S be a subset of the alphabets of the component
processes, although it would be pointless to include extra events in S.

Thus 

  PAR PRI [{a}]
    P1
    P2

is a process which will always perform the event a if it is available:
that is when it is offered by the environment and can be accepted by
P1||P2.
If a is a common event jointly executed by P1 and P2 and P1 and P2 are
both capable of performing a, then it will be performed in preference to
any other events. The more interesting case is when P1 or P2 or both can
perform a independently of its partner (interleaving) : once again, a is
performed in preference to other events. 

  PAR PRI [{a,b}]
    P1
    P2
    P3

is similarly a process that gives priority to the events a and b. If
both are offered and can be accepted, the choice between a and b is non
deterministic.

  PAR PRI [{a}]
    PAR PRI [{b}]
      P1
      P2

is a process that will always perform a if it is offered and can be
accepted; otherwise it performs b if that is available; and performs
other available events otherwise.

It seems worthwhile to have a compact way of writing more complicated
priorities, so we have

 PAR PRI [S1,S2,...,Sn]

where S1,S2,...,Sn are each sets of events. And events in Si take
priority over events in Sj when i>j. In effect, we have a partial order
relation with

  xi > xj  when i >j for xi \in Si and xj \in Sj.

It is easy to give an HCSP (and THCSP) denotational semantics for these
constructors. We have a clean easily understood compositional element.

This seems such an obvious and simple primitive: why hasn't it been
suggested before? Probably because a software implementation on a
conventional sequential CPU will have a large overhead, although of
course conventional interrupt hardware is essentially an implementation
of PAR PRI for certain special external events. 

In occam, are the sets of events just channels?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So far, I have used an abstract occam-like pseudo syntax. At present
occam does not include an explicit syntax for sets. How do we write S =
{a,b}? Perhaps exactly in that form: {a,b}?

However, channels are simply sets of events. So an occam binding could
just use channels as in

PAR PRI [{c,d}] .

Then any events on channels c and d have priority. That applies whether
the communications are outputs or inputs or both when the communicating
partners are in the scope of the PAR PRI.


What about assignment? In HCSP. assignments can be regarded as special
sorts of event. Is there a need to allow assignments in the list of
prioritized events? If so, what syntax would be sensible?

Efficiency
~~~~~~~~~~

Hardware compilation of PAR PRI is elementary and efficient. It can be
as efficient as an ordinary PAR: indeed a typical compilation of PAR
will actually be a PAR PRI!

Software implementations on conventional CPUs however may pose greater
challenges. PRI PAR is, of course, easily handled with a set of run time
queues, and one suspects that this is the real reason for its presence
in the language. Would one ever want PRI PAR if one could have PAR PRI
at no extra cost?  PAR PRI needs to examine the potential high priority
events after every action, and possibly context switch. As noted above,
this is exactly what the interrupt machinery of a conventional CPU does;
the interrupt status is sampled at each machine cycle. Likewise various
other mechanisms. And we all know that typical CPUs are abysmal at such
context switching in these and other circumstances. 

I haven't given much thought to this software implementation question,
but I suspect that the spectacular strategies used in KRoC and SPOC
aren't going to help much here. But over to Kent and SOTON here... If
this is right, it looks as if one should use PAR PRI sparingly when the
target is a conventional CPU. 

But if this is the right primitive, then it is conventional CPU's that
need to be "adjusted" rather than the language :-)

Of course, I still agree with a comment made by Barry at Keele: we
probably need a higher level of abstraction in which we declare what
timeliness properties we require rather than reason at the lower level
of priority. But as I don't know how to do that yet, and because an
implementation of such a specification may well require it, I offer PAR
PRI for your consideration.

Comments?


Adrian
-- 
Dr A E Lawrence (from home)