Basic Real-Time Concepts -- Events and Determinism

Local Mobile Advertising
Local Coupons

Events and Determinism

In software systems, a change in state results in a change in the flow-of-control of the computer program. Consider the flowchart below.

The decision block represented by the diamond suggests that the stream of program instructions, can take one of two paths, depending on the response in question. if-then, go to, and case statements in any language represent a possible change in flow-of-control. Invocation of procedures in C and Ada represent changes in flow-of-control. In object-oriented languages, instantiation of an object or the invocation of a method causes the change in sequential flow-of-control. In general, consider the following definition.

Definition: Any occurrence that causes the program counter to change non sequentially is considered a change of flow-of-control, and thus an event.

 

In scheduling theory, the “release” time of a “job” is similar to an event.

 

Definition: The release time is the time at which an instance of a scheduled task is ready to run, and is generally associated with an interrupt.

 

Events are slightly different from jobs in that events can be caused by interrupts as well as conditional and unconditional branches.

 

Synchronous and Asynchronous Events

 

An event can be either synchronous or asynchronous. Synchronous events are those that occur at predictable times in the flow-of-control, such as that represented by the decision box in the flowchart  The change in flow-of-control, represented by a conditional branch instruction, or by the occurrence of an internal trap interrupt, can be anticipated (although it may not always occur).

 

Asynchronous events occur at unpredictable points in the flow-of-control and are usually caused by external sources. A clock that pulses “regularly” at 5 milliseconds is not a synchronous event. While it represents a periodic event, even if the clock were able to tick at a perfect 5 milliseconds without drift (which it cannot for physical reasons), the point where the tick occurs with the flow- of-control is subject to many factors. These factors include the time at which the clock starts relative to the program and propagation delays in the computer system itself. An engineer can never count on a clock ticking exactly at the rate specified, and so a clock-driven event must be treated as asynchronous.

 

Events that do not occur at regular intervals (or periods) are called aperiodic. Aperiodic events that tend to occur very infrequently are called sporadic.

 

Table below characterizes a sampling of events.

 For example, an interrupt generated by a periodic external clock represents a periodic but asynchronous event. A periodic but synchronous event is one represented by a sequence of invocation of tasks in a repeated, circular fashion, otherwise known as cyclic code. A typical conditional or unconditional branching instruction that is not part of a code block and that runs repeatedly at a regular rate represents a synchronous but aperiodic event. A branch instruction that happens infrequently, say, on the detection of some exceptional condition, is both sporadic and synchronous. Finally, interrupts that are generated irregularly (randomly) by an external device are classified as either asynchronous aperiodic or sporadic, depending on whether the interrupt is generated frequently or not with respect to the system clock.

 

 Determinism

 

In every system, and particularly in an embedded real time system, maintaining control is extremely important. For any physical system certain states exist under which the system is considered to be out of control; the software controlling such a system must therefore avoid these states. For example, in certain aircraft guidance systems, rapid rotation through a 180◦ pitch angle can cause loss of gyroscopic control. The software must be able to anticipate and avert all such scenarios.

Another characteristic of a software-controlled system is that the CPU continues to fetch and execute instructions from the program area of memory, rather than from data or other unwanted memory regions. The latter scenario can occur in poorly tested systems and is a catastrophe from which there is almost no hope of recovery.

Software control of any real-time system and associated hardware is maintained when the next state of the system, given the current state and a set of inputs, is predictable. In other words, the goal is to anticipate how a system will behave in all possible circumstances.

 

Definition: A system is deterministic if, for each possible state and each set of inputs, a unique set of outputs and next state of the system can be determined.

 

Event determinism means the next states and outputs of a system are known for each set of inputs that trigger events. Thus, a system that is deterministic is event deterministic. Although it would be difficult for a system to be deterministic only for those inputs that trigger events, this is plausible, and so event determinism may not imply determinism.

It is interesting to note that while it is a significant challenge to design systems that are completely event deterministic, and as mentioned it is possible to inadvertently to end up with a system that is nondeterministic, it is also hard to design systems that are deliberately nondeterministic. This situation arises from the difficulties in designing completely random number generators. Deliberately nondeterministic systems would be desirable, for example, as casino gambling machines.

Finally, if in a deterministic system the response time for each set of outputs is known, then, the system also exhibits temporal determinism.
A side benefit of designing deterministic systems is that guarantees can be given that the system will be able to respond at any time, and in the case of temporally deterministic systems, when they will respond. This reinforces the association of control with real-time systems.