This is a work-in-progress, highly condensed, preview of my work-in-progress book An Introduction to Fundamental Principles of Dynamically Real-Time Systems [Jensen 2018].
This Introduction first briefly summarizes the keystone ideas that the book and this preview are about. Then it describes the topic of each chapter.
The book is primarily a scholarly monograph focused on conceptual foundations for the general case of real-time per se, which has dynamic timeliness and predictability of timeliness due to inherent epistemic uncertainties in the system and its operational environment.
In theory and in practice, an action, or a system of actions, provides a quality of service which 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.”
Timeliness and predictability of timeliness in the general case of real-time actions and systems of actions are subject to kinds and amounts of epistemic uncertainties about the actions, systems, and their operational environments. A system, or one of its agents such as a scheduler, may be partially or totally ignorant (at a particular time) of particular information about the system or its environment. Alternatively, information may be non-deterministic, and even not knowable with the desired accuracy and precision. Such systems are dynamically real-time ones, or by convention herein, simply termed dynamic real-time ones.
Analogously, driving from location A to location B in a vehicle on a congested highway during accident-prone bad weather, has a familiar real-time quality of service that is dynamic due to uncertainties. The arrival at location B is subject to contention for the driver’s availability, congestion and weather related vehicle speeds, driving skills and accidents, routes of different distances, satisfactorily operational condition of the vehicle, etc. The arrival time is not known for certain until it occurs, and predicting it prior to, and during, the trip uses uncertain or unknown information in an ad hoc manner. Note that handling this situation may differ between a personal trip and a commercial one (e.g., delivery vehicle).
This book and site are about solving problems similar to the analogy above—i.e., a scheduler seeking action and system timeliness and predictability of timeliness according to one or more optimality criteria, despite uncertainties—in a formal and automated way.
There are aspects of systems other than the real-time ones of timeliness and predictability of timeliness that make them dynamic in various ways and to degrees—e.g., being adaptable. Those aspects are relevant to dynamic real-time actions and systems, but as a topic per se, they are mostly outside the scope of this book.
Reasoning about dynamic real-time actions and systems (analogous to reasoning about the spectrum of paint colors) requires formalization of “timeliness” and “predictability.”
This book and site employ the time/utility (sometimes called time/value) function paradigm [Jensen 77, Jensen 85] as the basis for formalizing action and system timeliness. Although that paradigm has been discussed in many papers and dissertations, much more detail about it is provided here.
Formalizing predictability of timeliness in dynamic real-time systems usually requires application-specific use of a mathematical approach to dealing with uncertainties. There exists a variety of candidate mathematical approaches, each having specific conceptual and practical properties for different applications. A number of those which are potentially more relevant to general real-time are summarized in the book.
In particular, probability and predictability theories are introduced to synopsize the topic of probability interpretation and that topic’s relevance to general real-time systems. The widely familiar frequentist theory of probability (e.g., as applied to rolling dice) is the least applicable of those to dynamically real-time (and many other) systems. Alternative theories of probability are shown to be more useful for dynamic real-time systems.
One class of those theories is chosen to be explored more deeply here—the mathematical theories of evidence or beliefs. These theories use application-specific rules to fuse evidence or subjective beliefs from multiple sources in the system and its environment, to increase the credence of beliefs, or to form new beliefs, for decision making (e.g., action scheduling) and predictability (e.g., of schedule outcomes with respect to the scheduling criteria). This book primarily focuses on the Transferable Belief Model revision of Dempster-Shafer theory (itself a popular generalization of Bayesian theory).
Traditional real-time computing systems are shown to be relatively simple special cases of the general case, in which there are (presumed to be) no relevant uncertainties. It is not unusual to find researchers and practitioners struggling with little or no success to solve dynamic real-time problems with a static real-time mindset (cf. the Bed of Procrustes). The foundations of the general case also shed deep insights on the abilities and disabilities of the static special case. (Consider the analogy of black vs. not-black paint, compared with the whole paint color spectrum.)
This book provides a unique scholarly exposition of one set of 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 has been selected to be 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 (e.g., ignorance, non-determinism). 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, TUF) 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.
Chapter 4 emphasizes the Transferable Belief Model as the mathematical theory of evidence for the system models of primary interest in this book.
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