Path: utzoo!utgpu!jarvis.csri.toronto.edu!rutgers!apple!ames!sgi!karsh@trifolium.wpd.sgi.com
From: karsh@trifolium.wpd.sgi.com (Bruce Karsh)
Newsgroups: comp.realtime
Subject: Re: IEEE Tutorial (Really priority scheduled real time os)
Message-ID: <34054@sgi.SGI.COM>
Date: 31 May 89 05:17:52 GMT
References: <7252@hoptoad.uucp>
Sender: daemon@sgi.SGI.COM
Reply-To: karsh@trifoliu.UUCP (Bruce Karsh)
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 38

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.