Re: Conflicting Priorities in occam

[<P.H.Welch@xxxxxxxxx>]

Priority Inversion:
===================

Barry (I think) raised the priority inversion problem.  I think this is
also a red-herring -- i.e. not really a problem for a well-designed system.

If a high-priority process tries to synchronise (communicate) with a lower
priority process, it has to wait until that lower process gets to the point
at which it's ready to proceed with the synchronisation.  Effectively,
the high-priority process is demoted to the level of the lower priority,
as that lower priority process fights with the scheduler to be scheduled
and reach that synchronisation point.

This is `priority inversion' and it's just what we want!  The last thing
I want is for my ginormous matrix mutiplication process -- which I have
deliberately set at low priority -- to have its priority raised simply
because some high-priority process attempts contact!!  If that happened,
the matrix mutiplication will stop being preemptable (or pseudo-preemptable)
by the high priority processes managing all the time-critical stuff.

The standard occam pattern would be to manage the time-critical stuff
with high-priority processes and also set (equally) high-priority processes
to interface between the time-critical ones and the low-priority background
computations.  These high-priority interfaces ALT between servicing (and
perhaps discarding) information from the time-critical ones and the
low-priority processes delivering results and/or wanting fresh data.
Those high-priority interfaces guarantee time-critical service to
the time-critical processes and prompt retrieval/delivery of information
from/to the background processes.  We don't want those high-priority interface
processes raising the priority of their low-priority clients -that would be
plain wrong!

This is in a paper from OUG-7 back in 1987 (Grenoble - what a conference
- we shall not see its like again!).  I don't see that the needs of real-time
have changed to invalidate this argument, but someone may know otherwise?
The Twente designs for rate-monotonic (i.e. PRI PAR with multiple levels)
have processes at lots of priority levels all commincating and no priority
inversion worries ... indeed, they would not work if this problem were ever
`fixed'.

So, I feel quite comfortable with the notion of priorities being attached
to processes -- rather than attaching priority to messages.


Prioritised messaging:
======================

If we want to have a prioritised messaging scheme between two (presumably
remote) processes, there is an easy way to model it.

Suppose A needs to communcate to B through some buffered medium -- the
following makes no sense for an unbuffered one.  Messages are flagged
with a range of priority levels and sent off.  What is supposed to
happen is that messages with higher priority should be received before
messages of lower priority -- assuming those lower priority messages
are still in transit when the higher priority ones are sent.

Easy!  Connect A and B with an array of channels c -- one element for each
message priority level.  Stick an appropriately large buffer process
into each channel:


        __________                                   __________
        |        |    c[0]    __________     d[0]    |        |
        |        |------>-----| buffer |------->-----|        |
        |        |            ----------             |        |
        |        |                .                  |        |
        |        |                .                  |        |
        |   A    |                .                  |   B    |
        |        |                .                  |        |
        |        |                .                  |        |
        |        |   c[n-1]   __________    d[n-1]   |        |
        |        |------>-----| buffer |------->-----|        |
        |        |            ----------             |        |
        ----------                                   ----------

[If we weren't just modelling, these buffers would be present in the
distribution fabric connecting A and B, which are remote from each other.
Presumably, we would arrange for the channels carrying the higher priority
messages to be a bit faster (and have lower latency) than the others ...]

Now, when A wants to send a message, x, with priority p (assuming that p lies
in the specified range 0 through n-1), all it does is:

        c[p] ! x

When B decides to take another nessage from A, it simply PRI ALTs across its
input channels, d.

To avoid deadlock in the communication fabric, the buffers need to be
overwriting (or infinite!) ... but that would probably be the case in
practice.

So, the PRI ALT gives us prioritised messaging for free.  I don't think
we need another concept?

Note: in Java, with JCSP or CTJ, we could encapsulate the above mechanism
into a single PrioitisedChannel class with simple read and write methods.
The write method would take an extra parameter to indicate the priority
of the message.  The read method would have the usual parameter list and
silently do the PRI ALT on its internal channel array.  In JCSP, we can
configure the channels to have whatever buffering policy (including none
and infinite) we like.


Peter.