Re: Conflicting Priorities in occam

[Denis A Nicole <dan@xxxxxxxxxxxxxxx>]

On Tue, 2 Mar 1999 P.H.Welch@xxxxxxxxx wrote:

 
> > 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?

I guess we could make it a compiler option.  But, of course, the default
behaviour is all-important; do we want it "correct" or "according to the
standard established by INMOS".  recent precedent suggests serious legal
problems (Microsoft/SUN) if we improve occam.
 
> 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?

> 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.

More importantly, there is a well-defined worst-case cost for
rate-monotonic.  So you can actually evaluate the _practical_ advantages,
if any, of deadline.

Anyway, supporting multiple priorities is no more a problem for SPoC than
supporting two.  You just need an array of queues, sized by the PRI PARs.

Denis A Nicole                      WWW:   http://www.hpcc.ecs.soton.ac.uk/~dan 
High Performance Computing Centre   Email: dan@xxxxxxxxxxxxxxx                  
University of Southampton           Phone: +44 1703 592703                      
UK.                                 Fax:   +44 1703 593903