Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!decwrl!sgi!karsh@trifolium.esd.sgi.com
From: karsh@trifolium.esd.sgi.com (Bruce Karsh)
Newsgroups: comp.realtime
Subject: Re: Technical Details (was Re: Measuring timing of Realtime Systems)
Message-ID: <68100@sgi.sgi.com>
Date: 29 Aug 90 22:43:10 GMT
References: <9724@tekigm2.MEN.TEK.COM> <12582@netcom.UUCP> <182@srchtec.UUCP> <1990Aug29.152604.28573@zip.eecs.umich.edu>
Sender: guest@sgi.sgi.com
Reply-To: karsh@trifolium.sgi.com (Bruce Karsh)
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 36

In article <1990Aug29.152604.28573@zip.eecs.umich.edu> walden@dip.eecs.umich.edu (Eugene Marvin Walden) writes:

>   If an algorithm is proven to be optimal, as the RM
>scheduling algorithm has been, then there is no "better" algorithm. In the case
>of scheduling periodic tasks with priorities that remain constant through their
>lifetime ("static" scheduling) on a single processor, the RM algorithm is op-
>timal. Period. There are several problems with implementation, however, as I 
>mention below. 
>   In the case of scheduling periodic tasks on a single processor where the
>priorities of the tasks can change ("dynamic" scheduling), the deadline-driven
>algorithm is optimal. 
>   Your search for an alternative method to an algorithm brings up a point. If
>an algorithm is optimal, then there is no need to go any further.

This is an oversimplification.  Rate Monotonic Scheduling is optimal with
respect to certain criteria.  E.g., that the process's priorities are fixed,
that processes are periodic, that lower priority processes may be preempted,
that preemption does not cost anything, that the figure of merit is the
CPU utilization.

If you choose other criteria, like least number of preemptions for a fixed
task-set, then you'll perhaps come up with slightly different algorithms.

> To say that
>another algorithm is better than an optimal algorithm is like saying that Mary
>is more pregnant than Sue.

Even so, a rate-monotonic schedule is not a unique optimal schedule for
a set of tasks.  Before you decide that there is "no need to go further",
it may be a good idea to look at other optimal scheduling rules.

The non-fixed priority schedulers are pretty neat things and they come in
a variety of optimal forms.

			Bruce Karsh
			karsh@sgi.com