schmitz@fas.ri.cmu.edu (Donald Schmitz) (09/28/90)
At my last job (I'm actually posting this from an account there), we wrote a
real-time development environment (named CHIMERA) for an embedded controller
used in robotics control research. The system was slightly different than
typical commercial systems, as the controller software was constantly being
modified, however the controller had fairly typical realtime requirements -
run several periodic tasks (that implemented sampled feedback control loops)
at precise intervals (1 to 100 millisec range) with hard deadlines, run
several less deterministic tasks at lower rates with soft deadlines, plus
execute various opportunistic tasks when CPU time was avialable.
The project was started while commercial products like VxWorks were still in
their infancy, and being a university, it was easy to justify writing our
own kernel, scheduler, etc. Our goal was to provide a threaded programmng
environment with real-time primitves that would allow writing the timing
dependent parts of the controller software in C, at a conceptual level above
the underlying hardware and scheduler. The programs ran on a dedicated
68020. We also wanted to make the primitive interfaces general enough that
we could transparently slide new algorithms under the applications. Not
being directly involved in real-time research, we had the advantage of not
knowing how hard this was. Our primitives went through several
design/implementation/application cycles, we ended up with the following,
which is still in use (I don't remember exact interface names, but the
semantics are correct):
For a thread to specify a deadline, there was:
void setDeadline(minCpuTime,maxCpuTime,deadlineTime)
This told the scheduler that the thread required at least minCpuTime,
and possibly maxCpuTime of CPU cycles, before deadlineTime arrived.
The min and max values were required to deal with tasks with variable
execution times. The scheduler assumed the task needed the max value,
however a deadline failure was not assumed until minCpuTime could not
be allocated. When a deadline failure was detected, an (optional)
exception handler was triggered, or the task reverted to a
non-deadline state. The exception handler could do things like modify
the thread's priority, longjump() the thread to a different state, set a
new deadline, or bring the system down. Curiously, this was one of
the features theoretical real-time people were really excited about,
but I don't think any of our applications ever used it (admittedly our
applications did not have to be 100% reliable).
For repetitive (not necessarily periodic) tasks, a variation was provided
for use in an "infinite" loop:
void deadlinePause(startTime,minCpuTime,maxCpuTime,deadlineTime)
The calling thread blocks until startTime, it then becomes active with
the specified CPU requirements and deadlineTime. A non-deadline pause()
interface was also provided, which took only a startTime argument,
and simply blocked until at least startTime.
In addition to the deadline interfaces, a thread could set two sorts of
static integer priority for itself - a "criticality" index which superseded
the deadline constraints, and a "user priority" index (its hard comming up
with different names for priority) which was used to settle deadline
scheduling ties. There were simple setxxx() and getxxx() interfaces
for this. These prioritys could be used to schedule a (sub)set of tasks
using a rate-monotonic model with fixed prioritys.
Synchronization was provided with classic P & V counter semaphores:
void P(semP) - blocking P (take semaphore) operation
int Peek(semP) - non-blocking P operation, returns outcome of attempt
void V(semP) - V (release semaphore) operation
These were more than spin locks, the system kept track of the threads
waiting on a semaphore and tried to award the semaphore to the most
important/critical thread when the current owner released it. We still
hadn't figured out how to deal with priority inversion when I left - it is
not obvious how to implement the priority inheritance algorithm with dynamic
(deadline) prioritys - but we felt we could fit it into the P/V interface.
For a practical solution, we suggested that sempahore locked code be kept
short, and provided an interface to disable pre-emption for use while
holding critical semaphores. Dealing with IO is a similar can of worms, we
used blocking IO based on the semaphore interface, and relied on intelligent
use by applications.
There were lots of other things we ended up providing, but these are
the primary real-time primitives. The scheduler (min laxity) had some
interesting ideas in it it too, but I don't have time to discuss it now.
Don Schmitz