Sunday, July 19, 2009

Overview of Fundamental Real-Time Concepts and Terms

This is a 1-page synopsis of my formulation of the most fundamental yet almost universally misunderstood concepts and terms of real-time computing. This formulation is elaborated on the pages listed in the right hand Outline column. This formulation has been demonstrated to greatly facilitate the cost-effective construction of real-time computing systems that are far more complex (e.g., dynamic, adaptive, distributed) than can be constructed using traditional ill-defined real-time concepts.

Real-time computing is about satisfying time constraints acceptably well with acceptable predictability according to application- and situation-specific acceptability criteria, given the current circumstances.

Thus, there are two fundamental factors involved in what "real-time," "hard real-time," and "soft real-time" mean:

bullettime constraints on individual activities;
bulletcriteria for using those time constraints to achieve system timeliness that is acceptably optimal with acceptable predictability.

Very often when people discuss what "real-time," "hard real-time," and "soft real-time" mean, they focus on the first factor and largely overlook the second this results in serious misunderstandings.

Time Constraints

Most systems (not just those that are commonly considered "real-time" ones) include activities that have time constraints i.e., activities that each have utility to the system as a function of when that activity completes. Such activities could be the conspicuous cornerstone of a time-critical targeting application [insert your own example here]), or they could be buried inconspicuously inside device drivers for a desktop PC operating system.

The most familiar example of a time constraint is a deadline, which is (properly but not popularly) defined as a time until which the activity's completion has more utility to the system, and after which the activity's completion has less utility.

A hard deadline is the special case where utility is the binary set {1,0}: completing the activity by the deadline results in the system receiving all the utility possible from that activity, and completing the activity after the deadline results in zero utility (i.e., resources consumed by the activity were wasted, such as when a message is transmitted from a satellite after it has dropped below the horizon [insert your own example here]) or some negative value of utility (i.e., the activity was counter-productive, such as when an incoming missile is intercepted by an anti-missile missile from its target when it is only 20 meters away [insert your own example here]).

The general case of a deadline (which is a soft deadline) has utility measured in terms of lateness (completion time minus deadline), tardiness (positive lateness), or earliness (negative lateness). Larger positive values of lateness or tardiness represent lower utility, and consequently larger positive values of earliness represent greater utility.

The significance of more or less utility in both the hard deadline and soft deadline cases is a system- or application- or situation-specific decision, and (contrary to popular mis-usage) is not part of the proper definitions of hard and soft deadlines. Missing a hard deadline may be either relatively insignificant (e.g., a sensor data sample is missed [insert your favorite example here]) or relatively significant (e.g., a torpedo alert is missed [insert your own example here]). Any given value of tardiness may be either relatively insignificant (e.g., affecting the battery power needed to transmit from a satellite as it declines toward the horizon [insert your own example here]) or relatively significant (e.g., affecting the circular error probability of kill [insert your own example here]).

Deadlines are not intrinsically short; they may be from microseconds to megaseconds, depending on the activity, application, and system. The magnitude of a deadline (how soon it is) is independent of the significance of meeting or missing it some short deadlines are relatively insignificant, and some long deadlines are safety-critical.

Beyond deadlines are more general time constraints e.g., specifying an activity's utility to the system as any function of when it completes. A hard deadline is the special case of a binary unit-valued downward step function, and a soft deadline is the special case of a particular 2-segment linear function. There are also other forms of time constraints. For simplicity and brevity on this page, we will confine our attention to the popular special cases of hard and soft deadlines. Additional information is provided on subsequent pages of this web, beginning with the time constraints page.

Scheduling Optimality Criteria

A system typically includes a multiplicity of actions; at any particular time, some of these actions are ready to execute. In a uniprocessor computer (assumed here for simplicity), only one action can execute at a time, so the action executions need to be sequenced (scheduled or dispatched; the distinction is outside the scope of this page). Usually some sequences of action executions are considered better than others, according to some goal; the goal is formally called the "sequencing optimality criterion".

When the actions have deadlines, the ideal goal is for the system to always meet all of its actions' hard and soft deadlines (the goal normally has other factors also, such as satisfying precedence constraints and resolving resource conflicts, which we disregard here for simplicity). Circumstances may make meeting that goal either not cost-effective, or not possible at all. Frequent examples of such circumstances include: the combination of the actions' deadlines and execution durations; conflicts among the actions for shared resources; the failure of some resources. Given those circumstances, the goal becomes to meet the deadlines as best as possible.

For hard deadlines, "as best as possible" means always meet all the hard deadlines if possible, otherwise change the hard deadline actions in some way to make it possible this is normally done statically by a' priori analysis and scheduling of the actions, or by execution time action admission control.

For soft deadlines, "as best as possible" often means minimize the number of missed soft deadlines or the mean tardiness of the soft deadlines (there are many other possible and popular sequencing goals for soft real-time actions, but we limit ourselves on this page to these two for brevity and simplicity) this may be done either statically a' priori, or dynamically at execution time.

Sequencing goals have two components. The first component is to meet all the hard deadlines, and/or to minimize the number of missed, or the mean tardiness of, the soft deadlines; this is the optimality component of the goal. The second component is how much can be known about that optimality (number of missed deadlines, etc.) before the activities execute; this is the predictability component of the goal.

If the sequencing optimality that will be attained is known exactly, in advance of all the activities completing execution, then the optimality is deterministic this applies both to hard deadlines (it is known in advance that all deadlines will always be met) and soft deadlines (it is known in advance what the number of missed deadlines or the mean tardiness will be). Otherwise, the predictability of the optimality is non-deterministic (usually considered to be stochastic). Deterministic timeliness requires deterministic characteristics of the actions, the system, and the execution environment. Dynamic uncertainties in those characteristics necessitate non-deterministic sequencing optimality.

Predictability is a continuum, with determinism being the maximum predictability end-point. The minimum predictability end-point is that nothing is known a' priori about the optimality which will be attained. (There are various predictability models with analytical measures, but these are outside the scope of this page, and are discussed on a subsequent page.)

System-, application-, and situation-specific acceptable sequencing optimality, and acceptable predictability of that optimality, are essential to the correctness of a system's real-time (i.e., time-constrained) actions. Such timeliness is integral to the logic of the application. This is equally true for actions with hard or soft deadlines. Systems with non-real-time (i.e., non-time-constrained) actions have sequencing goals for those actions (usually focused on system throughput and fairness) with optimality and predictability components but those goals are only for performance rather than for correctness, they are not integral to the logic of the application.

A system having only actions with hard deadlines, and a sequencing goal of always meeting all those hard deadlines (i.e., deterministic maximum sequencing optimality), is a hard real-time system. Many systems have mixtures of hard and soft deadlines, and thus their sequencing goals are that all hard deadlines be met deterministically, and that the number of missed (or tardiness of) the soft deadlines be acceptably low and have acceptably high predictability. Such systems can be said to be hard real-time systems to the degree that they have hard versus soft deadlines.

The theory and techniques employed to guarantee that hard deadlines will always be met are much simpler and more commonly understood than the theory and techniques employed (a' priori or at execution time) to assure that soft deadlines will attain acceptable sequencing optimality and predictability of that optimality. In other words, "Hard real-time is hard, but soft real-time is harder." For this reason, the soft deadlines that are intrinsic to most systems are usually transformed into artificial hard deadlines. This results in the need for increased resources (because the requirement for deterministic characteristics of the activities, system, and environment requires resources to be reserved for the worst cases); consequently, the system is less adaptable to changes.

No comments: