CODEWITHSUNDEEP
algorithmparallel-processinggarbage-collectionconcurrent-mark-sweep
user16009754
user16009754

Reputation:

Why does a mark & sweep collector have to stop the world and not run in parallel?

I am reading "The Garbage Collection Handbook: 2nd Edition". In the "Mark-Sweep garbage collection" page, it is mentioned that all mutator threads stop while the collector thread runs.

What is the reason? In the marking phase, the collector only touches bytes (mark flags) that it owns and the mutator shouldn't even use. In the sweep phase, it only deallocates objects which in the first place can't even be touched by the mutator because they are unreachable (not marked).

I must be missing something, but if it can run completely in parallel (like mentioned above), why would all the mutator threads be stopped?

Upvotes: 1

Views: 506

Answers (1)

rici
rici

Reputation: 241821

In the marking phase, the collector only touches bytes (mark flags) that it owns and the mutator shouldn't even use.

It only mutates bytes that it owns. But it examines bytes owned by the mutator. Which might mutate bytes while the collector examines them.

Specifically, if the marker and the mutator run at the same time, nothing stops the mutator from mutating a cell which has already been marked. The new contents of that cell will then remain unmarked, with the consequence that the value referenced will be collected even though it is still alive.

You could mitigate this problem in the case that the new contents of the cell reference a new object, by simply ensuring that objects are born marked. But in languages which allow mutation, there is no guarantee that it is a new object.

Concretely, consider the following sequence:

Mutator                           Marker
--------------------              -------------
                                  Mark temp
temp := v[i]
v[i] := v[j]
                                  Mark all of v
v[j] := temp

Whatever was originally in v[i] was not marked (unless there was some other reference to it), and therefore will be erroneously collected.

I only have the first edition of Richard Jones' useful text; in that edition, there is a whole section on how to implement concurrent mark/sweep garbage collection. One possibility is to implement a write barrier which intercepts mutations like the ones in the above example; the write barrier forces the new value to be marked if it has not been marked already. Of course, there is a synchronisation penalty, since the write barrier runs in a mutator thread, not the marker thread.

Upvotes: 2

Related Questions