Time-Predictable Dynamic Memory Management for Java Based on Reference Counting

Abstract

Certain types of computer systems, hard real-time safety-critical systems, must be able to guarantee their correct operation. Any incorrect actions potentially lead to injury or substantial property damage. These systems must function correctly and they have to prove that they do so within a specified time. Attesting that these hard real-time systems are timely necessitates static analysis of their executing code. Usual approaches to Garbage Collector (GC), a powerful tool that makes the code simpler to develop and safer, complicate the timing analysis. This work suggests a different approach, performing a system’s memory management tasks in a separate hardware unit, the Reference Counting Unit (RCU), thereby simplifying static analysis and improving worst-case performance. This thesis presents both the concepts and specific memory models underpinning the RCU, and how they relate to Java (the programming language targeted). Because the RCU implements a reference counting GC algorithm, special consideration must go to how the unit handles certain data structures. Avoiding fragmentation of the heap is a priority; the types of system that this work targets expect to be in operation for long periods of time. Use of an RCU compatible collector changes the analysis of a system’s execution time; the affected set of operations no longer complete within a constant length of time. That necessitates a change in how the bytecode, the compiled form of Java, is analysed. Multiple implementations of the RCU concept have been tested. The first, the Reference Counting Memory Management Unit (RCMMU), targets single-core designs and its effectiveness validates the idea. The second, the Extended Reference Counting Memory Management Unit (XRCMMU), also targets single-core applications and adds a Heap Access Unit (HAU), completing the same benchmark in 25% of the time for an RCMMU-based system. Investigations have looked at multi-core options; different core topologies have their own impacts on how the data relating to in-use and collectable objects can be kept accurate. Of those, the Time-Division Multiple Access Reference Counting Memory Management Unit (TDMA-RCMMU) is developed further and shows strong performance, completing one benchmark 3.7 times faster when utilising four cores instead of one.