This is a work-in-progress preview of my work-in-progress book An Introduction to Fundamental Principles of Dynamic Real-Time Systems [Jensen 2018].
The book is primarily a specialized monograph about timeliness and predictability of timeliness in the general class of dynamically (i.e., non-static) real-time systems, including computing systems and operating systems, of which traditional static ones are a notable special case.
There are aspects of systems other than real-time ones that make them dynamic in ways and to degrees—e.g., being adaptable. Those aspects are outside the scope of this book.
The book is not a tutorial or textbook about the whole topic of real-time systems.
It provides a unique scholarly exposition based on explicit first principles. That necessarily requires correcting the babel about concepts and terminology which is endemic to the real-time computing field. That confusion and inconsistency impedes the theory and practice of real-time systems, both static and dynamic ones.
The purpose of the preview is to provide early access to some abbreviated and simplified content of the book, because writing the book is arduous, and must compete for time with my consulting tasks (and life).
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 to satisfy those demands.
Instead, almost all practitioners and researchers in real-time computing systems have limited themselves to 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 has been addressed by:
- application domain (military, industrial automation, telecommunications, etc.) experts but who usually lack substantive computer science and real-time computing 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 computing 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 hard won personal experience (some good and some not so) 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 the topic and its constituent elements. That is essential for dynamically real-time computing systems, and valuable even for non-trivial conventional static ones.
This paradigm for dynamically real-time computing (and other) systems is not the only feasible one, much less for all applications. It is one I initially devised [Jensen 77, Jensen 85], is the most extensive one I am aware of in either public or proprietary use, and is one that has been successfully applied to various extreme instances of wickedly dynamic (e.g., military combat) real-time systems for many years. It has recently been the focus of a decade of academic Ph.D. research to further develop it since my original creation (my co-authors and I published 89 scholarly papers in ACM and IEEE computer science journals and conference proceedings in that decade [ ]). The paradigm can be (and has been) employed in different ways, ranging from being a mental model for improved insight into traditional static real-time concepts and technologies, to being partial guidance for developing and implementing actual dynamically real-time computing systems.
The opportunities in advancing both research on, and practice of, building and applying dynamic real-time computer systems offer major scientific, pragmatic, and financial rewards.
To make this preview readily accessible to an intelligent non-specialist audience, I am doing three things to reduce its breadth and depth.
First, I seek to limit the preview length drastically from the book length—e.g., from an estimated approximately 350 to approximately 50 printed 8.5″ x 11″ 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, and may lead to a sense of déjà vu in subsequent chapters. My intent is that for some readers, Chapter 1 alone might suffice, at least initially.
Thirdly, I seek to minimize the prerequisite mathematical and other analytical knowledge, by using language that is a compromise between informality and precision. Terminology that is helpfully and briefly used without definition is quickly revisited for explication.
The book itself is somewhat more demanding in parts. It requires a modest amount of maturity for reasoning about abstractions, problem solving, and making both conceptual and engineering trade-offs. It includes limited formalisms, such as some mathematics widely used in computer science (e.g., discrete mathematics, algorithm theory, data structures) and statistics (e.g., probability theory, stochastic processes), that fall within what most college STEM undergraduates either know or can easily learn sufficiently well.
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). Other references provide optional additional background outside the main scope of the book.
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 ones), at the level of their internals.
My many years of experience teaching and applying the material in this book has been that: in some cases, the less that people know about traditional static real-time computing systems, the more natural and easy they find this material; while in other cases, the more that people know about traditional static real-time computing systems, the more foreign and difficult to assimilate this material is. 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 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. As mentioned above, it 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, 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).
Chapter 3 provides an overview of predictability theories and metrics, especially for acceptably satisfactory action completion times—including the correct definitions of the essential terms predictable and deterministic that are widely 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.
The primary character of real-time systems is the management of software and hardware resources according to the application and system’s logic in terms of action (e.g., task) timeliness (e.g., deadlines) and predictability of timeliness (e.g., the probability that no more than 10% of the actions will be more than 25% tardy). The core of such resource management is acceptably satisfactory resolution of concurrent contending action requests to access shared resources (e.g., scheduling actions’ use of processor cycles) 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 uncertainties. Many uncertainties are inherent in the nature of the application (e.g., military combat), and others can be malicious. Both these forms of uncertainties are sometimes considered to be resource management adversaries. The algorithms and heuristics—notably for action sequencing (e.g., scheduling)—are normally far more sophisticated than those for static systems, so Chapter 4 is the most analytically challenging one.
Embedded systems also are briefly described 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 future work needed.
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., clouds, server farms, transaction systems, etc.).
Chapter 7 has a brief survey of some open problems remaining 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 [ ], 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.
I include a brief autobiography relevant to the topic of this web site.
Lastly is a Blog, both for my asynchronous thoughts on real-time systems, and for readers to interact with me.