Multi-million line systems are being developed in Java for avionics, shipboard computing and simulation. A key attraction of the Real-Time Specification for Java for such systems is that it makes it possible to develop applications that mix hard-, soft-, and non-real-time tasks in the same environment in a memory-safe way. Unfortunately these advantages come at the expense of predictability of the real-time subsystems. One of the main culprits for such unpredictability in Java is garbage collection, which often requires applications to be interrupted for hundreds of milliseconds. Such pauses are not acceptable in real-time systems. One way to address this critical problem is to develop real-time garbage collectors (RTGC) with worst-case bounds on pause times and minimum mutator utilization. RTGC research is still in its infancy. There are limits to the applicability of current algorithms in terms of the strength of the timing guarantees that they offer. Furthermore, one serious limitation to the use of RTGC in safety- and mission- critical settings is the issue of certification of the software. In the current state of the art, no garbage collector has been formally verified. Without these guarantees there is little hope of adoption.
This research comprises work on two crucial issues in real-time virtual machines for high-level languages. First, it is exploring new approaches to RTGC based on probabilistic lock-free synchronization that provide strong timing guarantees that have a vanishingly small probability of being violated. Second, it uses theorem proving to generate a provably correct garbage collection algorithm. This step is critical for certification of advanced runtime environments and, as best is known, has never been attempted before. RTGC prototypes are being implemented in the context of a high-performance open source real-time Java virtual machine. This experimental platform is an industrial strength implementation of Java which is the only Java virtual machine to have been flight tested (in a collaboration with Boeing). Outcomes include empirical results for a suite of large real-time Java programs. All results are being released as open source.
This project looked at producing high-assurance certified automated memory managment algorithms. Our main achievement is the invention of a new algorithm which we call Schism. Schism addresses a hard problem: while managed languages such as Java and C# are being considered for use in hard real-time systems, the hurdle to their widespread adoption is the lack of garbage collection algorithms that offer predictable space-and-time performance in the face of fragmentation. Fragmentation is a common phenomenon in long-lived computer systems where the memory available for computation is broken off into a myriad of small pieces, none large enough to be of use. Schism is a new concurrent and real- time memory management algorithm that is fragmentation tolerant and guarantees time-and-space worst-case bounds while providing good througpput. Schism combines best of breed memory management techniques such as mark-region collection of fragmented objects and arrays with separate replication-copying collection of immutable arraylet spines, so as to cope with external fragmentation when running in small heaps. This unique combination makes it possible for Schism to manage reliably the memory of hard real-time embedded systems without pausing the application for long periods of time. We also implemented Schims in a virtual machine that was partially funded by this project, and later transitioned to a startup company. The Fiji VM is a high-performance Java virtual machine for mission-critical systems, along with a thorough experimental evaluation on a wide variety of architectures, including server-class and embedded systems. Our final result show that the novel algorithm outperforms commercial products from IBM and Oracle and provide the best all-round performance and predictability for embedded systems.
