Parallel, Real-Time Garbage Collector

摘要

In an earlier paper 2, we presented an algorithm for a parallel, real-time garbage collector for shared memory multi- processors with provable bounds on time and space usage. Since the algorithm was designed to keep the analysis simple, it had some features that were impractical. This paper presents the modifications necessary for a practical implementation: reducing excessive interleaving, handling stacks and global variables, reducing double allocation, and special treatment of large and small objects. An implementation based on the modified algorithm is evaluated on a set of 15 SML benchmarks on an UltraSparc- II multiprocessor. To our knowledge, this is the first implementation of a parallel, concurrent, real-time garbage collector. On 8 processors, our collector has a speedup ranging from 5.5 to 7.8 and maximum pause times from 3 ms to 5 ms. In contrast, a non-incremental collector (whether generational or not) has maximum pause times from 10 ms to 650 ms. Compared to a non-parallel, stop-copy collector, parallelism has a 39% overhead, while achieving real-time behavior has an additional 12% overhead. Since the collector takes about 15% of total execution time, these features respectively have an overall time costs of 6% and 2%.