No Silver Bullet - Garbage Collection for Java in Embedded Systems

Which Garbage Collection for Embedded Java?

In order to adapt Java garbage collection to embedded systems, you must consider four issues: the nature of the runtime environment, the hardware characteristics and limitations of the embedded platform, the expected performances (acceptable general overhead and maximum pause times), and the way in which critical memory situations need be handled.

The runtime environment will mainly influence the way roots are identified. An interpreted or semi-compiled (JIT) environment can make references clearly identifiable so the Java heap and the Java stack can be scanned non-conservatively. On the other hand, the pre-compiled approach -- like the one currently being developed at Cygnus -- needs to rely on conservative scanning, unless additional information is made available to the runtime by a cooperative compiler.

Memory, both RAM and ROM, is a scarce resource. Memory constraints usually rule out all copying and generational algorithms and prevents sophisticated solutions like adaptive collectors (that are dynamically changing the way they garbage collect the memory to achieve greater efficiency) or cooperative collectors (featuring several algorithms in one collector, to get the best of several worlds) because of the amount of ROM required for their implementation.

Additionally, reference counting requires the count field of an allocated object to be roughly the same size as a pointer or some other value that can represent all valid addresses of the system. This field has to remain tied to the object. On the other hand, information tags required by a mark and sweep range from a minimum of 1 bit to several bits for the implementation of three colors algorithms (which are based on an abstraction introduced by Dijkstra, attributing different colors to memory cells depending on the need for the collector to visit, re-consider or discard them) or pointer-reversal marking algorithms (a time and space bound algorithm that stores in the currently examined memory cells the value of its parent pointer).

Most embedded systems don't provide swapped virtual memory, which implies that accessing a random portion of the memory has a fixed cost. This diminishes the impact of the mark-sweep and the space-costly copying collectors that visit all live cells before reclaiming the dead ones. On the other hand, this also means the heap can't be expanded. When reaching a low water mark situation, the collector can't count on tapping some virtual memory as a temporary solution.

An embedded application running Java has a strong chance of being interactively operated by a user. This demands a fast, non-disruptive garbage collector that also provides predictable performance for future memory allocation. Periodically performing partial garbage collection must be sufficient to prevent the need to run the garbage collector when a cell is allocated. However, no noticeable slow down should occur in the extreme case that the collector is forced to run.

You can enhance predictability by improving heap fragmentation so that the low-level operation of reserving memory doesn't have to scan the heap trying to find sufficient free memory for an indeterminate amount of time. It should also be guaranteed to succeed if enough free memory is known to be present. It is unacceptable for an embedded system to have a memory allocation failure because the fragmentation of the heap prevents the allocator from finding a memory block of a sufficient size.

Fragmentation can be fought by compacting the heap. While compacting the heap, cells can be moved either by using a technique called sliding, where the cells' allocations are retained, or by using a technique called linearizing, where a cell pointed to by another cell is moved to a close adjacent position. In addition to the copying algorithm, which compacts the heap as a side-effect of copying a live cell from one semi-space to an other one, there are several compacting mark-sweep algorithms (also called mark-compact) with complexities ranging from O(M) to O(M log M) (where M is the size of the heap). Note that conservative scanning imposes restrictions on objects that can be moved.