Dynamic Priority

[Adrian Lawrence <adrian.lawrence@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx>]

Dynamic Priority:
~~~~~~~~~~~~~~~~~
I suggest that we extend PRI PAR to permit an optional PRIORITY
component:-

PRI PAR
  PRIORITY
    c ? priority
  P0
  P1
  ...
  Pn

If PRIORITY is omitted or if it is present and no communication
has occurred on the associated channel c, then the construct is the existing
PRI PAR.

Otherwise, a communication on c (which has the highest precedence)
can change the relative priority in the fixed list of processes
[P1,P2,..,Pn]. The value communicated must be a bijection: for example

0 |--> 1
1 |--> 0
2 |--> 2    just promotes P1 above P0 and leaves the rest. 
  ...
i |--> i
  ...

One way is to send the set of integers [1,0,2,...,N]. Since the channel
c might be external, and the source may have any architecture and perhaps
even built by a different compiler, we need to permit portable
data types, so a table of any INT type seems the right choice. Perhaps BYTES
may also be allowed since applications will frequently be very sensitive
to efficiency. And even BIT streams in the future :-). 

I suppose that the type of c could be either [N]INTw, or a counted array,
so that the example above could avoid the redundancy and send just 
2::[1,0].

I am not quite sure what the value of priority should mean after the first
communication. Does the next bijection refer to the original syntactical
order? Or to the current order? The first requires an implementation to keep
some record of the original order, but makes it easy to "reset" to original
if required. The second seems simpler to implement. 

As I have noted, the small extension seems to be in the spirit of occam:
I can define a precise semantics in CSPP. It is compatible with static memory
allocation. And it gives a simple and efficient way to implement standard
real time algorithms like RMPA (Rate Monotonic Priority Assignment).
I realize that you poor compiler implementers have to engineer the priority
queues. 

---------------------------------------------------------------------------
Comments please:- 

Is this needed? 
Is it a lightweight extension of the existing language? 
Does it lift an arbitrary restriction?
What should the protocol on c be?
What does a new mapping mean after the first change: is it relative to the
original priority or the current order?
Does it work: can we really implement useful algorithms this way, or have
I overlooked something?

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