lindsay@MATHOM.GANDALF.CS.CMU.EDU (Donald Lindsay) (06/01/89)
In article <34054@sgi.SGI.COM> karsh@trifoliu.UUCP (Bruce Karsh) writes: > 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]. >It is called a rate monotonic priority schedule. Hmmm, let's see if I've got this right. We are assuming that all tasks are known, are strictly cyclic, have known upper bounds on their compute time/cycle, have no external dependencies or interdependencies, and do not require latencies less than the respective cycle times. Further, we are assuming 10/7 = 43% excess resources over the worst-case requirement, and we are disregarding equipment failure, exception handling and reporting, communications, and reconfiguration. Under these conditions, we have proved that a trivial algorithm will work fine. I agree wholeheartedly. However, there are problems which violate each and every one of the assumptions. Some problems violate them all. As we automate more and more life-critical control systems, I submit that hard problems are unavoidable: only the theorists can wish them away. -- Don D.C.Lindsay Carnegie Mellon School of Computer Science --
karsh@trifolium.wpd.sgi.com (Bruce Karsh) (06/01/89)
In article <5084@pt.cs.cmu.edu> lindsay@MATHOM.GANDALF.CS.CMU.EDU (Donald Lindsay) writes: >Hmmm, let's see if I've got this right. > >We are assuming that all tasks are known, are strictly cyclic, have >known upper bounds on their compute time/cycle, have no external >dependencies or interdependencies, and do not require latencies less >than the respective cycle times. It is not necessary to assume that all tasks are known. Only the tasks which require a real-time guarantee need to be "known". By "known", I mean that they can be characterized by C and T. I don't believe that you can have a guaranteed real time schedule without "knowing" something about the resource requirements of the tasks you want to schedule. The tasks need not be strictly cyclic - they need only have some minimum inter-onset time T[i]. > Further, we are assuming 10/7 = 43% >excess resources over the worst-case requirement, and we are >disregarding equipment failure, exception handling and reporting, >communications, and reconfiguration. At least 69% of the CPU cycles are devoted to real time tasks for any number of real-time tasks. If there is only 1 real time task, 100% of the cycles can go to it. If there are 2, 83% can go to them. So in the worst case, no more than 31% of the cycles need be held back for other than real-time tasks - not 43%. The issues of equipment failure, exception handling and reporting ... etc are red herrings here. If you want to make a guaranteed schedule system have those capabilities, then you have to schedule CPU time for them, like any other consumer of CPU resources. There are a whole host of design issues concerning these capabilities. But none of them rule out the use of a rate-monotonic priority scheduler in a hard real-time system. >Under these conditions, we have proved that a trivial algorithm will >work fine. I agree wholeheartedly. >However, there are problems which violate each and every one of the >assumptions. Some problems violate them all. As we automate more and >more life-critical control systems, I submit that hard problems are >unavoidable: only the theorists can wish them away. I don't wish to suggest that the rate-monotonic priority schedulers is a panacea, or that there is no other good ways to design a real-time system. Instead, I like to think of it as a simple and reliable component in which can be used in real-time systems. By the way, theorists don't wish away hard problems, they create, discover and revel in them. -- 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.