Welcome back. 1
In the previous video we've been discussing Incremental and Concurrent collectors 2
when a Collector can be interrupted by the Mutator before the Collector cycle is fully completed. 3
And 4
we also mentioned there are some synchronization challenges related to these implementations. 5
In particular, recall the situation when during the initial portion of work some object was not marked 6
as reachable by the Collector. 7
Then the Collector was interrupted before the completion, and Mutator took place, at which point this 8
object actually received an alive reference. 9
Then when the Collector again is activated to complete its work, it should somehow already understand 10
that this object is now actually alive. 11
So in today's lecture we're going to talk about the actual mechanism used by the Collector to determine 12
that some object became alive during Mutator's activation, and to avoid incorrect reclamation of this 13
object. 14
The technique is known as Tri-color abstraction. So the Collector handles objects by small portions during 15
the time slice it has the opportunity to do its work. For example, in total we have 5 objects on the 16
heap, and during the first time slice Collector marked only first two objects 17
then on the next time slice -- two more objects, etc. And to distinguish which objects Collector has already 18
handled on the previous time slice, from those which it still needs to handle on the current slice 19
The Collector uses this Tri-coloring of the objects. 20
Let's see what it is. 21
Let's consider the following graph. 22
The Tri-color abstraction works as follows. The Black objects are those which Collector has already handled 23
on the previous time slice. 24
That is, they were identified as reachable on the previous step. 25
Besides the object itself, Collector also reached all direct children of those Black objects. 26
In other words, a Black object is the one which was traced on the previous step. 27
What this means, when the Collector continues from the place it was interrupted by the Mutator 28
It doesn't reconsider the Black objects again. 29
So right before the Collector is interrupted by the Mutator, the Collector knows for sure that the object A 30
is alive, and the object B is alive, since a direct children of a Black object are visited as well. 31
It didn't follow the nested children though in this case, since was interrupted by the Mutator 32
that is at this point 33
Collector doesn't know yet, whether the objects C, D, and E are alive. 34
Okay. 35
This brings us to the next group of objects, known as the Gray objects. The Gray objects are those which 36
were identified as alive, but which children haven't been scanned yet. 37
The Gray objects usually identified as alive on the previous step. And the Gray objects are exactly 38
those from which a Collector starts its analysis in the current round of scanning. 39
Right. 40
As we said, Collector always skip already scanned, that is Black, objects, and 41
always starts the tracing from the current Gray objects. During the trace of the Gray objects they are 42
marked as Black, and their children are marked as Gray. 43
So on the next cycle the Collector will continue the analysis from the objects C and D, not touching 44
anymore of the objects A and B. 45
But let's get back to the original graph. And the White objects are those, which haven't been yet visited. 46
That is, Collector doesn't know anything about those objects. And these objects are the potential garbage. 47
For example, let's say, we have one more White object F, not connected to anything, and which is clearly 48
a garbage 49
So the Collector already handled the object A, and starts its analysis from the Gray object B. After 50
tracing its children, it colors the object B as Black, and the C and D became Gray. On the next time 51
slice it starts from the Gray objects C and D 52
and colors them as Black 53
moving further to the Gray object E. And on the final cycle it colors E as Black, and -- that's it. 54
There is nothing more to handle, and on the Sweep phase the Collector will reclaim the White object F. 55
That is, to reiterate, the White objects are always considered as a potential garbage for reclamation. 56
Okay let's get back again to the original graph. 57
Now let's consider the following situation. 58
So let's say, the Collector was interrupted at this point, when object A was colored Black. 59
And then here's what's happened. 60
Mutator created the connection from A to D object. 61
And 62
in addition, it also changed the connection from B to D, to point from B to E now. 63
Have you noticed already the problem? So the problem here is, from which objects the Collector starts 64
the next portion of work. 65
As we said, the Black objects are considered fully scanned. Which means, Collector will not reconsider 66
them on the next cycle. But this creates a big problem for the object D. 67
This object is White, and at the end the Collector reclaims all White objects. The object D will stay 68
forever as White 69
in this case, since it doesn't have an opportunity to become Gray. And simply because Collector doesn't 70
reconsider Black objects, treating them as already handled. Which means, the object D will not be visited 71
Eventually 72
as we said, the object D will incorrectly be reclaimed, even though being absolutely reachable from the 73
Mutator's perspective. That is, will be breaking heap invariants by removing an alive object. 74
So what should we do here? 75
Okay, here's the first rule of the Incremental and Concurrent collectors. 76
The Black to White pointers are illegal. 77
This is one of the Tri-color invariants, and Black to White pointer is illegal as long as there is 78
no any pointers from a Gray object to this White object. 79
So an Incremental and Concurrent collector should not allow such pointers, and in the next lecture will 80
see the exact technique used to prevent this condition. Running forward 81
we should say, the technique is called Read- and Write-barriers. 82
However, there is also concept of a "legal" Black-White pointer. A Black to White pointer is actually allowed 83
as long as there is a path from any Gray object to this White object. Since the Gray objects will be 84
visited 85
and 86
their children will be traced as well. 87
In this case we have the connection from Gray object B to the white object C. So the A->C pointer is allowed. 88
And 89
again let's define the illegal condition of the Tri-color invariant. So a pointer is illegal if 90
it is a direct pointer from a Black object to a White object. And there is no path from any Gray 91
object to this White object. 92
Okay, so this is our problem statement which we'll be working with in the next lecture when we'll be 93
talking about Read- and Write-barriers to synchronize the coloring of the objects between Mutator and 94
Collector 95
Thanks and see you in the class.