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

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 ?

• An interrupt server may interrupt any context and, therefore must save the context at the start of the server and restore it at the end. For scanning, the interrupted context needs to be saved only before the first handler to be called and restored only when there are no more events to be handled.
• The test will usually be the equivalent of 2 to 3 "standard" instructions and the return from the handler will also be the equivalent of about 2 "standard" instructions. For hardware vectoring, the cost of the interrupt and return from interrupt is usually of the order of 6 to 10 standard instructions.
• Under close to worst case conditions, nearly every test during the scan will be positive and so very little time will be "wasted" making negative tests.

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

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.

• It is not possible to add or change handlers.
• It is difficult to accommodate external events with widely different repetition rates.
• It is difficult to accommodate handlers with widely different execution times.

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:

   • the maximum number of machine cycles for the whole of the handler,
   • the maximum number of cycles up to each critical point in the code and
   • the code to test whether the handler is top be invoked.

    b. Each external event is characterised by:

   • the deadline from the event occurring to each critical point in the corresponding handler,
   • the maximum repetition rate,
   • the maximum burst rate (if different from the "normal" repetition rate) and
   • the maximum length of burst.

    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.

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

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,

  Back to table of contents.