JVM 中的垃圾回收算法

垃圾回收是一种自动化的内存管理方式，它可以监测并清除内存中不再使用的对象，使得内存空间可以被回收并重新利用。在 JVM 中，垃圾回收器负责管理虚拟机的内存分配和回收。

JVM 中常见的垃圾回收算法主要包括：标记-清除算法、复制算法、标记-整理算法和分代算法。

一、标记-清除算法

标记-清除算法是一种垃圾回收算法，用于清理动态分配内存中无用的对象。在JVM中，标记-清除算法作为主要的垃圾回收算法之一，被用于检查并清理Java程序创建的所有对象。

标记-清除算法由两个阶段组成，分别是标记和清除。在标记阶段，JVM遍历所有可访问的对象，并打上标记；而在清除阶段，JVM将没有标记的对象视为垃圾，并回收其占用的内存空间。

标记-清除算法的实现相对简单，但也存在明显的缺点。其中最重要的一点是，它会导致内存碎片。由于标记-清除算法只是简单的清除那些没有标记的对象，因此可以想象出这样一种情况：如果有大量的内存块被频繁地创建和销毁，它们将在内存中留下许多小而不规则的碎片，这些碎片太小无法再分配给新的大型对象，从而导致可用内存空间变得稀缺，限制了Java程序的性能。

标记-清除算法的实现

标记-清除算法通常需要两个额外的数据结构来辅助执行垃圾回收。这些数据结构分别是根集以及标记位。

根集

在Java中，根集是从内存中的引用开始的对象集合。它包括静态变量、类变量和活动线程的本地变量，JVM通过遍历这些根集中的对象来确定程序中的可访问对象。

标记位

标记位是一个额外的表格或者标记位向量，用于跟踪哪些对象是活动的。当垃圾回收开始时，所有对象都被标记为未使用。在标记阶段中，JVM通过遍历根集的可访问对象来标记对象，并在标记位向量中记录它们。

一旦标记完成，JVM开始遍历整个堆空间，将没有标记的对象视为垃圾，并清除它们占用的内存空间。清理之后，剩余的内存块会重新组合，从而减少了空间碎片化问题的发生。

以下是标记-清除算法的主要步骤：

1. 初始化标记位向量，将所有对象标记为不用
2. 从根集开始遍历，标记所有可访问的对象，将其标记为已使用
3. 遍历整个堆空间，将未被标记的对象视为垃圾，并回收该对象所占用的内存
4. 对内存空间进行重新组合，减少空间碎片化

原理示例

在以下Java示例代码中，我们创建了一个MyObj类作为测试对象。这个类包含两个成员变量：objName和objNum，用于记录每个对象的名称及编号。我们还通过一个静态objects列表模拟了Java程序中的动态分配内存，将新创建的MyObj对象添加到列表中。在执行垃圾回收时，程序会遍历objects列表，并标记所有仍然有用的对象。如果对象没有被标记，则将其设置为null，以便之后被JVM清除。

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

public class MarkAndSweepDemo {

    private static List<MyObj> objects = new ArrayList<>();

    public static void main(String[] args) {
        // 创建一些对象
        for (int i = 0; i < 10; i++) {
            objects.add(new MyObj("Object " + i, i));
        }

        // 标记并清理垃圾
        markAndSweep();

        // 打印剩余的对象
        System.out.println("Remaining Objects:");
        for (MyObj obj : objects) {
            if (obj != null) {
                System.out.println(obj.toString());
            }
        }
    }

    private static void markAndSweep() {
        // 初始化标记位向量
        boolean[] marked = new boolean[objects.size()];

        // 标记所有可访问的对象
        for (int i = 0; i < objects.size(); i++) {
            if (objects.get(i) != null) {
                mark(i, marked);
            }
        }

        // 清理没有标记的对象
        for (int i = 0; i < objects.size(); i++) {
            if (!marked[i]) {
                objects.set(i, null);
            }
        }

        // 对内存进行重新组合
        while (objects.contains(null)) {
            objects.remove(null);
        }
    }

    private static void mark(int index, boolean[] marked) {
        // 如果已经标记过，则不需要再次标记
        if (marked[index]) {
            return;
        }

        // 标记该对象
        marked[index] = true;

        // 递归标记所有可访问对象
        MyObj obj = objects.get(index);
        for (int i = 0; i < objects.size(); i++) {
            if (objects.get(i) != null && obj.isRelated(objects.get(i))) {
                mark(i, marked);
            }
        }
    }
}

class MyObj {
    private String objName;
    private int objNum;

    public MyObj(String name, int num) {
        objName = name;
        objNum = num;
    }

    public boolean isRelated(MyObj other) {
        return objNum == other.objNum - 1 || objNum == other.objNum + 1;
    }

    @Override
    public String toString() {
        return objName + " " + objNum;
    }
}

在上述示例代码中，我们定义了一个markAndSweep()方法用于执行垃圾回收。该方法首先初始化标记位向量，并通过递归遍历所有可能的对象来标记可访问的对象。如果没有被标记的对象将被设置为null，以便JVM在之后执行清理操作时有机会将其回收。

在执行完垃圾回收后，我们还打印出剩余的对象，以证明垃圾回收算法已经成功地清理程序中无用的对象。

二、复制算法

复制算法是最早的垃圾回收算法之一，它的基本思路是将可用内存空间分为两个相等的区域，每次只使用其中一个区域，当一个区域用尽后，将所有还存活的对象复制到另一个空闲区域中，然后清除原先的区域中所有的对象。通过反复地执行这个过程，可以保持内存的整洁并避免内存碎片问题。

在Java中，复制算法通常被用于实现新生代的垃圾回收器。新生代包含Eden空间、两个Survivor空间和老年代。当Eden空间被用尽时，JVM会将其中的存活对象复制到一个Survivor空间中，并清空Eden空间。经过多次垃圾回收之后，存活时间较长的对象将逐渐被移动到另一个Survivor空间中，并最终被复制到老年代中。复制算法的实现过程可以分为以下几个阶段：

• 当内存需要分配时，将内存分配给Eden空间；
• 当Eden空间用尽时，触发一次Minor GC（或Young GC）；
• 在Minor GC过程中，标记所有存活对象，并将它们复制到Survivor空间中；
• 清空Eden空间和上一个Survivor空间中不再使用的对象；
• 将当前Survivor空间和下一个Survivor空间的位置进行交换（Swap）；
• 重复执行步骤1至步骤5，直到达到一定的阈值或者老年代被占满。

复制算法的优点在于它极大地简化了垃圾回收，因为在处理内存时无需考虑内存碎片问题。此外，由于每个对象在分配时必须移动到新的内存位置，因此内存的分配和回收速度较快。

原理示例

public class CopyingGC {

    static class Object {
        int size;
        
        public Object(int size) {
            this.size = size;
        }
    }

    public static void main(String[] args) {
        // 初始化内存空间大小
        int heapSize = 20;

        // 初始化两个Eden空间和两个Survivor空间
        Object[][] heap = new Object[heapSize][2];

        // 初始化对象列表
        List<Object> objects = new ArrayList<>();

        // 分配内存空间并将对象添加到列表中
        for (int i = 0; i < heapSize; i++) {
            Object obj = new Object(i);
            objects.add(obj);

            // 将对象分配到Eden区域中
            heap[i][0] = obj;
        }

        // 清空Eden区域和Survivor区域
        for (Object[] block : heap) {
            Arrays.fill(block, null);
        }

        // 触发一次垃圾回收操作
        gc(objects, heap);

        // 遍历所有对象并打印尚未被清除的对象
        System.out.println("Remaining Objects:");
        for (Object obj : objects) {
            if (obj != null) {
                System.out.println(obj);
            }
        }
    }

    private static void gc(List<Object> objects, Object[][] heap) {
        // 将存活的对象从Eden区域复制到Survivor区域
        for (int i = 0; i < objects.size(); i++) {
            Object obj = objects.get(i);

            if (obj != null) {
                int age = obj.size / 10;
                if (age < 2) {
                    // 将年龄小于2的对象复制到Survivor0区域中
                    allocate(heap, 0, obj);
                } else {
                    // 将年龄大于等于2的对象复制到Survivor1区域中
                    allocate(heap, 1, obj);
                }
            }
        }

        // 清空Eden区域和上一个Survivor区域
        for (int i = 0; i < heap.length; i++) {
            Object obj = heap[i][0];
            if (obj != null) {
                objects.remove(obj);
            }
            heap[i][0] = null;

            obj = heap[i][1];
            if (obj != null && obj.size >= 20) {
                // 将年龄达到阈值的对象转移到老年代中
                objects.remove(obj);
                heap[i][1] = null;
            }
        }

        // 将下一个Survivor区域和当前Survivor区域位置进行交换
        Object[][] temp = new Object[heap.length][2];
        for (int i = 0; i < heap.length; i++) {
            temp[i][0] = heap[i][1];
            temp[i][1] = heap[i][0];
        }
        heap = temp;
    }

    private static void allocate(Object[][] heap, int block, Object obj) {
        // 随机分配到Survivor区域中的任意一个块
        Random r = new Random();
        int index = r.nextInt(heap.length);
        heap[index][block] = obj;
    }
}

该示例中，我们定义了一个Object类来模拟程序中动态分配的内存对象，然后初始化了两个Eden空间和两个Survivor空间。在分配内存空间并将对象添加到列表中后，手动触发一次垃圾回收操作。

在gc()方法中，我们遍历所有对象并将存活的对象从Eden区域复制到Survivor区域中。根据对象的大小（即占用内存的大小），我们将它们分配到不同的Survivor块中，以便后续的垃圾回收操作。

在完成复制操作后，我们清空了Eden区域和上一个Survivor区域，并将年龄达到阈值的对象转移到老年代中。最后，我们将下一个Survivor区域和当前Survivor区域位置进行交换，以确保下一次垃圾回收时可以使用正确的Survivor块。

三、标记-整理算法

标记-整理算法（Mark-Compact）也是将内存垃圾分为两类，即已使用和未使用的对象，但与标记-清除算法不同的是，在整理阶段，标记-整理算法将存活的对象集中到一端，然后清除掉另一端的所有未使用的空间。

标记-整理算法可以看作是标记-清除算法的改进版，它的优点是避免了标记-清除算法产生的内存碎片问题。但由于需要整理内存空间，因此标记-整理算法在性能上不如复制算法，在空间使用效率方面也稍逊于复制算法。

标记-整理算法实现原理

标记-整理算法的实现原理可以分为两个步骤：

1. 标记阶段

   标记阶段是通过根对象从堆中可达对象开始遍历整个堆。具体步骤如下：

   • 将根对象放入待处理队列中。
   • 从待处理队列中取出一个对象，并且将该对象标记为已处理。
   • 遍历该对象的引用，将所指向的对象加入到待处理队列中。
   • 重复执行第二、三步直到队列为空。

   标记阶段结束后，所有存活的对象都被标记为已处理，而未被标记的对象则为无用对象，可以进行垃圾回收。

2. 整理阶段

   整理阶段是通过移动存活对象来清理堆中无用对象。具体步骤如下：

   • 从堆的起始地址开始，遍历堆内存中的所有对象。
   • 如果当前对象已被标记为存活，将其移动到前面的空闲内存处。如果未被标记，则表示该对象已经死亡，将其释放掉。
   • 移动对象之后，更新该对象的引用地址。
   • 一旦全部存活的对象都被移动到连续的一段地址空间中，对于这一段连续的地址空间，采用一种高效的内存分配算法（例如指针碰撞法或者空闲列表法）进行重新分配。

原理示例

import java.util.*;

public class MarkAndSweep {
    private Set<Object> roots = new HashSet<>(); // 根对象集合
    private Map<Object, Boolean> marked = new HashMap<>(); // 标记表

    /* 遍历所有根对象以及它们的引用，将所有可达的对象进行标记 */
    public void markFromRoots() {
        for (Object root : roots) {
            mark(root);
        }
    }

    /* 对对象进行标记 */
    private void mark(Object obj) {
        if (obj == null || marked.containsKey(obj) && marked.get(obj)) {
            return;
        }
        marked.put(obj, true);  // 标记该对象已访问
        Set<Object> refs = getReferences(obj);
        for (Object ref : refs) {
            mark(ref);  // 递归标记该对象的直接或间接引用
        }
    }

    /* 获取对象的引用集合 */
    private Set<Object> getReferences(Object obj) {
        // TODO: 根据实际需求获取对象的引用集合
        return Collections.emptySet();
    }

    /* 遍历堆中的所有对象，将所有存活的对象移动到堆的起始位置 */
    public void sweepObjects(Object[] heap) {
        int from = 0, to = 0;  // from指向需要处理的对象，to指向下一个空闲空间

        while (from < heap.length) {
            Object obj = heap[from];
            if (marked.containsKey(obj) && marked.get(obj)) {
                // 当前对象存活，移动到下一个空闲位置处
                heap[from] = null;
                heap[to] = obj;

                // 更新对象的引用地址
                updateReferences(obj, from, to);

                to++;
            } else {
                // 当前对象已死亡，释放内存
                heap[from] = null;
            }
            from++;  // 处理下一个对象
        }

        // 重置标记表
        marked.clear();
    }

    /* 更新对象的引用地址 */
    private void updateReferences(Object obj, int fromAddr, int toAddr) {
        Set<Object> refs = getReferences(obj);
        for (Object ref : refs) {
            if (ref != null && marked.containsKey(ref)) {
                // 如果引用对象存活，则更新引用地址
                int refAddr = findObjectAddress(ref);
                if (refAddr >= 0 && refAddr < heap.length) {
                    updateReferenceAddress(fromAddr, toAddr, refAddr);
                }
            }
        }
    }

    /* 获取对象在堆中的地址 */
    private int findObjectAddress(Object obj) {
        for (int i = 0; i < heap.length; i++) {
            if (heap[i] == obj) {
                return i;  // 找到对象，返回对象地址
            }
        }
        return -1;  // 未找到对象，返回-1
    }

    /* 更新引用地址 */
    private void updateReferenceAddress(int fromAddr, int toAddr, int refAddr) {
        if (refAddr == fromAddr) {
            heap[refAddr] = heap[toAddr];
        } else if (refAddr > fromAddr && refAddr <= toAddr) {
            heap[refAddr] = heap[refAddr - (toAddr - fromAddr)];
        }
    }

    /* 添加根对象 */
    public void addRoot(Object root) {
        roots.add(root);
    }

    /* 从根对象中删除指定对象 */
    public void removeRoot(Object root) {
        roots.remove(root);
    }
}

在上述代码中，我们定义了一个MarkAndSweep类来实现标记-整理算法。首先，我们维护了一个根对象集合和一个标记表，其中根对象集合包含了所有根对象，而标记表用于记录每个对象是否被访问过。

markFromRoots()方法遍历所有根对象以及它们的引用，将所有可达的对象进行标记。对于每个对象，我们首先检查它是否为null或者已经被标记过了，如果是则直接返回；否则，标记该对象，然后递归地标记该对象的直接或间接引用。

sweepObjects()方法遍历堆中的所有对象，将所有存活的对象移动到堆的起始位置。对于每个对象，我们首先检查它是否被标记过了，如果是则移动到下一个空闲位置处，并更新对象的引用地址；否则，释放该对象占用的内存空间。此外，我们还需要重置标记表，以备下一次垃圾回收使用。

最后，我们定义了addRoot()和removeRoot()方法用来添加或删除根对象。通过这些方法，我们可以动态地增加或减少根对象，在下一次垃圾回收时进行处理。

四、分代算法

分代算法（Generational）是目前应用最广泛的垃圾回收算法之一。它基于一个假设，即大部分对象都具有很短的生命周期，因此可以将对象按照年龄分为不同的代，然后使用不同的垃圾回收算法来处理不同代的对象。

在 JVM 中，一般将堆分为年轻代和老年代。年轻代包括一个 Eden 区和两个 Survivor 区，新创建的对象首先被分配到 Eden 区，如果 Eden 区没有足够的空间，就会触发一次 Minor GC，此时存活的对象会被复制到其中一个 Survivor 区，另外一个 Survivor 区则被清空。当某个 Survivor 区被充满时，存活下来的对象则会被复制到老年代中，当老年代也满了，就会触发一次 Full GC。

分代算法的优点是它可以针对不同代的对象使用不同的垃圾回收算法，从而提高程序的效率。同时，由于年轻代中大部分对象都是短命的，因此可以通过快速、频繁的 Minor GC 来减少 Full GC 的次数，从而进一步提高程序的性能。