Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!srcsip!klemmer!vestal
From: vestal@SRC.Honeywell.COM (Steve Vestal)
Newsgroups: comp.realtime
Subject: Re: Technical Details (was Re: Measuring timing of Realtime Systems)
Message-ID: <89135@srcsip.UUCP>
Date: 29 Aug 90 17:51:03 GMT
References: <9724@tekigm2.MEN.TEK.COM> <12582@netcom.UUCP> <182@srchtec.UUCP> <1990Aug29.152604.28573@zip.eecs.umich.edu>
Sender: news@src.honeywell.COM
Lines: 59
In-reply-to: walden@dip.eecs.umich.edu's message of 29 Aug 90 15:26:04 GMT

In addition to the rate monotonic and earliest deadline algorithms, there are
also cyclic scheduling and least laxity scheduling.

Least laxity scheduling, like earliest deadline scheduling, is a dynamic
priority algorithm that is feasible up to 100% utilization for arbitrary task
sets (which is not true for rate monotonic scheduling).  I believe it requires
that task execution time be declared to the scheduler in advance, but may
exhibit more desirable behavior in some overload situations than earliest
deadline scheduling.  Is anyone familiar enough with this algorithm to
describe its properties in detail?

Cyclic scheduling is more or less restricted to sets of tasks whose periods or
frequencies are multiples of each other.  A cyclic schedule consists of some
number of frames or cycles that are usually built by hand, where the cycles
are dispatched in round-robin fashion at the same frequency F as the highest
frequency task.  Each frame invokes the highest frequency task; a task whose
frequency is F/N is invoked every Nth cycle.  The general problem of producing
an optimal cyclic schedule is NP-complete (bin-packing can be reduced to this
problem).

My own opinion (which with $1 will get you a cup of coffee at some airports)
is that none of these are superior in all ways in all applications.  Here's
what I would look for:

Cyclic.  If processor utilization is low, the task set is small, and the ratio
         of the highest to lowest frequencies is reasonable (number of
         distinct cycles is reasonable) this has some things going for it.
         First, it has a simple implementation (a case statement in a handler
         for a periodic interrupt will do).  Inter-task communication is via
         parameters or global shared variables.  Skew, jitter and transport
         lag can usually be more easily controlled than with preemptive
         disciplines.  This is also extremely attractive for high-reliability
         systems (e.g. fly-by-wire).  The strictly deterministic nature of the
         schedule makes some people more comfortable, and there's almost no
         runtime scheduling code to certify.

Rate Monotonic: Although feasibility up to 100% utilization is not guaranteed
         for all possible task sets, it is for harmonic task sets.  Also, it's
         been shown that the expected breakdown utilization for a task set
         with a random mixture of frequencies is reasonably high (88% sticks
         in my mind).  For processors with prioritized interrupts and multiple
         timers, hardware priority can be used to get a simple high-speed
         implementation.  For harmonic task sets, a 	 self-interrupting
         handler can be used for a high-speed implementation.  Well-suited for
         languages that support static priority assignment (e.g. Ada).
         Solutions exist for supporting inter-task communication, aperiodic or
         event-driven tasks, modeling runtime overheads, graceful
         degradation during overload, and fault-tolerance for overrun/timing
         bugs.  My personal favorite if modularized, maintainable software is
         desired.

Dynamic Priority Disciplines: Don't know much about these, other than that
         they are feasible up to 100% utilization for arbitrary task sets.  I
         believe they may also have some advantages for providing graceful
         degradation during overload conditions.

Steve Vestal
Mail: Honeywell S&RC MN65-2100, 3660 Technology Drive, Minneapolis MN 55418 
Phone: (612) 782-7049                    Internet: vestal@src.honeywell.com