Design

The RTSJ comprises seven areas of extended semantics. This chapter introduces the extensions. Further detail, exact requirements, and rationale are given in the opening section of each relevant chapter. The seven areas are discussed in approximate order of their relevance to real-time programming. However, the semantics and mechanisms of each of the areas—scheduling, memory management, synchronization, asynchronous event handling, asynchronous transfer of control, asynchronous thread termination, and physical memory access—are all crucial to the acceptance of the RTSJ as a viable real-time development platform.

Scheduling

One of the concerns of real-time programming is to ensure the timely or predictable execution of sequences of machine instructions. Various scheduling schemes name these sequences of instructions differently. Typically used names include threads, tasks, modules, and blocks. The RTSJ introduces the concept of a schedulable object. These are the objects that the base scheduler manages, RealtimeThread and its subclasses and AsyncEventHandler and its subclasses.

Timely execution of schedulable objects means that the programmer can determine by analysis of the program, testing the program on particular implementations, or both whether particular threads will always complete execution before a given timeliness constraint. This is the essence of real-time programming: the addition of temporal constraints to the correctness conditions for computation. For example, for a program to compute the sum of two numbers it may no longer be acceptable to compute only the correct arithmetic answer but the answer must be computed before a particular time. Typically, temporal constraints are deadlines expressed in either relative or absolute time.

We use the term scheduling (or scheduling algorithm) to refer to the production of a sequence (or ordering) for the execution of a set of schedulable objects (a schedule). This schedule attempts to optimize a particular metric (a metric that measures how well the system is meeting the temporal constraints). A feasibility analysis determines if a schedule has an acceptable value for the metric. For example, in hard real-time systems the typical metric is "number of missed deadlines" and the only acceptable value for that metric is zero. So-called soft real-time systems use other metrics (such as mean tardiness) and may accept various values for the metric in use.

Many systems use thread priority in an attempt to determine a schedule. Priority is typically an integer associated with a schedulable object; these integers convey to the system the order in which the threads should execute. The generalization of the concept of priority is execution eligibility. We use the term dispatching to refer to that portion of the system which selects the thread with the highest execution eligibility from the pool of threads that are ready to run. In current real-time system practice, the assignment of priorities is typically under programmer control as opposed to under system control. The RTSJ's base scheduler also leaves the assignment of priorities under programmer control. However, the base scheduler also inherits methods from its superclass that may help determine feasibility.

For the base scheduler the feasibility methods may assume a sufficiently fast processor to complete any proposed load on schedule. The RTSJ expects that the base scheduler may be subclassed in particular implementations (e.g., an EDF scheduler) and for those implementations the feasibility methods may correctly indicate the actual feasibility of the system under the given scheduler. Note that for the base scheduler the RTSJ is no different than most real-time operating systems in current use.

The RTSJ requires a number of classes with names of the format <string>Parameters (such as SchedulingParameters). An instance of one of these parameter classes holds a particular resource-demand characteristic for one or more schedulable objects. For example, the PriorityParameters subclass of SchedulingParameters contains the execution eligibility metric of the base scheduler, i.e., priority. At some time (construction-time or later when the parameters are replaced using setter methods), instances of parameter classes are bound to a schedulable object. The schedulable object then assumes the characteristics of the values in the parameter object. For example, if a PriorityParameters instance that had in its priority field the value representing the highest priority available is bound to a schedulable object, then that object will assume the characteristic that it will execute whenever it is ready in preference to all other schedulable objects (except, of course, those also with the highest priority).

The RTSJ is written so as to allow implementers the flexibility to install arbitrary scheduling algorithms and feasibility analysis algorithms in an implementation of the specification. We do this because the RTJEG understands that the real-time systems industry has widely varying requirements with respect to scheduling. Use of the Java platform may help produce code written once but able to execute on many different computing platforms (known as Write Once, Run Anywhere.) The RTSJ both contributes to this goal and detracts from it. The RTSJ's rigorous specification of the required priority scheduler is critical for portability of time-critical code, but the RTSJ permits and supports platform-specific schedulers which are not portable.

Memory Management

Garbage-collected memory heaps have always been considered an obstacle to real-time programming due to the unpredictable latencies introduced by the garbage collector. The RTSJ addresses this issue by providing several extensions to the memory model, which support memory management in a manner that does not interfere with the ability of real-time code to provide deterministic behavior. This goal is accomplished by allowing the allocation of objects outside of the garbage-collected heap for both short-lived and long-lived objects.

Memory Areas

The RTSJ introduces the concept of a memory area. A memory area represents an area of memory that may be used for the allocation of objects. Some memory areas exist outside of the heap and place restrictions on what the system and garbage collector may do with objects allocated within. Objects in some memory areas are never garbage collected; however, the garbage collector must be capable of scanning these memory areas for references to any object within the heap to preserve the integrity of the heap.

There are four basic types of memory areas:

  1. Scoped memory provides a mechanism, more general than stack allocated objects, for managing objects that have a lifetime defined by scope.
  2. Physical memory allows objects to be created within specific physical memory regions that have particular important characteristics, such as memory that has substantially faster access.
  3. Immortal memory represents an area of memory containing objects that may be referenced without exception or garbage collection delay by any schedulable object, specifically including no-heap real-time threads and no-heap asynchronous event handlers.
  4. Heap memory represents an area of memory that is the heap. The RTSJ does not change the determinant of lifetime of objects on the heap. The lifetime is still determined by visibility.

Scoped Memory

The RTSJ introduces the concept of scoped memory. A memory scope is used to give bounds to the lifetime of any objects allocated within it. When a scope is entered, every use of new causes the memory to be allocated from the active memory scope. A scope may be entered explicitly, or it can be attached to a schedulable object which will effectively enter the scope before it executes the object's run() method.

The contents of a scoped memory are discarded when no object in the scope can be referenced. This is done by a technique similar to reference counting the scope. A conformant implementation might maintain a count of the number of external references to each memory area. The reference count for a ScopedMemory area would be increased by entering a new scope through the enter() method of MemoryArea, by the creation of a schedulable object using the particular ScopedMemory area, or by the opening of an inner scope. The reference count for a ScopedMemory area would be decreased when returning from the enter() method, when the schedulable object using the ScopedMemory terminates, or when an inner scope returns from its enter() method. When the count drops to zero, the finalize method for each object in the memory would be executed to completion. Reuse of the scope is blocked until finalization is complete.

Scopes may be nested. When a nested scope is entered, all subsequent allocations are taken from the memory associated with the new scope. When the nested scope is exited, the previous scope is restored and subsequent allocations are again taken from that scope.

Because of the lifetimes of scoped objects, it is necessary to limit the references to scoped objects, by means of a restricted set of assignment rules. A reference to a scoped object cannot be assigned to a variable from an outer scope, or to a field of an object in either the heap or the immortal area. A reference to a scoped object may only be assigned into the same scope or into an inner scope. The virtual machine must detect illegal assignment attempts and must throw an appropriate exception when they occur.

The flexibility provided in choice of scoped memory types allows the application to use a memory area that has characteristics that are appropriate to a particular syntactically defined region of the code.

Immortal Memory

ImmortalMemory is a memory resource shared among all schedulable objects and threads in an application. Objects allocated in ImmortalMemory are always available to non-heap threads and asynchronous event handlers without the possibility of a delay for garbage collection.

Budgeted Allocation

The RTSJ also provides limited support for providing memory allocation budgets for schedulable objects using memory areas. Maximum memory area consumption and maximum allocation rates for individual schedulable objects may be specified when they are created.

Synchronization

Terms

For the purposes of this section, the use of the term priority should be interpreted somewhat more loosely than in conventional usage. In particular, the term highest priority thread merely indicates the most eligible thread—the thread that the dispatcher would choose among all of the threads that are ready to run—and doesn't necessarily presume a strict priority based dispatch mechanism.

Wait Queues

Threads and asynchronous event handlers waiting to acquire a resource must be released in execution eligibility order. This applies to the processor as well as to synchronized blocks. If schedulable objects with the same execution eligibility are possible under the active scheduling policy, such schedulable objects are awakened in FIFO order. For example:

Priority Inversion Avoidance

Any conforming implementation must provide an implementation of the synchronized primitive with default behavior that ensures that there is no unbounded priority inversion. Furthermore, this must apply to code if it is run within the implementation as well as to real-time threads. The priority inheritance protocol must be implemented by default. The priority inheritance protocol is a well-known algorithm in the real-time scheduling literature and it has the following effect. If thread t1 attempts to acquire a lock that is held by a lower-priority thread t2, then t2's priority is raised to that of t1 as long as t2 holds the lock (and recursively if t2 is itself waiting to acquire a lock held by an even lower-priority thread).

The specification also provides a mechanism by which the programmer can override the default system-wide policy, or control the policy to be used for a particular monitor, provided that policy is supported by the implementation. The monitor control policy specification is extensible so that new mechanisms can be added by future implementations.

A second policy, priority ceiling emulation protocol (or highest locker protocol), is also specified for systems that support it. This protocol is also a well-known algorithm in the literature; somewhat simplified, its effect is as follows:

Note that while the RTSJ requires that the execution of non-heap schedulable objects must not be delayed by garbage collection on behalf of lower-priority schedulable objects, an application can cause a no-heap schedulable object to wait for garbage collection by synchronizing using an object between an heap-using thread or schedulable object and a non-heap schedulable object. The RTSJ provides wait-free queue classes to provide protected, non-blocking, shared access to objects accessed by both regular Java threads and no-heap real-time threads. These classes are provided explicitly to enable communication between the real-time execution of non-heap schedulable objects and regular Java threads or heap-using schedulable objects.

Determinism

Conforming implementations shall provide a fixed upper bound on the time required to enter a synchronized block for an unlocked monitor.

Asynchronous Event Handling

The asynchronous event facility comprises two classes: AsyncEvent and AsyncEventHandler. An AsyncEvent object represents something that can happen, like a POSIX signal, a hardware interrupt, or a computed event like an airplane entering a specified region. When one of these events occurs, which is indicated by the fire() method being called, the associated instances of AsyncEventHandler are scheduled and the handleAsyncEvent() methods are invoked, thus the required logic is performed. Also, methods on AsyncEvent are provided to manage the set of instances of AsyncEventHandler associated with the instance of AsyncEvent.

An instance of AsyncEventHandler can be thought of as something similar to a thread. It is a Runnable object: when the event fires, the associated handlers are scheduled and the handleAsyncEvent() methods are invoked. What distinguishes an AsyncEventHandler from a simple Runnable is that an AsyncEventHandler has associated instances of ReleaseParameters, SchedulingParameters and MemoryParameters that control the actual execution of the handler once the associated AsyncEvent is fired. When an event is fired, the handlers are executed asynchronously, scheduled according to the associated ReleaseParameters and SchedulingParameters objects, in a manner that looks like the handler has just been assigned to its own thread. It is intended that the system can cope well with situations where there are large numbers of instances of AsyncEvent and AsyncEventHandler (tens of thousands). The number of fired (in process) handlers is expected to be smaller.

A specialized form of an AsyncEvent is the Timer class, which represents an event whose occurrence is driven by time. There are two forms of Timers: the OneShotTimer and the PeriodicTimer. Instances of OneShotTimer fire once, at the specified time. Periodic timers fire initially at the specified time, and then periodically according to a specified interval.

Timers are driven by Clock objects. There is a special Clock object, Clock.getRealtimeClock(), that represents the real-time clock. The Clock class may be extended to represent other clocks the underlying system might make available (such as a execution time clock of some granularity).

Asynchronous Transfer of Control

Many times a real-time programmer is faced with a situation where the computational cost of an algorithm is highly variable, the algorithm is iterative, and the algorithm produces successively refined results during each iteration. If the system, before commencing the computation, can determine only a time bound on how long to execute the computation (i.e., the cost of each iteration is highly variable and the minimum required latency to terminate the computation and receive the last consistent result is much less than about half of the mean iteration cost), then asynchronously transferring control from the computation to the result transmission code at the expiration of the known time bound is a convenient programming style. The RTSJ supports this and other styles of programming where such transfer is convenient with a feature termed Asynchronous Transfer of Control (ATC).

The RTSJ's approach to ATC is based on several guiding principles, informally outlined in the following lists.

Methodological Principles

Expressibility Principles

Semantic Principles

Pragmatic Principles

Asynchronous Real-Time Thread Termination

Although not a only real-time issue, many event-driven computer systems that tightly interact with external real-world non-computer systems (e.g., humans, machines, control processes, etc.) may require mode changes in their computational behavior as a result of significant changes in the non-computer real-world system. It would be convenient to program threads that abnormally terminate when the external real-time system changes in a way such that the thread is no longer useful. Without this facility, a thread or set of threads have to be coded in such a manner so that their computational behavior anticipated all of the possible transitions among possible states of the external system. It is an easier design task to code threads to computationally cooperate for only one (or a very few) possible states of the external system. When the external system makes a state transition, the changes in computation behavior might then be managed by an oracle, that terminates a set of threads useful for the old state of the external system, and invokes a new set of threads appropriate for the new state of the external system. Since the possible state transitions of the external system are encoded in only the oracle and not in each thread, the overall system design is easier.

Earlier versions of the Java language supplied mechanisms for achieving these effects: in particular the methods stop() and destroy() in class Thread. However, since stop() could leave shared objects in an inconsistent state, stop() has been deprecated. The use of destroy() can lead to deadlock (if a thread is destroyed while it is holding a lock) and although it was not deprecated until version 1.5 of the Java specification, its usage has long been discouraged. A goal of the RTSJ was to meet the requirements of asynchronous thread termination without introducing the dangers of the stop() or destroy() methods.

The RTSJ accommodates safe asynchronous real-time thread termination through a combination of the asynchronous event handling and the asynchronous transfer of control mechanisms. To create such a set of real-time threads consider the following steps:

The effect of the happening is then to cause each interruptible method to abort abnormally by transferring control to the appropriate catch clause. Ultimately the run() method of the real-time thread will complete normally.

This idiom provides a quick (if coded to be so) but orderly clean up and termination of the real-time thread. Note that the oracle can comprise as many or as few asynchronous event handlers as appropriate.

Physical Memory Access

The RTSJ defines classes for programmers wishing to directly access physical memory from code written in the Java language. RawMemoryAccess defines methods that allow the programmer to construct an object that represents a range of physical addresses. Access to the physical memory is then accomplished through get[type]() and set[type]() methods of that object where the type represents a word size, i.e., byte, short, int, long, float, and double. No semantics other than the set[type]() and get[type]() methods are implied. The VTPhysicalMemory, LTPhysicalMemory, and ImmortalPhysicalMemory classes allow programmers to construct an object that represents a range of physical memory addresses. When this object is used as a MemoryArea other objects can be constructed in the physical memory using the new keyword as appropriate.

The PhysicalMemoryManager is available for use by the various physical memory accessor objects (VTPhysicalMemory, LTPhysicalMemory, ImmortalPhysicalMemory, RawMemoryAccess, and RawMemoryFloatAccess) to create objects of the correct type that are bound to areas of physical memory with the appropriate characteristics - or with appropriate accessor behavior. Examples of characteristics that might be specified are: DMA memory, accessors with byte swapping, etc. OEMs may provide PhysicalMemoryTypeFilter classes that allow additional characteristics of memory devices to be specified.

Raw Memory Access

An instance of RawMemoryAccess models a range of physical memory as a fixed sequence of bytes. A full complement of accessor methods allow the contents of the physical area to be accessed through offsets from the base, interpreted as byte, short, int, or long data values or as arrays of these types.

Whether the offset specifies the most-significant or least-significant byte of a multibyte value is affected by the BYTE_ORDER static variable in class RealtimeSystem, possibly amended by a byte swapping attribute associated with the underlying physical memory type.

The RawMemoryAccess class allows a real-time program to implement device drivers, memory-mapped I/O, flash memory, battery-backed RAM, and similar low-level software.

A raw memory area cannot contain references to Java objects. Such a capability would be unsafe (since it could be used to defeat Java's type checking) and error prone (since it is sensitive to the specific representational choices made by the Java compiler).

Physical Memory Areas

In many cases, systems needing the predictable execution of the RTSJ will also need to access various kinds of memory at particular addresses for performance or other reasons. Consider a system in which very fast static RAM was programmatically available. A design that could optimize performance might wish to place various frequently used Java objects in the fast static RAM. The VTPhysicalMemory, LTPhysicalMemory, and ImmortalPhysicalMemory classes allow the programmer this flexibility. The programmer would construct a physical memory object on the memory addresses occupied by the fast RAM.

Exceptions

The RTSJ introduces several new exceptions, and some new treatment of exceptions surrounding asynchronous transfer of control and memory allocators.