Java中标记清除垃圾收集算法

垃圾收集算法（例如标记和清除）在后台运行，以管理 C++ 和 Java 等编程语言中的内存。当动态创建对象时，它们会占用堆中的内存。但是，如果我们继续创建对象而不释放内存，则可能会导致内存不足错误。

为了防止这种情况，垃圾收集会自动释放程序中不再引用或无法访问的对象的内存。它减轻了程序员的内存管理负担，因为垃圾收集器为未引用的对象释放内存，确保为要分配的新对象提供可用空间。

标记和清除算法
标记和清除垃圾收集算法是一种简单而有效的算法，用于回收应用程序不再使用的内存。该算法的工作原理是首先标记所有仍在使用的对象。一旦所有活动对象都被标记，垃圾收集器就会扫描堆并回收所有未标记的对象。

1. 标记阶段：
在标记阶段，垃圾收集器从根（全局引用、局部变量和静态引用）开始遍历对象图，并标记所有可到达的对象。不可访问的对象被视为垃圾。

当对象创建时，标记位设置为0。标记阶段负责识别堆中的所有活动对象。它是通过遍历堆并标记从堆的根部可到达的所有对象来完成的。堆的根是应用程序可以直接访问的对象，例如局部变量和对象引用。

根变量是指可从局部变量访问的对象的变量。我们假设只有一个根。

  1. 根源：
    • 全局引用（例如静态变量）。
    • 线程堆栈中的局部变量。
  • 遍历：
    • 从根开始遍历对象图。
    • 将对象标记为可达。


    算法：

    Mark(root)  
    If markedBit(root) = false then  
                         markedBit(root) = true  
                                           For each v referenced by root  
                                           Mark(v)  

    2.清扫阶段：
    在清理阶段，垃圾收集器识别并回收未被标记为可达的对象占用的内存。这涉及遍历整个堆并为未引用的对象释放内存。

    清扫阶段负责回收堆中所有未标记的对象。具体做法是释放分配给未标记对象的内存。

    1. 可用内存：
      • 未标记（垃圾）对象占用的内存被释放。
  • 对象状态：
    • 未标记的对象可能会重置其状态或返回到空闲对象池。 


    Sweep()  
    For each object p in heap  
    If markedBit(p) = true then  
                      markedBit(p) = false  
                                     else  
                                         heap.release(p)  

    标记-清扫算法被称为 "跟踪式垃圾收集器"，因为它能系统地跟踪并识别所有可直接或间接从程序根引用到达的对象。

    代码

    class Node {
        Node next;
    }

    public class Example {
        public static void main(String[] args) {
            Node root = new Node();
            root.next = new Node();
            root.next.next = new Node();

            // Assume root is a global reference, and other nodes are reachable from it

                // ... Program logic ...

                // At some point, the garbage collector is triggered

                // Mark-and-Sweep phases
            mark(root);        // Mark phase
            sweep(root);       // Sweep phase
        }

        static void mark(Node root) {
                // Recursive or iterative marking algorithm
                // Traverse the object graph, marking reachable objects
        }

        static void sweep(Node root) {
            Node current = root;

                // Iterate through the heap
            while (current != null) {
                if (isMarked(current)) {
                        // Object is marked (reachable), keep it
                    unmark(current);
                } else {
                        // Object is not marked (garbage), free its memory
                    freeMemory(current);
                }
                current = current.next;
            }
        }

        static boolean isMarked(Node node) {
                // Check if the object is marked as reachable
                // (implementation-specific)
            return false;
        }

        static void unmark(Node node) {
                // Unmark the object (implementation-specific)
        }

        static void freeMemory(Node node) {
                // Free memory occupied by the object (implementation-specific)
        }
    }

    在 Java 中，垃圾收集过程（包括所使用的算法）由 Java 虚拟机 (JVM) 管理。JVM 通常采用更复杂的算法（包括分代垃圾收集）来提高内存管理的效率。标记和清除算法是理解垃圾收集原理的概念基础。

    标记清除算法的优点

    • 标记和清除算法可以处理循环引用，而不会陷入无限循环。它确保算法即使在循环中也能正确识别可达对象。
    • 该算法在执行过程中不会引入额外的开销，使其成为一种高效可靠的垃圾收集方法。

    标记和清除算法的缺点
    • 标记和清除方法的显着缺点之一是，它会在垃圾收集算法运行时导致正常程序执行中断。
    • 标记和清除垃圾收集算法的另一个缺点是，在程序上运行多次后，可到达的对象会变得碎片化，它们之间有许多小的未使用内存区域。

    压缩compact算法：
    当小的、未使用的内存区域分散在整个堆中时，就会出现碎片问题。当垃圾收集器从不再需要的对象回收内存时，就会发生这种情况。如果垃圾收集器不压缩堆，这些小的、未使用的内存区域可能会阻止分配新对象。

    压缩正在重新排列堆中的对象，以便空闲内存区域是连续的。可以通过在堆中移动对象或将它们复制到新位置来完成。

    Compaction可以减少碎片并提高垃圾收集器的性能。当堆被压缩时，垃圾收集器可以快速找到空闲内存区域。

    如果堆被压缩，五个空闲内存区域将被组合成一个大小为 12 个单位的空闲内存区域。它将允许分配需要 10 个内存单元的对象。

    压缩可能非常耗时，因此垃圾收集器有时才会执行压缩。然而，压缩对于经常出现碎片的应用程序可能是有益的。