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

[Condensed excerpts from]
 Chapter 3: Predictability [Major update pending]


“It must, in all justice, be admitted that
never again will scientific life be as satisfying and serene
as in days when determinism reigned supreme. 

In partial recompense for the tears we must shed and the toil we must endure
is the satisfaction of knowing that we are treating significant problems
in a more realistic and productive fashion.”

— Richard BellmanAdaptive Control Processes: A Guided Tour


The excepts from Chapter 3 briefly over-view the second fundamental foundation of real-time, predictability of satisfactory action completion time and preference, despite dynamic uncertainties.

Predictability is a very much deeper topic than even graduate level statistics courses examine, contrary to how shallowly it is considered in the real-time computing communities. Here there is necessity and space for only a limited formality glimpse of the minimal fundamentals of predictability which are most pertinent specifically to timeliness quality of service of time-constrained (both conventional real-time, and especially the general case of dynamic real-time) actions and systems.

The real-time computing practitioner and research communities use the term “predictability” frequently, with little or no definition, and virtually always thoughtlessly confuse “predictability” with “deterministic.” This can have serious negative consequences.

Practitioners use the term primarily for latencies of non-sequenced actions such as interrupt response and system services. They tend to look for least upper bounds, and sometimes distributions. Predictability of actions’ (e.g., tasks’) execution completions is sometimes done with zero-laxity time division multiplexing of tasks—i.e., laying them out consecutively end-to-end, from each task’s beginning to completion, on an execution timeline (commonly called cyclic executives).

Researchers use the term for timeliness of sequenced tasks, such as meeting deadlines. They usually focus on the hard real-time special case that:

  • the sequencing criterion timeliness optimality factor is simply to meet all deadlines of periodic tasks (and sometimes to be fair to, non-deadline constrained tasks);
  • the predictability of that factor is limited only to presumably knowing in advance whether or not all the deadlines will always be met (e.g., with rate-monotonic analysis).

Predictability analysis for real-time actions, and achieving an optimum sequence of such actions, is generally computationally intractable (NP-hard) [ ]—but a variety of heuristic techniques can achieve acceptable (and sometimes arbitrarily close to optimal) results in many cases [ ], as discussed in the dynamic real-time systems Chapter 4.

Informally, something is predictable to the degree that it can be known in advance.

So there must be a process and metric for measuring that degree—i.e., making predictions. In the human cases such as when the action of arriving at your child’s school should complete, etc., the process and metric are informal—driving typically employs knowledge-based decision making that takes past experience and current data (e.g., accident and weather reports on the radio) into account.

But many cases—such as scheduling and driving commercial delivery trucks so they complete delivery actions on time, or scheduling missile course updates— benefit greatly from being based on formal (mathematical) predictability theory and models augmented by the operator’s knowledge and assessment of the circumstances. Non-human cases, such as data networks, factory manufacturing machines, etc., normally require analytical solutions for making predictions about an action’s completion time—whether in advance of, or during, the action’s operation. Dynamic real-time actions and systems, and even some non-trivial conventional real-time computing, are in this class.