Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!caen!umich!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: <1990Aug29.152604.28573@zip.eecs.umich.edu> Date: 29 Aug 90 15:26:04 GMT References: <9724@tekigm2.MEN.TEK.COM> <12582@netcom.UUCP> <182@srchtec.UUCP> Sender: news@zip.eecs.umich.edu Organization: University of Michigan EECS Dept., Ann Arbor, MI Lines: 85 In article <182@srchtec.UUCP> johnb@srchtec.UUCP (John Baldwin) writes: >Not to start flames, but I must comment that it is about time we had some >*real* real-time postings.... Hmmmm...... Well, I am not sure if this is a "real" real-time post or not, but I'll try to answer your questions. >Most of the reading I've been doing has been concerning the "Rate Monotonic >Theory." A problem I've run up against is that I cannot easily find any >strongly opposed alternative methods. I'm sure there must be at least one. No, there really aren't. 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. To say that another algorithm is better than an optimal algorithm is like saying that Mary is more pregnant than Sue. If an algorithm has not been proved optimal, then the question is still open. The hottest open topic in real-time scheduling re- search is the problem of scheduling real-time tasks on a multiprocessor system. This problem has been proven to be NP-complete (unsolvable) in the general case. This means that no "optimal" algorithm will be possible with a reasonable amount of computing time. > >Does anyone know of a good paper presenting the "con" side of the RM theory, >or could you post a short (!) statement of the current position of >various methods? The following is an excerpt from a paper entitled, "Solutions for some Practical Problems in Prioritized Preemptive Scheduling," by Sha, Lehoczky and Rajkumar. It appears in the 1986 IEEE Real-Time Systems Symposium. Here is the abstract: "Most existing real-time control systems use ad hoc static priority schedu- ling methods. This is in spite of the fact that the rate monotonic scheduling algorithm was proved to be the optimal static priority scheduling algorithm for periodic tasks over a decade ago (1973). This lack of use is, in part, because a direct application of this algorithm leads to a number of practical problems which have not been fully addressed in the literature. In this paper, we give a comprehensive treatment of a number of practical problems associated with the use of the rate-monotonic algorithm. These include the scheduling of messages over a bus with insufficient priority levels but with multiple buffers. We also review the methods to handle aperiodic tasks and present a new approach to stabilize the rate monotonic algorithm in the presence of transient processor overloads. Finally, the problem of integrated processor and data I/O scheduling is addressed. New results clearly establish the importance of using an integra- ted approach to schedule both the processor and data I/O activities." To summarize the problems with the RM scheduling algorithm: 1. If task execution times are stochastic, and they often are, *ensuring* that the processor never becomes overloaded requires the use of absolute worst case execution times for your tasks. This can lead to very poor CPU util- ization. 2. The rate-monotonic and deadline-driven algorithms operate optimally in good conditions, but behave unpredictably in overload conditions. This is ironic because it is usually when a system is in overload that scheduling correct- ness becomes most critical. 3. Because most I/O devices like serial interfaces, DMA, etc., use simple FIFO type scheduling schemes, and because some tasks must wait for other tasks, it is quite likely that the optimal priorities assigned by your scheduling algorithm will conflict with the FIFO scheme used for I/O. To really have an optimal scheduler, you need to have optimal I/O scheduling as well. 4. Neither the rate-monotonic algorithm nor the deadline-driven algorithm are optimal in the multiprocessor case. There are probably other cons, but, for the sake of brevity, I will stop here. If you got my post on real-time references, you might find some other papers that refer to the RM scheduler and the DD scheduler. Good luck! >John T. Baldwin | johnb%srchtec.uucp@mathcs.emory.edu >Search Technology, Inc. | > | "... I had an infinite loop, >My opinions; not my employers'. | but it was only for a little while..." - Eugene Walden (walden@dip.eecs.umich.edu)