What's the 'mostly-concurrent garbage collector'?

Question

I know concepts of stop-the-world, incremental, parallel, concurrent, (soft/hard) realtime garbage collectors. But I can't understanding mostly-concurrent GC. Is it different with concurrent GC? What's the difference? Why it is called mostly?

Rhombus

Answer 1

I know concepts of stop-the-world, incremental, parallel, concurrent, (soft/hard) realtime garbage collectors. But I can't understanding mostly-concurrent GC. Is it different with concurrent GC? What's the difference? Why it is called mostly?

Like so many other subjects, garbage collection is shrouded in a fog of terminological ambiguity. Boehm is particularly infamous for using conventional terms in unconventional ways but we should forgive him because he was pioneering the field at a time when the conventional meanings had not yet been ossified! :-)

As I understand it, stop-the-world GC refers to an algorithm that suspends all mutator threads for the entire duration of a GC cycle, e.g. when marking the entire heap. For example, the .NET Server GC does this and incurs huge 300ms pause times as a consequence. Incremental GCs perform a little bit of major GC work at each minor GC cycle, e.g. "major slices" in OCaml's GC. Parallel means the GC uses multiple threads to speedup the process of collecting garbage. Concurrent GC means the GC runs at the same time as the mutators, e.g. .NET workstation GC. Real-time is difficult to define, originally meant bounded maximum pause times but now also means minimum mutator utilization (MMU), to avoid the pathological problem of a GC that never pauses a mutator for long by never allowing it to run! According to Richard Jones' new book, an on-the-fly GC never suspends more than one mutator at a time (i.e. there is no stop-the-world phase) although I suspect he meant that mutators are suspended independently of each other. Finally, a mostly-concurrent GC is one that does suspend all mutator threads simultaneously but only for a short period of time and not for an arbitrarily-long GC cycle. Therefore, the mutators are allowed to run freely most of the time while the GC is running and, hence, it is called "mostly concurrent" GC.

The classification of "mostly concurrent" is important because most (all?) major GCs fall into this category because it provides a good trade-off between pause times and throughput. For example, the .NET workstation GC suspends all mutator threads when taking a snapshot of the global roots but resumes them while it marks and sweeps.

Piwowar

Answer 2

You can find an accessible description in the paper "Mostly Parallel Garbage Collection" by Bohem, Demers, and Shenker (Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, SIGPLAN Notices 26, 6 (June 1991), pp. 157-164).

They write:

Assume we are able to maintain a set of virtual dirty bits, which are automatically set whenever the corresponding pages of virtual memory are written to. (An acceptable implementation of this feature can be obtained by write-protecting pages and catching the resulting write faults, with no modifications to the underlying OS kernel; an implementation in the OS kernel would of course be more efficient.) For any tracing collector defined for stop- the-world operation, consider the following collection algorithm. At the beginning of the collection, clear all virtual dirty bits. Perform the traditional tracing operation in parallel with the mutator. The virtual dirty bits will be updated to reflect mutator writes. After the tracing is complete, stop the world and trace from all marked objects that lie on dirty pages. (Registers are considered dirty.) At this point, all reachable objects are marked, and garbage can safely be reclaimed.

...

In this algorithm, the parallel tracing phase provides an approximation to the true reachable set. The only objects unmarked by this parallel tracing process which are indeed reachable must be reachable from marked objects which have been written since being traced. The stop-the-world tracing phase traces from all such objects, so that in the end no truly reachable objects remain unmarked.

When they refer to tracing garbage collectors, they are referring to collectors that start from designated "root nodes" (usually the program's registers) and follow pointers to every reachable object. Everything unreachable is garbage.

In short, a mostly-parallel collector does the bulk of the work in parallel, then halts the program's execution to correct any changes that the program made while the collector was running. Hence, it is "mostly parallel."

Xhosa