A Lock-Free, Concurrent, and Incremental Stack Scanning Mechanism for Garbage Collectors

• Main Authors: Gabriel Kliot, Erez Petrank, Bjarne Steensgaard
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Subjects: Algorithms; Design; Performance; Reliability Keywords Stack scanning; Lock-free data structures; Incremental and Concurrent garbage collection; The Pointers
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.155.136; http://www.cs.technion.ac.il/~gabik/publications/StackScanning-OSR2009.pdf

Two major efficiency parameters for garbage collectors are the throughput overheads and the pause times that they introduce. Highly responsive systems need to use collectors with as short as possible pause times. Pause times have decreased significantly over the years, especially through the use of concurrent garbage collectors. For modern concurrent collectors, the longest pause is typically created by the need to atomically scan the runtime stack. All practical concurrent collectors that we are aware of must obtain a snapshot of the pointers on each thread’s runtime stack, in order to reclaim objects correctly. To further reduce the duration of the collector pauses, incremental stack scans were proposed. However, previous such methods employ locks to stop the mutator from accessing a stack frame while it is being scanned. Thus, these methods introduce potentially long and unpredictable pauses for a mutator thread. In this work we propose the first concurrent, incremental, and lock-free stack scanning mechanism for garbage collectors, that allows high responsiveness and support for programs that employ fine-grain synchronization to avoid locks. Our solution can be employed by all concurrent collectors that we are aware of, it is lock-free, it imposes a negligible overhead on the program execution, and it supports intra-stack references as found in languages like C#.