What are the algorithms behind low pause GC?

Question

Some languages, for exemple java, introduced a low pause GC.

Those GC can do most of the work without pausing the whole world. This is obviously a quite hard problem because it require to analyze the memory when thread are modifying it, resulting in data that can be used in the begining of the process and not anymore when it finishes, or data that appears to be garbages but because the reference was moved in memory and never appeared where the GC was looking.

So basically, what is the algorithm(s) behind that ?

Research papers or really technical article's link would be considered as valid answer, as this topic is really technical.

Answer 1

So basically, what is the algorithm(s) behind that?

It's basically a mark and sweep algorithm which "just" runs concurrently in a separate thread.

As for the research papers on that subject:

• Very Concurrent Mark and Sweep Garbage Collection without Fine-Grain Synchronization

• Concurrent mark-sweep garbabe collector (contains links to two papers, one listed below)

• Implementing an On-the-fly Garbage Collector for Java

• Portable, Unobtrusive Garbage Collection for Multiprocessor Systems (Doligez Leroy, Powerpoint Presentation)

• On-the-fly garbage collection: An Exercise in Cooperation (by Edsger Wybe Djikstra)

Answer 2

as far as I understand, Java G1 garbage collector uses so called heap regions to avoid pausing the whole world. The way I see it is that while one of the regions is locked by GC performing cleanup, memory allocation is done in another region.

Here is an explanation from Jeremy Manson:

The principle is simple: the collector splits the heap up into fixed-size regions and tracks the live data in those regions. It keeps a set of pointers — the "remembered set" — into and out of the region. When a GC is deemed necessary, it collects the regions with less live data first (hence, "garbage first"). Often, this can mean collecting an entire region in one step: if the number of pointers into a region is zero, then it doesn't need to do a mark or sweep of that region...

• here is a technical paper from Sun engineers explaining their design: Garbage-First Garbage Collection

Answer 3

IBM's real-time JVM uses a garbage collector called Metronome that splits the GC activity into discrete quanta and interleaves them with application processing. So basically instead of periodic (and non-deterministic) stop-the-world GC pauses, the application instead runs slightly slower while the GC is done in parallel.

There's another GC that does dynamic defragmentation and meets hard-realtime requirements, but the only reference I can find is here (ACM membership required).

An interesting concurrent real-time garbage collector is stopless. It uses the traditional mark-and-sweep approach, but is designed for use on multiprocessor systems and supports lock-free concurrent multithreading.

Answer 4

The reason that it works is because in Java, only the GC can free memory which might contain GC references. That means that as long as you can read objects in a separate thread safely, you would only need to pause the program to observe the references on the stack.

I would suggest for mutation that they implement some form of copy-on-write to inform the GC about the change.