Photo
METRONOME

Real-time Garbage Collection is the process of collecting data that is no longer in use by an application at the same time that the application continues to run, while keeping the interruptions by the collector (also called pause times) short and evenly spaced. The goal of the Metronome project is to produce a garbage collector with pause times that are below 1 millisecond in the worst case while providing highly uniform CPU utilization, low memory overhead, and low garbage collection cost.

To date we have achieved these goals with a maximum pause time of 2 milliseconds. The results rely on:

  • Metronimic Scheduling, in which real-time scheduling is based on time rather than work quanta, which we show to be fundamentally necessary for real-time response and different from most previous real-time collectors.
  • A high-performance read-barrier with only 4% CPU overhead. This is an order of magnitude faster than previous software read-barriers which typically had overheads of 20-40%. We achieve this high performance by tightly integrating the collector with the compiler, which is able to extensively optimize the read barrier.
  • Arraylets, a technique for efficiently breaking up large arrays into smaller objects to limit the real-time cost of scan, update, or move operations on large objects.
Based on these techniques, we are able to provide guaranteed performance based on a small number of input parameters from the programmer (maximum heap size, allocation rate, and either CPU utilization requirement or space utilization requirement).

 

Current research focuses on driving maximum pause times down to 250 microseconds, reducing space overhead with real-time generational collection, extending the system to work on multiprocessors, and defining a comprehensive set of interfaces and real-time services for a garbage collected virtual machine.

The first implementation of Metronome was in the open-source Jikes Research Virtual Machine (RVM). A second-generation implementation is now under way in IBM's J9 production virtual machine.

University collaborations are under way with the University of California, Berkeley, the Universität Salzburg, and Cambridge University.

 

Previous work on multiprocessor concurrent garbage collection demonstrated the feasibility of building a very low-latency, multiprocessor garbage collector based on reference counting with cycle collection. The result was the Recycler, which combined reference counting with a novel scheme for deferred reference count updates that are pipelined to a garbage collection processor, along with a sophisticated concurrent cycle collection algorithm.