From: lph@sei.cmu.edu (Larry Howard)
Subject: Re: Real_time systems
Keywords: non-preemptive scheduling
Organization: Software Engineering Institute
Date: Tue, 22 Dec 1992 10:31:05 EST

Andrew McRae writes:

> Preemption and priorities are a slippery slope; once you
> are on them, you quickly slide down into a sticky swamp. Why?
> Prioritisation implies preemption - there would be no point in
> having a higher priority task if it did not preempt a lower
> priority task. If you have preemption, then you have a problem
> with synchronisation and locking, especially with shared data structures
> such as lists and queues. Fine, you then add semaphores, messaging
> and mailboxes so that you can overcome the locking problems, but
> you have to ensure that preemption works properly and that
> tasks do not get switched in the middle of critical sections. So you
> add monitors, or have the concept of priviledge (priviledged sections
> do not get switched), and then after each monitor/semaphore you have
> checking for preemption... And then you find that your real time
> operating system has grown too big and slow for your real time
> processing needs, since it spends all its time locking and
> messaging and semaphoring and preempting, so you have to
> buy a bigger processor with more memory, and buy a more
> expensive licence for your whiz-bang real time OS.

While preemptive scheduling admittedly comes with an assortment of challenges,
let's not pretend that non-preemptive scheduling in hard real-time systems
doesn't provide a "slippery slope" of its own.

Simulating multiple periodic rates with a single control tread typically leads
to rate coercion into uniformly harmonic rate series.  This reflects minor
cycle frames as the basic scheduling quantum.  All periodic processing must be
allocated to such frames.  Schedulability analysis is an instance of the
bin-packing problem (which is NP complete.)  Under-packed bins (frames) lead
to dead time which decreases resource utilization.  Improving utilization
usually results in segmentation, which is an optimization on a given schedule.
Such segmentation leads to modifiability problems when the schedule must be
changed to reflect increased utilization within a given periodic activity.
The more finely tuned the schedule becomes, the more difficult it becomes to
change the "time line mosaic" as the system evolves.

Large hard real-time systems, such as flight simulators, often distribute
their processing across a number of computational resources.  In shared memory
multi-processing systems, concurrent execution leads to the same data
synchronization problems found with preemptive scheduling.  Solving these
problems leads to an additional optimization, where groups of periodic
activities with strong data dependencies are allocated to the same processing
resource.  This optimization results in the same schedule rigidity as before.
As the load on a given processor approaches its maximum potential,
re-balancing the load leads to additional data synchronization problems when
cooperating periodic activities are allocated to different processors.

My purpose here is not to argue for one scheduling discipline or another.
Such arguments must be made in context of a given application's functional and
non-functional attributes, together with some sense of the system's evolution.
Rather, my point is that the wealth of experience with non-preemptive
scheduling has motivated interest in alternatives, especially in the area of
distributed hard real-time systems.  As long as the use of non-preemptive
scheduling results in modifiability and extensibility problems, leading to
premature product mortality, this interest will likely remain strong.

 Larry Howard  (lph@sei.cmu.edu)                       |
 Software Engineering Institute, Carnegie Mellon Univ. | Vera pro gratiis.
 Pittsburgh, PA 15213-3890   (412) 268-6397/5857 (fax) | 
Xref: sparky comp.realtime:1475 comp.unix.ultrix:9043 comp.sys.m68k:1490