Browse Prior Art Database

Metering concurrent garbage collection work across allocation and background collector threads Disclosure Number: IPCOM000020622D
Original Publication Date: 2003-Dec-04
Included in the Prior Art Database: 2003-Dec-04
Document File: 3 page(s) / 61K

Publishing Venue



There is a need in an algorithm to decide: When to start the concurrent collection (the "kickoff"). How much tracing work to assign to mutators, taking into account tracing done by the background threads.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 34% of the total text.

Page 1 of 3

Metering concurrent garbage collection work across allocation and background collector threads

Traditionaly, Garbage Collection is invoked when all memory is used up. Then, GC stops all user threads ("mutators"), and traces all reachable objects ("live memory"). Objects which were not reached during the tracing, are declared dead and their memory is reclaimed. As the tracing is done with mutators stopped, such algorithms are called stop-the-world GC. Main disadvantage of stop-the-world GC is that it introduces disruptive pauses, whose length is proportional to the amount of live memory.

    The goal of "mostly concurrent" gc is to cut down the pause time dividing the tracing work to two phases. During the first phase (the concurrent phase), objects are traced concurrently with the mutators either on behalf of mutators or by specialized background threads. A write barrier is used to keep track of objects which were modified after concurrent phase started. These objects have to be re-traced later, during either concurrent or stop-the-world phase. During the second phase (the stop-the-world phase), mutator threads are stopped, and objects which were not traced during the concurrent phase are traced.

    The mostly concurrent collector releases all memory which was unreachable at the beginning of the concurrent phase. Objects which became unreachable after the initiation of the concurrent phase and before the stop-the-world phase may or may not be released at this cycle of GC (but they will be necesserily released by the next cycle). Memory occupied by such objects is called "floating garbage", and it is important to keep its amount to the minimum.

    The concurrent tracing must be started in time and done in proper pace to achieve the goal of short pause time, without increasing the amount of floating garbage. If concurrent tracing is started too early, it results in accumulated floating garbage and reduces the overall performance. If concurrent tracing is started too late or done too slow, not enough tracing is done before memory is exhausted, and short pause time is not achieved.

    There are two approaches to concurrent tracing. First approach is to link tracing work to allocation and do it on behalf of mutators. The advantage of this approach is that the amount of tracing work is easier to control. Its disadvantage is that processor's idle time cannot be utilized. Second approach is to do concurrent tracing by specialized background threads. While it allows utilizing processor idle time, the amount of tracing done by background thread depends on external factors, and cannot be trusted upon. For best results, both approaches should be combined, and the work done on behalf of mutators should take into account work done by the background threads


We introduce a formula to compute the needed amount of concurrent tracing to ensure short pause times for mutator threads doing concurrent collection work. The formula ties the amount of tracing...