Real Time Scheduling Methods

Real Time Scheduling Methods

[kronos.arc.nasa.gov!iscnvx!news]

As promised, here is a summary of all mail received on any scheduling
methodology other than Rate Monotonic which can ensure that all time
constraints are fulfilled:

   NONE.

   Sorry about that guys, but it looks like Rate Monotonic is the only game
in town.

                          ghaddad@lmsc.lockheed.com
I found these opinions on my doorstep, would you please give them a good home?

Re: Real Time Scheduling Methods

[cis.ohio-state.edu!zaphod.mps.ohio-state.edu!moe.ksu.ksu.edu!hobbes.physi]

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

No, there's deadline based scheduling.  Deadline based scheduling is
incompatable with Ada, because it requires that the priority of each
process be, at any instant, the deadline by which the process must
complete its next critical action.  Once the process completes the
action, it changes its deadline to the time of the next action (note
that in Ada, priorities are fixed).

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.

Thus, deadline based scheduling can be superior to rate monotonic
scheduling, but it's illegal in Ada.

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.

					Doug Jones
					jones@cs.uiowa.edu

Re: Real Time Scheduling Methods

[Tucker Taft]

In article <1992Oct28.203415.9815@news.uiowa.edu> 
  jones@pyrite.cs.uiowa.edu 
  (Douglas W. Jones,201H MLH,3193350740,3193382879) writes:

>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.
>
>No, there's deadline based scheduling.  Deadline based scheduling is
>incompatable with Ada, because it requires that the priority of each
>process be, at any instant, the deadline by which the process must
>complete its next critical action.  

Deadline-based scheduling is not actually incompatible with Ada.

In Ada 83, if no priority is specified for any task, then all
scheduling is totally implementation-defined.  An implementor
may provide a separate package to set the Deadline for a task,
thereby supporting an alternative scheduling paradigm.

In Ada 9X, alternative scheduling paradigms are acknowledged
explicitly.  The only requirement is that a compiler conforming
to the Real-Time Annex provide support for strict priority-based
scheduling, though it may support other scheduling algorithms as
well.  Furthermore, priorities can be dynamic in Ada 9X,
so almost any scheduling approach can be mapped to
fiddling at appropriate moments with the priority of some
or all of the tasks (hardly an efficient way to do it,
but perhaps useful to keep the semantic model simple).

> . . .
>Thus, deadline based scheduling can be superior to rate monotonic
>scheduling, but it's illegal in Ada.

Not really, as pointed out above.  Of course, if no Ada compiler
or RTS in existence supports it, then who cares anyway?  But
it is definitely not "illegal" for an ambitious Ada compiler- or
RTS-implementor to try to provide deadline-based scheduling if they
so choose.

>					Doug Jones
>					jones@cs.uiowa.edu

S. Tucker Taft         stt@inmet.com
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138

Re: Real Time Scheduling Methods

[John Goodsen]

Doug Jones (jones@cs.uiowa.edu) writes:
>
>Thus, deadline based scheduling can be superior to rate monotonic
>scheduling, but it's illegal in Ada.
>

Deadline based scheduling is not *illegal* in Ada, you just
have to add it on your own.  See your local friends up at
Rockwell International in Cedar Rapids and ask them about their 
Real Time Executive for Avionics applications written in Ada... :-)

I believe it fits your definition of "deadline based scheduling"...


--
John Goodsen                           PCIS Programme
Software Process & Environments        Ada Joint Program Office       
EVB Software Engineering               goodsenj@ajpo.sei.cmu.edu
jgg@evb.com

Re: Real Time Scheduling Methods

[kronos.arc.nasa.gov!iscnvx!news]

------------------------- Original Article -------------------------
> No, there's deadline based scheduling.  Deadline based scheduling is
> incompatable with Ada, because it requires that the priority of each
> process be, at any instant, the deadline by which the process must
> complete its next critical action.  Once the process completes the
> action, it changes its deadline to the time of the next action (note
> that in Ada, priorities are fixed).

>  << additional good stuff about why it won't work for Ada deleted. >>

Okay, thanks.  I assume that every time a deadline is updated, so is
that task's priority.

Re: Real Time Scheduling Methods

[agate!doc.ic.ac.uk!uknet!yorkohm!minster!ken]

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"