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'!)