🚀 go-pugleaf

This is a reply to Ron Daniel's question about communications between high and
low priority processes in a PRI PAR on a transputer.  The simple answer is
that: no, there is no clever scheduling. The complicated answer takes a bit
longer.

You can think of low-priority-ness as a real tar-baby: a high-priority process
that communicates on a channel the other end of which is held by a low-priority
process has to put up with the vagaries of the low-priority process scheduler.
If a high-priority process communicates on a channel with a process that is not
already waiting, it is descheduled.  If there is then no (other) ready high-
priority process, a low-priority process will be scheduled and time-sliced and
so on until one of them completes the synchronisation and restarts the high-
priority process again.

The examples in the question were, roughly

        PRI PAR                         PRI PAR
          WHILE ...                       WHILE ...
            SEQ                             SEQ
              P                               P
              SEQ i = 0 FOR n                 SEQ i = 0 FOR n
                c[i] ! e(i)                     c[i] ! e(i)
          PAR i = 0 FOR n                 WHILE ...
            WHILE ...                       SEQ i = 0 FOR n
              SEQ                             SEQ
                c[i] ? x[i]                     c[i] ? x[i]
                Q(i)                            Q(i)

and in both cases there can be periods when there is no high priority process
executing.

In the parallel case, the first time around the loops, it can in the worst case
take a time long enough to set up all of the inputs before any one of the
outputs can happen; but it can only take as long as that for all of the outputs
to complete.  Thereafter, of course, each of the Q(i) has to have completed
before the next communications can happen, so it takes n times the time it
takes to run Q(i) before the next cycle of the high priority loop completes.

In the sequential case, it is guaranteed that the high-priority process will
not be running while any of the Q(i), except the last, is running; so it will
take a time about (n-1) times as long as it takes to run Q(i) to complete the
n outputs to c[i].  The second is therefore significantly worse for keeping the
high-priority process `tied-up'.

There is a trick for keeping a high-priority process running even if it needs
to communicate with a low-priority process, and that is to insert a
`sacrificial' buffer.  The high-priority process communicates with the buffer
which also runs at high priority; the buffer communicates with the low-priority
process.  If you have pitch that needs to be touched without your becoming
defiled, you get someone else to do it for you.  In

        PRI PAR
          PAR
            WHILE ...           -- high priority
              SEQ
                ...
                c ! e
                ...
            WHILE ....          -- buffer, also high priority
              SEQ
                c ? b
                d ! b
          WHILE ...             -- low priority
            SEQ
              ...
              d ? x
              ...

the output c!e cannot be responsible for descheduling all of the high-priority
processes: the second process can get stuck at the d!b, but whichever of the
processes first reaches the communication on c, the first process is able to
continue after the c!e and a delay at most as long as it takes the second
process to complete an input and start an output.

Of course, if the first process gets around its loop before the buffer has
been emptied, it has to wait for the next c!e, but you can put in a several-
place buffer to smooth out any short bursts of high-priority activity.

If, however, the high-priority process loops faster on average than the low-
priority process, no finite buffer will prevent the high-priority process from
being held up.  If you want to guarantee latency you need to throw away some
of the communications: if you have to service interrupts that may come too
often, you have to be prepared to throw some of them away.  There is an example
of an `almost-buffer' which is always ready to accept input (after at most a
bounded delay) but which throws away input for which it has no room in
Chapter 9 of `Programming in occam2', Jones and Goldsmith, Prentice-Hall 1988.
(Adverts get everywhere these days.)  It is something like this:

  PROC leaky.buffer(CHAN OF BYTE input,
                    CHAN OF SIGNAL request,
                    CHAN OF BYTE reply      )
    -- buffers up to type.ahead number of bytes at a time
    INT reader, writer, count :
    SEQ
      reader, writer, count := 0, 0, type.ahead
      [type.ahead]BYTE datum :
      WHILE TRUE
        ALT
          BYTE lost :
          count = 0 & input ? lost
            SKIP  -- could signal the error here
          count > 0 & input ? datum[writer]
            count, writer := count - 1, (writer + 1) \ type.ahead
          count < type.ahead & request ? CASE signal
            SEQ
              reply ! datum[reader]
              count, reader := count + 1, (reader + 1) \ type.ahead
  :

and it can be used to guarantee always to be ready for communication on `input'
if it is used with another idiomatic construction, called a `request buffer'
in Jones and Goldsmith:

  PROC request.buffer(CHAN OF SIGNAL request,
                      CHAN OF BYTE reply,
                      CHAN OF BYTE output     )
    WHILE TRUE
      BYTE datum :
      SEQ
        request ! signal
        reply ? datum
        output ! datum
  :

They are used like this:

        PRI PAR
          PAR
            WHILE ...   -- this is the `real' high priority process
              SEQ
                ...
                c ! e
                ...
            leaky.buffer(c, request, reply)
            request.buffer(request, reply, d)

          WHILE ...     -- this is the low priority process
            SEQ
              ...
              d ? x
              ...

with both of the buffering processes also running at high priority.  Now only
the request.buffer can ever get stuck talking to a low-priority process, so the
conversation between the real high-priority process and the leaky.buffer is
carried out entirely at high priority.
                                                                            gj