As it stands now, neither the Java language
nor the Java Virtual Machine is compatible with truly real-time systems. However, extensions to the Java specifications are now being made to make Java a better language for real-time programming. This article describes what’s needed.
The goal of real-time systems is to ensure that tasks or operations are completed with acceptable and predictable timeliness, including responding to events within an upper-bounded timeframe, and meeting the hard deadlines for any tasks. A priori
predictability of completion timeliness is the essence of real-time computing. The real-time extensions to the Java platform take up the challenge of building on the strengths of Java in areas such as concurrent programming, providing the predictable execution environment required to allow realistic reasoning about the ability of the platform to meet an application’s timeliness constraints. The extensions also provide new facilities that are commonly required in real-time systems.
A bit of history
The process of creating real-time extensions to the Java platform began in early 1998, when several independent efforts were initiated. In the first quarter of that year IBM approached key RTOS vendors with the intent of creating agreement on ways to standardize access to the real-time features of their operating systems for implementations of the Java platform. At the same time, other third-party vendors and prospective users started a working group
under the sponsorship of the National Institute for Standards and Technology (NIST) to define the requirements for implementation of real-time systems in the Java programming language. In July of that year, the groups coordinated their efforts to generate a single document outlining these requirements.
The combined group continued to meet throughout the remainder of the year, with the participation of NIST in a coordinating capacity. The goal of the group was to define requirements for the Java platform
which would allow real-time systems developed using existing practice to be implemented in the Java language and which would also lay the foundations for new, more advanced real-time practices to be fully supported by the Java language.
The NIST requirements document approached this dichotomy by defining requirements for a broad range of core functionality that could be used to create real-time systems according to existing practice and allowing the definition of profiles that addressed the unique
requirements of different application domains. These were embodied in a set of nine core requirements outlined in the document.
Java Community Process and Real-Time Expert Group
In December of 1998, Sun Microsystems announced the establishment of the Java Community Process (JCP). This process embodies the mechanism by which Sun has produced the specifications for its extensions to date and attempts to further open up the process by extending
participation to any interested parties. The JCP includes a process for creating expert groups to develop new specifications for extensions to the Java platform whereby Sun selects a leader who, in turn, selects the rest of the group from amongst the JCP signatory companies interested in developing the specification. The JCP also includes a formal outside audit of the activities of each expert group to ensure that proper procedures were followed.
Shortly after the JCP announcement, a Real-Time Expert Group was
established to respond to the first Java Specification Request (JSR) submitted and approved under the JCP. This JSR gives the Real-Time Expert Group the mandate to define new mechanisms to support the development of real-time applications in Java, and define amendments to the Java Language Specification (JLS) and the Java Virtual Machine (JVM) specification to address semantic issues that are too vague or ambiguous for real-time use.
The Real-Time Expert Group was actually formed in March 1999 with Greg
Bollella of IBM selected by Sun to be its leader. The group is composed of two teams. The first team is a smaller core group of experts who are producing the actual specification. The second team is a larger consulting group acting in an advisory capacity and providing feedback on the working documents created.
Principles
The ultimate goal of the Real-Time Expert Group is to define a specification for core real-time capabilities that satisfy
the NIST requirements document. The core specification is designed to be practical for the development of real-time systems using current practices, including those that make use of existing—primarily static priority assignment—methodologies such as rate monotonic analysis (RMA). While embracing existing practice, the group has endeavored to be forward-looking and produce an extensible specification. By allowing extension, the specification fosters the adoption of other, more dynamic
methodologies such as deadline-based scheduling techniques, and thus lays the foundation for accommodating new real-time concepts and techniques as the states of the art and practice advance.
In developing the specification, the group is following two guiding principles regarding compatibility. The first of these is a statement of upward compatibility. A conforming implementation should be capable of allowing correctly written existing Java applications to run with the same guarantees mandated by the existing JLS and
no more, while real-time components developed according to the real-time specification work with additional semantic guarantees provided by that specification. Real-time and non-real-time components must be able to co-exist within the same implementation without adversely effecting the behavior of each other.
The second guiding principle regarding compatibility concerns the “write once, run anywhere” value proposition. The group is committed to following this to the extent possible given the
constraints imposed by different run-time environments. For this reason, the group applies to the more conservative “write once carefully, run anywhere conditionally” approach—by which we mean that a real-time application, coded correctly to take into account the differing characteristics of the underlying platform, can be deployed on different conforming implementations and adapt to the capabilities of the environment. In some cases, the application may not be capable of meeting the necessary
real-time constraints on the chosen target, and the application should be capable of determining this.
Areas of consideration
The real-time specification addresses issues in six major areas of the JLS and JVM specifications. The most important of these areas—the Java thread model, synchronization, and memory management—have significant impact on the ability to provide predictable behavior. The remaining areas concern other
features important to real-time systems, such as responding to external stimuli, providing accurate timing, and asynchronous transfer of control.
Thread model. The thread model employed by Java is designed to be implementable on a wide variety of systems, predominantly desktop computers and servers. Consequently, Java’s current thread model doesn’t provide strong guarantees regarding the behavior of threads in the system. Given the prevalent practice of mapping deadlines onto thread priorities,
real-time systems need additional assurances with respect to the semantics of threads and so the specification tightens these semantics in critical areas.
The specification defines a scheduler that is responsible for controlling threads. The scheduler must be able to support fixed-priority preemptive scheduling of threads by default, allowing conventional techniques that involve a priori assignment of thread priorities to work correctly. Under this scheme, the application can programmatically adjust thread
priorities, but the implementation itself may only adjust thread priorities to bound the effects of priority inversion associated with synchronization.
A real-time scheduler implementation must provide a number of priority levels that are all distinct, and preemptive priority dispatching within those priorities. For example, a higher priority thread will always take precedence over a lower one. If a higher priority thread becomes eligible to run when a lower priority one is already running, it will
preempt the lower priority thread. An implementation is required to provide at least 28 distinct priority levels with preemptive behavior. Using 28 priorities yields a reasonable number of distinct priority levels to map threads to, and for systems that provide 32 priority levels, it also allows several to be reserved for use within the JVM.
Taken together, the requirements regarding priority scheduling ensure that the reasoning, such as RMA, used to map time periods onto thread priorities can be reasonably
employed without being subverted by the JVM implementation.
The real-time specification describes a scheduling interface that allows real-time threads to be created by the application with greater control over the behavior of those threads. This interface is designed to be flexible enough to allow an underlying implementation to provide various alternative scheduling policies, and allow the application to take advantage of new scheduling policies as implementations for them are developed. For example,
different forms of deadline-based scheduling policies can be expressed within the scheduling interface.
When a new real-time thread is created, a set of scheduling parameters is passed to the constructor of the thread object. The thread may select the set of parameters from a known class by the thread, or it may negotiate with the scheduler to obtain a class of applicable parameters. In this way, an application may take advantage of some form of deadline-based scheduling if it is available and fall back to
priority assignment if it is not.
The scheduler is responsible for ensuring the correct behavior of newly created threads based on the scheduling parameters provided. It may also use these parameters for admission control of new threads. In this case, the scheduler attempts to create a viable schedule when the new thread is created, and if none is possible, it may refuse to create the thread.
The scheduling interface will be validated in the reference implementation by providing implementations of
three realistic scheduling policies: fixed priority preemptive dispatch, earliest deadline first, and earliest deadline first with dynamic deadline modification.
Synchronization.
Java provides strong built-in support for concurrent programming. As part of this, Java provides an object monitor abstraction for sharing resources. Any object can act as a monitor in the system, and only one thread may enter a monitor at a given time. Entry and exit of the monitor is provided automatically with the
synchronized language feature. A Java programmer can protect critical sections of code within an object by placing them in a statement or method marked as synchronized. The Java language run time ensures that the thread is in the monitor before executing the code, and exits the monitor upon completion.
In addition, a thread within the monitor may wait for the object to be in a particular state by performing a wait() on the object. This will allow another thread to enter the monitor, and the waiting thread
will be blocked until another thread performs a notify() to signal a change in the monitor state. At the time of the notify(), the runtime will wake up one of threads waiting on the monitor, which then must re-enter the monitor before continuing.
If threads share resources in a real-time system, synchronization introduces an effect where a lower priority thread can block a higher priority thread when both are contending for the resource (that is, a thread must wait to enter a monitor that a lower priority
thread is already in). If threads with intermediate priorities become ready to run, they can hold off the high priority thread for an indefinite period of time in a phenomenon known as priority inversion.
The real-time Java specification provides a mechanism to bound the amount of time a thread may be blocked waiting to enter a monitor held by a lower priority thread. Implementations must use a priority inversion avoidance policy known as priority inheritance protocol for all monitors by default.
Priority inheritance will temporarily boost the priority of the thread in a monitor to the priority of the highest priority thread waiting to enter the monitor. This prevents priority inversions from being introduced by threads with intermediate priorities. The dynamic priority adjustment is undone when the thread inside the monitor exits it.
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 JVM implementation. The policy specification is extensible so that new mechanisms can be added by future implementations. A second policy, highest locker, is also specified for systems that support it.
The highest locker protocol boosts the priority of any thread entering a monitor to the priority of the highest priority thread that will ever enter the monitor. This requires global knowledge about all resource contention in the system and is difficult to determine
automatically, so the programmer assigns a priority ceiling to the monitor indicating what the highest locker would be. A key advantage to this approach is that it has been shown that providing a monitor entry queue isn’t necessary, and that the longest amount of time the highest priority thread can wait to enter the monitor is the maximum execution time of the critical section.
Memory management.
The Java language fosters a model of programming that makes substantial use of dynamic
memory allocation, since objects can only be allocated statically or from the heap, with no stack allocation of objects. As a result, there is a substantial dependency on garbage collection to reclaim unused memory from the heap. Garbage collection is a global process that affects all threads and creates unforeseeable and unpredictable opportunities for independent threads to adversely affect the ability of other threads to run at the appropriate times.
The real-time specification takes a two-pronged approach
to dealing with the issue of memory management. It places some additional requirements on garbage collection to provide more predictable behavior of any garbage collector present in the implementation. It also provides mechanisms to facilitate a style of programming that isn’t as dependent on dynamic allocation from the garbage-collected heap. This is useful in particular for a significant class of real-time applications in which dynamic allocation is eschewed in favor of pre-allocating all of the
objects required by the application.
Garbage collection
If an implementation provides garbage collection, it must be able to support controlled preemption. In this case, real-time threads can be run at a higher priority than the effective priority of the garbage collector and any of these must preempt the collector in a controlled fashion if it becomes ready to run. The bounds on the associated preemption latency must be known and available for
query by the application. This restriction allows real-time threads that aren’t attempting to allocate memory to proceed without being completely suspended by a garbage collection cycle (although the preemption latency may be introduced after any blocking operation). No specific latency requirement is imposed; it may correspond to an increment of work performed by the collector, or it may be the amount of time required for the garbage collector to back off the work that was in progress. In either
case, the garbage collector must leave the heap in a consistent state.
This method doesn’t address the problems inherent in allowing applications to proceed and meet timeliness constraints while continuing to allocate memory, which requires the garbage collector to be able to reclaim memory at a rate that is at least equivalent to the rate at which all threads are allocating memory. This is the domain of real-time garbage collection. Provision is made to allow real-time threads to specify their memory
demands to the garbage collector and scheduler. This can be used to pace the garbage collector and to perform admission control within the scheduler. Real-time garbage collection isn’t a generic solution, however, and the latencies and overheads involved may not meet the demands of many applications.
To handle the issue of allocation/reclamation rates and the latency issue, two orthogonal constructs are provided for memory management: allocation regimes and access regimes.
Allocation regimes
Allocation regimes allow time-critical code segments to allocate memory without being subject to the temporal vagaries of garbage collection. The use of different allocation regimes allows the application to deal with the variation in latency associated with attempts to allocate new memory.
Allocation regimes involve the logical partitioning of the heap into regions with different characteristics, including the lifetime of objects created from
that region and the time at which garbage collection may be performed on that segment of the heap. When an allocation regime is in effect for a thread, any new objects it creates are allocated from the heap partition associated with the allocation regime.
The real-time specification defines allocation regimes that allow objects to be created within a thread-specific partition, to be long-lived, or to reside at a specific physical memory location. New objects or arrays can be allocated within an allocation
regime with a method call on the allocation regime. In addition, the specification provides a mechanism to scope a region of the thread that will employ the given allocation regime for all objects within that scope. The scoping mechanism is particularly useful in conjunction with allocation regimes used for long-lived objects and objects that don’t exist outside of the current lexical scope. The immortal regime allows the application to create objects whose lifetime is somewhere between the next time a
class is loaded and the lifetime of the application itself. In this case, the objects are created in a region of the heap that can only be garbage-collected during class loading or when the application terminates. During its setup phase, a real-time application can pre-load all the required classes, as well as pre-allocate objects that can safely be used later in time-critical code that doesn’t access the garbage collected heap, with an access regime described in the next section.
Scoped objects
have a lifetime that is confined to the current lexical scope. Scoped objects can be created from a thread-specific partition using a scoped allocation regime. In this case, the implementation can use an alternate allocation strategy that behaves as though the object were on the stack. The allocator must be able to create an object from this partition in constant time, and the space is reclaimed when the scope is exited.
The existence of scoped objects, in particular, introduces a coherency problem. It is
important in this case that heap objects don’t have references to scoped objects. It is also important that scoped objects in outer scopes don’t have references to scoped objects from an inner scope. Assignment rules prohibit such illegal object references, and these should be checked by a static analyzer when possible. Run-time checking may also be used to enforce these within the virtual machine.
Access regimes
Access regimes are
orthogonal to allocation regimes. They provide a means for the application to deal with the wide variation in preemption latency associated with the garbage collector.
In particular, a non-heap access regime allows the garbage collector to be preempted in a fashion that isn’t controlled, as described in the section on garbage collection. This allows for time-critical code such as controller loops that can’t tolerate the latency that could be introduced by garbage collection when the thread
becomes ready to run. In this case, the thread can be scheduled without waiting for the garbage collector to reach a preemption point. The thread can perform a query to determine whether the garbage collection latency is greater than would be tolerable in the time-critical sections of code, and use the non-heap access regime when it is.
The non-heap access regime is effectively a contract between the application and the garbage collector indicating that the application won’t refer to any objects in the
garbage-collected heap while the access regime is in effect. In this case, the garbage collector doesn’t need to restore the heap to a consistent state to allow the thread to run.
If the non-heap access regime is provided, the virtual machine must provide run-time checks to ensure that the thread doesn’t access any heap objects while the non-heap access regime is in effect.
Asynchronous event handling
Asynchronous event
handling allows the application to respond to real-world events, usually presented as a software signal, or to programmatically generated events. These events are generated in an asynchronous fashion and don’t require an active listener or polling to have an effect. A complex application may have hundreds or even thousands of event types to handle, precluding any portable use of listening threads as an effective implementation strategy.
From a logical viewpoint, handlers for events are considered to be
schedulable entities like a thread. They are created with scheduling parameters and are subject to admission control like threads. There is no requirement for the implementation to create a thread for each event, however, except as needed to respond to events.
An event handler is a small fragment of code that is run in response to an external stimulus. The code fragment is defined by creating a run() method on a subclass of the asynchronous event handler class. Event handlers are registered with an associated
event type. The handler is run at the appropriate time after the event type is triggered, either by another thread, in response to a signal, or on expiration of a timer.
Timers
Real-time systems often incorporate threads that are scheduled on a periodic basis or must trigger behavior at a particular point in time. The relevant time scale may either be relative to a previous event, or it may be important for the behavior to take place at a
particular point in time. Having the ability to determine or control the granularity of the timer being used is also important. For low-latency applications, sub-millisecond accuracy is important.
The specification provides abstraction of time related to the epoch, with nanosecond granularity. However, the underlying system may only support a larger granularity. The time abstraction is used throughout the interfaces provided by the specification. Programmable timers are also provided to allow an event to
be triggered at a particular time. The programmable timers are provided as event types, so that the asynchronous event handling mechanism can be used in conjunction with them. An event handler may be created and associated with a timer, so that the event handler is run when the timer expires. Both one-shot and periodic timers are provided.
Asynchronous transfer of control
In many cases, the real-time application needs to respond to events
asynchronously in a way that may alter the sequence of control of a particular thread. One of the most frequent occurrences is the expiration of a watchdog timer, which should cause the current operation to abort. In other cases, an event may be used to notify the application of a significant condition that may require special handling such as shedding load in response to overload. Asynchronous transfer of control is a mechanism that extends the asynchronous event handling facility to allow this.
The
asynchronous transfer of control facility makes use of the same lexical scoping mechanism as allocation and access regimes to mark regions of code that are abortable. When an asynchronous event occurs that attempts to abort the current operation, the thread immediately exits any abortable operation it is performing and continues to unwind through all stack frames that are abortable, while still allowing non-abortable operations to complete normally. This process uses a more orderly regression than simply
destroying the thread or throwing an exception asynchronously in a section of code that doesn’t expect it. For example, throwing an exception within a synchronized block could cause the monitored object to remain in an inconsistent state, violating the monitor invariant. At the time of this writing, asynchronous transfer of control isn’t a well-understood problem. Practical problems such as handling nested timeouts aren’t resolved. For this reason, this form of asynchronous transfer of control may
not be a good candidate for specification at this time. Its inclusion in the final real-time Java specification is uncertain.
See for yourself
The Java Real-Time Expert Group was formed to create a specification for extensions to Java platforms that add capabilities to support real-time programming in Java and to support the adoption of new methodologies as they enter into practice. The group has focused on new APIs, language, and virtual
machine semantics in six key areas. The specification is currently available for review by participants in the Java Community Process. Public review should begin around the time this article is published. Anyone wishing to see it immediately can register as a participant. Otherwise, the public review will be held open for at least 30 days. For updated information on the status of the specification, timeframes, or for any other additional information, visit the Web site for the Real-Time Expert Group at
www.rtj.org.
Steve Furr is a senior software developer at QNX Software Systems. He is responsible for directing Java development at QSSL and acts as their representative to the Java Real-Time Expert Group core team.
