Real-Time Updated on 25 September 2018 at 11:55 am

Deadline Semantics

Misconceptions about deadlines and completion time constraints in general drastically limit the possible kinds of real-time actions and systems that can be built, and the cost-effectiveness of those actions and systems.

Fortunately, there is a vast body of more general real-time principles and successful practices—but in fields other than, and little-known to, real-time computing [ ]. This generality has been demonstrated to be somewhat analogous to the capabilities gained (e.g., for physics, etc.) by generalizing from algebra to calculus.

In the field of conventional real-time computing, preferable is interpreted as acceptable vs. unacceptable—moreover, usually acceptable is defined as “correct” and unacceptable is defined as “failure.” Real-time computing practitioners use this special case interpretation as one of their various meanings for the term hard real-time. The real-time computing research community has near-consensus on this being the exact definition [ ].

That interpretation is essentially a confusion between the syntax and the semantics of a deadline, which actually are independent.

Syntax is concerned with the bare arrangement of expressions of certain types, such as an action’s time constraint (e.g., deadline), as discussed above. Semantics refers to the meanings of the expressions—e.g., what the consequences are of an action’s completion time with respect to its time constraint (e.g., deadline).

That popular interpretation of real time is a simple special case, limited in two fundamental respects to a small subset of how action deadlines are used in all human lives and almost all automated systems.

The first limitation is the exclusive view of an action either meeting or missing a deadline. The real-time computing field most frequently presumes that there is no preference for when a hard real-time action completes, if it meets its deadline [ ].

Less frequently, there is a need to know á priori what time (at or before its deadline) a hard real-time action will complete (given an assortment of static assumptions). This is the reason why there are hard real-time techniques and tools whose objective is for the hard real-time action to complete exactly at (not before or after) its deadline—i.e., in that case, optimum preferable—time.  In that sense, the action is harder than one which simply completes before its deadline. For example, cyclic executive scheduling intends to cause every action to complete exactly at its deadline (which is optimal in some cases) [ ], whereas rate monotonic scheduling can only cause every hard real-time action to meet its deadline [ ]—in both cases, subject to the required static conditions. One metric for characterizing how much more or less hard a hard real-time deadline can be, without being a soft real-time deadline, will be discussed below.

In all but a tiny percentage of real cases, an action’s completion time with respect to its deadline, and thus its acceptability, is not binary. Almost always, how long before, or how long after, its deadline that the action completes is more or less preferable in a situation-specific way. That is the general case semantic property of a deadline.

The physics of an operational context (athletic game, military combat engagement, etc.) implies the acceptability of completing a real-time action at any specified time tc. Completing that action at times after, or before, its deadline generally results in a greater or lesser preferable outcome. Outside the real-time computing communities, preference of outcomes are often specified in terms of utility, benefit, value, reward, or cost [ ]. The worst case real-time action completion time with respect to its deadline may be the soonest rather than the latest, or some time in between.

The standard scheduling theory terminology for any action’s completion time deviation either direction from its deadline is lateness [Pineto 2016]. Negative lateness, how soon an action’s completion occurs before its deadline, is called earliness. Positive lateness, how long an action’s completion occurs after its deadline, is called tardiness. Expressed arithmetically,

  • lateness tl = completion time tc – deadline td;
  • earliness te = max [0, – lateness tl];
  • tardiness tr = max [0, lateness tl].

Chapter 4 discusses the frequent case that actions may each have different positive or negative values corresponding to its lateness.

A small number of academic researchers on heavily static real-time computing systems have ventured into considering tardiness [ ].

The second limitation of this specific common hard real-time definition of real-time is the binary interpretation of preferable as correct vs. incorrect.

Well-known examples where that simple special case of hard real-time is essential include automated control of aircraft flight, nuclear power plants, railroad crossing signals, certain radiology medical devices, etc. Academic research on the conventional interpretation of real-time computing focuses almost exclusively on this precisely defined narrow, but often important, niche. That is primarily because the research is much easier than when lateness is included, and no exposure to the majority of non-trivial real real-time systems is required (or usually even feasible)—so starting there can be seen as practical. Unfortunately, almost no research progress has occurred in that community from that starting point toward the general and more widely useful general cases of real-time computing.

Real-time computing practitioners use the term “hard real-time” in a variety of different inconsistent (usually ill-defined) ways, infrequently including but not limited to the real-time computing researchers’ consensus definition—i.e., an action with a (hard) deadline is assured to be met if the presumed underlying strong conditions are satisfied. A popular class of examples is that an action (e.g., task) is defined as a hard real-time one by the duration of its execution—e.g., an interrupt or service response time action is often said to be a hard real-time one if it is real fast enough to meet a deadline of (say) 10 microseconds.

Understand that the degree to which an action is a real-time one is properly related to “real-fast” only in the mental model of minimizing manifestation latency (as opposed to the mental model of action time constraint based latency). Some of the world’s most important or dangerous real-time actions have deadlines that are seconds, minutes, even hours long—examples are in the Chapter 4 excerpts.