Garbage collection algorithms from the old days

Heap = New generation + old age, but note that old age does not include permanent generation (method area), that is, there are only new generation and old age in the heap, and permanent generation refers to the method area.

Having introduced the garbage collection mechanism of the new generation, let’s take a look at the algorithms used in the garbage collection mechanism of the old generation.

New generation GC: MinorGC has been introduced before, but the replication algorithm diagram is quite clear

Old GC: FullGC is the GC of the old era. In the new generation, if the existing object or the newly created object needs to be moved to the old era for some reason, but the old era does not have such a large memory space to hold the object, A FullGC will be thrown, and if there is no way to allocate memory for these objects after the FullGC, it is time to throw an exception of the type OutOfMemoryError.

FullGC uses a different algorithm than MinorGC, which uses a tag clearing algorithm to parse a wave by a wave graph. The diagram in the book on the JVM looks something like this,

Look at the name is marked first, and then delete. This is also the most basic algorithm. It’s a two-step algorithm

• Mark process: Find all accessible objects and Mark them.

• Swep process: Traverses the heap memory to make a collection of unmarked objects.

See some documents, said mark before, and then dropped the unmarked objects to recycling, actually means about the same, but in the deep understanding of the JVM book, said the first mark all need recycled object, after the completion of a tag unified recycle all the marked objects, in fact, I understand and feel a little different in the book, but the difference is little. Let me explain my understanding.

With that in mind, one more concept is GC Root, which we can think of as a Root node like this

A, B, C and D in the figure above are living objects, and if there is a reference to, say, B to A, then A belongs to a living object. When we run out of available memory space in the old memory area, it’s time to stop the world and start preparing for garbage collection.

• Tag: Iterate through all GC Roots, and then mark all objects reachable by GC Roots as living objects. • Purge: The purge process traverses all objects in the heap and removes all unmarked objects. That is, if memory is low, the GC thread will be fired and the program will be paused, then the remaining objects will be marked, and finally all unmarked objects in the heap will be cleared, and the program will resume running.

The flowchart looks like this at the beginning of the old state of the object

This is an unmarked state, and then running out of memory, the GC thread stops and starts marking

Abcdeh that starts traversing the tag at the root node is a viable object, followed by the start tag.

The next step is to clear the data, which is even easier

Once it’s clear, there’s also the mark to remove, which can be continued the next time the mark is cleared

Now that the tag clearing is done, there are two more things to say,

One is why the program should stop the world while the algorithm is marked.

Second, what are the advantages and disadvantages of the tag clearing algorithm? (Stop the World)

Program to stop actually understandable, because if not stop the program, after we finish this by tag object b, J we new a new object, can from a to b J, that is to say, this time J should be marked, but the actual situation is certainly not, this object in after a tag, b will end right away, When we create a new object, we can imagine that it must be unmarked, so in the second stage of clearing, the unlucky J will be cleared, which is definitely not in line with our actual situation.

You see, this new object is cleared and suddenly becomes null, which is not in line with our requirements. So he would stop the program, and then it wouldn’t happen again, and then he would start the marking phase.

The advantages and disadvantages

First of all, we can look at the disadvantages. His disadvantages are very obvious.

• Because it recurses through Root, it stops the World for a long time, which is not very pleasant to be kept waiting. • The second is that the memory space cleared by this method is discontinuous, as you can see from this graph

The top and bottom of the dead are divided into two parts, which are not contiguous. This puts an additional burden on the JVM to maintain a free list of memory. If we try to create an array at this time, do you think it will be much more difficult for him to find the contiguous memory space?

He has some good points,

• We can think of two classes that refer to each other, newB in A, newA in B, a.b= B,b.a = A, right, and the tag clearing algorithm can recycle A, B, and B, because it iterates from the root element, that is, from ab. Then the single A and single B are unmarked, so this avoids the problem of circular references. It also feels the same, as references are made when memory is out. There’s nothing to be said for that.

Tag – Collation algorithm

Since the mark-clear algorithm leads to uneven space in the memory allocation, there is another algorithm, which directly marks the surviving objects and then pushes them to the edge of the memory space, and then directly clears the rest. This method is clear in the diagram, the rest is the same as the tag removal algorithm, as if there is no explanation, directly above

In the book, you can see that the survival of the memory space is the upper part of the memory space, you can also interpret it as up, down, left and right are OK.

The above is the heap memory of the old two garbage collection algorithm, if there is not appropriate, hope the big guys can correct, together discuss.

Java Geek technology public account, is set up by a group of technical people who love Java development, focus on sharing original, high quality Java articles. If you think our article is good, please help to appreciate, read, forward support, encourage us to share better articles.

Pay attention to the public account, you can reply “nuggets” in the background of the public account, to obtain the author Java knowledge system/interview must see information.