CODEWITHSUNDEEP
concurrencygarbage-collectionlanguage-implementation
josh
josh

Reputation: 1017

What are the possible ways to do garbage collection in concurrent systems?

I need to write a garbage collector for an interpreter that will support concurrency, but I can only find information about garbage collection without anything to do with concurrency.

Are there specific methods for garbage collection of objects in multithreaded systems? Where can I find information on their architecture and implementation?

Upvotes: 2

Views: 392

Answers (3)

J D
J D

Reputation: 48687

Are there specific methods for garbage collection of objects in multithreaded systems? Where can I find information on their architecture and implementation?

There are two main solutions:

  1. Prohibit mutation and exploit the referential transparency in the resulting unidirectional heap by deep copying values when they are passed from one thread to another. Then use non-concurrent collection. Erlang does this.

  2. Use a concurrent garbage collector. See the Garbage Collection Handbook chapter 15, Concurrent Garbage Collection, for detailed information. .NET and the JVM do this. You'll need a write barrier (Dijkstra, Steele or Yuasa) in order to record mutations of the heap topology while the collector is running.

Concurrent garbage collectors range from full concurrency (no pauses) to mostly concurrent (some short stop-the-world pauses, usually to get a self-consistent snapshot of the global roots). Full concurrency is costly in terms of throughput because keeping the GC apprised of the constantly-changing heap topology requires fine-grained synchronization. Coarse-grained synchronization is possible with collectors like the beautiful Very Concurrent Garbage Collector (VCGC). FWIW, I wrote an article about a VCGC implementation in F# for the F#.NET Journal.

Upvotes: 0

Daniel Ralston
Daniel Ralston

Reputation: 2280

Concurrent garbage collection is actually a lot trickier to get right. There has been research into concurrent garbage collection algorithms, however.

Mark & Sweep: http://doc.cat-v.org/inferno/concurrent_gc/

Mark & Sweep (PDF warning): http://www.win.tue.nl/~jfg/articles/CSR-04-31.pdf

Generational-Copying: https://labs.oracle.com/techrep/2000/abstract-88.html

Generational-Copying: http://chaoticjava.com/posts/parallel-and-concurrent-garbage-collectors/

The difficulty is synchronizing the threads, so the heap isn't left in an inconsistent (invalid) state.

Upvotes: 1

jdmichal
jdmichal

Reputation: 11152

Maybe I'm just not understanding this well... But what would concurrency have to do with how many references to an object are alive? It either has living references or it doesn't; multiple threads have no effect on that.

I could see maybe having to trace out each thread separately to see what references are alive or not. But that should be just applying the single-threaded trace multiple times.

Also, why not just program your interpreter on top of a VM that already does all this? Like JRuby (Java VM) or IronPython (.NET) have done.

Upvotes: 0

Related Questions