Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors

Existing real-time garbage collectors are either unable to scale to large multiprocessors, or unable to meet hard real-time requirements even with specialized hardware support.

These limitations are rapidly becoming unacceptable: hardware improvements have brought multi-gigabyte heaps and ubiquitous multi-core parallelism; applications have increasingly stringent real-time requirements; and non-embedded, highly parallel server applications form an increasing percentage of real-time workloads.

We present Staccato, an algorithm that supports both hard- and soft-real-time garbage collection on stock hardware and both real-time and stock operating systems. The algorithm is incremental, concurrent, and parallel. Defragmentation can be performed on a per-object basis using a lock-free algorithm which requires no atomic mutator operations in the common case. On a real-time operating system it is capable of meeting hard real-time bounds.

We have implemented Staccato in IBM’s J9 virtual machine and present an evaluation on IBM’s real-time variant of Linux. Staccato is able to achieve maximum pause times of 753μs and an MMUof 85% over a 5ms time window, out-performing both IBM’s Metronome-based product and Azul’s soft real-time, hardware-assisted collector.