February 7, 2011
Filip Pizlo
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. This presentation starts with my Stopless algorithm, which was the world’s first lock-free concurrent copying real-time garbage collector, and continues through the evolution of this approach. My subsequent Chicken and Clover algorithms improve on the Stopless design with opportunistic and probabilistic guarantees respectively. Finally, I present Schism, the world’s first wait-free concurrent copying garbage collector with proven time and space bounds. An implementation of these algorithms in two production-strength compiler infrastructures (Microsoft Bartok and Fiji VM) will be discussed, and a thorough evaluation of the collectors’ throughput and predictability characteristics will be presented. All four algorithms are shown to exhibit predictability and throughput that exceeds that of previous approaches to concurrent defragmentation.