Teresa Higuera
email: teresa.higuera@inria.fr

Michel Bana

Tre Jean-Philippe

Lesot Fre

 De

Ric Parain

Gilbert Cabillic

Memory Management for Real-Time Java: An Ef®cient Solution using Hardware Support*

Keywords: Java, real-time, embedded, garbage collection, memory regions, write barriers, performance

This paper addresses the issue of improving the performance of memory management for real-time Java applications, building upon the real-time speci®cation for Java (RTSJ) from the Real-Time Java Expert Group. In a ®rst step, a collecting dynamic memory solution including both a real-time garbage collector and region-based memory management, is proposed. A thorough analysis of the parameters in¯uencing the performance of write barriers in memory management, together with ways of improvement are then presented. Finally, the implementation of a memory management solution compliant with the RTSJ and integrating the proposed improvements is sketched.

Introduction

The Java environment provides attributes that make it a powerful platform to develop embedded real-time applications. However, it presents some important lacks regarding its use in this kind of systems (Higuera et al., 2000). The original Java platform was designed for computers with RAM memory ( personal computers or workstations). Then, other Java platforms were de®ned to support real-time and embedded systems. In particular JavaCard (Sun, 1998), EmbeddedJava (Sun, 1999) and PersonalJava (Sun, 1998) are three different platforms from Sun Microsystems. But none of these Java adaptations integrate the techniques and methods that real-time systems require.

The National Institute of Standards and Technology (NIST), has produced a basic requirements document (Carnahan, 1998) for a standard real-time Java API extension. Solutions that comply with this document are the real-time speci®cation for Java (RTSJ) (RTJEG, 2000) and the real-time core extension for the Java platform (RT Core) (J Consortium, 1999). There are some other solutions that were introduced before the NIST document. The simplest one is a prototype introducing tasks support over RT-Mach (RT-Threads) [START_REF] Miyoshi | Implementation and evaluation of Real-time Java threads[END_REF]. Another proposal is the portable executive for reliable control (PERC) [START_REF] Nilsen | Adding real-time capabilities to Java[END_REF], that is close to the J Consortium solution, the latter being actually an evolution of PERC. A very different solution is the communication threads for Java (CTJ) [START_REF] Hilderink | A new Java thread model for concurrent programming of real-time systems[END_REF], that is based on the CSP algebra, the Occam2 language and the Transputer microprocessor. Other solutions integrate the JVM into the operating system such as the GVM (Bak et al., 1998), a prototype centered around resource management. Another option to improve the performance of Java is to integrate the JVM in a microprocessor as the Aj-100 (Hardin, 2001), which implements the entire JVM instruction set in silicon and directly supports the Java thread model in hardware.

We have analyzed and studied how the above solutions resolve the problems that Java presents to effectively support embedded real-time applications (Higuera et al., 2000). We have divided these problems in the following categories: (i) the inability to access the underlying hardware, (ii) the unspeci®ed behavior for thread scheduling, (iii) synchronization that requires stronger semantics, (iv) the inability to handle events, (v) the inability to specify resources, and (vi) dynamic memory management. A comparison of the aforementioned solutions is summarized in Table 1.

From our point of view, the RTSJ constitutes the most adequate solution for real-time systems in general, and a hardware support such as Aj-100 enables improving the system's performance. In the context of the activities of the Solidor group at INRIA, we are currently developing a Java-based software environment accounting for embedded real-time [START_REF] Issarny | Providing an embedded software environment for wireless PDAs[END_REF]. This paper focuses on how to make Java memory management real-time while accounting for relevant Java speci®cations: the RTSJ, the KVM (Sun. 1999) targeting limited-resource and network connected devices, and the picoJava microprocessor core (Sun, 1999).

Background

Implicit garbage collection has always been recognized as a bene®cial support from the standpoint of promoting the development of robust programs. However, this comes along with overhead regarding both execution time and memory consumption, which makes (implicit) garbage collection poorly suited for small-sized embedded real-time systems. This must not lead to undertake the unsafe primitive solution that consists in letting the

(i) (ii) (iii) (iv) (v) (vi) RTSJ A A A A M A RT Core A A A M M A PERC A A M M A A RT-Threads A A Ð Ð M M CTJ A Ð Ð Ð Ð Ð GVM M A Ð Ð M Ð Aj-100 A A A M M M
Notes. We use A, M, andÐto respectively mean that the corresponding issue is addressed in detail, only partly addressed, and not addressed.

application programmer to explicit deal with memory reclamation. As an alternative, region-based memory allocation enables grouping related objects within a region. This is an intermediate solution between explicit memory deallocation (e.g., free() in C) and garbage collection. Application of the two above implicit strategies has been studied in the context of Java, which are combined in RTSJ. The MemoryArea abstract class supports the region paradigm in RTSJ through the following three kinds of regions (see Figure 1): (i) immortal memory contains objects whose lifetime ends only when the JVM terminates (i.e., supported by the ImmortalMemory 1 and the ImmortalPhysicalMemory classes); (ii) (nested) scoped memory enables grouping objects having well-de®ned lifetimes and that may either offer temporal guarantees (i.e., supported by the LTMemory class) or not (i.e., supported by the VTMemory and the ScopedPhysicalMemory 2 classes) on the time taken to create objects; and (iii) the conventional heap (i.e., supported by the HeapMemory class).

Whereas there are only one ImmortalMemory and one HeapMemory objects in the system, several ImmortalPhysicalMemory and ScopedMemory objects can exist. Then, an application can allocate objects into the heap, the immortal region, or several scoped regions. Several related threads, possibly real-time, can share a memory region, and the region must be active until the last thread has exited. The default region is the Java heap. Allocations outside the active region can be performed by the newInstance() methods or the newArray() as shown in Figure 2.

Paper Organization

In the context of RTSJ, this paper proposes such a study, focusing on minimizing the execution time overhead caused by write barriers in implicit memory reclamation. We ®rst present basic modi®cations to the garbage collector of a Java VM in order to make it compatible with real-time tasks execution, and a possible implementation of the memory region abstraction presented by the RTSJ (Section 2). A thorough analysis of the parameters in¯uencing the performance of write barriers is presented regarding the management of memory regions (Section 3). A solution improving the write barrier performance of both memory regions and the collector is then given (Section 4). Results of this analysis are further exploited to derive a memory management solution for a Java environment aimed at wireless PDAs, which we are experimenting through adaptation of the KVM (Section 5). Finally, a summary of our contribution together with an overview of our ongoing and future research work towards offering an overall memory management solution for next-generation wireless PDAs conclude this paper (Section 6).

The Basic Approach

From a real-time perspective, the garbage collector (GC) introduces unpredictable pauses that are not tolerated by real-time task. Real-time collectors eliminate this problem but introduce a high overhead. An intermediate approach is to use memory regions (MRs) within which allocation and deallocation are customized, and also space locality is improved. Note that both collection strategies are complementary: a GC may be used within some regions in order to limit their size, while the use of regions allows reducing the runtime overhead due to GC.

In this section, we propose a possible implementation of memory reclamation for Java that is compliant with the RTSJ speci®cation [START_REF] Bollella | The real-time speci®cation for Java[END_REF]. The proposed solution addresses real-time constraints of the GC in the heap, and the problem associated with inter-region references introduced by MRs (i.e., external references, illegal accesses, and illegal references).

GC Strategy

There are some important considerations when choosing a real-time GC strategy. Among them are space costs, barrier costs, and available compiler support. Copying GCs require doubling the memory space, because all the objects must be copied during GC execution. Non-copying GCs do not require this extra space, but are subject to fragmentation. We speci®cally base our solution on the incremental non-copying collector called treadmill (Baker, 1991). Since this allows the application to execute while the GC has been launched, a mechanism, called read barrier, is used to keep the state of the GC consistent by coordinating the execution of the GC and of the application. The basic algorithm is as follows (see Figure 3): an object is colored white when not reached by the GC, black when reached, and gray when it has been reached, but its descendants may not be (i.e., they are white). Gray objects make a wavefront, separating the white (unreached) from the black (reached) objects, and the application must preserve the tri-color invariant that no black objects have a pointer to a white object, which is achieved using read barriers (i.e., the white object is grayed when it is accessed). The collection is completed when there are no more gray objects. All the white objects can then be recycled and all the black objects become white after the recycling phase. In this process, objects that must execute the finalize() method 3 are moved to a ®nalize-list as in the Kaffe JVM (Petit-Bianco and Tromey, 1998).

To coordinate the application and the GC, we use write barriers (i.e., a white object is greyed when the application creates a pointer from a black object) instead of read barriers (Wilcon and Johnstone, 1993). This decision is motivated by the fact that write barriers are more ef®cient than read barriers, 4 and that the resulting collector can further be easily extended to generational, distributed, and parallel collection. Then, violation of the tricolor invariant must be checked when executing instructions that store references within MEMORY MANAGEMENT FOR REAL-TIME JAVA other objects (or arrays) (i.e., when executing putfield, putstatic, aputfield quick, aputstatic quick, aastore, or aastore quick bytecodes).

Dealing with Fragmentation

In general, memory fragmentation is not a severe problem, but for embedded systems (like PDAs) the amount of memory is normally small. Additionally, if the application only allocates objects with small size, acceptable worst-case bounds can be given. For objects with large size, strategies such as fragmenting the object into smaller-size chunks may be used. Another strategy relies on occasionally running a compacting GC, which implies some degradation of real-time guarantees. Since in Java, the size of reachable objects does not change much and is rather small (see Table 2 for applications from SPECjvm98; SPEC, 1998), the average cost of each compactation phase is constant.

Normally, to reduce the cost of object relocation, each object has a non-moving handle. Compaction is made in two phases: the object space is ®rst compacted, and the handles are then updated. In this way, relocating objects is transparent to the application program, which always accesses objects using their non-moving handle. Given the small average object size (i.e., 36 Bytes), it appears imperative to keep the number of header words to a minimum. For example, a header of only a word will consume about 11% of the total memory heap, whereas if the header has two words, this consumption will increase to 20%. Hence, for some applications, it can be interesting to not use a compacting phase, avoiding handles.

Since objects outside the heap are not moved, we can improve the performance by avoiding the handle of these objects, and hence use direct reference objects. Eliminating handles improves also the memory consumption in a word per object. Note that this strategy is always possible even if the GC has a compactation phase requiring handles for objects within the heap. Suppressing handles in the heap improves the performance of both the application and the collector.

External References

Since objects allocated within immortal or scoped regions may contain references to objects in the heap, the collector must take into account these external references, adding them to its reachability graph. To facilitate this task, we color black each object allocated outside the heap (see Figure 4). In this way, a reference from an object allocated in a region (i.e., black) to an object in the heap that is still not reached (i.e., white) is treated as a write barrier (i.e., the white object is grayed to be reached by the GC). Black objects outside the heap are considered as root by the GC. This requires that all objects of all the MRs must be explored by the collector, which introduces high overhead. Scoped regions can be nested. A safe region implementation requires that a region gets deleted only if there is no external reference to it. This problem has been solved in RTSJ by using a reference-counter for each region which keeps track of the use of the region by threads, and a reference-counting GC collects scoped memory regions when their reference-counter reaches 0. The reference-counter is increased upon entering a new scope through the enter() method, the creation of a real-time thread with a scoped region, and the opening of an inner scope. It is decreased when an inner scope returns from its enter() method or when the real-time thread using the scoped region exits.

Illegal Accesses

RTSJ makes distinction between three main kinds of tasks: (i) critical tasks that cannot tolerate preemption latencies, (ii) high-priority tasks that cannot tolerate unbounded preemption latencies, and (iii) low-priority tasks that are tolerant with the GC. 5 Whereas high-priority tasks require a real-time GC (i.e., the behavior of the algorithm given in Section 2.1 must be deterministic), critical tasks must not be affected by the GC, and as consequence cannot access any object within the heap. To detect these illegal accesses, we introduce a fourth color (e.g., red) meaning that the object cannot access objects within the heap (Figure 5).

An access from a red object allocated for a critical task to another object allocated in the heap (i.e., white, black, or gray) causes a MemoryAcessError exception. Illegal accesses from a red object to an object within the heap must be checked when executing instructions that load a reference to an object or array (i.e., at every read barrier, those bytecodes causing a load operation: getfield, getstatic, agetfield quick, agetstatic quick, or aaload and those causing a load-store operation: putfield, putstatic, aputfield quick, aputstatic quick, aastore, or aastore quick).

Illegal Asignments

The lifetime of objects allocated in scoped regions is governed by the control ¯ow (see Figure 6). To maintain the safety of Java and avoid dangling references, objects in a scoped MR can only reference objects within an outer region, within the heap, or within immortal memory. And, objects within the heap or within the immortal region cannot reference objects within a scoped region. In our example, an object within the scoped region associate which task t1 can only be referenced by objects allocated within the same region or within an inner region (see Figure 7), i.e., within the scoped region associated which task t3.

To detect illegal references, we propose a stack-based algorithm, which associates a region stack with each thread. Note that references from objects within the heap, an immortal MR, or a scoped MR, to objects within the heap or an immortal memory are allways allowed. Then the region stack of a thread supports scoped regions where the thread can reference objects. Figure 8 shows the region stack associated with the tasks of our example. This mechanism was introduced in Higuera et al., (2001) and is similar to the contaminated GC, a Java stack-based collector given in [START_REF] Cannarozzi | Contaminated garbage collection[END_REF], which collects objects when the scoped associated to a control ¯ow ends.

We detail below how to support such a functionality:

When an object is created, it is associated with the scope of the active region.

When removing a region, the top of the region stack is adjusted, and it is sure that there is no object dependent on an older scoped region. Note that the immortal memory and the heap, which are at the bottom of the stack end with the application, and as consequence are never removed from the stack.

Illegal inter-region references causes an IllegalAsignmentError exception and must be checked when executing instructions that store references to objects outside the heap within other objects (or arrays) (i.e., when executing putfield, aputfield quick, aastore, or aastore quick bytecodes). The putfield (aputfield quick) instruction causes the object X to reference Y, whereas the aastore (aastore quick) instruction stores a reference Y into an array X of references. If the object Y is within a scoped region, the region of the object X must be inner to the region of Y. This check can be made by using the region stack, from the region of X down to the region of Y (an outer region). If the region of Y is not found in the stack (i.e., the heap that is the outest region and hence the bottom of the stack is reached), this is noti®ed by throwing an exception.

Whereas the putstatic(aputstatic quick) instruction causes a reference to an object whithin the outermost region (i.e., the HeapMemory object). Then, checking the stack is not needed.

Analyzing the Performance of Region Management

In general, the management of memory regions introduces overhead, which we characterize in this section. The cost to maintain MRs is considered as a fraction of the total program execution time. To estimate the time overhead of different implementations, two measures are combined: (i) the number of events that occur during the execution of a program, and (ii) the measured cost of the event. Then, the region overhead is given by dividing the application execution time with the number of events and the cost per event. The region implementation given in [START_REF] Gay | Memory Management with Explicit Regions[END_REF] presents a time overhead that is constant per instruction executed. The RTSJ imposes strict rules on assignments to or from regions. The JVM must detect illegal accesses and assignments and throw an exception when they occur. Also, the collector must scan regions for references to objects within the heap which introduces an additional overhead.

Memory Management Overhead

Each MR is managed so as to embed objects that are related regarding associated lifetime and real-time requirements. GC within the heap relies on the (real-time) collector of the JVM. The immortal memory region is never subject to GC and may be exploited by critical tasks. And scoped region get collected as a whole once it is no longer used and may or may not be subject to internal real-time GC depending on their temporal properties. 6 Then, the overall cost introduced by region management is given by the cost associated with: region allocation, reference counter updates, and region deletion. The time cost to allocate a new region is always constant. Note that by collecting regions, problems associated with reference counting collectors are solved: the space to store reference counters is minimal, and there cannot be cycles among regions. Before cleaning a region, the finalize() method of all the objects in the region must be executed, and it cannot be reused until all the ®nalizes execute to completion. Problems with the finalize() method are resolved by adding to the ®nalize-list of the GC, all the objects within the terminated region that are pending to execute this method.

From a real-time perspective, regions give predictable performance, since the cost of every allocation operation is easily bounded. Assuming that objects in a ScopedMemory region are not subject to GC and may not be moved, 7 the time to allocate an object is proportional to the object size, and in the worst case may include time to acquire additional memory for the region. Whereas an allocation in a VTMemory region may take variable time, the time taken in a LTMemory region is linear to the object size. Then, the memory space for a LTMemory region must be continuous, 8 and its size is further speci®ed upon creation, remaining ®xed over its lifetime. Since objects allocated in LTMemory regions are not garbage collected the allocation time is proportional to the object size, 9 it is safe to associate this subclass with critical tasks. However, an instance of VTMemory is created with an initial size and may grow up to a given maximum size.

Region Barrier Overhead

Experimental measures indicate that in Lisp programs the references to the heap (as opposed to the runtime stack) account for an average of 12% of all executed instructions (Zorn, 1990). However, all the objects created in Java are allocated in the heap, only primitive types are allocated in the runtime stack (Gay and Steensgaard, 1998). In most applications of the SPECjvm98 benchmark suite, 10 less than half of the references are to the heap memory (i.e., 45%), the other half is to either the Java or the C stack (see Table 3), and about 35% of the total executed instructions are memory references [START_REF] Kim | Memory system behavior of Java programs: methodology and analysis[END_REF], where typically 70% are load operations and 30% store operations.

Then, 15% (i.e., 0.45 * 0.35) of instructions executed by a Java application is a reference into the heap or another memory region, where 11% require read barriers executing the code of Figure 9 for checking illegal accesses (see Section 2.4). Thus we estimate the read barrier overhead as 0.11 * read-Barrier, where the readBarrier parameter is the percentage of the number of instructions executed by the code taged as readBarrierMR proportional to the number of instructions required to access an object.

In addition, a 5% of executed bytecodes require write barriers executing the code of Figure 10 for checking illegal accesses and also illegal assignments (see Section 2.5).

Thus we estimate the inter-region reference overhead as 0.05 * writeBarrierRegion, where the writeBarrierRegion parameter is the percentage of the average number of instructions executed by the code taged as writeBarrierMR proportional to the number of instructions required by an assignment. Note that read barriers are not strictly necessary. The restriction on critical tasks can be reduced to write barriers checks since reads does not interfere with the GC. 11 Write barriers-supporting MRs include check for both illegal inter-region references (which causes an IllegalAssignmentError exception), and illegal access from critical task to objects within the heap (which causes a MemoryAccesError exception). We thus add the getWriteBarrierOverhead() method to the MemoryArea abstract class, which serves to identify region barrier overhead. Note that for write barrier-based collectors (e.g., incremental or generational collectors), this method gives the write barrier overhead caused by the GC.

Collector Barrier Overhead

Hence, the write barrier cost introduced by the GC is as for regions (i.e., 0.05 * writeBarrierCollector). However, in this case as shown in Figure 11, the writeBarrierCollector parameter is the average cost to preserve the tri-color invariant (e.g., test if a white object is referenced by a black object, then grey the referenced object and link it to the gray-list) proportional to the number of instructions required by an assignment.

The most common approach to implement write barriers is by in-line code, consisting in generating the instructions executing write barrier events with every store operation. This solution requires compiler cooperation (e.g., JIT), and presents a serious drawback because it nearly doubles the application's size. Regarding systems with limited memory such as PDAs, this code expansion overhead is considered prohibitive. Alternatively, we can instrument the bytecode interpreter, avoiding space problems, but this still requires a complementary solution to handle native code.

Minimizing the Write Barrier Overhead

A solution minimizing the write barrier overhead consists in using hardware support such as the picoJava-II microprocessor, 12 which allows performing write barrier checks in parallel with the store operation.

Using Hardware Support

Upon each instruction execution, the picoJava-II core checks for conditions that cause a trap. From the standpoint of hardware support for GC, the core of this microprocessor checks for the occurrence of write barriers, and noti®es them using the gc notify trap. This trap is triggered under certain conditions when assigning a new reference to a ®eld of an object (i.e., when executing putfield, putstatic, aputfield quick, aputstatic quick, aastore, or aastore quick bytecodes). The conditions under which this trap is generated are governed by the values of the PSR and the GC CONFIG registers. If the GCE bit of the PSR register is set, then write barriers are enabled. Hence to disable them it suf®ces to unset this bit. The GC CONFIG register governs two types of write-barrier mechanisms: page-and reference-based. We can use both mechanisms simultaneously. Also, we can disable either or both of the mechanisms if we do not want to use them (e.g., if the current tracing rate allows disabling the GC). The con®guration of this register is summarized in Table 4.

The reference-based write barriers of picoJava-II can be used to implement incremental collectors. An incremental collector traps when a white object is written into a black object; the GC TAG ®eld for black objects is %11 and for white objects %00 (see Figure 12).

The page-based barrier mechanism was designed speci®cally to assist train-based generational collectors (Wilson and Johnstone, 1993). A train-based generational collector traps when, within a larger memory divided into a number of ®xed-size spaces, an object (X) references another object (Y) located in the same space but in a different car (see Figure 13).

For example, if in the GC CONFIG register, we initialize the REGION MASK ®eld (h31 : 21i bits) as %00000000000, and the CAR MASK ®eld (h20 : 16i bits) as %11111, we divide the memory address space in 32 regions, each one divided in 16 KB cars (see Figure 14). If we choose a %11110 value for the CAR MASK, then we have 16 regions, and a car size of 32 KB.

We use the page-based write barrier mechanism to detect references across different regions. In order to use this hardware mechanism of picoJava-II, we adapt our algorithm as follows: (i) in the header object, the h31 : 30i bits give the color of the object and the h18 : 14i bits give the memory area in which the object is allocated, 13 and (ii) an associated exception handler determines whether to execute the algorithm described in Section 2.5 to detect erroneous inter-region references, and whether to execute actions preserving the tri-color invariant of the GC. The only overhead is the handling of the exception trap. However, this solution is very costly, due to the high costs of operating system traps.

Improving Write Barrier Performance

Regarding the proposed solution, which con®gures picoJava-II to enable page-based and reference-based write barriers, to handle the gc notify trap, we can distinguish three main conditions depending on the MR of the referenced object (i.e., the Y object): (A) when it is within the immortal region, (B) when it is within the heap, and (C) when it is within a scoped region (see Table 5). The A condition is always allowed and does not require any treatment. For the B condition, we must make distinction depending on the color of the object that makes the reference (i.e., the X object):

B.1 when the X object is black, B.2 when the X object is red and the Y object is within the heap.

Finally, for the C condition, we make distinction depending on the MR of the X object: C.1 is within the immortal region or within the heap, C.2 is within a different region than the Y object.

Figure 14. A memory map for memory regions: the h30 : 30i bits (i.e., GC TAG ®eld) and h1 : 0i bits (i.e., X and H bits) of the reference object are masked to address the object. Since we must treat each condition in a different way, it is pretty interesting to make distinction by hardware whether the trap is caused by a reference-or a paged-based condition 14 (e.g., gc notify 0 when reference-based traps and gc notify 1 when paged-based traps). In order to improve the performance of critical tasks, the treatment of the B.1 condition is prioritized. Then, we establish three main priority levels, where level 3 is the highest:

1. the reference-based write barrier trap is triggered, 2. the page-based write barrier trap is triggered, 3. both traps are triggered.

The exception with priority 3 treats the B.1 and B.2 conditions. The routine of priority 2 treats the A, C.1, and C.2 conditions. Finally, the routine associated with priority 1 treats the B.1 condition. Note that for the B.2 condition, both write barriers mechanisms are always activated (i.e., the heap have not red objects). These conditions must be treated as follows:

A: is always allowed. The above solution minimizes the cost of write barriers, which is zero for intra-region references. 15

Implementation Issues

This section discusses the implementation of a memory management strategy for a Java environment aimed at wireless PDAs. Regarding speci®cally the offered memory management, it builds upon the RTSJ and the KVM, and integrates the aforementioned solutions for improving the performance of write barriers in GC and region management.

Integration within the KVM

We are currently implementing the proposed memory management solution within the KVM in a way compliant to the RTSJ. The RTSJ de®nes the GarbageCollector abstract class, which has been specialized through an IncrementalGC subclass. We have implemented such a class within the KVM by modifying some ®les of the interpreter to support our real-time GC (i.e., garbage:c to implement the collector algorithm and interpreter:c to implement the write barriers, as well as native:h and nativeCore:c that support the interface for the Java native methods). The incremental collector can be introduced in the system by using the run-time type identi®cation (RTTI) that the class Class offers, (e.g., GarbageCollector gc (GarbageCollector) Class:forName (`IncrementalGC'):newInstance();).

As discussed in the previous section, a signi®cant source of performance improvement for memory management is to exploit hardware aid. We are thus implementing memory management so that it can be run over picoJava-II. In order to make our memory management implementation compliant with this microprocessor, we have modi®ed the object header tag of the KVM as follows: GC TAG h31 : 30i, SIZE H h29 : 19i, CAR MASK h18 : 14i, SIZE L h13 : 7i, TYPE h6 : 2i, X h1i, and H h0i. We thus take six bits of the KVM SIZE h31 : 8i ®eld (i.e., the maximum size of the objects has thus been reduced from 16 MB to 256 KB). Note that the restriction on object size is not severe penalty as suggested by the small average size of Java objects in SPECjvm98 (SPEC, 1998) applications (e.g., Jess 40 Bytes, Db 31, Javac 36, Mtrt 25, and Jack 31). We also reduce the KVM TYPE h7 : 2i ®eld since 5 bits are suf®cient (i.e., only 20 types are handled). These bits have been used as the GC TAG h31 : 30i, and the CAR MASK h18 : 14i ®elds of picoJava-II (i.e., these ®elds are used to store the color of the object and the embedding memory region). The KVM MARK BIT that is used by the collector to mark the object is no longer used because objects are marked by color. Then, this bit is exploited to support the X bit of picoJava-II. Finally, the KVM STATIC BIT is now used to mean the H bit of picoJava-II. Since the collector does not move objects, handles are suppressed. This strategy increases the performance of both, the application and the collector. Then, the H bit is ®xed to 0, and the core of picoJava-II accesses the object starting a word after the handle. Eliminating handles improves also memory consumption by a word per object. Given the small average size of Java objects the space overhead can be reduced to 12% of the total dynamic memory space (i.e., 4=33 4 6 100, where 4 and 33 are respectively the handle size and the average size of Java objects in bytes). Since objects in memory regions are not moved, this strategy is always possible even if the objects in the heap are accessed via a handle.

Experiment

Instead of using the SPECjvm98 benchmark, which is not compatible with the KVM, we use an arti®cial collector benchmark. This is an adaptation made by Hans Boehm from the John Ellis and Pete Kovac benchmark. 16 Two data structures of the same size are kept around during the entire process: (i) a tree containing many pointers and (ii) a large array containing double precision ¯oating point numbers, which we have modi®ed to contain integers to make it compatible with the KVM. This benchmark executes 262610 6 bytecodes and allocates 408 MB. Then, the allocation rate is about 1.6 KB/1000-executed bytecodes. The number of garbage collection pass, the total time spent by garbage collection in microsecond, and the percentage overhead introduced by our collector are given in Table 6.

The maximum latency to preempt the incremental collector has been measured as 1 ms. The number of executed bytecodes performing write barrier test is 15610 6 (i.e., aastore : 1610 6 , putfield : 6610 6 , putfield fast : 7610 6 , putstatic : 19, and putstatic fast : 0) for a total of 262610 6 executed bytecodes. This means that 5% of executed bytecodes perform a write barrier test, as already obtained in Section 3.2 with SPECjvm98 (SPEC, 1998). And the overhead introduced by the software write barrier test in each assignment, is: 31% to maintain the root-set.

31% to preserve the tri-color invariant. 65% to detect possible illegal references. 45% to check a nested scoped level.

Additional Considerations

Our solution requires con®guring write barriers in picoJava-II. Notice that if the GCE bit of the PSR register is set, write barriers are enabled. The instruction set of picoJava-II provides extended bytecodes allowing access to the PSR and the GC CONFIG registers (i.e., priv read psr, priv write psr, priv read gc config, and priv write gc config). The routines given in Figure 16 allow enabling and disabling write barriers. Whereas, Figure 17 shows how reference-and page-based write barriers can be enabled to have our desired con®guration. In this example, we have chosen 32 regions with a car size of 16 KB, and we have established the following color codes: %11, %10, %01, and %00 meaning black, gray, red, and white, respectively. The partition of the heap in cars is transparent for the GC by using a mask (e.g., $FFE0FFFF). This implementation is ef®cient, but quite in¯exible. We must con®gure the system to determine the virtual region memory map. In addition, our solution requires the size of a region to be a multiple of the car size, which may possibly introduce internal fragmentation. Finally, for a VTMemory scoped region that can change its size up to its maximumSize, the additional memory must be assigned in terms of cars. This problem can be unpractical for classes dealing with I/O mapped memory (e.g., ScopedPhysicalMemory), which specify in their constructor not only the size of the region, but also the base address. However, our solution improves the memory management performance, because it minimizes the cost of intra-region references, which has been reduced to the write barrier cost introduced by the GC algorithm in the heap, and to zero for the other memory regions. Note further that intra-region references are much more frequent than inter-region references.

Conclusion

This paper has presented solutions for improving the performance of memory management in the RTSJ, hence addressing performance improvement of both GC and region management. Our proposal builds upon existing work since the area of memory management in general, and of GC in particular, has for long been deserving a great deal of attention in the programming language and system communities. The contribution of our work comes from the adaptation and integration of relevant solutions, in the context of the RTSJ, based on the analysis of the parameters that are the most in¯uential in memory management performance. In addition, we have discussed the implementation of the resulting memory management solution within the KVM.

We omit write barriers in native code, which may be addressed using either of the two following solutions: (i) forcing the native code to register their writes explicitly, or (ii) using virtual memory protection to detect and register changes. The latter solution needs further investigation because it is not trivial to combine real-time bounded collection with barriers supported in the MMU. Our solutions for improving performance of memory management partly addresses the use of hardware aid by exploiting existing hardware support for Java (i.e., picoJava-II). In general, our study should be complemented with work on improving memory management performance at the hardware level considering both hardware aid and the features of the underlying processor, e.g., impact of garbage collection upon cache management [START_REF] Kim | Memory system behavior of Java programs: methodology and analysis[END_REF].

Notes

1. This class supports a region with special memory attributes (e.g., ALIGNED, BYTESWAP, DMA, and SHARED). 2. This class supports a memory region with physical properties, having limited lifetime. 3. This method is a member of the Object class, which is executed just before discarding an object marked as garbage. 4. Whereas read barriers take actions upon every each object access, write barriers take actions when the application updates pointers. 5. In RTSJ, critical tasks are instances of the NoHeapRealtimeThread class, high-priority tasks of the RealtimeThread class, and low-priority of the Thread class. 6. We can build a VTMemory object with a speci®c GC. Note that in this case, critical tasks must be able to use it. 7. This is always the case for objects within an instance of LTMemory but this is not mandatory for objects within an instance of VTMemory. 8. Typically, the ScopedMemory implementation is made by using malloc() and free() routines to manipulate memory. 9. In Baker-based algorithms, the work of the GC is performed in small increments triggered by allocations requests. 10. http://www.spec.org/osg/jvm98 11. We apply the same optimization as for the incremental GC which is to use write barriers instead to read barriers. 12. http://www.sun.com/microelectronics/picoJava

Figure

  Figure 1. The MemoryArea hierarchy: Whereas ImmortalMemory, HeapMemory, and ImmortalPhysicalMemory objects end with the application, the life of ScopedMemory objects depend on the program control ¯ow.

Figure 2 .

 2 Figure 2. Using memory regions in RTSJ: This code shows a real-time thread, which allocates an array of 10 integers in the heap, and another of 20 integers in the MR called myRegion.

Figure 3 .

 3 Figure3. The GC strategy: to maintain list coherency, all the operations on shared lists must be synchronized with the application threads.

Figure 4 .

 4 Figure 4. External references: objects within the heap referenced from immortal or scoped regions must be considered reachable by the GC.

Figure 5 .

 5 Figure 5. Illegal accesses: red objects cannot access objects within the heap.

Figure 6 .

 6 Figure6. Using scoped memory regions in RTSJ. This code shows three tasks (t1, t2, and t3), whose one is critical (t3), which allocate allocating objects in a MR (i.e., t1 within r1, t2 within r2, and t3 within r3).

Figure 7 .

 7 Figure 7. Illegal references: an object within a scoped region can only be referenced by objects from the same region or within an inner region (the region r3 is inner to the region r1 from the code of Figure 6.

Figure 8 .

 8 Figure 8. Region stack: Each task has an associated region stack: (a) region stack of the critical task t1, (b) region stack of task t2, and (c) region stack of task t3.

Figure 9 .

 9 Figure 9. Read barrier code for MRs.

Figure 10 .

 10 Figure 10. Write barrier code for MRs: the checkNestedRegions() function is an implementation of the algorithm given in Section 2.5.

Figure 11 .

 11 Figure 11. Write barrier code for the collector.

Figure 12 .

 12 Figure 12. Reference-based write barriers.

Figure 13 .

 13 Figure 13. Page-based write barriers.

  Two different mechanisms detect the above conditions: (i) B.1 and B.2 conditions are partly detected by reference-based write barriers and (ii) A, B.1, B.2, C.1, and C.2 conditions are detected by page-based write barriers mechanisms. Then, B.1 and B.2 conditions are detected by both mechanism reference-and page-based write barriers.

B. 1 :

 1 colors gray referenced object. B.2: throws the MemoryAccessError exception. C.1: throws the IllegalAssignmentError exception. C.2: explores the region stack associated to the active task.

Figure 15 .

 15 Figure 15. Treating write barrier exceptions.

Figure 16 .

 16 Figure 16. Enabling and disabling barriers. If the GCE bit of the PSR register is set, then the paged-based writebarriers are able. Hence to disable them it is suf®ce to set the bit to 0.

Figure 17 .

 17 Figure 17. Con®guring write barriers: We have established the following color codes: %11, %10, %01, and %00 mean black, gray, red, and white respectively. And we have divided the address space in 32 regions.

Table 1 .

 1 Comparison of studied solutions.

Table 2 .

 2 Object characterization: number of objects allocated by each application, average object size in Bytes, average object lifetime in millions of references, and average number of references per each object.

		Allocated objects	Size	Lifetime	References
	JESS	8,131,609	40	1.3	87
	DB	3,262,899	31	129.5	449
	JAVAC	6,244,896	36	55.2	116
	MTRT	6,695,116	25	10.8	86
	JACK	6,955,528	31	1.6	147

Table 3 .

 3 Memory reference characteristics: number of instructions executed for each application, heap memory allocated in KB, and average allocation rate in Bytes/(1000 instructions).

		Executed	Data	Percentage of references
		instructions	references	into the heap
	JESS	9,168610 6	1,798610 6	39:40
	DB	712610 6	3,211610 6	45:61
	JAVAC	7,717610 6	2,515610 6	28:70
	MTRT	3,917610 6	1,129610 6	50:97
	JACK	6,553610 6	2,014610 6	50:74

Table 4 .

 4 Garbage collector register (GC CONFIG).

	Bits	Field	Type	Description
	31 : 21	REGION MASK	RW	It allows knowing if both, the reference and
				the stored data belong to the same page.
	20 : 16	CAR MASK	RW	It allows knowing if both, the reference and
				the stored data belong to the same car.
	15 : 0	WB VECTOR (Write Barrier Vector)	RW	If the corresponding bit is set, then, the above
				bytecodes signal a gc notify trap.

Table 5 .

 5 Treatments for inter-region references.

	X object	Y object	Treatment
	Immortal	Immortal	Allowed
	Immortal	Heap	Color analysis
	Immortal	Scoped	Illegal assignment
	Heap	Immortal	Allowed
	Heap	Heap	Color analysis
	Heap	Scoped	Illegal assignment
	Scoped	Immortal	Allowed assignment
	Scoped	Heap	Color analysis
	Scoped	Scoped	Region stack exploration
			(when both scoped regions are different)

Table 6 .

 6 Garbage collection overhead.

	Memory heap	GC pass	Time collecting	Execution time	Percentage overhead
	8 MB	51	13:54610 6	72:87610 6	18.85
	16 MB	27	13:17610 6	72:72610 6	18.11
	24 MB	17	12:80610 6	71:99610 6	17.80
	32 MB	13	11:82610 6	70:50610 6	16.50

* This work has been partially funded by Texas Instruments.

 Petit-Bianco, A., and Tromey, T. 1998. Garbage collection for Java in embedded systems. In Proceedings of IEEE Workshop on Programming Languages for Real-Time Industrial Aplications, December. RTJEG (The Real-Time for Java Expert Group). 2000. The real-time speci®cation for Java. Technical Report, RTSJ, http://www.rtj.org, June. SPEC (The Standard Performance Evaluation Council)