From: varney@cbnewsd.cb.att.com (Al Varney)
Subject: Re: Real_time systems
Organization: AT&T Network Systems, Lisle, IL
Distribution: na
Date: Wed, 6 Jan 1993 04:52:41 GMT

In article <1992Dec22.041024.25911@megadata.mega.oz.au> andrew@megadata.mega.oz.au (Andrew McRae) writes:
>From article <1992Dec17.234430.18247@cbnewsm.cb.att.com>, by lfd@cbnewsm.cb.att.com (Lee Derbenwick):
>> In article <1992Dec16.120723.6377@lut.ac.uk>, R.Sheikhan2@lut.ac.uk (ZAGROS) writes:
>>> Is it true to say that, preemption is an essential characteristic of 
>>> a real_time system? if not how can we make sure that all tasks will
>>> meet their deadlines? 
>> 
>> "Preemption" assumes that you've got processes to be preempted,
>> which is already saying way too much.
>> 
>> A classic real-time technique is simply an infinite loop, which
>> calls one function for each "task" it needs to do.  Each function
>> is restricted to a maximum operating time (i.e., _they_ can't
>> have unrestricted loops), and the sum of all these times must be
>> less than the maximum tolerable latency for any action.  You
>> don't even need interrupts.

>>  --   Lee Derbenwick, AT&T Bell Laboratories, Holmdel, NJ

   Excellent description of the basic software in the No. 1/1A ESS(tm)
and 4ESS(tm) switching systems.  The former do use a single repeated
5 msec. interrupt to drive "timing-dependent" functions, because the
basic "peripheral hardware" doesn't buffer things like dial pulses and
DTMF digits.  The actual loop isn't really constrained to some fixed
time for each cycle, but the average time around the loop over time had
better be below a fixed time period -- if not, the offered load is above
your CPU capacity (you're in overload).  Adding a pre-emptive scheduler
in such an environment will just use up more CPU cycles, since the offered
load is beyond capacity.  The key is to have each "task" do a small amount
of work with very little overhead.  When "stitched" together, all the tasks
cooperate to perform useful work.

   Where pre-emption is needed is when "tasks" are added to such a system
that are not performing time-critical or capacity-related functions.
Thus the pre-emptive scheduler can "defer" these tasks and let the time-
critical tasks run.  Even if interrupts are needed in a system, one can
structure the non-critical tasks as pre-emptive and run the others in
a higher-priority "supervisor" or "kernel" layer using the infinite loop
technique.  Interrupts (other than sanity timers, routine timers and fault
detection) are usually a "bad" design idea for real-time systems.  After
all, it means that at peak load (max. interrupt rate), you're spending
a lot of CPU time saving/restoring process state.  Instead, spend those
CPU cycles "scanning" for work, which at peak load will usually be presented
to the CPU at just the rate it can get around to servicing it.

   Note that the "anti-interrupt" statement above means that the real-time
software/CPU will spend a lot of time in useless "scanning" when there's
very little load.  So what? -- unless you have something non-critical to
also run on the CPU, there isn't any more useful way to use up those CPU
cycles.  In the same two states, the pre-emptive/interrupt-intensive
model will do very well at small loads (CPU cycles are allocated well),
but will itself consume much of the CPU during peak load.

   Of course, bigger/faster CPUs fix the latter problem -- if they exist
and you can afford to replace what's "out there".

   Several AT&T products use the 3B20D(tm) processor as an embedded part
of the product.  The OS [UNIX(tm in transition] RTR) supports a kernel
with message passing, events, dynamically-loaded/replaceable device drivers,
etc. on a paged/segmented architecture.  The UNIX part is really a scheduler
with support processes that basically all run at USER levels.  But the
OS supports "kernel processes" at various priority levels, and provides
mechanisms supporting "light-weight processes" within the kernel.  The
combination provides for multiple "mini-OSes" running on the kernel, each
managing it's own processes.  UNIX is just one of those "mini-OSes".

   While not ideal, RTR does allow for some fairly efficient task execution
at the kernel process level (you don't have to have pre-emption of kernel
processes), and still gives you a UNIX environment at the USER level for
all those non-critical processes.  Seems like a reasonable trade-off to me.
(Still, in the end, the CPU has to eventually get around to running everything
or you're still out of capacity.)

   UNIX RTR is described in one of the Bell System Technical Journals
that was devoted to the 3B20 processor (the "D" in 3B20D is for DUPLEX,
a loosely-coupled dual-CPU reliable verion of the basic 3B20).  The early
fore-runner of RTR was called DMERT (Duplex Multi-Execution Real-Time),
which was an enhanced version of MERT, documented in one of the original
Bell System Technical Journal issues devoted to UNIX.  MERT ran on the
DEC PDP-11/70, and supported such things as DMA I/O direct to/from user
address space (even for block devices) and asynchronous I/O with event
waiting at the user level.  I can remember virtually stalling an 11/70
by doing a double-buffered tape-to-tape copy with 20K blocks -- the UNIBUS
just didn't have many cycles to spare when two tape devices were both
transferring data.  On the other hand, the tapes really MOVED!!!

>Having worked on embedded real time systems for 10 years, and
>written a number of embedded operating systems on various
>platforms, I heartily agree. I see a lot of companies selling
>whiz-bang `Real Time' Operating Systems that have complex
>priority and preemption schemes; especially true with the
>Unix-compatible systems, where non-realtime and realtime tasks
>are mixed (IMHO put the real time tasks where they belong - out
>of Unix and into embedded systems...)

>The complexity of these systems is mostly (I say again, *mostly*,
>not *always*) unwarranted and often add to the overall cost
>of the system (in terms of memory, CPU, software cost etc.)
>In the truly embedded world, it is often better to simplify
>the OS and make the processes/tasks running under it `co-operative',
>so that timing contracts are met.

   Well, I'll add my 20 years on to that -- interrupts and pre-emption
work well at SHARING a CPU, and there are lots of reasons to do that --
"real-time" and "sharing" just don't go together well.  Co-operative,
non-premptive methods, on the other hand, support the maximum utilization
of the CPU under load.  It's hard to believe an OS can support both needs
on the same CPU without supporting non-premptive tasks above pre-emptive
ones (support for communication with low/no interrupts may also be needed).

>I have come to the conclusion that preemption is to be
>avoided *if at all possible*, since it carries a lot of
>baggage with it. But having said all that, it certainly
>has its place outside of the hard real time world, ....

>Only my opinion, of course.
>
>Andrew McRae			inet:	andrew@mega.oz.au

Al Varney - just MY opinion, too.

Newsgroups: comp.realtime