The heap contains almost all object instances in the Java world, and the first thing the garbage collector needs to do before collecting the heap is to determine which of these objects are “alive” and which are “dead” (objects that can no longer be used in any other way)

1. Reference counting algorithm

Many textbooks determine whether an object is alive by adding a reference counter to the object and incrementing the counter by one each time a reference is made to it. When a reference is invalid, the counter decays by 1; An object whose counter is 0 at all times is no longer usable.

The implementation of Reference Counting algorithm is simple and the judgment efficiency is high. In most cases, it is a good algorithm. But reference counting algorithms are not used in The Java language to manage memory, and one of the main reasons is that it is difficult to solve the problem of circular references between objects.

Such as: In testGC(), both objects objA and objB have fields instance, which are assigned to obja.instance =objB and objb.instance =objA. There are no references to either object, and in fact both objects are no longer accessible. But because they refer to each other, the exception is that their reference counts are not zero, so the reference counting algorithm cannot tell the GC collector to reclaim them.

public class ReferenceCountingGC {
    public Object instance = null;
    private static final int _1MB = 1024 *1024;
    /**
     * 只是为了占点内存
     */
    private byte[] bigSize = new byte[2 * _1MB];

<span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span>(<span class="hljs-params">String[] args</span>) </span>{
    ReferenceCountingGC objA = <span class="hljs-keyword">new</span> ReferenceCountingGC();
    ReferenceCountingGC objB = <span class="hljs-keyword">new</span> ReferenceCountingGC();
    objA.instance = objB;
    objB.instance = objA;

    objA = <span class="hljs-literal">null</span>;
    objB = <span class="hljs-literal">null</span>;

    <span class="hljs-comment">//假设在这里发生GC，那么objA与objB是否会被回收</span>
    System.gc();

}
Copy the code

The running results are as follows:

[GC [DefNew: 234K->64K(960K), 0.0009447 secs][Tenured: [Perm: 365K->365K(12288K)], 0.0058659 secs] [Times: 3282K -> 3289k [Perm: 365K->365K] Sys =0.00, real=0.00 secs] [Full GC (System) [Tenured: 4237K->141K(6148K), 0.0052656secs] 4237K->141K(7108K), [Perm: 365K->365K(12288K)], 0.005297secs] [Times: User =0.01 sys=0.00, real=0.01 secs] Heap def new generation total 960K, used 18K [0x23B10000, 0x23c10000, 0x23ff0000) eden space 896K, 2% used [0x23b10000, 0x23b14818, 0x23bf0000) from space 64K, 0% used [0x23c00000, 0x23c00000, 0x23c10000) to space 64K, 0% used [0x23bf0000, 0x23bf0000, 0x23c00000) tenured generation total 6148K, used 141K [0x23ff0000, 0x245f1000, 0x27b10000) the space 6148K, 2% used [0x23ff0000, 0x240136b8, 0x24013800, 0x245f1000) compacting perm gen total 12288K, used 365K [0x27b10000, 0x28710000, 0x2bb10000) the space 12288K, 2% used [0x27b10000, 0x27b6b578, 0x27b6b600, 0x28710000) ro space 8192K, 63% used [0x2bb10000, 0x2c023b48, 0x2c023c00, 0x2c310000) rw space 12288K, 53% used [0x2c310000, 0x2c977f38, 0x2c978000, 0x2cf10000)Copy the code

You can see in the result that the GC log contains “4237K->141K”. The old age is changed from 4273K to 141K, which means that the virtuality does not recycle the two objects because they reference each other. This also proves that virtuality does not depend on reference counting algorithms to determine whether objects are alive or not. You can see that objects go into the old age, but as you know, when objects were created they were assigned to the new generation, and the default age to go into the old age is 15, but objA and objB are going into the old age. This is because the Java heap grows dynamically, the heap is small to begin with, and there is a rule that objects age directly when the sum of survivor-generation objects exceeds half the size of survivor-generation objects.

2. Root search algorithm

In the mainstream commercial programming languages (Java and C#), GC Roots Tracing is used to determine whether an object is alive or not. The basic idea of this algorithm is to search down from a series of objects named “GC Roots” as the starting point, and the search path is called the Reference Chain. When an object is not connected to GC Roots by any Reference Chain, it is proved that the object is unavailable. The diagram below:

Objects bject5, object6, and object7 are not reachable to GC Roots, so they will be judged to be recyclable. In the Java language, GC Roots objects include the following:

  • Object referenced in the virtual machine stack (local variable table in the frame)
  • The object referenced by the class static property in the method area
  • The object referenced by a constant in the method area
  • The object referenced by JNI in the local method stack

Read more Java articles: javawu.com