TruePERSPECTIVES_logo.png

Understanding Predictability in Real-Time Systems

Posted by Guest Blogger on Sep 28, 2015 8:22:14 PM

The following is a guest post by veteran developer E. Douglas Jensen. Doug is internationally recognized as one of the original pioneers and leading visionaries of distributed real-time and time-critical computer systems. His principal interest is advancing and applying the principles and best practices in the field of time-critical embedded systems for control applications at all levels of an enterprise. He has four decades of performing system architecture, detailed design, and software/hardware implementation on the system's entire life cycle-from initial requirements to deployment to product improvements.You can follow Doug on Facebook.

NOTE: We are looking for more guest contributors to our blog. If you have an interesting perspective on embedded development or tips and techniques you want to share with your fellow developers, please contact Stephen Martin (stephen.martin@atollic.com).

Predictable is not the same as deterministic

Virtually everyone's personal and professional lives--and a great many physical, chemical, etc. processes--have numerous actions with a property that I term timeliness quality of service (QoS).

This timeliness QoS property is an integral part of the logic of the actions, not (for example) a performance metric of the action's logic, such as "how fast" an action takes place.

An action's timeliness QoS property has two keystone elements:

  • the action's completion time constraint (a deadline is a familiar, simple special case)
  • the predictability of the action's completion time with respect to the time constraint (always meeting all deadlines is a familiar, simple special case).

Completion Time Constraint

Because time constraints so often are, or involve, deadlines, it is important to clarify the principles of a deadline. In particular, a deadline time constraint is not binary (miss, meet), it involves more than a single point in time, instead it includes the times on each side of the deadline time.

Consider an action to take your child to school. That action has a timeliness QoS: the school has a deadline for students arriving. Leaving your child at school too much earlier than the deadline ("earliness") may have some kinds and degrees of negative consequences to the child, depending on how early and the situation. Likewise, leaving your child at school too much time after the deadline ("tardiness") may have some kinds and degrees of negative consequences to the child, depending on how tardy and the situation. The case of picking up your child from school is similar, but earliness and tardiness have consequences different from the drop off times. There is a time interval containing the deadline (not generally symmetrically) for each of these two actions, during which the action's timeliness QoS is satisfactory to the parent and the school.

The deadline time separates earliness from tardiness. The standard technical definitions of earliness and tardiness are that they are negative and positive "lateness," respectively. More precisely: lateness = completion time - deadline; earliness = max [0, -lateness]; tardiness = max [0, lateness].

A deadline signifies urgency. But it does not specify or even imply the consequences of an action's timeliness QoS. This is contrary to the simple special case that the conventional real-time computing field limits itself to--i.e., that an action which misses its deadline has failed or is incorrect. In most of the real world, an action's timeliness QoS has application- and even situation-specific consequences.

There are many cases where an action missing its deadline may result in timeliness QoS which is less satisfactory than when the action meets its deadline. For example, a computation that misses its deadline may produce results that are less useful (lower quality, overwritten input data sample, etc.). Conversely, an action that completes too early also may produce results that are less useful than if it had completed closer to its deadline.

The conventional real-time computing field focuses on the binary consequences of an action missing or meeting a deadline, but does not consider that an action which completes too early may also have timeliness QoS with negative consequences, including action failure or incorrectness.

An action's time constraint need not be or have a deadline. In general, the consequences of an action's timeliness QoS are defined and measured in an application- and situation-specific way. An action's "utility" is some function of its completion time (and other factors, such as relative importance, discussed later)--whether conventional real-time computing's simple unit binary value set {0,1} interpreted as action failure vs. success, or an arbitrary function f{t,…} defining an appropriate utility value.

The predictability of the action's completion time

Predictability per se, and more generally uncertainty, are extremely complex topics-there are many academic research books, and professional society journals and conferences, on uncertainty in general and specifically on predictability.

Very few of the principles and practices of predictability are at all familiar to the conventional real-time computing community. Consequently in that community there is no consensus on the concept of predictability--it is almost universally misunderstood in various ways. Thus, conventional real-time concepts and techniques are not applicable beyond that niche in the general case.

In general, the vast majority of non-human and human actions (and systems) have timeliness QoS properties. Here there is necessity and space for only an informal glimpse of the minimal fundamentals of predictability which are most pertinent to timeliness QoS and real-time computing.

Informally, "predictability" of something (e.g., the time when an action completes) is the degree to which 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, benefit greatly from being based on formal models augmented by the drivers' knowledge and assessment of the circumstances. Non-human cases, such as data networks, factory machines, etc., normally require analytical solutions for making predictions about actions (e.g., completion times)--whether in advance of, or during, the action's occurrence. Most timeliness QoS and non-trivial conventional real-time computing are in this class.

The most commonly thought of model for predictability is frequentist (sometimes called physical) probability theory. There are alternative theories of probability, popularly Bayesian, Dempster-Shafer, and others--these are typically more effective for predictability in timeliness QoS (and other purposes). But because the frequentist theory is best known, it is used for discussion here.

Since there are degrees of predictability, that continuum of probability distributions has two end-points. The maximum predictability end point is obviously the deterministic distribution--e.g., the action completion time is deterministic (known in advance). The minimum predictability end point would obviously seem to be the uniform distribution (but subject to complications out of scope in this post)--the action is equally likely to complete at any time, and thus is maximally non-deterministic. Everywhere between these end points are probability distributions corresponding to degrees of non-determinism--e.g., about the action completion time.

This shows that non-determinism is the general case of predictability (the whole continuum of probability distributions), and determinism is the special case end point of predictability (the deterministic distribution).

Conventional real-time computing is limited to the deterministic special case, and timeliness QoS accommodates reasoning about the whole continuum of non-determinism, including the deterministic end point.