Re: Conflicting Priorities in occam

[<P.H.Welch@xxxxxxxxx>]

> Continuing this plot to fill Peter's mail box before he gets back tomorrow...

Humm ... you're going to regret this ...

First, I want to look again at the equivalence:

  PAR         =      ALT
    a ? x              a ? x
    b ? y                b ? y
                       b ? y
                         a ? x

This equivalence immediately falls out from the CSP definition of parallel,
which is in terms of its non-deterministic choice operator.  CSP-equivalence
reflects the inability of any environment to distinguish between the above
two fragments of code (and where that environment is blind to pragmatic
details like time).

>From a pragmatic (e.g. implementation) point of view, the PAR version permits
a parallel implementation, wheras the ALT one looks as though it ought to be
serial.  But that's just an impression, since a clever compiler would be
entitled to tranform the ALT into the PAR and implement it using parallel
hardware.

Now, consider the prioritised version:

  PRI PAR     =      PRI ALT
    a ? x              a ? x
    b ? y                b ? y
                       b ? y
                         a ? x

This time, the PRI ALT requires the imposition of determistic control in
choosing what to do first if its environment is offering both communications.

In our traditional software implementations of PRI PAR on a uniprocessor
(e.g. on the INMOS transputer), two processes are spawned for each
communication.  Only one can be done at a time.  If the envoronment is
offering both, both processes are runnable and the higher priority one
is scheduled first.  So, the trace of communications can only be exactly
the same as for the PRI ALT version - i.e. <a, b>.

But the transputer sported lots of internal parallelism - in particular,
it had links.  Suppose the `a' channel is a link and the `b' one is an
internal (soft) channel.  Good practice dictates that the PRI PAR version
(rather than just a PAR) should be used.  This PRI PAR strangely enforces
*serial* control over the ordering with which the two communications are
started.  The link engine is instructed to get on with receiving the data
and to place it into `x'.  Following that instruction, the `b' communication
can be scheduled.  We now see the reason for that `good practice': the `a'
communication can proceed concurrently with the `b' one ... and will do so
if the environment is offering both.

So, the PRI PAR exercises serial control on the start-up of the communications
and that allows the parallel hardware (link + processor) to operate them
in parallel -- which is effective but, on the surface, a little peculiar.
[Note that if we had written the components of the PRI PAR the other way
around, no parallelism would have been possible in these circumstances and
the soft `b' communication would have been performed in sequence before
the link `a' one.]

Of course, just because the `a' communication *starts* before the `b' one
and, then, runs concuurently with it ... that doesn't mean that the `a' one
will *finish* first.  If `x' and `y' were the same size (say 1 Kbyte),
I would put my money on the `b' -- software communications being faster
than link ones.  That appears to mean that the trace actually performed was
<b, a>, in defiance the ordering of the PRI PAR (remember the environment
was offering both communications)?  This seems quite reasonable to me.

Otherwise, we would require that PRI PAR should exercise (CSPP `hard'?)
control over these communication to ensure that, if the environment is
offering both, the trace performed is <a, b>?  That control is what you get
with the PRI ALT version of this code.  Except that PRI ALT implementations
(for instance for the transputer, KRoC and SPoC) exercise somewhat stronger
control, forcing the `a' communication in sequence before the `b' - i.e.
enforcing the <a, b> trace by preventing any parallelism.

I'm not sure that we should.  Putting in control to enforce an <a, b> for
the PRI PAR (when the environment offers both communications) denies the
implementaion of that PRI PAR by parallel (and independent) hardware.
Parallel things should be allowed to operate in parallel and that means
that they can terminate in any order -- regardless of priority (as the
above example of the link and internal communication shows).

Once components of a PRI PAR are running on parallel pieces of hardware,
their relative priorities are, I would have thought, irrelevant.  In the
above, the PRI PAR ensured the *serial* delivery of each component to its
own hardware engine.  Since the soft `b' communication hardware is responsible
for that delivery, parallel execution is ensured by delivering the `b'
communication second.

Adrian: in CSPP, are not the following equivalent?

  PRI PAR     ?=?      PAR
    a ? x                a ? x
    b ? y                b ? y

This is not to say, of course, that all PRI PARs are PAR -- just in the
above case.  Look at that case:

  If the environement offers neither communication, neither of the above
  codes can proceed.

  If the environment offers the `a' communication, both of the above become:

    b ? y

  If the environment offers the `b' communication, both of the above become:

    a ? x

  If the environment offers both communications, both of the above terminate
  (with `x' and `y' updated identically).

Only if you have the following tests, would they be different:

  If the environment offers both communications but offers the `a' one at
  higher priority to the `b', both of the above terminate.

  If the environment offers both communications but offers the `b' one at
  higher priority to the `a', the PAR one terminates but the PRI PAR one
  deadlocks ????

But I don't feel comfortable with that ... ?

The only possible difference that I can see is if we *insist* that, if the
environment offers both communications, the PRI PAR version gives us the
trace <a, b> whereas the PAR version can give us <a, b> or <b, a>.  Now
that distinction *is* made by the ALT equivalents:

  PRI ALT     ?=?      ALT
    a ? x                a ? x
      b ? y                b ? y
    b ? y                b ? y
      a ? x                a ? x

Since you agreed about the CSPP-equivalence between the PRI PAR/PRI ALT
codes ;-) and the CSP-equivalence between the PAR/ALT codes, *if* you were
to agree with the above PRI PAR/PAR equivalence, you would have to agree with
the PRI ALT/ALT equivalence!  Thus, the difference in the trace semantics is
irrelevant.  I think this is one of the points of your CSPP?  And I think
it's a good one.  I can't see any way any environment could detect which trace
(<a, b> or <b, a>) had happened and, hence, exploit the fact that the trace
<b, a> could not happen.

Except, of course, if you have the `hard' semantics for PAR and your example:

  PAR
    PRI ALT              -- i.e. PRI PAR
      b ! 2                        b ! 2
        a ! 1                      a ! 1
      a ! 1
        b ! 2
    PRI ALT
      a ? x
        SKIP
      b ? y
        SKIP

where the first process in the above PAR *prefers* to execute the trace <b, a>
(and offers both `a' and `b' events) and the second *prefers* to execute <a>
(and offers both `a' and `b' events) and `hard'-PAR yields deadlock.

The hardware implementation you sketched for the above (dated: Sat, 27 Feb
1999 09:18:32 +0000 (GMT)) showed a third-party `control' process arbitrating,
discovering the conflicting priorities and forcing deadlock.  We would need
that third-party for a software implementation of `hard'-PAR and that would
be expensive -- indeed, the need for an independent third-party is why output
guards were excluded from the occam ALT in the first place.  If occam had
allowed output guards, then this question of conflicting (PRI ALT) priorities
would have showed itself early on ... as in the above code ... and may
have been resolved by an arbitrary choice (CSPP soft-PAR) or deadlock
(CSPP hard-PAR).

I understand your occam-motivation for hard-PAR: such a conflict may be
a design error and it's better to deadlock (i.e. STOP) rather than proceed
with a choice that's bound to be wrong for one party.

But occam does not allow explicit output guards and the implicit output guards
(equivalent to a PRI PAR) always occur in front of processes that *allow*
traces that are an arbitary permutation of the leading events of components
within the PRI PAR, only *prefering* some above others.  So, the CSPP soft-PAR
seems quite reasonable to me.  If a design needs a hard-PAR, we can always
explicitly add the necessary controller to the design ... or get one generated
automatically by a HARD PAR extension to the language.

So, for now I'd vote that PAR = SOFT PAR.  It's efficient to implement
(and is what the transputer did) and has a well-defined semantices in the
presence of priorities (thanks Adrian).  Extending Adrian's above example
only slightly, it means that:

  PAR
    PRI ALT      -- illegal occam
      b ! 2
        a ! 1
      a ! 1
        b ! 2
    PRI ALT
      a ? x
        b ? y
      b ? y
        a ? x

which equals:

  PAR
    PRI PAR      -- legal occam
      b ! 2
      a ! 1
    PRI PAR
      a ? x
      b ? y

always terminates and terminates in the same state (i.e. x = 2, y = 1),
regardless of the order (or concurrency) of the communications.  I don't
see that we would want anything else?

But if we did want the hard-semantics, we just write:

  HARD PAR
    PRI PAR      -- legal occam
      b ! 2
      a ! 1
    PRI PAR
      a ? x
      b ? y

This would generate the implementation modelled by Adrian's control circuit
and yield the deadlock.

But I'm really not sure.  It does seem a shame that one of the PRI ALT
equivalences of one of the above PRI PARs has its notion of PRI disregarded
in the soft-PAR semantics.  These output-guarded PRI ALTs only exist in the
formally-minded mind's eye ... but, maybe, we should care about this.
If we do care, then the soft-PAR semantics looks dodgy.

Bit of a bummer this.  Thanks, Adrian, for raising it.  I wonder if all
those people using multi-priority real-rime kernels agonise over such
things ...

Now, what else has been going on ... my mail box is very very full!

Cheers,

Peter.