Stella External Event Management

 

Stella external event managers are extremely streamlined deadline and repetition rate task managers for external event handlers. By providing a highly efficient and fairly flexible sequencing for time critical handlers, they remove many of the problems previously encountered with this approach. In particular, under worst case conditions, they have overheads that are an order of magnitude lower than ordinary hardware prioritised interrupt handling schemes and two to three orders of magnitude lower than "conventional" real-time schedulers.

The external event manager provides a solution that is within one or two instructions per external event of an optimum hand coded state machine. In practice, this means that Stella can be used where an operating system (or even a simple executive) would previously have been unthinkable.

External event management principles

The Stella external event managers are based on a common interrupt system where all external events are channelled through a single interrupt vector. The appropriate handler for a particular event is found by scanning all the event sources until the event is found.

This approach is required for simple hardware environments without hardware vectoring, but it has a quite unjustified reputation for inefficiency: "modern" systems use hardware interrupt vectoring to call the interrupt server directly. It is true that for single, isolated, interrupts, scanning is less efficient than hardware vectoring. Under worst case conditions, however, scanning becomes more attractive. In the case where all the interrupts occur at the same time (close to the worst case for vectored interrupts) scanning is much more efficient than hardware vectoring.

That scanning is more efficient than hardware interrupt vectoring is, perhaps, counter-intuitive for engineers used to designing systems with hardware interrupts. After all, why waste time checking all the possible sources of external events when the hardware can call the code directly ?

This example is for two external interrupts only. The more sources of external interrupts there are, the greater the improvement that may be obtained by scanning rather than hardware vectoring. For a scanning system with a simple series of tests and handlers, there is no need for all the events to occur at the same time for scanning to be more efficient than hardware vectoring. The efficiency of hardware vectoring is

where Th is the (average) handler execution time
Ti is the interrupt call and return time
Tsr is the context save and restore time
While for scanning the efficiency is

where Tt is the event test and return time
m is the number of event sources
n is the number of events that overlap

Using typical values for critical interrupt servers (Th = 12, Ti = 8, Tsr = 10, Tt = 4 "standard" instructions) the efficiencies of the two methods are

0.4 (hardware vectors) and (scanning)


The efficiency of scanning depends on the number of events that can overlap

While the efficiency of the scanning approach is better than generally appreciated (particularly under heavy load conditions when the efficiency is most important), there are some drawbacks. If the scanning is "hard coded" within the handlers, the main problem is inflexibility.

Some of the inflexibility can be removed by using a table (vector) of tests and linkages. In principle it is possible add or change handlers and the table can have several interleaved tests for external events that are likely to occur very often.

Using a table in this way is only part of a solution. It not only makes the system less efficient, but it is still difficult to set up the tables to guarantee deadlines or repetition rates.

The Stella external event manager uses the same concept of a structure set up at run time as the table approach. It incorporates, however, three features that improve the efficiency, the simplicity of use and the flexibility.

  1. The structure is not held together by a table or vector of definitions, but by "in-line" code generated by the external event manager itself. This "threaded bead" approach costs one to two instructions more, per bead, than an optimum hard coded scanned solution. On most computers, this is a far higher efficiency than that provided by hardware interrupt vectoring.

  2. The system designer is not required to place the beads himself. The external event manager simplifies the design process by providing proprietary algorithms for placing the beads. The bead placement is based on timing information about the handlers and about the external events themselves.

     a. Each handler is characterised by:

     b. Each external event is characterised by:

     c. The whole collection of events and handlers is characterised by a single test for the presence of any pending event.

  3. The flexibility is maximised by run-time generation of the threaded bead structure. This enables new handlers to be added at any time, or existing handlers to be replaced or removed. The recalculation of the bead placement is a lengthy operation, but the replacement of an old threaded bead structure by a new threaded bead structure is a single instruction.
For maximum efficiency, the external event manager sets up a closed loop of beads and will stay in the loop until there are no more events pending. This requires an additional test to check whether there are any pending events. As this test is only performed if a test for a particular event is negative, and the test will usually be shorter than the whole of an event handler, this test is free: it has no impact on the performance under full load.

A further benefit of the threaded bead approach is that it provides automatic overload isolation. The response of each handler can be guaranteed even in the presence of an overload on one or more other handlers. Moreover, it is possible to detect overloads and take corrective actions even if the source of the overload is the highest priority event.

If the processor has more than one interrupt priority level, then the external event manager can generate separate threads for each level.

Run-time code generation

Not only does the external event manager perform run time code generation for threading the beads, it also generates code within the beads.

The design of the "operating system function calls" set up by the Stella external event manager results from breaking the principle Clean => Inefficient therefore Efficient => Dirty that is so dear to computer scientists.

External event handlers in Stella are invoked (via the external event manager) by interrupts. The efficiency of an external event handler is critical, not just for the efficiency of the system as a whole, but for the reliability of the system. If an external event handler spends too long treating one event, then other events may be missed. The true relationship for a reactive system is, therefore, Inefficient => Unreliable. But if Clean => Inefficient, then Clean => Unreliable. The logic is inescapable. The fault lies not in the logic, but in the artificial concept of inefficient cleanliness promoted by computer scientists.

A common requirement of an external event handler is to transfer data between internal data structures and peripheral hardware. It may be necessary, in addition, to notify a lower priority task that a transfer has been made (for example, a job may be waiting for data input). For conventional, inefficient operating systems, the additional cost of an operating system call is fairly small by comparison with the intrinsic costs of the operating system functions. For a Stella system, however, the most commonly used operating system functions for external event handlers are rarely more than half a dozen instructions and may only be a single instruction. Even the overheads of a direct operating system call would significantly reduce the system efficiency.

The solution adopted by the external event manager is to create the code for the operating system function "in-line". It does not just copy the code for the operating system function in-line into the program (no overhead) but generates optimised code that accesses the target data structures directly, creating a "negative overhead" operating system call.

No checks are required when invoking the direct operation on the data structures for two reasons.

  1. The "parameters" are checked when the code is created and they will still be valid when the function is used.

  2. The target data structures will either be owned by the operating system (and, therefore, permanent) or owned by an entity linked to the handler. This user linkage ensures that the data structures cannot disappear or become invalid while the handler is still using them.

The direct operation on the operating system data structures by an external event handler cannot, therefore, cause any reliability problems and this type of operating system "call" is, therefore,

Really Clean and Very Efficient.
 

  Back to table of contents.


Copyright (c) 1997 Tony Tebby.