Improve Real-Time Java performance and reliability with ScopedMemory Allocation: Part 1 - Embedded.com

Improve Real-Time Java performance and reliability with ScopedMemory Allocation: Part 1

The Real-Time Specification for Java (RTSJ) provides the ScopedMemoryabstraction as an alternative to the use of automatic tracing garbagecollection to supply the temporary memory allocation needs ofapplication software.

Real-time Javaprograms instantiate ScopedMemoryallocationcontextswithin which temporary objects are allocated. After all threads exit aScopedMemory context, all of the objects allocated within that contextare instantly reclaimed without any need for traditional garbagecollection tracing.

Using the ScopedMemory programming abstractions as an alternative togarbage collection has provenvery difficult. ScopedMemory programmingerrors result in reliability problems because program componentsterminate with various run-time exceptions.

Maintenance of software and composition of independently developedsoftware components are especially difficult because the ScopedMemoryassumptions upon which each component's validity depends are notdocumented nor enforced in the interface description of the component.

This article describes a system of Java 5.0 style annotations whichenables static analysis tools to prove that ScopedMemory protocols arefollowed correctly within methods that make use of ScopedMemoryobjects. These annotations also make it possible to automaticallydetermine the size of each ScopedMemory allocation context as requiredfor reliable operation of the code that allocates objects within thescope.

Though these annotations have been designed specifically to supportthe development and certification of safety-critical Java code, theiruse is also relevant to the development and maintenance of hardreal-time mission-critical code. The principles are illustrated withvarious code samples.

Some Historical Context
The use of Java with real-time garbage collection as an implementationlanguage for soft real-time systems has now been proven in a largenumber of successful mission-critical deployments with millions ofhours of 5-9's reliability.

This technology delivers full access to traditional Standard EditionJava libraries and off-the-shelf components available under bothcommercial and open-source licensing terms. Statistical analysisdemonstrates that these systems provide reliable compliance withreal-time constraints as low as a single millisecond.

However, there are several reasons why this particular technologyhas not penetrated into the deepest levels of embedded real-timesystems:

1) Standard Edition Javaenhanced with real-time garbage collectionruns significantly slower (up to three times slower) than optimized Ccode for CPU-intensive activities that are typical of low-leveloperations such as radar and sonar signal processing, software-definedradios, global positioning systems, and so forth.

2) The minimum footprint foreffective deployment of a StandardEdition Java application is several megabytes, much too large forcertain memory- and power-constrained embedded devices.

3) Though it may betheoretically possible to prove that agarbage-collected Java application satisfies hard real-time timingconstraints, the complexity of the real-time garbage collectionalgorithms and the subtle interplay between garbage collection andapplication behavior makes such proofs extremely difficult to developand maintain in the face of software evolution.

Also, the sorts of problems that programmers deal with in the lowestlayers of their embedded software hierarchies tend to be very static,and these programmers see little need for the generality of automaticgarbage collection.

The emergence of the scoped-memoryalternative
When the Real-Time Specification for Java (RTSJ) was published in 2001,it provided an alternative to the use of automatic garbage collectionfor use in very low-level software.

This mechanism is known as scoped memory. Conceptually, a memoryscope is a reusable memory region within which allocated temporaryobjects persist until the scope is no longer referenced by any programcomponents.

At this point, all of the objects that had been allocated within thescope are reclaimed and the scope can be reused to serve the temporarymemory allocation needs of another program component. To assure theabsence of dangling pointers, memory scopes are organized as a stack.

The order in which scopes are reclaimed is the reverse of the orderin which they are entered (LIFO). Objects allocated withininner-nested(more recently entered) scopes may refer to objects residing in moreouter-nested scopes.

But if an attempt is made to create a reference from an objectresiding in an outer-nested scope to an object residing in aninner-nested scope, a run-time check associated with the assignmentoperation throws an IllegalAssignmentError exception.

This protocol assures that program execution will never result indangling pointers, a common C and C++ bug that results when the memoryfor particular objects is reclaimed before all of the references to thereclaimed object have disappeared.Early experimentation with the RTSJ has demonstrated that thisparticular approach to memory management delivers predictable real-timedeterminism that matches C and C++ practices. However, differentproblems have emerged. In particular –

1) Market analysts studyingthe adoption of Java within the embeddeddevelopment community have identified several key impediments. Amongthese, commonly cited objections include its size and speed.Unfortunately, the RTSJ scoped memory mechanism causes “real-time Java”to be even larger and slower than traditional Java.

2) Among key benefits oftraditional Java are its high-level supportfor reliable integration of independently developed softwarecomponents. This greatly simplifies the evolution of software that isso common in the embedded industry, where many software systems doublein size every eighteen to thirty-six months.

Unfortunately, the scoped memory programming abstractions areextremely fragile in the context of evolving software. A component thatreliably follows scoped memory protocols in one context is likely toabnormally abort with a run-time exception due to violation of theseprotocols if the component is incorporated within a different context.

3) Another key benefit oftraditional Java is its high-level ofintegrity checking to assure reliable operation of software. Thescoped-memory programming abstractions place a tremendous burden ofdetail on programmers, and the RTSJ provides no tool support to assistthe programmers in managing this detail.

Programmers are required to calculate by hand the size of each scopeto make sure the scope is large enough to represent all of the objectsthat might need to be allocated within it. As well, programmers arerequired to invent ad hoc mechanisms to enforce that scoped memoryprotocols are honored at each module interface.

Modules that expect to operate on objects residing in scoped memorymay fail if they are passed references to objects residing in othermemory regions. Run-time checks assure that scoped memory protocols arenot violated. Unfortunately, enforcement of these protocols reduces thelikelihood that program components will successfully fulfill theirassigned responsibilities.

The special memory disciplines described in this article offerimproved reliability, maintainability, and performance of the RTSJscoped memory programming abstraction by enforcing compliance withscoped memory usage protocols at compile time rather than at run time.

The Thread Stack Abstraction
One of the reliability difficulties associated with the use of RTSJmemory scopes is that creation of a new scope is itself an unreliableoperation. This is because the memory pool within which scopes areallocated and deallocated may become fragmented.

When this pool becomes fragmented, it may not be possible toallocate a new scope of size N bytes even though there is much morethan N bytes of available memory. In some situations, programmers mayexploit detailed knowledge of the implementation techniques used in aparticular RTSJ product to establish confidence that memoryfragmentation will not hinder reliable execution.

However, use of this knowledge compromises software portability andusually results in future software maintenance problems. The practicerecommended by RTSJ experts is to avoid creation of scopes at run time.Instead, they suggest that a pool of appropriately sized scopes becreated during program startup.

This pool mechanism also introduces considerable softwaremaintenance complexity. Understanding how many scopes of each size arerequired in the pool requires laborious and difficult analysis, eachtime the code is modified.

Dividing all available memory into fixed-size scopes at the start ofexecution reduces memory utilization because memory that is dedicatedto the representation of particular scopes will sit idle during phasesof execution that do not make use of those scopes.

An alternative discipline for the organization of memory scopesenables higher performance and more reliable operation. At startup, allof the temporary memory available to support execution of a program isset aside as the run-time stack for the main thread of the hardreal-time Java program.

If the application makes use of multiple threads, the main programcarves memory from its run-time stack to represent the run-time stacksfor each of the threads it spawns. Figure 1 below illustratesthe organization of the main thread's run-time stack immediately afterit has spawned three new threads. This illustration assumes that allthree threads were spawned from the same context within the mainthread.

Figure1: Main Thread Stack After Spawning Three Threads

Note that space has been reserved within the main thread's stack toallow the main thread to continue to populate its run-time stack. Alsoit is essential at this point in the program's execution to know theamount of memory that must be reserved to represent each of the spawnedthread'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 giventhread. Our memory disciplines make it possible to automaticallydetermine through compile-time analysis the amount of memory requiredfor each thread, including the main thread.

As execution proceeds, each of the three spawned threads and themain thread will continue to populate their respective stacks. At asubsequent execution point, assume the stack memory is organized asshown in Figure 2 below .

Figure2: Stack Organization After Each Thread Has Populated Its Stack

The scoped memory usage guidelines, as defined in the RTSJ, allowinner-nested objects to refer to objects residing in more outer-nestedscopes, but forbids references that go in the opposite direction. Figure 3 below illustrates a numberof allowed object reference relationships and Figure 4 following it illustratesseveral disallowed object reference relationships.

Figure3: Allowed References Between Nested Scope-Allocated Objects

These scope-nesting restrictions guarantee that there will neverexist a dangling pointer from an outer-nested object to an inner-nestedmemory location that no longer exists because its inner-nested scopehas been reclaimed.

This usage protocol requires that any data structures that need tobe shared between multiple threads must reside either in immortalmemory (the outer-most scope, which is never reclaimed) or must existwithin the parent or some other ancestor thread's stack above the pointat which the descendant thread was spawned.

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

Figure4: Disallowed References Between Scope-Allocated Objects

As seen in Figure 4 above ,besides disallowing references that originate in high-memory and pointto low-memory, these rules also prohibit pointers from within spawnedthreads to that portion of an ancestor thread that was populated afterthe point at which the child was spawned.

A special protocol must be enforced to support these conventions. Inparticular, whenever an ancestor thread desires to unwind its threadstack beyond the point at which it had spawned descendent threads, itmust wait for all of the threads that were spawned from this context toterminate execution before it returns from this context.

Otherwise, we might create a situation in which a spawned childthread refers to non-existent objects that once resided within theparent's scope. This special protocol is enforced by the hard real-timeJava byte-code verifier.

In particular, the byte-code verifier requires that the spawning ofa new thread or BoundAsyncEventHandler occur within a try statement,and that the corresponding finally statement include an invocation ofthe joinUninterrupted() operation on the corresponding ThreadStackobject.

This method waits for spawned thread to terminate before returning.This is exemplified in the following code:

try {
        NoHeapRealtimeThread thread = newA_NoHeapRealtimeThread(args);
        ThreadStack stack = newThreadStack(thread);

       stack.spawn(thread);
}     finally {
       stack.joinUninterrupted();
}

There are several ways to parameterize the ThreadStack constructor.An integer argument represents the desired number of bytes in thecorresponding ThreadStack. If the argument is of type Class and theclass represents a subclass of NoHeapRealtimeThread, the byte-codeverifier requires that the run() method for the class be declared withthe @StaticAnalyzable annotation to enable automatic determination ofits stack memory requirements.

If the argument is of type Class and the class represents anextension of BoundAsyncEventHandler, the byte-code verifier requiresthat the corresponding implementation of handleAsyncEvent() be declaredwith the @StaticAnalyzable to enable automatic analysis of theasynchronous event handler's worst-case stack memory needs.

Whenever practical, programmers are encouraged to use automaticanalysis of stack memory needs as this code will be much easier tomaintain.

Next in Part 2: Principles of Scoped Memory Operation

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

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.