Re: Conflicting Priorities in occam

[<P.H.Welch@xxxxxxxxx>]

Oyvind ran Adrian's example under SPoC:
=======================================

  PAR
    PRI PAR
      b ! 2
      a ! 1
    PRI ALT
      a ? x
        SKIP
      b ? y
        SKIP

> -- This compiles in SPoC, communicates over b fine,
> -- sends on a, but there is no receiver and the queue
> -- is empty, so SPoC issues a critical error.

As Barry said later (can't find it for the moment), this is a red-herring!
The example is bound to deadlock and would deadlock under KRoC (or on the
transputer) with exactly the same sequence of events Oyvind describes.
KRoC would also issue a deadlock report.

But this is not an example of deadlock being thrown as a result of priority
conflict!  If that were the case, it would deadlock without any communication
over b - once the conflicting priorities were detected. That is not what is
reported.  SPoC is implementing soft-PAR, in line with KRoC and the transputer.

Adrian: please note ...


KRoC's PRI PAR are, currently, just PAR:
========================================

SPoC manages two run queues, just like the transputer, but with voluntary
(i.e. non-preemtive) switching between them.  Currently, I'm afraid,
KRoC manages just the one and ignores the PRI in PRI PAR.

However, there is an option in KRoC that checks a sync-flag in the kernel
at each backward unconditional jump.  This sync-flag tells us if an
external peripheral need servicing (e.g. the keyboard, a timeout or
network communication - in the case of our still unreleased KRoC-NoW
system).  If the sync-flag is set, the process is rescheduled along
with whatever processes were waiting for those external peripherals.
It's a sort of pseudo-preemption.

Of course, this would work much better with multiple priorities and
we've always meant to do this.  The Twente paper at the last WoTUG
conference at Bristol says how to do this.  And you don't really
need premption, especially with the above pseudo-premption trick.

Jim Moores' paper at the forthcoming WoTUG-22 describes his kernel
for KRoC-Linux that also supports an API close to the old INMOS C
API for the transputer.  This gives you occam-like processes, channels,
ALTing -- at occam-like costs -- for standard (GNU-)C applications.

For interest, he threw in 32 levels of priority for the C version
(which he calls CCSP).  Actually, this was at the request of his
sponsors.

Context switching remains a unit-time overhead except in one circumstance.

Scheduling higher level priorities is unit-time.  As the Twente people
pointed out, this only happens becuase an external peripheral is ready
(and our pseudo-premption will spot this if a backward jump occurs before
the next scheduling point - when it would be spotted anyway) or because
you communicate with a waiting higher-priority process (more on this later!).

Scheduling lower level priorities is unit-time (e.g. you communicate with
a waiting lower-priority process).  Scheduling a same priority process is
unit-time - it's what unipriority occam schedulers do anyway.

Only if you exhaust the priority queue currently being executed is there
a non-unit time overhead.  Then, you have to find the highest non-empty
priority queue -- there won't be one above the queue just exhausted -- so
it's an O(n) search, where n happens to be 32.  This does not take long.

Jim could do this for C because he could create the space to hold the
priority associated with each process - 5 bits (I think he uses a whole
word though!).  SPoC could do this also.

KRoC has a problem that we work with the memory map devised for the
transputer ... and that only reserved one bit to hold process priority
(high or low).  That bit is the lowest bit in the process descriptor
word.  The original INMOS compiler always forced process worspaces to
start at an even address, so that bit was free.

Actually, because KRoC targets 64-bit processors, it has a flag that
ensures that the (modified INMOS) compiler forces workspaces to be
double-word aligned (i.e. at multiples of 8).  This frees up 3 bits
in which to hold process priority.  Sometime, we will make this
double-word alignment the default (it's not that memory wasteful,
even for an 8-bit target architecture) and that would allow us to
offer 8 priority levels.

Of course, if we were brave enough to modify the old INMOS compiler
some more, we could just allocate an extra word in each process workspace
to hold the priority and offer more priorities than anyone would ever need.
We could also remove the restriction that PRI PARs only have two components!

If we could just get SGS-Thompson to let us make these compiler sources
`open', anyone could do it ... we're still trying to do that ...

Peter.