This is a work-in-progress, highly condensed and less formal, preview of my work-in-progress book An Introduction to Fundamental Principles of Timeliness in Dynamically Real-Time Systems [Jensen 2018].
The purpose of this preview is to provide early access to some abbreviated and simplified content of the book, with the hope of fostering new research on its topics.
This Introduction first briefly summarizes the keystone ideas that the book and its preview discuss, and why I am writing about them. Then it describes the topic of each chapter. It is prerequisite reading for the rest of the preview.
Most people implicitly have an informal mental model that considers information or an event as being “real-time”
- if, or to the extent that, it is manifest to them with a delay that can be related to its perceived currency
- i.e., in a time frame that the information or event has satisfactory usefulness to them.
That mental model is meaningful, but reasoning about it requires some formalization.
The book is primarily a scholarly monograph focused on conceptual foundations for timeliness and predictability of timeliness, which are the two keystone properties of real-time actions and systems—including, but not limited to, real-time computing ones. The archetypal use of those properties in real-time computing systems is for scheduling tasks or exogenous physical behaviors.
There is a strong need for deeper and more general thinking about timeliness and predictability of timeliness, based on first principles (i.e., axiomatically, deductively). That thinking is conspicuously lacking in the context of traditional real-time computing systems, where habitual misconceptions of those properties (and, indeed, of “real-time” per se) are ad hoc and very limited (the book provides numerous examples).
A first principle for the general case of real-time systems is that they are unavoidably dynamic due to intrinsic epistemic uncertainties—e.g., ignorance, imprecision, non-determinism, conflicts—in the system and its application environment.
An important example is that dynamically real-time systems are common in (but not limited to) the defense domain, where they are often exceptionally mission- and safety-critical. They may require the strongest feasible assurance of satisfactory timeliness and predictability of timeliness despite those adverse uncertainties. Guaranteed ideal timeliness and predictability of timeliness in dynamically real-time systems is a physical impossibility (for example, in the defense domain, cf. The Fog of War).
Traditional real-time computing system concepts and techniques are for a narrow (albeit important) special case, based on presumed a’ priori omniscience of a predominately static periodic-based system model. They are not applicable to the general case of dynamically real-time systems which dominate the real world.
There is a strong need for deeper and more general thinking about timeliness and predictability of timeliness, based on first principles (i.e., axiomatically, deductively). That is particularly necessary in the context of traditional real-time computing systems where habitual misconceptions of those properties (and, indeed, of “real-time” per se) are ad hoc and very limited (the book provides numerous examples).
The first primary limitation of those misconceptions is that (at least almost) every aspect which may affect system timeliness and predictability of timeliness–usually of a group of tasks–is certain and known a’ priori.
One of those aspects, task execution times, receives extra attention because even if a task is simple enough that its execution time as a program can be established, its actual execution time on most computers is typically quite variable. The real-time computing community seeks to eliminate that uncertainty by determining a (usually approximate) worst case upper bound so one or more such tasks can be treated as having static execution times (cf. Procrustean).
The second primary limitation is that moreover, those static aspects–e.g., task arrivals, task periods, task execution durations, task deadlines–are confined to predominately periodic instances, and consequently overloads and task resource conflicts are presumed to be avoidable.
That highly constrained system model, referred to in various imprecise ways by the real-time computing community as being “hard real-time,” is a special case.
That community has even less understanding of concepts and vocabulary for the general, and more frequent and difficult, case of “not hard real-time”–notably “soft real-time.” “Firm real-time” is a misnomer for a subset of soft real-time systems, as shown in the chapter on real-time.
Analogously, categorizing the spectrum of paint colors to be only “black” and “not black” is a very myopic perspective on the real world. Regardless of how much one might be able to say about the special case of the color “black,” that categorization lacks the concepts and vocabulary for reasoning about the whole paint color spectrum.
A lexicon for hard real-time and soft real-time actions and systems is rigorously defined in the book, and summarized in this preview.
Most real-time systems in the general sense are inevitably subject to kinds and degrees of inherent uncertainties. Uncertainty can be understood as a condition of limited knowledge–e.g., due to ignorance, randomness–in which it is impossible to exactly describe the state of the world or its future evolution. Uncertainties necessarily cause timeliness and predictability of timeliness to be dynamic–e.g., variable, unknown, or non-deterministic, before and during system operation.
Hence the book emphasizes fundamental principles of timeliness and predictability of timeliness for that general case of dynamically real-time systems subject to uncertainties. Those principles scale down to encompass the niche static special case as well.
(There are aspects of systems other than timeliness and predictability of timeliness that make them dynamic in various ways and degrees—e.g., being adaptable. They are outside the scope of this book.)
Timeliness and predictability of timeliness are the topics of book and preview Chapters 2 and 3, respectively.
Timeliness and predictability of timeliness are the basis for what “real-time” means. They are integral to the logic of a real-time action (e.g., computational task) or system.
“Integral to” includes, but is not limited to, the correctness (whether binary or not) of that logic. Thus, in principle, an action or system of actions is not confined to either being a real-time one or not being a real-time one.
Herein it is often convenient to refer to that general class of actions and systems simply as “real-time” ones.
Note that the time frame(s)—e.g., whether microseconds or megaseconds—of a real-time action or system are encompassed in “integral to,” and are not per se part of the definition of “real-time.” Imagining that “real-time” is the same as “real fast” is an instance of being confused about one of the semantic aspects of timeliness.
Fortunately, there is a large body of widely used theory and practice for dynamically real-time systems outside the computing field. Consequently, meeting the demands for dynamically real-time computing systems with inherent uncertainties has been addressed by:
- application domain (military, industrial automation, telecommunications, etc.) subject matter experts but who usually lack substantive computer science, real-time computing, and uncertainty expertise;
- researchers in the disparate theoretical topics, such as mathematical uncertainty models, that enable dynamic and particularly dynamically real-time computing systems—but who too usually lack the same substantive computer science and real-time computing expertise as do the application domain experts, and also usually lack substantive exposure to dynamic application domains.
The corporate application domain experts almost always hold their dynamically real-time experiences to be proprietary, and the military experiences are usually classified.
The theoreticians write in the jargon of their fields and publish in forums of their fields. Few computer scientists and engineers, and application domain experts, have the time and inclination to even discover these results, much less attempt to understand and apply them.
This book seeks to help bridge at least part of that gulf using a combination of both innovative and extant principles from both sides—together with decades of hard-won personal experience with various extreme instances of wickedly dynamic and uncertain (e.g., military combat) real-time systems.
It provides a unique scholarly exposition of one set of timeliness and predictability foundations for general real-time systems, based on explicit first principles, not on historical anecdotal artifacts as is normal in the real-time computing field.
That necessarily requires correcting the babel about concepts and terminology which is endemic in that field. Such confusion and inconsistency impede the theory and practice of real-time systems, not only dynamic ones but even many static ones.
“Typically, we think reproductively—that is, on the basis of similar problems encountered in the past. When confronted with problems, we fixate on something in our past that has worked before. We ask, “What have I been taught in life, education or work on how to solve the problem?” Then we analytically select the most promising approach based on past experiences, excluding all other approaches, and work within a clearly defined direction towards the solution of the problem. Because of the soundness of the steps based on past experiences,
we become arrogantly certain of the correctness of our conclusion.
In contrast, [one should] think productively, not reproductively. When confronted with a problem, [one should] ask “How many different ways can I look at it?”, “How can I rethink the way I see it?”, and “How many different ways can I solve it?” instead of “What have I been taught by someone else on how to solve this?”
[Then people] tend to come up with many different responses,
some of which are unconventional and possibly unique.
In order to creatively solve a problem, the thinker must abandon the initial approach that stems from past experience and re-conceptualize the problem.
By not settling with one perspective, [people] do not merely solve existing problems,
They identify new ones.”
—Michael Michalko, creativitypost.com
To make this preview readily accessible to an intelligent non-specialist audience, three things reduce its breadth and depth.
First, the preview length is drastically limited from the book length—e.g., from an estimated 350 to approximately 50 pages. That entails judicious selection, and concise re-writing, of only the most fundamental and easily understandable topics.
Second, Chapter 1 of the preview is relatively comprehensive and self-contained, given that it is just the first part of a preview (which may lead readers to a sense of déjà vu in subsequent chapters). The intent is that for some readers, Chapter 1 alone might suffice, at least initially.
Thirdly, the prerequisite mathematical and other knowledge is reduced by using language that is a compromise between informality and accuracy.
The book itself is somewhat more demanding in parts than this preview. It requires a modest amount of cognitive maturity for abilities such as: learning unfamiliar concepts; reasoning about abstractions; problem solving; and making both conceptual and engineering trade-offs between algorithms and efficient implementations of them.
Some of the book’s references provide remedial coverage of formal topics that readers may need, such as for optimization (e.g., non-deterministic scheduling algorithms) and subjective probability theories. Other references provide optional additional background outside the main scope of the book. In this preview (but not the book), no-cost on-line references are chosen as much as suitable.
The readers of the preview and the book are expected to have experience with some non-trivial systems which are considered to be real-time ones according to some plausible definition. Examples include: real-time applications such as industrial automation control systems, robotics, military combat platform management, etc.; and real-time operating systems, including substantive ones such as Linux kernel based or UNIX/POSIX based (not just minimal embedded ones), at the level of their internals.
Many years of experience teaching and applying the material in this book have shown that: in some cases, the less that people know about traditional static real-time computing systems, the more natural and easy they find much of this material; while in other cases, the more that people know about traditional static real-time computing systems, the more foreign and difficult it is for them to assimilate this material. Chapter 1 discusses that dichotomy, and the sociology and psychology behind it—but that is not in this preview.
The book’s Chapters 1, 2, and 3 focus on dynamically real-time at the level of individual actions, such as tasks or threads executing in computing systems, and physical behaviors performed by exogenous non-computational (e.g., mechanical) devices.
Chapter 1 is about the general necessity for the concept of real-time actions and their properties, especially dynamic ones, to be based on first principles, mental models, and conceptual frameworks. The minimal basics of epistemic uncertainty and alternative probability interpretations are introduced. As noted above, Chapter 1 also deliberately seeks to serve as an extended abstract for the first three Chapters. (Attempted inclusion of Chapter 4 in Chapter 1’s abstract role has thus far made Chapter 1 too long and difficult, but an eventual revision of Chapter 1 may yet accomplish that inclusion.)
Chapter 2 discusses action completion time constraints, such as deadlines and time/utility functions, and expressing those in ubiquitous priority-based execution environments (e.g., operating systems).
Most of the concepts and techniques in Chapters 3 and 4 drawn on a vast body of deep mathematical and philosophical theory, and a great deal of successful use in a variety of applications outside of real-time systems. The point of these chapters is to briefly introduce readers to using those concepts and techniques in dynamically real-time systems. Innate complexity, divergent viewpoints by probability theory and uncertainty researchers, and unsolved problems make these chapters somewhat difficult.
Chapter 3 is focused primarily on the very complex topic of predictability, for resolving dynamic resolution of contention for shared resources (e.g., scheduling) and predicting the outcomes, particularly timeliness—in the presence of uncertainties.
The book provides an overview of some important probability interpretations for that purpose, and some predictability theories and metrics—especially for acceptably satisfactory predictions of acceptably satisfactory action and schedule completion times. It begins with the familiar viewpoint of traditional probability theory. Then it re-focuses on alternative predictability theories unfamiliar to the book’s presumed readership. These are needed for reasoning about richer (e.g., epistemic) uncertainties. They include mathematical theories of evidence (i.e., belief theories), which use application-specific rules for combining imprecise and potentially contradictory multi-source beliefs about the system and its environment to form new beliefs.
As a side effect, Chapter 3 provides the correct definitions of the essential terms predictable and deterministic that are ubiquitously misunderstood in the real-time computing practitioner and even research communities.
Chapter 4 addresses dynamically real-time systems, including computing systems and operating systems, that are based on dynamically real-time actions under uncertainties.
A system is characterized in large part by its system model. That defines properties such as of its actions, and of how the system’s resource management agents (such as a scheduler) handle actions according to specified optimality criteria including (but not limited to) actions’ timeliness and predictability of timeliness.
The essence of system resource management (especially by operating systems) is acceptably satisfactory resolution of concurrent contending action requests to access shared hardware and software resources (e.g., scheduling actions’ use of processor cycles and synchronizers) according to application-specific optimality criteria.
In dynamically real-time systems, that resolution must be acceptably satisfactory despite the number and kinds and degrees of epistemic uncertainties. Uncertainties must be accommodated by the system resource management agent(s) (e.g., scheduler) obtaining and refining credence of beliefs about the current and time-evolution state of the system, using an appropriate mathematical theory. On that basis, resource management decision (e.g., action schedules) are made.
Because almost no operation environments (e.g., operating systems) have first order abstractions for action time constraints (e.g., deadlines) and timeliness predictability, the scheduled actions must then be mapped onto the operational environment priority mechanism.
Embedded systems also are briefly described in Chapter 4 because of their close relationship to real-time systems: most real-time computing systems are embedded; and many embedded systems are real-time to some degree.
Chapter 5 summarizes research on dynamically real-time computing systems by my Ph.D. students and co-advisor colleagues and I, and identifies some of the future work needed to expand on that. Those research results in their published form may be analytically challenging for some readers, but the chapter summarizes their important contributions.
Chapter 6 illustrates dynamically real-time computing systems and applications with examples inspired by my professional work, using material (re-)introduced in this book. It also shows some examples of how the paradigm is being employed outside the field of real-time systems (e.g., high performance computing, clouds, web server farms, transaction systems, etc.).
Chapter 7 has a brief survey of some important open problems to be solved for dynamically real-time systems. It also notes relevant work by researchers inside and outside the field of real-time systems.
Chapter 8 describes the need for software tools appropriate for thinking about, demonstrating, and designing dynamically real-time computing systems. It describes one open source program for doing so using material from this book [ ]. It mentions generic tools, such as MATLAB [ ], R [ ], Stan [ ], JASP [ ], etc., which can be very useful.
Chapter 9 is a annotated list of selected references, primarily by members of my research teams, plus relevant papers and books by other authors.
A brief autobiography relevant to the topic of this web site is included.
Lastly is a Blog, both for my asynchronous thoughts on real-time systems, and for readers to interact with me.