JVM GC算法

基础概念

 

GC Roots：

 The objects that a program can access directly are those objects which are referenced by local variables on the processor stack as well as by any static variables that refer to objects. In the context of garbage collection, these variables are called the roots

在Java语言中，包括但不限于以下几种：

1.虚拟机栈中引用的对象

2.方法区中类静态属性引用的对象

3.方法区中常量引用的对象

4.本地方法栈中JNI引用的对象

5.Thread对象

 

哪些对象该被GC？

如果一个对象到GC Roots没有任何引用链，该对象就是不可达对象，即可以被GC。

 

句柄（Handles）：

The Java virtual machine specification does not prescribe how reference variables are implemented. A common approach is for a reference variable to be implemented as an index into an array of object handles . Every object instance has its own handle. The handle for an object typically contains a reference to a Class instance that describes the type of the object and a pointer to the region in the heap where the object data resides.

也就是说我们代码中的引用可能是直接引用对象，也可能是引用的是对象的句柄，对象的句柄再引用对象。用句柄的好处是当对象的地址改变时，只需改变句柄指向新的地址即可，即只需改一个地方，但是如果不用句柄的话就需要更新每一个引用。

 

 

一、标记清除算法（Mark-and-Sweep）

 When using mark-and-sweep, unreferenced objects are not reclaimed immediately. Instead, garbage is allowed to accumulate until all available memory has been exhausted. When that happens, the execution of the program is suspended temporarily while the mark-and-sweep algorithm collects all the garbage. Once all unreferenced objects have been reclaimed, the normal execution of the program can resume.

 

标记清除算法是最基础的收集算法，后面的算法都是基于该算法扩展的，分为两个阶段：

标记阶段（Mark phase）：

从GC Roots出发，沿着引用链，遇到对象就标记该对象，直到所有可达对象都被标记。

清除阶段（Sweep phase）：

扫描整个heap，回收那些在标记阶段未被标记的对象的内存。

 

标记（mark）伪码描述：

for each root variable r
    mark (r);
sweep ();

 

void mark (Object p)
    if (!p.marked)
        p.marked = true;
        for each Object q referenced by p
            mark (q);

 清除（sweep）伪码描述：

void sweep ()
    for each Object p in the heap
        if (p.marked)
            p.marked = false
        else
            heap.release (p);

 

图示描述（只有一个root，a为标记前，b为标记后清除前，c为清除后）：

 

 

标记清除算法缺点：1.GC时用户线程必须暂停；2.标记和清除效率都不高；3.标记清除后会产生大量的内存碎片

 

 

二、停止复制算法（Stop-and-Copy）

When using the stop-and-copy garbage collection algorithm, the heap is divided into two separate regions. At any point in time, all dynamically allocated object instances reside in only one of the two regions--the active region. The other, inactive region is unoccupied.

 

停止复制算法将可用内存分为等量的两块，每次只使用其中的一块，当这一块无法满足新的内存分配时，即需要GC时，就扫描该块，将还存活的对象复制到另一块上面，然后再把已使用过的内存空间一次清理掉。

 

据研究，新生代的对象大多是短命的对象，所以不需要按照1：1的比例来划分内存空间，而是将内存划分为一块较大的Eden空间和两块较小的Survivor空间，每次使用Eden和其中一块Survivor。当回收时，将Eden和Survivor中还存活的对象一次复制到另外一块Survivor上，最后再清理Eden和原Survivor。Hotspot默认的比例Eden ：Survivor = 8 ：1.可以通过 -XX:SurvivorRatio=<N>来指定。值得注意的是，若复制时Survivor不够空间存放存活的Object了，则剩余的Object将进入Tenured Generation，即老年代。

 

Copy算法伪码描述（activeHeap：当前存放对象的那一块，inactiveHeap：当前未存放对象的那一块，forward引用所属对象在另一块中的复制对象，forward为null说明该对象还未被复制到另一块）：

for each root variable r
    r = copy (r, inactiveHeap);
swap (activeHeap, inactiveHeap);

 

void Object copy (Object p, Heap destination)
    if (p == null)
        return null;
    if (p.forward == null)
        q = destination.newInstance (p.class);
        p.forward = q;
        for each field f in p
            if (f is a primitive type)
                q.f = p.f;
            else
                q.f = copy (p.f, destination);
        q.forward = null;
    return p.forward;

 

图示描述：

 

 

 

停止复制算法缺点：1.每次GC都要复制所有存活的对象，如果对象的存活率很高，那代价未免太大了；2.内存浪费，即使是按照Hotspot的Eden-Survivor来划分，仍有不少内存是浪费的。

 

 

三、标记整理（压缩）算法（Mark-and-Compact）

 

标记整理算法和标记清理算法类似，也分为两个阶段：

标记阶段（Mark）：从GC Roots出发，沿着引用链，遇到对象就标记该对象，直到所有可达对象都被标记。

整理（压缩）阶段（Compact）：把所有的存活对象往一端移，然后清理掉端边界外的内存。

 

图示句柄的用法：

 

 

可以看到所有对象都是和句柄关联而不是直接和引用（变量）关联。

 

标记过程伪码描述：

void mark (Object p)
    if (!handle[p].marked)
        handle[p].marked = true;
        for each Object q referenced by p
            mark (q);

 整理（压缩）算法伪码描述：

void compact ()
    long offset = 0;
    for each Object p in the heap
        if (handle[p].marked)
            handle[p].object = heap.move (p, offset);
            handle[p].marked = false;
            offset += sizeof (p);

 

 

 

 注意：无论是哪种算法哪种收集器，在枚举根节点时都是要停顿（停顿指得是暂停所有用户线程），只是根据算法的不同以及收集器的不同该停顿时间的长短不同而已。