Re: Real Time Scheduling Methods

[agate!doc.ic.ac.uk!uknet!yorkohm!minster!ken@ucbvax.Berkeley.EDU]

Douglas W. Jones,201H MLH,3193350740,3193382879 (jones@pyrite.cs.uiowa.edu) wro
te:
: From article <92302.34020.LJ10891@LMSC5.IS.LMSC.LOCKHEED.COM>,
: by LJ10891@LMSC5.IS.LMSC.LOCKHEED.COM:
: > 
: >    Sorry about that guys, but it looks like Rate Monotonic is the only game
: > in town.
: 
: Liu and Leyland, the people who proved the sufficiency of rate monotonic
: scheduling as long as there is not too much over 60% cpu utilization,
: also proved that deadline based real-time scheduling was sufficient if
: there is up to 100% utilization.

This 100% condition for schedulability only holds if the deadline of a task
is equal to its period.

: Deadline based scheduling may also be a bit more difficult than rate
: monotonic scheduling because it requires that processes state their
: deadlines explicitly instead of merely bumbling along, but it can also
: be more flexible, because deadlines need not be strictly periodic, while
: rate monotonic scheduling theory is only good for processes with strictly
: periodic real-time deadlines.

Don't confuse the term "Rate monotonic" with "fixed priority scheduling".
Rate monotonic is simply a priority assignment policy, guaranteed to be
optimal for task sets where deadline=period. For arbitrary deadlines (either
less than or greater than periods) this assignment policy isn't optimal.

If you want other beahviours (e.g. deadline < period, or sporadic tasks with
response deadline < inter-arrival time) then all you need to do is derive 
analysis for the behaviour of the fixed priority dispatcher and you get a 
new family of scheduling disciplines. Hence, "deadline monotonic", for periodic
tasks with deadline<period.

--
Ken Tindell             Internet      : ken@minster.york.ac.uk
Computer Science Dept., Local FTP site: minster.york.ac.uk
York University,        Tel.          : +44-904-433244         
YO1 5DD, UK             Fax.          : +44-904-432708
--
"The Gulf War won't be like a Rambo film; it will be long, bloody and terrible"