Two Work-in-Progress Documents:
- A Preview of
- “An Introduction to Fundamental Principles of Dynamic Real-Time Systems”
E. Douglas Jensen
Revised 17 August 2017
This is a work-in-progress preview of my work-in-progress book An Introduction to Fundamental Principles of Dynamic Real-Time Systems.
The book is primarily a specialized monograph about timeliness and predictability in the general class of dynamic (i.e., non-static, as described in Chapter 1) real-time systems, including operating systems, of which traditional static ones are a notable special case. There are other aspects of systems 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 selected first principles. That necessarily requires correcting the babel about concepts and terminology which is endemic to the real-time computing field, which impedes the theory and practice of dynamic (and even many static) real-time systems.
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 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 who also usually lack substantive exposure to dynamic application domains.
The application domain experts almost always hold their dynamic real-time computing experiences to be proprietary. 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 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 dynamic real-time computing systems, and valuable even for non-trivial conventional static ones.
This paradigm for dynamic real-time computing (and other) systems is not the only feasible one, much less for all applications. It is one I initially devised [Jensen 76, 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 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 dynamic 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, Bayesian supervised learning), 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. 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. That includes: applications such as industrial automation control systems, robotics, military combat platform management, etc.; and operating systems, including substantive ones such as Linux kernel based or UNIX/POSIX based (not just minimal ones), at the level of their internals.
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, 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.
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 dynamic real-time computing systems, including operating systems, that are based on dynamic real-time actions. 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. Both dynamic real-time systems, and embedded systems, are explained in terms of first principles, mental models, and a conceptual framework.
Chapter 5 summarizes research on dynamic real-time computing systems by my Ph.D. students and co-advisor colleagues and I, and identifies future work needed.
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., clouds, server farms, transaction systems, etc.).
Chapter 7 has a brief survey of relevant work by some real-time computing systems researchers that is intended to nudge the field slightly away from its static niche.
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 also mentions other generic tools, such as MATLAB [ ], R [ ], etc., which also can be very useful.