与 C++ 程序设计语言相比，Java 程序设计语言拥有一个独特的语言特性——自动垃圾回收机制 (Garbage Collection)。在 Java 和 C++ 中，新创建一个对象都需要使用 new 运算符。然而，在 C++ 中，程序员需要人工管理内存，对于不再使用的对象使用 delete 运算符显式地回收内存；在 Java 中，程序员无需人工管理内存，JVM 会自动触发垃圾回收，将没有被引用的对象占据的内存空间释放。

基本垃圾回收机制

基本的 Java 垃圾回收机制如下：

首先，垃圾回收器会找出当前哪些对象是正在使用中的，并将其标记为存活对象；以及哪些对象是没有被引用的，并将其标记为未引用对象，这一步称为标记 。下图显示了一个标记前后的内存图的样式：

img

其次，垃圾回收器会将当前所有未引用对象删除，也就是上图中橙色的部分。

img

最后，为了提升性能，在删除完未引用对象后，通常还会采取压缩操作，将内存中的存活对象放置在一起，以便后续能够更加高效快捷地分配新的对象。

img

分代垃圾回收机制

在实际的程序中，如果完全采用上面的基本垃圾回收机制，会导致垃圾回收非常低效，这是因为每一次垃圾回收都需要标记所有的对象并进行删除和压缩；垃圾回收的耗时与分配的对象数量成正相关的联系。

实际上，对一个程序运行过程中所有对象的存活时间进行统计，可以得到下面的图：

img

横轴代表程序运行时间，纵轴代表分配的字节

从图中我们可以看出，大部分对象的存活时间都比较短(聚集在左侧)，存活的对象随着程序的运行逐渐减少，因此，利用对象存活时间的规律对内存中的对象进行分代，可以加快垃圾回收的效率。

JVM的分代将堆分为如下几个部分：

img

图中红色部分和橙色部分为新生代，用来存储刚分配的对象和分配不久的对象；蓝色部分为老年代，用来存储存活了一定时期的对象；绿色部分为永久代，主要用来存放类和元数据的信息。

在 JVM 分代的设计下，垃圾回收被重新设计为如下过程：

首先，任何新分配的对象都存放于 eden 内存中，此时两个 Survivor 都是空的。

image-20200513094116818

当新分配的对象达到一定数量时，会将 eden 的空间填满，此时会触发**次垃圾回收(小型垃圾回收)**，我们称之为 MinorGC。具体地，MinorGC 采用的是标记-复制算法，首先对 eden 和 FromSurvivorSpace 中的对象进行标记，然后将存活对象复制到 ToSurvivorSpace 中去，随之清空 eden 和 FromSurvivorSpace 中的对象，并将 FromSurvivorSpace 和 ToSurvivorSpace 区域调换，如下图所示：

img

在下一次的 MinorGC 时，会重复同样的操作，Survivor 区会再次发生交换：

img

注意到：从 eden 区迁移到 Survivor 区的对象此时开始有年龄 Age 的概念，这里的 Age 是用来表示对象的存活时间，每经过一次 MinorGC，对象的 Age 增加 1。

经过了一定次数的 MinorGC 后，有些对象的年龄会达到一定的阈值，图中示例为 8，此时这些年龄达到阈值的对象会被转移到老年区 tenured 中，表示为常使用的对象：

img

对于老年代中的对象而言，未引用的对象不会在 MinorGC 中被回收，而是在**主垃圾回收 (大型垃圾回收)**，我们称之为 MajorGC 中被回收。

MinorGC 的作用范围是新生代，MajorGC 的作用范围是老年代，MinorGC 发生的频率高，而 MajorGC 发生的频率则较低。老年代中的对象普遍比较稳定，通常会长期存在，所以变化不是特别频繁。MajorGC 采用的是标记-压缩算法，也就是上面提到的基本垃圾回收机制。

代码模拟

以下是一个简单的垃圾回收机制模拟：

  • MyObject
    • 模拟创建的对象
  • MyHeap
    • 普通小顶堆
  • JvmHeap
    • JVM 中的堆，eden、survivor、tenured 均使用堆来实现，继承自MyHeap。
  • MyJvm
    • 模拟的 JVM，负责管理堆、创建对象、删除对象引用和垃圾回收
  • Main
    • 模拟程序的输入输出，输入方式为先输入指令名称，换行后再输入参数。
    • 输入有以下几条指令：
      • CreateObject ：创建新的对象，换行后输入创建对象的个数
      • SetUnreferenced ：将对象设置为未引用，换行后输入删除引用的对象id，用空格分隔
      • RemoveUnreferenced：直接在堆中移除未引用的对象
      • MinorGC ：小型垃圾回收
      • MajorGC ：大型垃圾回收
      • SnapShot ：查看当前 JVM 中堆的快照

MyObject.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
public class MyObject implements Comparable<MyObject> {
    private static int totalId = 0;
    private /*@spec_public@*/ int id;
    private /*@spec_public@*/ boolean referenced;
    private /*@spec_public@*/ int age;

    MyObject() {
        id = totalId;	// 保证创建新对象的id不重复
        totalId++;
        referenced = true;
        age = 0;
    }

    /*@ public normal_behavior
      @ assignable age;
      @ ensures age == newAge;
      @*/
    public void setAge(int newAge) {
        this.age = newAge;
    }

    //@ ensures \result == age;
    public /*@pure@*/ int getAge() {
        return age;
    }

    //@ ensures \result == id;
    public /*@pure@*/ int getId() {
        return id;
    }

    /*@ public normal_behavior
      @ assignable referenced;
      @ ensures referenced == newReferenced;
      @*/
    public void setReferenced(boolean newReferenced) {
        this.referenced = newReferenced;
    }

    //@ ensures \result == referenced;
    public /*@pure@*/ boolean getReferenced() {
        return referenced;
    }

    /*@ public normal_behavior
      @ requires this == o;
      @ ensures \result == true;
      @ also
      @ requires this != o && (o == null || !(o instanceof MyObject));
      @ ensures \result == false;
      @ also
      @ requires this != o && o != null && o instanceof MyObject;
      @ ensures \result == (id == (MyObject) o.getId() &&
      @         referenced == (MyObject) o.getReferenced() &&
      @         age == (MyObject) o.getAge());
      @*/
    @Override
    public /*@pure@*/ boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof MyObject)) {
            return false;
        }
        MyObject myObject = (MyObject) o;
        return id == myObject.getId() && referenced == myObject.getReferenced()
                && age == myObject.getAge();
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, referenced, age);
    }

    /*@ public normal_behavior
      @ requires object != null;
      @ ensures ((age < object.age) || (age == object.age && id < object.id)) ==> (\result == -1);
      @ ensures ((age > object.age) || (age == object.age && id >= object.id)) ==> (\result == 1);
      @ also
      @ public exceptional_behavior
      @ requires object == null;
      @ signals (NullPointerException e) object == null;
      @*/
    public /*@pure@*/ int compareTo(MyObject object) {
        if (object == null) {
            throw new NullPointerException();
        }
        if ((age < object.age) || (age == object.age && id < object.id)) {
        // 年龄小的更小；年龄相同，则创建早的更小
            return -1;
        } else {
            return 1;
        }
    }
}

MyHeap.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package gcsimulation;

public class MyHeap<T extends Comparable<T>> {

    private Object[] elementData;	// 下标从1开始
    private int capacity;		   // 初始划分的容量
    private int size;			   // 实际堆的大小

    MyHeap(int capacity) {
        elementData = new Object[capacity + 1];
        this.capacity = capacity;	
        this.size = 0;			   
    }

    //@ ensures \result == size;
    public /*@pure@*/ int getSize() {
        return size;
    }

    //@ ensures \result == elementData
    public /*@pure@*/ Object[] getElementData() {
        return elementData;
    }

    /*@ public normal_behavior
      @ requires index >= 1 && index <= getSize();
      @ assignable elementData;
      @ ensures (\forall int i; 1 <= i && i <= getSize() && i != index;
      @          \not_modified(elementData[i]));
      @ ensures elementData[index] == element;
      @*/
    // 置换 index 处数据
    public void setElementData(int index, T element) {
        this.elementData[index] = element;
    }

    /*@ public normal_behavior
      @ assignable size;
      @ ensures size == 0;
      @*/
    // 清除堆的数据
    public void clear() {
        this.size = 0;
    }

    /*@ public normal_behavior
      @ requires newSize >= 0;
      @ assignable size;
      @ ensures size == newSize;
      @*/
    public void setSize(int newSize) {
        this.size = newSize;
    }

    /*@ public normal_behavior
      @ requires indexA >= 1 && indexA <= getSize() && indexB >= 1 && indexB <= getSize();
      @ assignable elementData;
      @ ensures (\forall int i; 1 <= i && i <= getSize() && i != indexA && i != indexB;
      @          \not_modified(elementData[i]));
      @ ensures elementData[indexA] == \old(elementData[indexB]);
      @ ensures elementData[indexB] == \old(elementData[indexA]);
      @*/
    private void swap(int indexA, int indexB) {
        T temp = (T) elementData[indexA];
        elementData[indexA] = elementData[indexB];
        elementData[indexB] = temp;
    }

    public void add(T newElement) {
        if (size == capacity) {
            Object[] oldElementData = elementData.clone();
            // 现有大小达到划分的容量，动态扩容
            capacity = capacity << 1;
            elementData = new Object[capacity + 1];
            for (int i = 1; i <= size; i++) {
                elementData[i] = oldElementData[i];
            }
        }
        elementData[++size] = newElement;
        int tempIndex = size;
        // 将新添加元素向上调整，使其满足小顶堆性质（父节点大于子节点）
        while (tempIndex / 2 != 0 &&
                ((T) elementData[tempIndex]).compareTo((T) elementData[tempIndex / 2]) < 0) {
            swap(tempIndex, tempIndex / 2);
            tempIndex /= 2;
        }
    }

    public void removeFirst() {
        if (size == 0) {
            System.err.println("No element found in list.");
            return;
        }
        // 删除堆顶常规方法，将最后一个元素置换到堆顶，再一路往下调整满足堆结构
        elementData[1] = elementData[size--];
        int index = 1;
        while (true) {
            if (index > size) {
                break;
            }
            // 左右儿子都有，那么如果不满足小于两个儿子的小顶堆性质，要保证换到父节点的儿子小于另一个儿子
            if (index * 2 + 1 <= size) {
                if (((T) elementData[index]).compareTo((T) elementData[index * 2]) > 0 ||
                        ((T) elementData[index]).compareTo((T) elementData[index * 2 + 1]) > 0) {
                    if (((T) elementData[index * 2 + 1]).compareTo(
                            (T) elementData[index * 2]) > 0) {
                        swap(index * 2, index);
                        index = 2 * index;
                    } else {
                        swap(index * 2 + 1, index);
                        index = 2 * index + 1;
                    }
                }
            } else if (index * 2 <= size) {
                if (((T) elementData[index]).compareTo((T) elementData[index * 2]) > 0) {
                    swap(index * 2, index);
                    index = 2 * index;
                }
            } else {
                break;
            }
        }
    }
}

JvmHeap.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package gcsimulation;

import java.util.List;

public class JvmHeap extends MyHeap<MyObject> {

    JvmHeap(int capacity) {
        super(capacity);
    }
    
    // 传入要设置为未引用的 id list，将id在该list中的对象状态置为未引用
    public void setUnreferencedId(List<Integer> objectId) {
        for (int id : objectId) {
            for (int i = 1; i <= this.getSize(); i++) {
                MyObject myObject = (MyObject) this.getElementData()[i];
                if (myObject.getId() == id) {
                    myObject.setReferenced(false);
                    this.setElementData(i, myObject);
                }
            }
        }
    }

    /*@ public normal_behavior
      @ assignable elementData, size;
      @ ensures size == (\sum int i; 1 <= i && i <= \old(size) &&
      @                              \old(elementData[i].getReferenced()) == true; 1);
      @ ensures (\forall int i; 1 <= i && i <= \old(size);
      @          \old(elementData[i].getReferenced()) == true ==>
      @           (\exist int j; 1 <= j && j <= size; elementData[j].equals(\old(elementData[i]))))
      @ ensures (\forall int i; 1 <= i && i <= \old(size);
      @          \old(elementData[i].getReferenced()) == false ==>
      @           (\forall int j; 1 <= j && j <= size;
      @           !elementData[j].equals(\old(elementData[i]))))
      @ ensures (\forall int i; 1 <= i && i <= size;
      @          (\exists int j; 1 <= j && j <= \old(size);
      @          elementData[i].equals(\old(elementData[j]))));
      @*/
    // 移除 Jvm 堆中所有未标记的元素。
    public void removeUnreferenced() {
        // 可对原有的堆进行克隆，并通过 clear 方法将堆的 size 置为 0
        Object[] oldElementData = this.getElementData().clone();
        int oldSize = this.getSize();
        clear();
		// 遍历原有的堆中的各个对象，调用 add 方法将其中已标记的对象加入至新堆中
        for (int i = 1; i <= oldSize; i++) {
            MyObject myObject = (MyObject) oldElementData[i];
            if (myObject.getReferenced() == true) {
                add(myObject);
            }
        }
    }

    /*@ public normal_behavior
      @ requires size > 0;
      @ ensures (\exist int i; 1 <= i && i <= size;
      @          (\forall int j; 1 <= j && j <= size && j != i;
      @            elementData[i].compareTo(elementData[j]) == -1) &&
      @           \result == elementData[i]);
      @ also
      @ public normal_behavior
      @ requires size == 0;
      @ ensures \result == null;
      @*/
    // 根据小顶堆性质，堆顶就是年龄最小的对象
    public /*@pure@*/ MyObject getYoungestOne() {
        if (getSize() > 0) {
            return (MyObject) getElementData()[1];
        }
        return null;
    }
}

MyJvm.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package gcsimulation;

import java.util.ArrayList;
import java.util.List;

public class MyJvm {
    private static final int DEFAULT_CAPACITY = 16;
    private static final int MAX_TENURING_THRESHOLD = 8;

    private JvmHeap eden;
    private ArrayList<JvmHeap> survive = new ArrayList<>();
    private int fromSurviveSpace = 1;
    private JvmHeap tenured;

    MyJvm() {
        eden = new JvmHeap(DEFAULT_CAPACITY);
        survive.add(new JvmHeap(DEFAULT_CAPACITY));
        survive.add(new JvmHeap(DEFAULT_CAPACITY));
        tenured = new JvmHeap(DEFAULT_CAPACITY);
    }

    public void createObject(int count) {
        for (int i = 0; i < count; i++) {
            MyObject newObject = new MyObject();
            eden.add(newObject);

            if (eden.getSize() == DEFAULT_CAPACITY) {
                System.out.println("Eden reaches its capacity,triggered Minor Garbage Collection.");
                // 填满eden时，会触发小型垃圾回收机制
                minorGC();
            }
        }
    }

    public void setUnreferenced(List<Integer> objectId) {
        eden.setUnreferencedId(objectId);
        survive.get(fromSurviveSpace).setUnreferencedId(objectId);
        tenured.setUnreferencedId(objectId);
    }

    public void removeUnreferenced() {
        eden.removeUnreferenced();
        survive.get(fromSurviveSpace).removeUnreferenced();
        tenured.removeUnreferenced();
    }

    public void minorGC() {
        // Eden 中已标记的对象变为 1 岁并转移到 ToSurvivorSpace；
        for (int i = 1; i <= eden.getSize(); i++) {
            MyObject mo = (MyObject) eden.getElementData()[i];
            if (!mo.getReferenced()) {
                continue;
            }
            mo.setAge(mo.getAge() + 1);
            survive.get(1 - fromSurviveSpace).add(mo);
        }
		// FromSurvivorSpace 中已标记的对象老一岁后，若未超过年龄阈值 8，则转移到 ToSurvivorSpace，反之转移到老年区 Tenured；
        for (int i = 1; i <= survive.get(fromSurviveSpace).getSize(); i++) {
            MyObject mo = (MyObject) survive.get(fromSurviveSpace).getElementData()[i];
            if (!mo.getReferenced()) {
                continue;
            }
            mo.setAge(mo.getAge() + 1);
            if (mo.getAge() > MAX_TENURING_THRESHOLD) {
                tenured.add(mo);
            } else {
                survive.get(1 - fromSurviveSpace).add(mo);
            }
        }
		// 清空 FromSurvivorSpace 和 Eden ，并交换 FromSurvivorSpace 与 ToSurvivorSpace。
        eden.setSize(0);
        survive.get(fromSurviveSpace).setSize(0);
        fromSurviveSpace = 1 - fromSurviveSpace;
    }

    public void majorGC() {
        // 拷贝老年区对象副本，清空老年区，将仍在引用状态的对象还回老年区中，相当于移除了未引用对象
        Object[] oldElement = tenured.getElementData().clone();
        int oldSize = tenured.getSize();
        tenured.setSize(0);
        for (int i = 1; i <= oldSize; i++) {
            MyObject mo = (MyObject) oldElement[i];
            if (!mo.getReferenced()) {
                continue;
            }
            tenured.add(mo);
        }
    }

    public void getSnapShot() {
        System.out.println("Eden: " + eden.getSize());
        for (int i = 1; i <= eden.getSize(); i++) {
            MyObject mo = (MyObject) eden.getElementData()[i];
            System.out.print(mo.getId() + " ");
        }
        System.out.println("");

        System.out.println("Survive 0: " + survive.get(0).getSize());
        for (int i = 1; i <= survive.get(0).getSize(); i++) {
            MyObject mo = (MyObject) survive.get(0).getElementData()[i];
            System.out.print(mo.getId() + " ");
        }
        MyObject youngestInSurvive0 = survive.get(0).getYoungestOne();
        if (youngestInSurvive0 != null) {
            System.out.print(", the youngest one " + youngestInSurvive0.getId() +
                    "'s age is " + youngestInSurvive0.getAge());
        }
        System.out.println("");

        System.out.println("Survive 1: " + survive.get(1).getSize());
        for (int i = 1; i <= survive.get(1).getSize(); i++) {
            MyObject mo = (MyObject) survive.get(1).getElementData()[i];
            System.out.print(mo.getId() + " ");
        }
        MyObject youngestInSurvive1 = survive.get(1).getYoungestOne();
        if (youngestInSurvive1 != null) {
            System.out.print(", the youngest one " + youngestInSurvive1.getId() +
                    "'s age is " + youngestInSurvive1.getAge());
        }
        System.out.println("");

        System.out.println("Tenured: " + tenured.getSize());
        for (int i = 1; i <= tenured.getSize(); i++) {
            MyObject mo = (MyObject) tenured.getElementData()[i];
            System.out.print(mo.getId() + " ");
        }
        MyObject youngestInTenured = tenured.getYoungestOne();
        if (youngestInTenured != null) {
            System.out.print(", the youngest one " + youngestInTenured.getId() +
                    "'s age is " + youngestInTenured.getAge());
        }

        System.out.println("\n---------------------------------");
    }
}

Main.java：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
package gcsimulation;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        MyJvm myJvm = new MyJvm();
        System.out.println("Start JVM Garbage Collection Simulation.");
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String operation = scanner.next();
            if (operation.equals("CreateObject")) {
                int count = scanner.nextInt();
                myJvm.createObject(count);
                System.out.println("Create " + count + " Objects.");
            } else if (operation.equals("SetUnreferenced")) {
                List<Integer> unrefList = new ArrayList<>();
                while (scanner.hasNextInt()) {
                    int id = scanner.nextInt();
                    unrefList.add(id);
                    System.out.println("Set id: " + id + " Unreferenced Object.");
                }
                myJvm.setUnreferenced(unrefList);
            } else if (operation.equals("RemoveUnreferenced")) {
                myJvm.removeUnreferenced();
                System.out.println("Remove Unreferenced Object.");
            } else if (operation.equals("MinorGC")) {
                myJvm.minorGC();
                System.out.println("Execute Minor Garbage Collection.");
            } else if (operation.equals("MajorGC")) {
                myJvm.majorGC();
                System.out.println("Execute Major Garbage Collection.");
            } else if (operation.equals("SnapShot")) {
                myJvm.getSnapShot();
            } else {
                System.err.println("Invalid operation.");
            }
        }
        scanner.close();
        System.out.println("End of JVM Garbage Collection Simulation.");
    }
}