c - 多个指针和标记和扫描

Question

我正在尝试实现一种小型脚本语言，并打算决定哪种垃圾收集算法适合我的利益。我选择了 Mark & Sweep，但我想我误解了这个概念。

假设调用了一个任意函数，它创建了以下变量(可能它们没有名称，但为了简单起见，假设它们是在这个函数中创建的)。

f() {
    /*f creates following variables*/     
    x = (1,2,(3,4,(5,6))); //this is tuple
    a = x;
    y = x[2];
    z = y[2];
    p = (10,y);
}

在上面的例子中，一切都是对象(整数、字符串、元组、 double 等)，元组持有指向其对象的指针。此外，每个对象都存在于堆中。当函数超出范围时，它必须删除分配的变量。函数作用域如下所示。

+-----+
|     |
|  x  +---------->(1,2,+)
+-----+           ^    |
                  |    v
+-----+           |    (3,4,+)
|     |           |    ^    |
|  a  +-----------+    |    v
+-----+                |    (5,6)
                       |    ^
+-----+                |    |
|     |                |    |
|  y  +----------------+    |
+-----+                |    |
                       |    |
+-----+                |    |
|     |                |    |
|  z  +---------------------+
+-----+                |
                       |
+-----+                |
|     |                |
|  p  +----------->(10,+)
+-----+

必须删除所有变量(a、x、y、z、p)，但问题是如何删除？我知道 Mark & Sweep 是一种垃圾收集算法，我认为这些变量现在是我的垃圾。函数完成了它的工作，它必须将分配的内存返回给系统。

我试过以下，每个对象都有一个标记位，创建后标记位设置为 0。当程序推送一个由变量保存的对象时，它会将其标记转换为 1，并且不会发生自由错误，因为每个人都在程序知道它有一个所有者。到目前为止，这种方法已经奏效了。但是如果我有很多像示例中的变量，我该如何删除多个指针？

这里我的假设是，首先打破 x 和它的对象之间的所有权。然后说每个变量来标记它们的对象(如果对象是元组，则递归地将其对象标记位设置为 1)。现在 (1,2,...) 对象的标记位被变量 'a' 设置为 1；我可以尝试释放它，但程序不允许。如果我为我的表中的每个变量都做这个，复杂性看起来会很大(我对每个对象都有标记和清除阶段)。

我的问题是我对 Mark & Sweep 算法的看法是否正确？根是我的变量吗？如何删除多个指针甚至循环引用？

Answer 1

对于标记和扫描，您需要能够在一侧扫描所有已分配的对象，在另一侧扫描所有可到达的对象。

• 假设所有已分配对象上的标记位都已清除，则扫描所有可从根变量访问的对象。当找到一个对象时，如果它已经被标记，则跳过它，否则标记它并递归枚举它指向的对象。这个阶段很棘手，因为这种递归可能会太深，因此需要比普通递归更聪明的方法。

• 一旦标记了所有可达对象，扫描所有分配的对象:对于每个对象，如果标记了，清除标记，否则不可达，因此收集它(即:使其可用于重新分配或释放它)。

在 Sweep 阶段结束时，所有分配的对象都未标记，因此假设成立。稍微更高效的实现会在 2 个状态之间交替，避免需要清除可达对象上的标记位，从而减少扫描阶段所需的内存带宽。

当您在程序的正常过程中更改对象引用时，您不需要做任何特殊的事情:只需存储新引用的地址。

要有效地删除从您的全局变量中引用的对象，您应该使这些变量指向null 或其他一些对象。

Mark & Sweep 的优点是算法相对简单，并且能够收集带循环的复杂结构。缺点是在stop the world 模式下花费的时间，特别是在多线程应用程序和实时应用程序甚至用户交互应用程序中。已发现更先进的方法来处理这些问题，但它们的实现可能非常棘手。