Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!sdd.hp.com!ucsd!ucbvax!agate!shelby!msi-s0.msi.umn.edu!umeecs!dip.eecs.umich.edu!walden
From: walden@dip.eecs.umich.edu (Eugene Marvin Walden)
Newsgroups: comp.realtime
Subject: Re: Technical Details (was Re: Measuring timing of Realtime Systems)
Message-ID: <1990Aug30.234851.8887@zip.eecs.umich.edu>
Date: 30 Aug 90 23:48:51 GMT
References: <182@srchtec.UUCP> <1990Aug29.152604.28573@zip.eecs.umich.edu> <68100@sgi.sgi.com>
Sender: news@zip.eecs.umich.edu
Organization: University of Michigan EECS Dept., Ann Arbor, MI
Lines: 44

In article <68100@sgi.sgi.com> karsh@trifolium.sgi.com (Bruce Karsh) writes:
>990Aug29.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
>
>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.

   Well, I guess I should have been more clear. What I meant was that, for the
problem stated in Liu-Layland [73] where the rate-monotonic and deadline-driven
schedulers are proven to be the optimal static and dynamic schedulers, respect-
ively, they are optimal. Thus, if you make the same assumptions as they did,
like static priorities, independent tasks, etc., then you need not look any
further for a "better" algorithm. 
   You also bring up a good point about how the performance of a scheduler is
measured. In a paper entitled "Local Non-Preemptive Scheduling Policies for
Hard Real-Time Distributed Systems," by Woodside and Craig, in the 1987 IEEE
Real-Time Systems Symposium, they compare the following policies:

   1. FCFS
   2. SJF
   3. LLF (least laxity first)
   4. EDD (deadline-driven)
   5. GM (Stankovic)
   6. MM (Moore)

   The performance criteria they used were CPU utilization, ratio of rejected
tasks, ratio of rejected tasks with positive laxity, and the remaining laxity 
of rejected tasks with positive laxity. No one algorithm is "best" for all 
performance criteria, so your point is well-taken.

>			Bruce Karsh
>			karsh@sgi.com


   - Eugene Walden (walden@dip.eecs.umich.edu)