Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!rutgers!rochester!pt.cs.cmu.edu!MATHOM.GANDALF.CS.CMU.EDU!lindsay
From: lindsay@MATHOM.GANDALF.CS.CMU.EDU (Donald Lindsay)
Newsgroups: comp.realtime
Subject: Re: priority scheduled real time
Keywords: rate monotonic trivial
Message-ID: <5084@pt.cs.cmu.edu>
Date: 31 May 89 18:30:37 GMT
References: <7252@hoptoad.uucp> <34054@sgi.SGI.COM>
Organization: Carnegie-Mellon University, CS/RI
Lines: 34

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
--