Sections:

All contributions in this site reflect the authors' opinions and they are not necessarily endorsed by, or reflect the beliefs of, anarchyinthetubes, as neither do most of the opinions in other sites.

/sys/doc/ Documentation archive

Very Concurrent Mark-&-Sweep Garbage Collection without Fine-Grain Synchronization

By Lorenz Huelsbergen and Phil Winterbottom

"We describe a new incremental algorithm for the concurrent reclamation of a program's allocated, yet unreachable, data. Our algorithm is a variant of mark-&-sweep collection that|unlike prior designs|runs mutator, marker, and sweeper threads concurrently without explicit ne-grain synchronization on shared-memory multiprocessors. A global, but infrequent, synchronization coordinates the per-object coloring marks used by the three threads; ne-grain synchronization is achieved without locking via the basic memory consistency guarantees commonly provided by multiprocessor hardware. We have implemented two versions of this algorithm (called VCGC): in the Inferno operating system and in the SML/NJ ML compiler. Measurements, compared to a sequential generational collector, indicate that VCGC can substantially reduce worst-case pause latencies as well as reduce overall memory usage. We remark that the degrees of freedom on the rates of marking and sweeping enable exploration of a range of resource tradeo s, but makes \optimal" tuning for even a small set of applications di cult."

original page
cat.4l77.com