Schism: Fragmentation-Tolerant Real-Time Garbage Collection

Pizlo, Filip and Ziarek, Lukasz and Maj, Petr and Hosking, Antony L. and Blanton, Ethan and Vitek, Jan

Abstract

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}
}