Re: Priority revisited: a new primitive

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

-- 
Dr A E Lawrence

I have just found time to reply properly to Gerald's first reaction,
although most of this has been covered already.

But let me start by saying that the PAR PRI suggestion is just that: a
suggestion. I do not know whether it is possible to implement it
efficiently nor whether it really solves problems like priority inversion.
When I have time, that needs investigation.

But some of you have been saying for a long time that we need to find a way
to give priority to events rather than to processes, and PAR PRI seems to
be the purest form for such a primitive. PAR PRI [S] is exactly and
precisely a construction to give the events in S priority over all other
events.

I have in mind an acceptance semantics which is quite independent of any
implementation, hardware, software or other-ware. In essence, if any event
in S is available *and* can be accepted by any of the (parallel) processes
governed by the PAR PRI, and there is no priority conflict, then it will be
so accepted in preference to events not in S. If more than one event in S is
available, the usual rules apply. All events which can be handled in
parallel by the available resources happen. If there is insufficient
parallelism to handle the available events in S, then the choice of which
occur is non-deterministic. Likewise if some of the available events are
in S and some outside, then some subset occurs depending on the parallel
resources, with events of S getting choosen first. And this continues until
the parallel components terminate.
Phew! It is much easier to write the denotational semantics :-)
My previous posts included some sort of algebraic semantics.

As I have noted before, I imagine that a scheduling mechanism rather like
the transputer scheduler could do the job with the high priority
external events being handled in a way somewhat similar to the TIMER queue.
Internal high priority events are a bit simpler in that the first partner
in a high priority communication will cause a context switch/transfer to the
scheduler. The scheduler must then find the partner process, and maybe
there needs to be some extra data structure in workspaces or extra queues
to support that. Some of you are expert in that area and can no doubt
devise a clever scheme. My only concern at this stage is to know that
PAR PRI could in principle be implemented, even if one called the scheduler
after every event which would be a massive overhead and make it completely
impractical.

My algebraic semantics using events involving 3 processes can be regarded
as a sort of specification of scheduler: it is the third, eventually hidden,
partner in the communications.

{{{  Response to Gerald's comments
{{{  Gerald said
This is very interesting and I have been wrestling with this for some time,
but I failed to find a bulletproof solution. The idea of assigning priority
to events is something I tried to understand, but I can't for two reasons:
(1) I couldn't clearly reason with this concept and (2) it is (too) complex
to implement this in software or in hardware.
}}}
{{{  ael
If you reason at the level of the (denotational) semantics, it seems very
simple. We will have to decide what to do in the case of conflicting
priorities, but there is nothing different in principle from the other
cases, and we can choose "hard" or "soft" priority or whatever else
according to taste and needs. The denotational semantics can cope with any
variant.

Reasoning about implementations {operational semantics} is usually much
harder. If we start with the denotational semantics and then verify or
derive implementations life is simpler.
}}}

{{{  Gerald
I belief, that the PRI PAR construct is a very useful solution at
process-level when priority is a feasible solution. The PRI ALT is a great
solution when the application needs to choose between guarded processes.
Neither PRI PAR nor PRI ALT assigns priority to events.

}}}
{{{  ael
Gerald told me that he wrote this very late at night, so I'm sure
he wouldn't want to defend it. But PRI ALT certainly *does* assign
priority to events. The guards (ignore conditional variants) *are*
events. The difficulty is that we can only specify initial events,
and only one event is selected. PAR PRI can select multiple events
repeatedly.

I would say that PRI PAR also assigns priority to events. Its
problem is that we can only select the *whole alphabet* of a process.
It does not allow us to pick and choose, and I think that here lies
the origin of the priority inversion problem, although that needs
checking.

What neither of them do is allow us to assign priority to an *arbitrary*
collection of events. Repeatedly. Which is what PAR PRI does.
}}}

{{{  Gerald
PAR PRI  [{a}, {b}, {c}]
  P(a)
  Q(b)
  R(c)
  S(a)
  T(b)
  U(c)

..

Conceptually, this example should work similar in software compilations as
in hardware compilation, but how? I think, that the PRI PAR and PRI ALT can
explain the implementation for software and for hardware. Example 1 can be
written as follows,

EXAMPLE 2:

PRI PAR
  WHILE TRUE
    PRI ALT
      a'?x
        a''!x
      b'?x
        b''!x
      c'?x
        c''!x
  PAR
    P(a')
    Q(b')
    R(c')
    S(a'')
    T(b'')
    U(c'')

Note: the direction of communication is not considered here.

Now, this example could be the implementation of example1. An important
difference is that in a software compilation the PRI ALT functions as a
one-place buffering process, which is not the case in example 1.

{{{  ael
As Gerald points out, this is *not* an implementation of PAR PRI. Not
so much because of the buffering, but because we need a 3-way
synchronization. That can be fixed in occam in several ways, maybe using
extra handshake channels or even better using "merged" events which is
really what Gerald does with PRI MALT below:
}}}

A correction to this problem is that the PRI ALT should check the readiness
of both events a' and a'', b' and b'', and c' and c''. In CTJ we can build a
PRI MALT, i.e., a prioritised multiple alternative construct, that can do
the job. The solution is given in example 3.

EXAMPLE 3:

PRI PAR
  WHILE TRUE
    PRI MALT
      a'? & a''!
        SEQ
          a'?x
          a''!x
      b'? & b''!
        SEQ
          b'?x
          b''!x
      c'? & c''!
        SEQ
          c'?x
          c''!x
  PAR
    P(a')
    Q(b')
    R(c')
    S(a'')
    T(b'')
    U(c'')
}}}

{{{  Gerald
The semantics of the PRI PAR for hardware compilation must be specified so
{{{  ael
The semantics for hardware compilation must be exactly the same as for
software compilation or anything else! I guess that Gerald really meant
implementation here?
}}}
that after each instruction the current flow of control must be preempted by
the PRI MALT process when it has a guard ready, otherwise the current flow
of control continues. After the PRI MALT is waiting, the preempted flow of
control continues. This is interrupting.
{{{  ael
I guess it all depends on what one means by "interrupting". That is whether
we include the manipulation of interrupt_enable flags and such. The point
about PAR PRI is that an event only happens when the partners are ready.
This may be a difference without a distinction if we compare that with
an interrupt service routine being called. But in CSP, an interrupt
operator has been defined in the past: that involves the flow (trace, I
suppose) being changed - all right then, interrupted - without the process
being able to exert any control. Here we are concerned with communication
events that occur when the relevant partners are ready.
}}}


This is also similar to the working
of the PRI PAR in software, which schedules the thread of control. In
hardware, this preemption can be realized by non-preemptive context
switching after each instruction.
{{{  ael
Again, I think that this is about particular implementations, rather
then the underlying universal semantics.
}}}


Unfortunately, there is a bullet hole with this implementation! If process
P(a') implements an (PRI)ALT then the guard using a' will never be ready and
the execution fails. If this can be fixed then example 3 is an
implementation of example 1. In this case the PAR PRI is a higher-level
representation of example 3.
{{{  ael
This is just a reflection of an imperfect implementation surely?
If the point is about priority conflict, then we can solve that any way we
choose. But I think that Gerald is worrying about plumbing here in the
particular implementation?
}}}

I always thought that the PRI PAR was useful for software compilations and
not very useful for hardware compilations, but the example above (as with
interrupt hardware mechanisms) illustrates that the PRI PAR is very useful
in hardware compilations as well. With the PRI PAR we could model nested
interrupt mechanisms as well, something PAR PRI cannot do!
{{{  ael
I don't follow that. Can't see why PAR PRI can't model this.

In passing, I wonder if

PAR PRI [\alphabet(P)]             PRI PAR
  P                            =     P
  Q                                  Q

Maybe PAR PRI makes PRI PAR a derived concept? :-) Should we reach for the
razor and excise PRI PAR? That might make Barry a Happy Bunny ;-)
}}}

Assigning a priority to a channel has only meaning if processes communicate
on the channel. What if they don't communicate or the channels are ready in
an alternating pattern then the priorities of these events have no effect?
Should the priority of the related processes be influenced by the priority
of channels?

Do we really need to assign priorities to events?
{{{  ael
I don't know. But PAR PRI is a way to do it if it is needed.
As I understand them, all Gerald's comments are about the difficulties
of implementation using a particular approach. Rather than a critique
of the idea itself?
}}}

Gerald.

(O)     (O) (o)
    (O)            (o)
  (O)  (o) (O)
                (O)

= some bullet holes :-)
{{{  ael
I think that the sandbags absorbed them perfectly safely?
}}}

}}}

}}}


Adrian