|Based on a white paper by Brian Goetz and edited by Robert Eckstein, July 2008|
Part 1 of this series looked at the Real-Time Specification for Java (RTSJ), JSR 1, and examined the topics of thread priorities, memory management, and advanced communication between threads. Part 2 will examine the topic of garbage collection and introduce the Sun Java Real-Time System (Java RTS), Sun's commercial implementation of the RTSJ.
Because garbage collection (GC) is one of the largest sources of unpredictability in Java applications, a real-time virtual machine (VM) must find a way to prevent collection pauses from causing tasks to miss their deadlines. However, it should be noted that the RTSJ does not define real-time GC.
There are several different approaches to scheduling GC within a real-time environment, each with benefits and weaknesses. These include work-based and time-based incremental collection approaches, which are aimed at minimizing the effect of GC on scheduling.
Although both processes reduce the duration and improve the predictability of specific pauses, they can be difficult to use and to tune, which limits their reliability for hard-real-time use.
The work-based approach has each thread do a specific amount of incremental GC work each time it allocates an object. This approach has nice fairness properties, in that the activities that allocate the most memory pay the largest share of the collection cost, as well as spreading out the collection cost into small chunks.
But this approach can only get you so far, because the amount of time it takes to do a fixed amount of incremental collection work is variable. That is, it depends on the allocation behavior of the entire application. Therefore, it is still difficult to predict the effect of collection on scheduling.
Figure 1 shows the risk of work-based GC: This variability can cause a high-priority task to miss its deadline if it allocates memory.
Rather than slicing up the incremental collections as in the work-based approach, the time-based approach schedules a fixed amount of time for GC in each scheduling period. This also spreads the GC cost equally throughout the scheduling periods. But again, there is no direct correlation between the amount of time that an incremental GC runs and the amount of memory it reclaims, so a fixed-time approach may not keep up with the application.
Figure 2 shows the effect of time-based GC and how it can cause the undesirable outcome of a high-priority thread missing its deadline -- even if it does not allocate memory.
A third approach, called Henriksson's GC, is to modify the work-based approach so that the incremental GC work associated with allocations in critical threads is deferred until the critical task finishes.
The garbage collector runs at a lower priority than the critical threads. This has the effect of making the lower-priority threads bear the full GC cost -- provided that you do not run out of memory during the execution of a high-priority task. Higher-priority threads can meet shorter deadlines than with other real-time garbage collectors, even if they allocate memory.
In addition, because the delayed GC activity does not affect the response time -- and consequently the likelihood of meeting the deadline -- of these critical threads, you can specify an overestimation of the amount of GC work to perform for each allocation. This decreases the risk of memory exhaustion due to bad GC configuration or a surge in allocations.
Figure 3 shows this algorithm.
Starting with Sun Java RTS 2.0, a new real-time garbage collector (RTGC), based on Henriksson's algorithm, is available. The garbage collector runs as one or more real-time threads (RTTs). These run at a priority that is lower than all instances of
NoHeapRealtimeThread ( NHRT) and that may be lower than some RTTs as well, so that critical threads may preempt the collector. In this way, critical threads are shielded from the effects of GC.
One of the tuning parameters in the RTGC algorithm is the maximum priority of the garbage collector. This divides the priority range into regions. The NHRTs receive the highest priority and are known as critical tasks. Next in priority are the critical real-time threads, followed by the noncritical real-time threads, and finally by the non-real-time threads. By default, the garbage collector runs at its initial priority, which is below that of the noncritical real-time threads. But as memory grows short, the VM will boost or raise the priority of the collector to the maximum configured priority.
Figure 4 shows the priority levels for the different types of threads in gray and for the garbage collector at its initial and maximum priorities in pink.
The important point about the RTGC provided with Java RTS is that it is fully concurrent, and it can thus be preempted at any time. There is no need to run the RTGC at the highest priority, and there is no stop-the-world phase, during which all the application's threads are suspended during GC.
In Figure 5, the RTGC starts executing at its initial priority and is preempted by a high-priority thread. When that thread stops, the RTGC runs again but is again preempted. Finally, if the running threads are allocating memory and the remaining memory becomes low enough, the RTGC is boosted to its maximum priority, where it is preempted only by critical threads.
On a multiprocessor, one CPU can be doing some GC work while an application thread is making progress on another CPU. In Figure 6, the critical NHRTs are running on a separate CPU and therefore do not preempt the RTGC. The RTGC runs to completion without its priority having to be boosted.
Thus, the RTGC offered by Java RTS is very flexible. Whereas garbage collectors in other real-time systems usually either have to be executed as incremental, periodic, high-priority activities or else induce an allocation-time overhead, the Java RTS RTGC can execute according to many different scheduling policies.
In addition, instead of trying to ensure determinism for all the threads of the application, the Sun Java RTS team based the default-scheduling policies on Henriksson's algorithm.
The RTGC considers that the criticality of an application's threads is based on the threads' respective priorities and ensures hard-real-time behavior only for real-time threads at the critical level, while trying to offer soft-real-time behavior for real-time threads below the critical level.
This reduces the total overhead of the RTGC and ensures that the determinism is not affected by the addition of new low-priority application threads. This makes the configuration easier because there is no need to study the allocation behavior of an application in its entirety in order to configure the RTGC. Typically, a developer designs determinism by looking only at the critical tasks.
By setting only two parameters, a memory threshold and a priority, you can ensure that GC pauses will not disrupt threads that are running at critical priority. The big advantage of this approach is that these parameters are independent of the noncritical part of the application. You do not need to reconfigure the RTGC when you add a new noncritical component or when the machine load changes.
The RTGC has an auto-tuning mechanism that tries to find the best balance between determinism and throughput. It tries to recycle memory fast enough at its initial priority for the noncritical real-time threads but without offering any guarantees for them.
If the noncritical load increases, the RTGC may fail to recycle memory fast enough for all the threads and will be boosted to its maximum priority. However, this will not disrupt the critical threads, as long as the memory threshold is set correctly for the application. Only the noncritical real-time threads will be preempted and temporarily suffer from some jitter, or variance in latency, due to memory recycling.
Note, however, that the RTGC is not a silver bullet that renders GC invisible. Rather, it is a mechanism by which you can tune scheduling parameters so that the critical threads are not interrupted by GC. Tuning the applications through the selection of the thread priorities and the RTGC parameters is critical for shielding critical threads from the effects of the rest of the application.
The Java RTS 2.1 FCS release contains the following enhancements to the previous version (Java RTS 2.0):
Immortal MemoryPool. The new DTrace probe is one of many new probes in the jrts probe provider.
For further release details, refer to the Java RTS technical documentation.
Part 1 of this series introduced you to the topics that real-time computing encompasses, and Part 2 has given you a closer look at the topic of garbage collection and the Sun Java RTS. You can find additional information in the resources listed at the end of this article.
The editor of this article wishes to thank David Holmes and Antonia Lewis for their work on the white paper on which this article is based. And thanks to Carlos Lucasius for his valuable technical review comments.
An Introduction to Real-Time Java Technology: Part 1, The Real-Time Specification for Java (JSR 1)
Sun Java Real-Time System (Java RTS): Frequently Asked Questions (FAQ)
Java RTS Technical Documentation
Training: Developing Real-Time Applications for the Java Platform (DTJ-4103)
JavaOne 2007 and 2008 Hands-On Labs: How to Build Real-Time Solutions for Real-World Devices
Java RTS: Feature Requests Survey
Brian Goetz, a senior staff engineer at Sun, has been a professional software developer for 20 years. He is the author of over 75 articles on software development, and his book, Java Concurrency in Practice , was published in May 2006 by Addison-Wesley. He serves on the JCP Expert Groups for JSRs 166, concurrency utilities; 107, caching; and 305, annotations for safety analysis.
Robert Eckstein has worked with Java technology since its first release. In a previous life, he has been a programmer and editor for O'Reilly Media, Inc. He has written or edited a number of books, including Java Swing, Java Enterprise Best Practices, Using Samba, XML Pocket Reference, and Webmaster in a Nutshell.