karsh@trifolium.wpd.sgi.com (Bruce Karsh) (05/31/89)
In article <7252@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes: > I find it hard to believe that most existing realtime tools (e.g. >VRTX, Rex) use priority scheduling. I'm interested in making the >GNU kernel able to deal with hard realtime events, such as >those required for support of high bandwidth, low latency hardware, >and priority scheduling would make systems that 'seem to work' but >in which there is no way to engineer them so that they WILL work. I don't agree that there is no way. If each real-time job, i, can be characterised as having inter-onset periods of T[i] and requiring an amount of coumputation time C[i] in its period, then defining the processor utilization of each task as: U[i] = C[i] / T[i] it can be shown that if the sum of U[i] over all real time tasks, i, is less that ln(2) ~= .7 then the tasks can all complete withing their respective periods under a straight priority scheduler. One need only to assign higher priority to tasks with lower T[i]. To see how this works, look at Liu & Layland, Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment, JACM 20(1):46-61 1973. It's reprinted in the IEEE Tutorial on Hard Real-Time Systems (page 174). Personally, I think this is one of the most amazing results in the field of real-time systems. It is called a rate monotonic priority schedule. A fancier scheduler perhaps can do better, but even a conventional priority scheduler can do amazingly well! -- Bruce Karsh karsh@sgi.com In fact men will fight for a superstition quite as quickly as for a living truth - often more so, since a superstition is so intangible you cannot get at it to refute it, but truth is a point of view, and so is changeable.
inst182@tuvie (Inst.f.Techn.Informatik) (06/01/89)
In article <34054@sgi.SGI.COM> karsh@trifoliu.UUCP (Bruce Karsh) writes: >In article <7252@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes: >> [stuff deleted] >>and priority scheduling would make systems that 'seem to work' but >>in which there is no way to engineer them so that they WILL work. > > I don't agree that there is no way. > > [Reference to and description of rate monotonic algorithm deleted] > >Personally, I think this is one of the most amazing results in the field >of real-time systems. It is called a rate monotonic priority schedule. >A fancier scheduler perhaps can do better, but even a conventional priority >scheduler can do amazingly well! Sure the result is amazing. But anyone planning to use this algorithm really ought to look at the assumptions Liu and Layland make (page 48 of that paper). Especially assumption 3 (Independence of tasks) does NOT hold for any real-time system I can think of. The effect of relaxing these assumptions is discussed in: Aloysius K. Mok, The Design of Real-Time Programming Systems based on Process Models, Proceedings of the IEEE Real-time Systems Symposium 1984 Highly recommended ... Alexander Vrchoticky (Student of CS , Technical University Vienna) alex@honey.at honey!alex@uunet.uu.net
gillies@p.cs.uiuc.edu (06/01/89)
In article <7252@hoptoad.uucp> gnu@hoptoad.uucp (John Gilmore) writes: > I find it hard to believe that most existing realtime tools (e.g. >VRTX, Rex) use priority scheduling. I'm interested in making the >GNU kernel able to deal with hard realtime events, such as >those required for support of high bandwidth, low latency hardware, >and priority scheduling would make systems that 'seem to work' but >in which there is no way to engineer them so that they WILL work. Wait a minute. What is so wrong with priority scheduling? Priority scheduling algorithms can be used to solve any problem that does not require inserted idle time in the schedule. All you need to do is assign the *right* priorities. Priority (greedy) scheduling is one of a handful of algorithms fast enough to be incorporated in a real-time system. Rate Monotonic Scheduling is an optimal *static* priority scheme (i.e. no other static scheme can do better). Are you complaining about "static" priority scheduling? Do these real-time systems prevent you from changing the priorities? At the moment, there is no panacea in real-time scheduling. We need more information on exactly the problems you wish to solve in the GNU kernel. In scheduling, there is *no* "general" algorithm to solve all (or even many of) the problems optimally. Don Gillies, Dept. of Computer Science, University of Illinois 1304 W. Springfield, Urbana, Ill 61801 ARPA: gillies@cs.uiuc.edu UUCP: {uunet,harvard}!uiucdcs!gillies