Real-Time for the Real World ™
Work-in-progress preview of a monograph:
Introduction to a Paradigm for
Timeliness and Predictability of Timeliness in Scheduling
of General Real-Time Systems
EXTENDED ABSTRACT
Numerous academic papers have been published about the Time-Utility Function/Utility Accrual (TUF/UA) real-time scheduling paradigm. Naturally, all have focused primarily on specific system models and specific instances of the paradigm. This monograph considers that paradigm more broadly.
TUF/UA is used for scheduling—the resolution of contention by a system’s actions for access to resources they share, by creating an access schedule of all ready requesting actions according to one or more optimality criteria. Various deadline-based scheduling algorithms are well-known [Pinedo 2022], and can be re-cast into the TUF/UA paradigm.
A system is a real-time one if its core properties of actions’ timeliness and predictability of timeliness are integral to its logic, not just to performance measures. In the real-time computing field, especially among practitioners, there is a large variety of ill-considered and conflicting “definitions.”a
The “timeliness” of a real-time action, using the TUF/UA paradigm, is more general than commonly thought. It is specified functionally as the application-specific utility the action contributes to the system at the time it completes. A conventional deadline is a special case in which the utility function is a unit-valued binary downward step at the deadline time.
“Predictability” and “predictable” are commonly misused in a binary sense—notably in the real-time computing field. The binary sense of “predictable”
In contrast, the most common example of using the term “real-time” is with respect to system performance, and refers to latency metrics. Typically, the primary latency metric is the time delay from when something happens (e.g., a stock’s share value changes), until that happening is manifest to receivers of that happenings’ notifications (e.g., stock buyers/sellers). Likewise, the secondary performance interest is typically the variability of that latency, most commonly called “jitter.” We informally say such systems are characterized predominately by how “real fast” they perform, rather than how “real-time” they operate. Systems often have application-specific combinations of real-time and “real fast” properties, so they must be characterized in both dimensions.
In general, the core properties (not just the usually presumed actions’ durations) of real-time systems are dynamic due to inevitable kinds and degrees of imprecisions and uncertainties in realistic everyday open worlda system models. Such systems constitute the spectrum of dynamically general real-time ones. Traditional (i.e., so-called “hard,” “firm”) real-time computing systems are narrow special (albeit often important) cases whose system models and core properties are predominantly static—or are treated as being (e.g., worst-case execution times)—and periodic. Dynamically real-time systems are often thought of as being instances of “soft” real-time ones, in various different ill-defined senses. However, none of those senses encompass the essential properties of “dynamic” intrinsic to open world real-time systems. Traditional real-time systems have very limited applicability compared to the general dynamic case. Dynamically real-time (including, but not limited to, computing) systems are widely used, often in application domains outside those of the traditional real-time computing field—thus are mostly unfamiliar to that field’s researchers and practitioners.
There is a great deal of research and development on the theories associated with the individual constituent properties of dynamic systems, such as imprecision and uncertainty. However, there is a lack of effort to formulate these results into coherent foundations general enough to express and achieve application-specific timeliness and predictability of timeliness in an adequate variety of dynamically real-time systems. This monograph summarizes one approach to that goal, by providing a mental model for scheduling in general dynamically real-time (including, but not limited to, computing) systems. Timeliness is dynamically expressive using my time/utility (née time/value) functions and utility accrual (née value-based) scheduling paradigm [Jensen 77] [Jensen+ 85] [Time-Utility Function] (TUF/UA). Schedules’ accrued utility and predictability of their timeliness require reasoning about them with some formal theories of uncertainty. Orthodox probability theory and even Bayesian probability theory cannot deal with the ignorance and paradoxical information which frequently occur in the reality outside of static closed world system models. This monograph briefly surveys some popular uncertainty theories which can do so, and focuses on applying belief-based theories—i.e., Dempster-Shafer (DS) theory and its subsequent derivations, such as the Transferable Belief Model. System model parameter imprecision is handled with a DS-related generalization of fuzzy set theory—i.e., epistemic random fuzzy sets.
The paradigm summarized here has been the topic of numerous academic research activities in a variety of contexts (see the references on the op. cit. Wikipedia page). More importantly, it has been successfully employed in a multiplicity of different applications—notably, many classified DoD real-time ones (e.g., mission and battle management, combat and surveillance platform management) having wickedly dynamic system models and core properties, where traditional static real-time perspectives and traditions were inadequate and counter-productive. The time frames of these contexts tend to range from milliseconds to megaseconds (recall from above, “real-time” is independent of “real fast,” contrary to popular misconception). However, from its inception and increasingly since, the TUF/UA paradigm—together with dynamic uncertainty accommodation—has often relied on sufficient performance of hardware augmentations (e.g., using multiprocessors/multicomputers, GPUs, FPGAs, custom ICs).
________
a. Note that “correctness” as a binary attribute is an important special case, but not the general case.
b. A closed world model represents total knowledge about everything in a particular system. An open world model represents partial knowledge where some things are known to be true, some are known to be false, some are unknown, and some are inconsistent.
N.B. There still are pages from the previous (c. 2008-2012) version of this site which I have not yet updated and integrated (or removed).