CODEWITHSUNDEEP
javaconcurrencygarbage-collection
Joffrey
Joffrey

Reputation: 301

Why remark phase is needed on concurrent GC

Concurrent GC needs remark phase. The role of remark phase is to mark modified objects during concurrent mark phase. But I think if we only mark the newly created objects during concurrent mark phase, there's no need to execute remark phase.

remark phase is needed because of the modified objects. The modification can be two type. One is new object creation and the other is modified pointer to another object. New object problem can be solved easily if we mark the newly created objects. And modified pointer to another object is not a problem in fact. Because

Dead object can not revive

Dead object means that no one could point that object. How can they revive? So modified pointer should point to already marked objects. It means there's no need to perform remark.

Someone could say that, "Marking new object on its creation is too expensive. So they cannot be marked during concurrent mark phase and that's the reason why remark phase is needed". It seems like reasonable. But this can arise another question. How could remark without traverse every objects from the root? If remark phase should traverse every objects from the root, the works done by concurrent mark phase is useless. Or if remark phase traverse only modified objects, the information that which object is modified should be saved somewhere. I think it could be much expensive than just marking .

Am I wrong? It should be wrong. But I have no idea which point is wrong.

Upvotes: 8

Views: 1679

Answers (2)

supercat
supercat

Reputation: 81123

The GC must always look at every stored reference which has been modified since the start of the current cycle, since it's possible that a reference held someplace the GC hasn't looked yet will be stored in a place it has looked and removed from its original location. A concurrent GC could revisit the modified references without stopping the world, but while it was doing so other threads would probably be continuing to modify more references.

If 10% of objects get modified while a GC is doing a full scan, it might be worthwhile for it to visit that 10% without stopping the world, but while it's visiting that 10% other threads might disturb 3%. Visiting that 3% concurrently might be worthwhile, but other threads might disturb 2%. Further passes might reduce the amount of work that will need to be done in stop-the-world mode, but the GC would be unlikely to complete fully while other threads were still in the process of disturbing references. Unless all threads spontaneously stop doing anything with references, the GC would never be able to 100% finish without stopping the world.

Note that it may be possible for a GC design to commit to never stopping the world for more than a certain amount of time, at the expense of possibly starving new allocation requests. There's no way a GC can know with certainty how long it will take to finish a cycle, since until the cycle is complete it would have no way of knowing whether there is an as-yet undiscovered reference to the root of a large collection of as-yet undiscovered objects. On the other hand, the GC could stop the world if it reaches a point where--in the absence of such discoveries--it would expect to complete within 1ms, but then let the world restart if new discoveries would cause it to take longer than 2ms. Letting the world restart would make it necessary to stop the world again before the GC could free up any memory, and it might be very difficult to guarantee that no combination of events could result in an endless cycle of aborted "final cleanup" attempts, but if the allowable "stop the world time" is reasonable relative to the amount of "churning" the code does with references, failed final cleanups should be rare and repeated ones exceptionally so.

Upvotes: 1

maaartinus
maaartinus

Reputation: 46392

And modified pointer to another object is not a problem in fact. Because

Dead object can not revive

They really can't but do you know which objects are dead? No! Why?

You don't know it after the initial mark phase as you look only at the thread stacks and don't follow references.

You don't know if after the concurrent mark phase as the following may happen:

  • A thread reads the field a.x and stores its value in its register (or on its stack or elsewhere).
  • Then this thread set a.x = null (or something else).
  • The GC comes and sees null there.
  • Then the thread restores a.x to its previous value.

Now, the GC has missed the object a.x points to. While the above scenario is not very common, it may happen and there are more realistic (and more complicated) scenarios.

So it's necessary to look at the modified memory again, which is the remark phase. Fortunately, not the whole memory must be scanned again, as a card table gets used.

I'm afraid this (otherwise nice) explanation is a bit misleading in this point:

The remark phase is a stop-the-world. CMS cannot correctly determine which objects are alive (mark them live), if the application is running concurrently and keeps changing what is live.

The threads do change what is live, but they also change what you can see as being live. And that's the problem.

This article states it rather clearly:

Part of the work in the remark phase involves rescanning objects that have been changed by an application thread (i.e., looking at the object A to see if A has been changed by the application thread so that A now references another object B and B was not previously marked as live).

I'd say: When you search one room after another, you may miss your glasses when children move them around.

A note concerning the scenario

I'm pretty sure, the above scenario is possible, it's just not exactly what a program usually does. For a pretty realistic example, consider

void swap(Object[] a, int i, int j) {
    Object tmp = a[i];
    a[i] = a[j];
    // Now the original reference a[i] is in a register only.
    a[j] = tmp;
}

Upvotes: 3

Related Questions