Concurrent reachability analysis (three color marking method)

The current mainstream programming language garbage collector basically depends on the reachability analysis algorithm to determine the object Is it alive , In theory, reachability analysis algorithm requires that the whole process is based on a snapshot that can guarantee consistency , This means that the running of the user thread must be frozen all the time .

To reduce the impact of freezing user threads , Increase of efficiency , Adopt the method of concurrent marking

The role of concurrency markers

according to Reachability analysis algorithm Core concept of , Using a series of root objects （GC Roots ） As starting point , Search a reference chain according to the reference relationship between objects , Determine the survival of an object by traversing the reference chain .

In the process , The time of root object enumeration is very short and relatively fixed , However , Traverse all reference chains （ Object graph ） The time required is proportional to the number of objects . therefore , The more objects , The more complex the reference relationship between objects , It takes more time to traverse all reference chains to Mark All objects .

The function of concurrency tag is to enable garbage collection thread and user thread to work at the same time , Concurrent execution .

The three color marking method is used to explain

Tricolor notation

• white ： Indicates that the object has not been accessed by the garbage collector . Obviously at the beginning of accessibility analysis , All the objects are Off-white , If at the end of the analysis , Still a white object , That is to say, it's impossible

• black ： Indicates that the object has been accessed by the garbage collector , And all references to this object have been scanned . Black object generation The table has been scanned , It's safe to live , If there are other object references pointing to black objects , No need to scan again . Black is right It seems impossible to directly （ Without going through the gray object ） Point to a white object .

• gray ： Indicates that the object has been accessed by the garbage collector , But at least one reference on this object has not been scanned , That is, you can continue scanning

If and only if the following two conditions are met at the same time , Will produce “ The object disappears ” The question of topic , That is, objects that should have been black are mistakenly marked as white ：

• Insert one or more new references from black object to white object

• All direct or indirect references from the gray object to the white object are deleted

Solution

Incremental updating The first condition to destroy , When a black object inserts a new reference relationship to a white object , Just put this new Record the inserted reference , After the concurrent scan , Then take the black objects in these recorded reference relationships as the root , Re sweep Trace once . This can be reduced to , Black objects once a new reference to a white object is inserted , It goes back to the gray object 了 .

Original snapshot The second condition is to be destroyed , When a gray object is to delete a reference to a white object , Just delete this In addition to the references recorded , After the concurrent scan , Then take the gray objects in these recorded reference relationships as the root , Rescan once . It can also be reduced to , Whether the reference relationship is deleted or not , Will be based on the snapshot of the object graph at the moment when the scanning just started To search .