GC算法实现篇之并发标记清除

简述

并发标记清除是一种适用于堆内存的垃圾回收算法，通常用于大型的应用程序或者需要长时间运行的应用程序中。其主要的特点是多线程标记和清除，相对于其他垃圾回收算法，具备了更好的性能表现。

基本流程

并发标记清除的基本流程如下：

1. 初始状态：堆中的所有对象都被标记为“未标记”

2. 初始标记：从根对象开始，对所有可达的对象进行标记。该过程是单线程的执行过程，它会暂停用户线程，阻塞整个应用程序。当初始标记完成后，应用程序会恢复运行。

3. 并发标记：该阶段可以并发运行，也就是说可以和用户线程同时进行。从根对象出发，对所有可达的对象进行标记，并建立一张被标记对象的清单表。

4. 并发清除：该阶段可以并发运行，只有在完成了并发标记阶段后，才能执行并发清除。清除没有标记过的全对象，并且更新对象引用。

5. 再标记：该阶段针对第三阶段的并发标记期间存在的问题。由于并发标记过程中，用户线程还在执行，因此必然会出现部分对象的标记状态发生改变，而这些标记状态发生改变的对象需要重新标记。此阶段也是单线程执行的。

6. 稳定阶段：当第五阶段的再标记完成后，就进入了稳定阶段。在这个阶段中，用户线程和标记线程都已经停止了，堆中的所有垃圾都被清除掉了。系统进入到一个稳定状态，等待用户线程的下一轮运行。

示例

下面通过一个示例来说明一下并发标记清除的基本流程。

示例1

假设有以下代码：

public void test(){
  List<String> list = new ArrayList<>();
  for(int i=0;i<1000000;i++){
    list.add("item:"+i);
  }
}

在这个方法中，会创建一个新的ArrayList对象list，并且向其中添加1000000个字符串。那么在这个过程中，会创建出非常多的String对象，这些String对象大部分是不需要运行时使用的，因此需要回收。

当JVM调用垃圾回收器时，会执行并发标记清除的算法。在这个过程中，需要执行以下几个步骤：

1. 初始标记：此时会标记出list对象以及其中的所有String对象，这个过程需要暂停用户线程。

2. 并发标记：运行时，我们假设JVM创建了4个线程来执行标记操作。在并发标记的过程中，可以和用户线程同时进行操作，这个过程中会标记出所有的可达对象，而不会标记不可达对象。

3. 并发清除：清除所有未标记的对象，并将存活的对象向空间中移动。

4. 再标记：由于并发标记的过程中，用户线程可能会改变某些对象的状态，因此需要再次对这些对象进行标记，以保证这些对象不会被误清除。这是一个单线程的过程。

5. 稳定阶段：此时系统进入到一个稳定状态，等待用户线程的下一轮运行。

示例2

假设有以下代码：

public class Node {
  private Node next;
  private Object value;

  public Node(Object value) {
    this.value = value;
  }

  public void setNext(Node next) {
    this.next = next;
  }

  public Node getNext() {
    return next;
  }
}

public void test(){
  Node node1 = new Node("item:1");
  Node node2 = new Node("item:2");
  Node node3 = new Node("item:3");
  node1.setNext(node2);
  node2.setNext(node3);
}

在这个方法中，会创建出3个Node对象，每个对象中都包含一个字符串对象。在将node1和node2、node2和node3连接时，会引用相互指向，形成了一个对象图。当JVM调用垃圾回收器时，会执行并发标记清除的算法。在这个过程中，需要执行以下几个步骤：

1. 初始标记：此时会标记出node1, node2, node3以及其中的所有字符串对象，这个过程需要暂停用户线程。

2. 并发标记：运行时，我们假设JVM创建了4个线程来执行标记操作。在并发标记的过程中，可以和用户线程同时进行操作，这个过程中会标记出所有的可达对象，而不会标记不可达对象。

3. 并发清除：清除所有未标记的对象，并将存活的对象向空间中移动。

4. 再标记：由于并发标记的过程中，用户线程可能会改变某些对象的状态，因此需要再次对这些对象进行标记，以保证这些对象不会被误清除。这是一个单线程的过程。

5. 稳定阶段：此时系统进入到一个稳定状态，等待用户线程的下一轮运行。