Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!wuarchive!zaphod.mps.ohio-state.edu!usc!snorkelwacker!bloom-beacon!eru!hagbard!sunic!mcsun!tuvie!vmars!alex
From: alex@vmars.tuwien.ac.at (Alexander Vrchoticky)
Newsgroups: comp.realtime
Subject: Scheduling (was: Technical Details)
Message-ID: <1782@tuvie>
Date: 30 Aug 90 12:34:17 GMT
References: <9724@tekigm2.MEN.TEK.COM> <12582@netcom.UUCP> <182@srchtec.UUCP> <1990Aug29.152604.28573@zip.eecs.umich.edu> <89135@srcsip.UUCP>
Sender: news@tuvie
Lines: 54


There has been some discussion about static and dynamic priority scheduling
in this newsgroup lately. A plea: *Please* bear in mind that those 
algorithms are *only* optimal for systems of independent tasks
(No precedence constraints, no mutual exclusion constraints).
The high cpu utilization of 1 for least laxity, and of >= ln(2) for 
rate monotonic also only does hold for such systems (called `task sets').

It is very easy to find a problem that can only be solved when
introducing precedence constraints. Consider for instance
a system with three tasks: A reading some data, B processing them, 
and C acting according to the results A and B. It is
necessary to process them in the order A-B-C. Problems of this nature
cannot be solved by algorithms dealing with independent tasks only.

It *is* possible to adapt RM scheduling to other task systems,
but it is by no means trivial, optimality is lost and cpu utilization is 
much lower (see e.g. [2] and [3]). 
In fact it has been proven that *no* scheduling algorithm
for general task systems can be optimal, unless it has some a-priori 
knowledge about the precedence and mutual exclusion constraints (see [1]).

And to answer the original question: Yes, there are other scheduling 
disciplines, even some that have no notion of priorities. 
Some are based on heuristic search techniques, used either in parallel with 
execution (see for instance [5]) or before run time [4]).

Alexander Vrchoticky

--- 
References:

[1] A. K. Mok, 
    `The Design of Real-time Programming Systems Based on Process Models'
    Proc of the 1984 Real-Time Systems Symposium, p. 5-17, Dec. 1984

[2] Sha, Lehoczky, Rajkumar: Priority Inheritance Protocols: An Approach to
    Real-Time Synchronization, Technical Report CMU-CS-87-181 CMU 1987

[3] Sprunt, Sha, Lehoczky: Aperiodic Task Scheduling for Hard Real-Time Systems,
    Real-Time Systems, Volume 1, Number 1, June 1989, pp. 27-61

[4] Krithi Ramamritham, Allocation and Scheduling of Complex Periodic Tasks,
    Proc ICDCS-10, May 1990, pp. 108-115

[5] Cheng, Stankovic, Ramamritham: Dynamic Scheduling of Groups of Tasks with
    Precedence Constraints in Distributed Hard Real-Time Systems,
    Real-Times Systems Symposium, Dec 1986


--
Alexander Vrchoticky  Technical University Vienna, Dept. for Real-Time Systems
Voice:  +43/222/58801-8168   Fax: +43/222/569149
e-mail: alex@vmars.tuwien.ac.at or vmars!alex@relay.eu.net  (Don't use 'r'!)