alex@vmars.tuwien.ac.at (Alexander Vrchoticky) (08/30/90)
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'!)