As a very high-level programming language, Java offers programmer and software maintenance productivity benefits that range from two- to ten-fold over uses of C and C++. By carefully applying Java technologies to embedded real-time systems, software engineers are able to deliver higher software quality, increased functionality, and greater architectural flexibility in software systems.

However, because of its heavy reliance on the use of automatic garbage collection, using traditional Java programming in hard real time as well as safety-critical embedded systems designs is problematic. Years of research and experimentation have resulted in recommended alternatives to traditional garbage collection that are more appropriate for this class of applications.

One of the costs of automatic garbage collection is the overhead of implementing sharing protocols between application threads. Application threads are continually modifying the way objects relate to each other within memory, while garbage collection threads are continually trying to identify objects that are no longer reached from any threads in the system.

This coordination overhead is one of the main reasons that compiled Java programs run at 1/3 to 1/2 the speed of optimized C code. The complexity of the garbage-collection process and of any software that depends on garbage collection for reliable execution is beyond the reach of cost-effective static analysis to guarantee compliance with all hard real-time constraints. Thus, we do not recommend the use of automatic garbage collection for software that has hard real-time constraints.

For this reason the Open Group's Real-Time and Embedded Systems Forum is developing a set of guidelines based on making effective use of the traditional standard edition Java in combination with appropriate profiles of the Real-Time Specification for Java defined by JSR-1 under the Java Community Process.

The Real-Time Specification for Java provides a very general framework for tackling a wide variety of real-time programming challenges. A profile is recommended for hard real-time and safety-critical systems to improve portability and efficiency, and to reduce complexity, as is required in order to achieve safety certification objectives.

These approaches are scalable in the sense that independently developed software components can be reliably and effortlessly combined into larger software systems, and code written for subset profiles (e.g., the safety-critical profile) can be repurposed for use on the larger profiles (e.g., the hard and soft real-time profiles).

Hard Real Time systems are those in which an action performed at the wrong time has zero or possibly negative value. The connotation of "hard real time" is that compliance with all timing constraints is proven using theoretical static analysis techniques prior to deployment.

Soft Real Time systems are those in which an action performed at the wrong time (either too early or too late) has some positive value even though it would have had greater value if performed at the proper time.

To allow developers to maintain many of the productivity advantages of standard Java in most embedded applications, special real-time virtual machines have been implemented to support preemptible and incremental operation of the garbage collector.

With these virtual machines, the interference by garbage collection on application code can be statistically bounded, making this approach suitable for soft real-time systems with timing constraints measured in the hundreds of microseconds.

The difference between hard real-time and soft real-time does not depend on the time ranges specified for deadlines or periodic tasks. A soft real-time system might have a deadline of 100 µs, while a hard real-time system may have a deadline of 3 seconds. Rather, the crucial distinction is the certainty of meeting the specified timing constraints. Hard real-time systems are provably deterministic and can be analytically guaranteed, whereas the assurance of meeting constraints of soft real-time systems is based on empirical measurements and heuristic techniques.

Safety-critical Java code is software that must be certified according to DO-178B or equivalent guidelines. Certification guidelines impose strict limits on software practices, including peer review, traceability analysis, and software testing.

The Thread Stack Memory Model
The need to support temporary memory allocation within real-time programs is well motivated. At the same time, there is general agreement that developers of hard real-time components do not require the full generality and flexibility offered by automatic garbage collection.

To address hard real-time programming constraints, the RTSJ uses the notion of scoped memory as an alternative to automatic garbage collection. The LTMemory data type represents a memory scope, within which objects may be allocated. The RTSJ run-time environment maintains a reference count to record how many components are currently interested in each scope. When the reference count reaches zero, all of the objects allocated within the LTMemory scope are reclaimed.

This service makes it possible to allocate new memory within a dynamic scope in time that is proportional to the size of the allocation request. A developer of hard real-time software must face several significant difficulties with the use of this abstraction:

1. Knowing how big to make an LTMemory region in order to reliably support the execution of a particular real-time component is quite difficult and error prone. Furthermore, it is highly non-portable between different compliant RTSJ implementations.

2. Instantiation of an LTMemory region is not a hard real-time operation. There is no bound on how much time this will take, and there is, in fact, no guarantee that a request to instantiate an LTMemory region will succeed even if there is sufficient available memory in the system at the time of the request. This is because memory may become fragmented during the course of a program's execution.

Many RTSJ programmers will overlook these difficulties with use of the LTMemory abstraction. They would regularly allocate and discard LTMemory objects, and successful execution of test programs may instill false confidence that the code will work reliably in the field.

This is a very dangerous practice, because it is not generally possible to test all of the different ways that the allocation pool might become fragmented. Further, the program may not behave the same way if it is moved to a different vendor's compliant RTSJ implementation, or even if the same vendor provides a new maintenance release of the same RTSJ implementation.

RTSJ programmers who understand and appreciate the risks of memory fragmentation find that the only way to reliably and safely use LTMemory abstractions in their hard real-time code is to allocate all of the LTMemory objects that their application might need during initialization of the application. This adds significantly to the difficulty of implementing and maintaining the software, and adds considerably to the amount of memory required for reliable execution of the application since many of the LTMemory instances allocated during startup sit idle throughout most of the program's execution.

Although the safety-critical Java profile also supports the notion of scoped memory, it hides the RTSJ APIs that manipulate memory scopes. Instead of relying on these APIs, safety-critical Java programmers describe their intentions with respect to use of scoped memory by using annotations which can be statically analyzed and enforced at compile time.

Like the RTSJ, the safety-critical Java profile also supports the notion of immortal memory, which represents the outer-most memory scope. Objects allocated within the immortal memory region will not be reclaimed. As with inner-nested memory scopes, safety-critical Java programmers use annotations to describe their use of immortal memory as well.

The hard-real-time Java profile addresses scoped memory reliability and maintenance issues by providing static analysis tools to determine the amount of memory required to execute particular program components and by requiring all creation and destruction of scopes to follow a strict LIFO (stack) ordering.

LTMemory objects at work
At startup, all of the temporary memory available to support execution of the program is set aside as the run-time stack for the main hard real-time Java program. If the application needs to support more than a single thread, the main program carves memory from its run-time stack to represent the run-time stacks for each of the threads it spawns.

Figure 1 " Main thread stack after spawning three threads

Figure 1 above illustrates the organization of the main thread's run-time stack immediately after it has spawned three new threads. This illustration assumes that all three threads were spawned from the same context within the main thread. Note that space has been reserved within the main thread's stack to allow the main thread to continue to populate its run-time stack.

Note also that it is essential at this point in the program's execution to know the amount of memory that must be reserved to represent each of the spawned thread's run-time stacks. These stacks need not be the same size. In a typical application, the size of each stack is custom-tailored to the needs of the given thread. The hard real-time Java platform automatically determines the stack sizes for components that are declared using the @StaticAnalyzable annotation.

As execution proceeds, each of the three spawned threads and the main thread will continue to populate their respective stacks. Assume the stack memory is organized, as shown in Figure 2, below, at a subsequent execution point.

Figure 2 " Stack organization after each thread has populated its stack

The scoped memory usage guidelines, as defined in the RTSJ, allow inner-nested objects to refer to objects residing in more outer-nested scopes, but forbids references that go in the opposite direction. Figure 3 illustrates a number of allowed object reference relationships and Figure 4 illustrates several disallowed object reference relationships.

Figure 3 " Allowed references between nested scope-allocated objects

Note that these scope-nesting restrictions guarantee that there will never exist a dangling pointer from an outer-nested object to an inner-nested memory location that no longer exists because its inner-nested scope has been reclaimed.

As shown in Figure 4, below, note that besides disallowing references that refer to low-memory addresses from high-memory addresses, these rules also prohibit references from spawned threads to that portion of an ancestor thread that was populated after the point at which the child was spawned.

Figure 4 " Disallowed references between scope-allocated objects

This usage protocol requires that any data structures that need to be shared between multiple threads must reside either in immortal memory (the outer-most scope, which is never reclaimed) or must exist within the parent or some other ancestor thread's stack above the point at which the descendent thread was spawned.

Shared objects do not necessarily need to exist at the time the subthreads are spawned, but the memory allocation context within which the shared object will eventually be allocated must be set aside within the parent thread's stack before the point at which the child thread is spawned.

Once the embedded system programmer has an understanding of this alternative scoped memory alternative to garbage collection, developing code appropriate to the application is relatively straightforward.

Within the hard real-time and safety-critical development environments, the use of scope-allocated memory is facilitated by consistency checking performed by a special byte-code verifier, based on programming annotations supplied in the standard libraries. This is discussed further in subsequent articles of this series.

Next in Part 2: Guidelines for soft real-time Java development

Kelvin Nilsen, Ph.D. is chief technology officer at Aonix North America.

References:

[1] Guidelines for Scalable Java Development of Real-Time Systems, available at http://research.aonix.com/jsc/rtjava.guidelines.3-28-06.pdf