Re: Priority revisited: a new primitive

[Denis A Nicole <dan@xxxxxxxxxxxxxxx>]

On Tue, 24 Oct 2000, p0072370 wrote:

> >A look at Stallings' "Operating Systems" gives us methods such as:
> >   * fixed priority scheduling
> >   * earliest-deadline scheduling using completion deadlines
> >   * earliest-deadline scheduling using unforced idle times
> >   * first-come first-served
> >   * rate monotonic scheduling
> >and this is not a complete list by a long way.
> >
> >Note that priority is just one of many ways to control scheduling (and in
> >Stallings' example it is one that FAILS to meet the requirements).
> >It appears that you can't have a correct program that DOES depend on
> >priority!
> I have complete faith in Physics and Engineering texts, but very, very 
> little in those on software. There, I prefer to draw my own conclusions...

It's not that bad. Deadline scheduling is optimal---if you know the
deadines.

Rate monotonic scheduling is only worse than deadline by a known (small)
worst-case factor---if your processes are all periodic with known periods.

Unfortunately, "optimal" means "if this scheduler doesn't work, nothing
else will" which is not the same as "correct".  The hard part is actually
computing the loads from the tasks, and dealing with the realities of
varying length non-periodic tasks. Dedicated processors joined up by occam
are one way to go.

Denis A Nicole                 WWW:   http://www.hpcc.ecs.soton.ac.uk/~dan
High Performance Computing     Email: dan@xxxxxxxxxxxxxxx
Department of Electronics      Phone: +44 23 8059 2703
       & Computer Science      Fax:   +44 23 8059 3903
University of Southampton
SO17  1BJ
United Kingdom