Managed languages such as Java and C# are being considered for use in hard real-time systems. A hurdle to their widespread adoption is the lack of garbage collection algorithms that offer predictable space-and-time performance in the face of fragmentation. We introduce SCHISM/CMR, a new concurrent and real-time garbage collector that is fragmentation tolerant and guarantees time-and-space worst-case bounds while providing good throughput. SCHISM/CMR combines mark-region collection of fragmented objects and arrays (arraylets) with separate replication-copying collection of immutable arraylet spines, so as to cope with external fragmentation when running in small heaps. We present an implementation of SCHISM/CMR in the Fiji VM, 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. The results show that SCHISM/CMR tolerates fragmentation better than previous schemes, with a much more acceptable throughput penalty.
@inproceedings{Pizlo+2010PLDI,
author = {Pizlo, Filip and Ziarek, Lukasz and Maj, Petr and Hosking, Antony L. and Blanton, Ethan and Vitek, Jan},
title = {Schism: Fragmentation-Tolerant Real-Time Garbage Collection},
booktitle = {ACM SIGPLAN International Conference on Programming Language
Design and Implementation},
series = {PLDI},
year = {2010},
pages = {146--159},
month = {June},
address = {Toronto, Canada},
doi = {10.1145/1806596.1806615},
acm = {http://dl.acm.org/authorize?N93667},
gscholar = {62}
}