Re: Conflicting Priorities in occam

[<P.H.Welch@xxxxxxxxx>]

Denis Nicole wrote:
===================

> Anyway, the real reason for the message was to discuss SPoC's
> implementation of PRI.  The SPoC scheduler essentially uses coroutines; it
> is not preemptive.  When it gains control, which includes every
> communication and PAR, it uses two queues, high and low priority, as in
> the transputer. The high priority queue is always run if possible.
> Without external communication, a high priority process can _only_ become
> ready at a scheduling point, so this model ensures that there is never a
> high priority process waiting on a low priority one.

But a high priority process, once running, could try to communicate with
a low-priority process way down on your low-priority process queue.  It would
then have to wait for all those earlier scheduled low-priority processes
to get out of the way before it could get on with its business.  Isn't
this the usual priority-inversion `problem'?

> ALTs are all PRI ALTs of the transputer sort, complete with the famous
> three-way PRI ALT bug (feature).  SPoC goes to great lengths to ensure
> transputer compatibility...

As does KRoC ;-) ...

Denis: should we fix this now?

We fixed this bug for JCSP (and, I believe, in CTJ which uses the same
algorithm).  The disables are carried out in reverse order, selecting
for execution the *last* ready guard found.  I think that's what Michael
Goldsmith tried to get the transputer people to do round about OUG-8 (at
Sheffield) in 1988?


James Wolffe wrote:
===================

> 2)PRI PAR is a very difficult thing to get right, since it reflects the desire
> to share a processor resource, normally a very implementation-dependent issue.
> Except for control of resource sharing I see no good reason to support it.
> Unfortunately, controlling the effects of resource sharing is a critical issue
> in concurrent real time systems

I think I agree totally with you.  Transputers never had a PLACED PRI PAR
after all!

Prioritised processes are used to try and make efficient use of a (single)
processor resource.  That's what all the rate-monotonic stuff from Twente
is about -- being able to put a greater load on each processor and still
guarantee deadlines.  With only two levels of priority, we have to make very
light (= inefficient) use of each processor for many control applications.
With n levels -- and control applications that require cyclic sampling and
actuation -- we can be much more efficient.

Rate-monotonic is implemented by a PRI PAR with lots of components.  There
is a classic argument between deadline-scheduling (which is *not* captured
by PRI PAR) and rate-monotonic, since deadline-scheduling is theoretically
more efficient.  `Theoretically' means ignoring the overheads of managing
the scheduling, which are high (and non unit-time) for dynamically changing
priorities -- especially when deadline-scheduling requires a *very* large
number of priorities.  The scheme outlined by Twente (mentioned in an
earlier mail) and implemented by Jim Moores for his CCSP/KRoC/Linux kernel
has very low overheads for rate-monotonic applications.

In any case, if the rate-monotonic cycle intervals form a sequence of integers
where each one is an exact multiple of the previous, the theorem says that
rate-monotonic scheduling is as efficient as deadlines.  And Andy says that
that condition is usually fixable.

> Bottom line: I see two independent areas fcr real time program specification:
> logical (consisting of occam including PRI ALT, but without PRI PAR), and
> temporal (relating processor performance capabilities and the process mappings
> to the timing requirements placed upon the logical design). PRI PAR styled
> priority functionality would be "buried" inside the runtime support package
> for a given as-mapped system. That is, the need for priority is a side-effect
> of meeting the timing requirements of the concurrent program on certain
> processors.

But I think that PRI PAR, as used above *within* a single processor on which
a particular functionality has been mapped, gives us a sufficient handle
with which to manage things - at least for rate-monotonic schemes or any
scheme in which the priority of a process is fixed.  The reasons for wanting
dynamic priorities -- e.g. to fix the prioriy inversion `problem' or for
deadline scheduling -- look weak.  If we "bury" the notion of priorities
within some runtime support package, we are only putting off the problem.
What is the semantics of that package?  With CSPP, we are begining to get
the semantics of PRI PAR.  This is good news ...


Adrian Lawrence wrote:
======================

> I remember some sessions with Roger Shepherd at a WoTUG meeting [Aberdeen?]
> in the days of the H1=T9000 design. I was only on the periphery, but I think
> Andy was involved. As I understood it, there was much feedback from real time
> people asking for special facilities on the T9 for priority|real time
> scheduling  control and such. Was there any discussion then about language
> issues? As far as I know, it was primarily about hardware facilities. How were
> these to be controlled from occam. Any one know about this?

This was Andy et al (from Twente) trying to pursuade them to introduce
multiple process priorities.  I can't remember whether Andy was pushing
a greatly expanded PRI PAR -- he might have had some other notation.
But I'm pretty sure he wasn't pushing for dynamic priorities.  The point
being that process fixed-but-multiple-priorities was cheap: almost as
cheap as the transputer's normal 2-priority scheme and, if you only used
those two priorities, *as* cheap.  Anyway, Roger didn't buy :-( ...

We came closer to success with *David* Shepherd from INMOS, when they were
planning the ST20-450.  But David was looking for ideas for allowing
multiple priorities for `interrupt' routines, not for ordinary processes.
So he didn't buy either :-( :-( ...

So the 450 came out with its 8-level interrupt-priority scheme, which
apparently conformed much more closely with what the (potential) porters
and users of commercial real-time kernels wanted.  But those interrupt
`routines' of the ST20 weren't proper transputer (i.e. CSP) processes.
They couldn't communicate via channels to normal processes.  They had
to share data with them and protect that data with semaphores ... a real
leap back in time.

And I never worked out why, if they could queue up on a semaphore, they
couldn't wait on a channel?  I suspect they probably could, but nobody
was ever told in case it scarred off the commercial real-time vendors
and users.  And I don't see how those interrupt-prioritised routines
(and you could only have one per priority level) could enable efficient
use of the processor for rate-monotonic application codes ... for example?

Oh well, I guess those commercial real-time vendors and users got scarred
off for other reasons!


Oyvind Teig wrote:
==================

> somewhat late/early. AND, if we could clean up these lists
> so that I don't get n-tuples of each message, it would be easier
> to know if "now AFTER before" is indeed positive!

Sorry Oyvind!  You were on occam-com with 3 different email addresses!!
I've pruned this to hopefully the right one ;-)

Is anyone else getting multiple mailings?

Cheers,

Peter.