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].
This Introduction first briefly summarizes the keystone ideas that the book and its preview are about, and why I am writing about them. Then it describes the topic of each chapter.
The book is primarily a scholarly monograph focused on conceptual foundations for timeliness and predictability of timeliness, which are the essential properties of real-time systems–including, but not limited to, real-time computing systems.
There is a strong need for deeper and more general thinking about those two properties–particularly in the context of traditional real-time computing systems where habitual perceptions of them (and, indeed, of “real-time” per se) are ad hoc and very limited.
The most limiting of those perceptions is that (at least almost) everything which may affect timeliness and predictability of timeliness is certain and known a’ priori. That highly constrained system model, alluded to in various inaccurate ways by the real-time computing community as “hard real-time,” is a special case. That community has even less understanding of concepts and terminology for the general case of “non-hard real-time” (notably “soft 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 that special case categorization, it lacks the principles and vocabulary for reasoning about the whole rest of the spectrum.
Informally, the fundamental essence of real-time systems in general is that timeliness and predictability of timeliness are an integral part of their logic.
Most real-time systems in that general sense are inevitably subject to inherent uncertainties. Uncertainty can be understood as a condition of limited knowledge 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 dynamic real-time systems. 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 briefly introduced next (and are the topics of book and preview Chapters 2 and 3, respectively).
An informal dictionary definition of “timeliness” (say, of a happening) is “The fact or quality of being done or occurring at a favorable or useful time.” Obviously, in general there needs to be a formalism for specifying, measuring, and reasoning about “favorable” or “useful” with respect to a happening’s completion time. The traditional static real-time system model has no such formalisms except for its special case (“hard”). The real-time computing academic research community’s formalism is based on the deadline construct.
The deadline construct is far richer than the intuitive special case which is commonly used, that limits “favorable” and “useful” to “meet” vs.”miss.” Even when lateness is recognized and exploited (e.g., in scheduling theory), deadlines still have severe limitations–especially regarding expressiveness of the essential characteristic “favorable” or “useful” time.
The limitations of deadlines can be overcome by a more general construct for completion time constraints, of which a deadline is a special case. This book and preview provide the most detailed discussion ever published of such a construct, called time/utility functions (formerly time/value functions) [Jensen 77, Jensen 85]. It has a history of cost-effectiveness in encompassing a broader than traditional scope of real-time systems–especially (but not limited to) real-time ones whose timeliness is dynamic instead of conventionally static.
The fore-mentioned need to specify, measure, and reason about “favorable” or “useful” with respect to a happening’s completion time often–always in real-time (computing and other) systems–includes dealing with the predictability of timeliness.
Predictability is ubiquitously misunderstood within the field of real-time computing.
Something (e.g., a happening) being predictable means only that it is not unpredictable, it provides no information about how that happening’s predictability is defined, measured, and reasoned about. In particular, “predictable” does not mean deterministic, which is one of the formal representations for the maximum end-point on a scale of predictability. The logic of most real-time systems includes some intrinsic kind(s) and degree(s) of non-deterministic timeliness and predictability of timeliness.
To reason about predictability in the presence of uncertainties, probability theory may first come to mind. However, probability theory is only one approach of several for predictability; and there are multiple alternative theories (interpretations) of probability (e.g., frequentist, Bayesian); and probability is notoriously difficult and non-intuitive for most humans to understand.
The book addresses predictability (especially of timeliness) from a number of probabilistic and non-probabilistic perspectives. Those include predictability for cases of epistemic uncertainty (e.g., ignorance, non-determinism) which lend themselves to mathematical treatment in terms of belief functions–a class of functions that represent a body of evidence.
Timeliness and predictability of timeliness are the basis for what “real-time” means. The book addresses real-time initially for individual actions and then for systems of actions.
In theory and in practice, an action, or a system of actions, is a real-time one to the degree that its timeliness and predictability of timeliness are integral to the logic of the action 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—any more than paint colors are confined to being either black or not black.
Except when the topics of “degree” or “integral to” are discussed herein, it is often convenient to refer to that 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 service 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.
This book provides a unique scholarly exposition of one set of timeliness foundations for general real-time systems, based on explicit first principles, not on historical anecdotal artifacts as is normal. That necessarily requires correcting the babel about concepts and terminology which is endemic to the real-time computing field. Such confusion and inconsistency impedes the theory and practice of real-time systems, not only dynamic ones but even many static ones.
The purpose of this preview is to provide early access to some abbreviated and simplified content of the book. Writing the book is arduous, and must compete for time with my consulting tasks (and life).
Understanding the full length result will require considerable intellectual investment by the readers.
Early access to some keystone content of the book is important to the real-time computing community and to society, because there is great demand in various civilian and military domains for assistance with dynamic real-time computing systems. However, there is a negligible supply of real-time computer scientists and engineers with the requisite knowledge and experience (or interest) to satisfy those demands.
Instead, almost all practitioners and researchers in real-time computing systems have limited themselves to the minority of predominantly or entirely static ones.
Fortunately, there is a large body of widely used theory and practice for dynamic real-time systems outside the computing field. Consequently, meeting the demands for dynamic real-time computing systems with inherent uncertainties has been addressed by:
- application domain (military, industrial automation, telecommunications, etc.) experts but who usually lack substantive computer science, real-time computing, and uncertainty expertise;
- researchers in the disparate theoretical topics that enable dynamic and particularly dynamic 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 dynamic 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.
Unsurprisingly, most of the resulting dynamic real-time computing systems have left much to be desired functionally and non-functionally in comparison with dynamic real-time systems outside the computing field.
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 contributing to the creation of dynamic real-time (including, but not limited to, computing) systems. It takes a systematic (with limited formalisms) approach, using first principles, mental models, and a conceptual framework, to facilitate reasoning about dynamic real-time systems and epistemic uncertainties.
That approach is has been successfully applied to various extreme instances of wickedly dynamic and uncertain (e.g., military combat) real-time systems for many years. It has also been applied in a number of computing fields outside of real-time systems.
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 printed letter size 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 dynamic 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 have a vast body of deep philosophical and mathematical 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 dynamic 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. There, the core of making dynamic predictions and decisions under uncertainties includes mathematical subjective probability theories, using application-specific rules for fusing imprecise and contradictory multi-source beliefs about the system and its environment. It 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 completion times (i.e., scheduling). The mathematical theories of evidence discussed begin with Bayesian, and successively generalize to Dempster-Shafer theory, the Transferable Belief Model, and Dezert–Smarandache theory.
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 dynamic real-time systems, including computing systems and operating systems, that are based on dynamic real-time actions under uncertainties.
A system is characterized in 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) handles 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. Most scheduling optimization is NP-hard, so algorithmic scheduling heuristics and action dispatching rules are widely used.
In dynamic 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 system) have first order abstractions for action time constraint (e.g., deadline) and timeliness predictability, the scheduled actions must then be mapped onto the operational environment priority mechanism (which in general is also NP-hard).
Real-time computing practitioners most often do an ad hoc manual assignment of O(10) priorities to actions (e.g., tasks) based on application action semantics, instead of algorithmically scheduling the actions. The actions are then dispatched by the OS in schedule order by simply indexing the actions with semantic-free priorities. The priority indexing can be performed by the scheduler, but that choice (aside from related OS design issues) tends to cause confusion of scheduling with dispatching, and hence of ends vs. means.
The primary distinction of real-time systems resource management is that it is performed according to the application and system’s logic in terms of action (e.g., task) timeliness (e.g., deadlines) and predictability of timeliness. Mathematical theories of evidence have rules for combining multiple evidence-based analytical beliefs about happenings that may justify acceptably strong credence in one or more predicted beliefs—notably, about the outcome of a schedule. For example (here avoiding the actual mathematical descriptions): that (say) no more than 10% of the most important actions will be more than 25% tardy; or that (say) the actions’ accrued utility will be normally distributed with a mean at least 75% of its theoretical maximum, while no more than 50% of the actions will attain less than 80% of their individual utilities.
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 dynamic 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 dynamic 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, server farms, transaction systems, etc.).
Chapter 7 has a brief survey of some important open problems to be solved for dynamic 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 dynamic 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.
“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,
like inventing an environmentally-friendly fuel.
They identify new ones.”
—Michael Michalko, creativitypost.com