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.

By: Bill McCloskey; David F. Bacon; Perry Cheng; David Grove

Published in: RC24504 in 2008


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .