Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

4 Answers 4

up vote 14 down vote accepted

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:

share|improve this answer

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...

share|improve this answer

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.

share|improve this answer
    
Nice ! Too bad I don't have access to ACM, this article looks really interesting. –  deadalnix Aug 23 '11 at 16:39

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.

share|improve this answer
    
That is not suffiscient as long as thoses reference can be updated at any time by any thread. –  deadalnix Aug 23 '11 at 13:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.