[Condensed excerpts from]
Chapter 2: Action Time Constraints
Systems are comprised of what the book calls actions. In the computing field, actions are typically computation execution entities such as threads, or tasks, or processes. In other fields, actions include mechanical motions by robots or factory entities such as machine tools, military weapons firing or launching, etc. To deal with systems, it is necessary to first address the lower level abstraction of actions.
Chapter 2 of the book explains timeliness for real-time actions and systems that are based on actions having completion time constraints (such as deadlines and time/utility functions).
A completion time constraint (such as a deadline) expresses an action’s urgency. Urgency is one of generally multiple criteria needed for satisfying concurrently ready actions’ timeliness requirements. Importance and energy are common examples of others.
Since an application’s inherent action deadlines are explicitly or implicitly critical to the design of real-time systems, Chapter 2 presents a mental model of time constraints in general, beginning with deadlines. It reveals properties about deadlines that are little known in the real-time computing context, and generalizes deadlines to completion time constraints. It describes how that generalized paradigm vastly increases the possible cost-effectiveness and applicability of complex dynamically real-time actions and thus systems and their applications. Such actions and systems are the general, and most common, case. Real-time actions are more expressive and powerful in general than is presumed in the real-time computing research and practitioner communities.
Everyone has an intuitive naïve idea what an action deadline is—a time before or at which completing the action (meeting the deadline) is preferable in some application-specific way(s) to later times (missing the deadline). This is the casual limited perception of an action being a real-time one.
Conventional real-time computing uses an action deadline in its most narrow sense, which provides two specific timeliness expressions—the action is either timely (the deadline is met) or not timely (the deadline is missed). This is the sense which is used traditional in real-time computing systems [ ] and some other fields. It is insufficiently expressive in many cases, as shown herein.
Few real-time operating systems directly support action deadlines as an optional first class programming abstraction, in the general sense of including or allowing various deadline-based scheduling algorithms. The two pioneering ones are CMU’s Alpha kernel [Jensen xx, Clark xx, Northcutt xx]), and the Open Software Foundation’s OSF/1 MK7.1 microkernel [Reynolds et al. 1998, Reynolds XX] using Alpha technology. Partially completed ones were undertaken at Digital Equipment Corporation (DEC) using Alpha technology, and IBM using Alpha technology licensed from DEC plus the OSF/1 microkernel (no public references are available for those two, they ended due to unrelated business decisions).
A number of real-time operating system kernels provide for deadlines with various approaches to the earliest deadline first (EDF) policy. The real-time computing community mistakenly claims that the EDF policy is “unpredictable” or “unstable” [ , ] if not all deadlines can be met, but actually in that case EDF usefully minimizes the maximum lateness [ ]. Few real-time computing community members (e.g., [ ]) understand or can accommodate the frequent case of lateness.
Most real-time kernels and operating systems provide only a limited priority mechanism for sequencing (e.g., scheduling) [ ] as almost all operating systems do. So application action deadlines are mapped onto action priorities [ ]. In non-trivial systems, that is usually a difficult and very lossy mapping (an NP-complete problem in general [ ]), as described in Chapter 2. Consequently, real-time computing systems may have baroque priority structures which complicate making priority assignment changes, or very simple ones applied in ways that distort and artificially complicate the application and the action sequencing. To make matters worse, most operating systems and kernels have non-schedulable actions, such as the scheduler itself, interrupt handling, direct memory accesses, and others.
Actions usually also have application- and situation-specific relative importance, which is orthogonal to their urgency—both must be part of the action sequencing optimality (more generally, satisficing) criteria. Urgency and importance almost always must be traded off against one another (analogous to trading off the return on an investment, vs. the safety against loss of an investment), as seen in the discussion of sequencing in Chapter 4 about conventional real-time and dynamically real-time systems.
A deadline can be relative either to the action’s arrival (or ready) time, or to absolute physical (i.e., so-called wall clock) time. Both of these are commonly used, and it is easy to think of examples. For instance: a deadline for controlling a mechanical motion (such as of a machine part, or a robot movement) is invariably relative to when the action begins making the motion; a deadline for having a communication with a landed planetary spacecraft depends on the radio horizons of the remote planet, and thus is relative to the fixed orbital relationship between the earth’s communication node and the location of the spacecraft on the remote planet—i.e., physical time. At the system level, sequencing multiple deadline constrained actions is much easier if they all have the same relativity. Deadline relativity can be converted either direction between release time and physical time. Because real-time actions most often are embedded (the converse is not true) in exogenous larger scale physical systems, their operation sequencing is ordinarily in terms of that enclosing system’s physical time.
An action’s deadline, herein denoted by td, is, by first principle, part of a scoped construct—the length of time that the deadline is taken into account by the action’s operation environment (principally for sequencing multiple actions at the system level). This first principle is the basis of a crucially significant mental model of a deadline—the most expressive approach to comprehending the general case of a deadline, and to potentially supporting deadlines (and more general completion time constraints) as a first class programming abstraction.
The scope has an initial time ti when the deadline becomes known to the operation environment—in common theory and practice, the initial time is the action’s arrival time ta. The scope has a terminal time tt when the deadline is no longer taken into account by the action’s operation environment—again, commonly, this is the same as the deadline time. In general, particularly outside the field of real-time computing systems, an action scope’s initial time may be earlier, equal to, or later than the action’s arrival time; and similarly, its terminal time may be either equal to or greater than its deadline. This is very significant for the subsequent topic about how a deadline is a simple special case of an action completion time constraint.
More precisely, when an action is taking place inside a deadline scope, it is a real-time action. While an action is taking place outside—prior to, or after—any deadline scope, it is not a real-time action.
An action is a real-time one if and only if
it is taking place inside a deadline scope
An action’s future completion time or worst case operation time (called “worst case execution time,” in the conventional real-time computing context), and deadline, are most often—in both theory and practice—presumed to be known á priori as parameters when an action arrives, by its operation environment (for example, a computer operating system sequencer), and the environment’s designers or users.
In traditional static real-time computing, off-line admission control makes assumption-based decisions about whether an action will meet its deadline [ ]. Almost always in the context of real-time computing (but not in principle), the scope encompasses the entire action’s existence—meaning that if it misses its deadline, it is terminated.
A real-time action that arrives with a deadline parameter
whose scope, and action existence, is from arrival to deadline
Alternatively, and more expressively and generally applicable, an action’s deadline may dynamically arise or change during its operation. This dynamic case usually occurs due to exigencies in the application—e.g., change of a meeting’s start time, change in direction by a hostile missile, and obvious other incidents in any particular application or environment.
An action that arrives without a deadline, then dynamically
declares a deadline scope that continues beyond the deadline
For example, a computational task may declare a lexical deadline scope initiation (and hence deadline) with a system call to its execution environment, which at the system level is a sequencing event. The terminal time is often the expiration of a down-counter from td, which is an exception—i.e., sequencing event. Less frequently and more expressively (as becomes clear below), it may be a system call—in this particular construct, for the task action to meet its deadline td, the tt terminal time system call must be executed before the deadline td occurs, else an exception event occurs.
A computational task action that is non-real-time until it
declares and completes a lexical completion time constraint scope
There are numerous other software-implemented scope constructs—for example, the td parameter could be replaced by a variable which the execution environment sets to the currently appropriate td. Outside of the computing field, time constraint scope constructs are defined in application- and system-specific ways.
That exception event generally initiates a corresponding handler, which may be performed by either that action or a different action. Either the action is switched by the action sequencer to doing event handing (e.g., a thread action invokes a method on an event handing object instance); or the action sequencer suspends the action and activates another action to handle the event (e.g., by making that method invocation).
The exception handling usually takes place within a time constraint scope either inside the current scope or in a new scope. These are application-specific design decisions.
Exception handling is one of the cases where an action might have multiple sequential time constraint scopes, or multiple concurrent—usually nested—scopes. There are complex inherent and application-specific issues, particularly at the system level, regarding how met and missed sequential or nested deadlines are dealt with by the action sequencer. These are very similar to dealing with the semantics of nested transactions in a database system [ ], with the addition of time constraint semantics. This topic is discussed in Chapter 4 of the book.
A realistic example is shown below of an action having sequential deadlines enclosed by an outer deadline. The semantics of sequential and concurrent deadlines is application-specific. In particular: what should happen regarding deadlines 0 and 2 if the action misses deadline 1; and likewise regarding deadline 0 if the action misses deadlines 1 or 2.
Nested and sequential deadlines’ scopes
have application-specific semantics