Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "what is the tricolor mark of GC garbage collection". The editor shows you the operation process through an actual case, the operation method is simple and fast, and it is practical. I hope this article "what is the tricolor mark of GC garbage collection" can help you solve the problem.

GC

GC full name Garbage Collection

At present, there are two kinds of mainstream garbage collection algorithms, which are tracked garbage collection algorithm (Tracing garbage collection) and reference counting method (Reference counting).

Tricolor labeling is a kind of tracking garbage collection algorithm.

The core idea of the tracking algorithm is to determine whether an object is reachable or not, because once the object is unreachable, it can be immediately reclaimed by GC.

How to judge whether an object is reachable

There are two steps:

The first step is to find all the global variables and the variables in the current function stack and mark them as reachable.

The second step, starting with the tagged data, further marks the variables they can access, over and over again, a process known as transitive closures.

Before go introduced tricolor labeling, the gc algorithm used by go was called Mark-And-Sweep (tag sweep).

This algorithm is implemented strictly according to the train of thought of tracking algorithm.

First set a flag bit to record whether the object is used, and at first all the flag bits are 0.

If it is found that the object is reachable, it will be set to 1, and a tree-like result will be presented step by step.

After the marking steps are completed, the objects that are not marked will be cleaned uniformly, and all the tag bits will be set to 0 again so that the next cleanup can be carried out.

The biggest problem with this algorithm is that during the execution of GC, the whole program needs to be completely paused, and the GC operation cannot be carried out asynchronously. Because the flag bits 0 and 1 of the sweep method have different meanings at different stages, the new object may accidentally delete the object no matter why the tag is marked. For systems with high real-time requirements, this mark cleaning method, which needs to be suspended for a long time, is unacceptable. So we need an algorithm to solve the problem of GC runtime program hanging for a long time, that is trichromatic notation.

Tricolor labeling method

Tricolor labeling is an improvement of traditional Mark-Sweep, which is a concurrent GC algorithm. On-the-fly

The principle is as follows

The memory occupied by each object in the whole process space can be regarded as a graph, and each memory object is marked white in the initial state.

First stop the world, the scanning task is immediately queued to the scheduler as multiple concurrent goroutine, and then processed by CPU. In the first round, all reachable memory objects are scanned first, marked as gray and placed in the queue.

In the second round, the start the world can be restored, and the objects referenced by the objects in the first step will be gray to join the queue. After all the objects referenced by an object are grayed out and added to the queue, the object can be set to black and removed from the queue. Over and over again, when the queue is empty at last, the remaining white memory space in the whole graph is the unreachable object, that is, the object that is not referenced.

The third round stop the world again, marking (gray) the memory applied by the new objects during the second round. Here, writebarrier (write barrier) is used to record the identity of the memory.

This algorithm can implement on-the-fly, that is, collecting the program while it is executing, without pausing the entire program.

The simplified steps are as follows:

1. First create three collections: White, gray, and black.

2. Put all objects in the white collection.

3. Then iterate through all objects from the root node (note that there is no recursive traversal here), putting the traversed objects from the white set to the gray set.

Because root set points to An and F, it traverses An and F from the root node, so it puts An and F into a gray set.

4. After traversing the grey set, the objects referenced by the grey object are put into the grey set from the white set, and then the grey object is put into the black set.

We can see that this A points to BPerry C No D, so that is to put BCD in gray, An in black, and F does not refer to any object, so put it directly in black.

5. Repeat 4 until there are no objects in gray

Because D points to A, D is also put in black, and B and C can be put into the black set, just like F, there is no object to point to.

6. Repeat the above operations to detect whether the object has changed through write-barrier.

Since the EGH does not have a direct or indirect relationship with RootSet, it will be cleared.

7. Collect all white objects (garbage)

So we can see the situation here, as long as the objects directly related to the root set root collection or indirectly related objects will not be clear. Only unrelated ones will be recycled.

This is the end of the content about "what is the tricolor tag of GC garbage collection". Thank you for reading. If you want to know more about the industry, you can follow the industry information channel. The editor will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.