Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!sun-barr!decwrl!sgi!karsh@trifolium.wpd.sgi.com From: karsh@trifolium.wpd.sgi.com (Bruce Karsh) Newsgroups: comp.realtime Subject: Re: priority scheduled real time Keywords: rate monotonic trivial Message-ID: <34190@sgi.SGI.COM> Date: 1 Jun 89 07:49:52 GMT References: <7252@hoptoad.uucp> <34054@sgi.SGI.COM> <5084@pt.cs.cmu.edu> Sender: daemon@sgi.SGI.COM Reply-To: karsh@trifoliu.UUCP (Bruce Karsh) Organization: Silicon Graphics, Inc., Mountain View, CA Lines: 59 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.