Skip to content

Garbage Collection

:material-circle-edit-outline: 约 474 个字 :material-clock-time-two-outline: 预计阅读时间 2 分钟

Garbage：已经分配的但不会再被用到的内存空间

我们采取保守策略：回收 not reachable 的空间，因为不可达的一定是垃圾

Mark-and-Sweep Collection

使用 DFS

通过 DFS 来检索出所有结点并将其标记

所有未标记的结点都是不可达结点，我们就通过 Sweep 进行回收，即，线性遍历 record，Link the unmarked nodes in a linked list (freelist)，并且消除所有标记，以便下一轮回收

这个算法的问题是使用了递归算法 DFS，栈可能爆，我们就用一个 explicit stack instead of recursion，改成非递归

Pointer Reversal

基本想法：基于上一种方法，但将 DFS 的 stack 储存在有向图里

遇到新 record 时：

  1. 标记 record
  2. 将 record 里的指针反转，指向 DFS 路径的前继节点
  3. 返回的时候恢复指针

Chapter13.pdf 23 页有例子 Chapter13.pdf 35 页有例子

image-20250519174131365

Reference Counts

记录每个 record 被多少个指针指向，然后没人指向它就说明是不可达，直接回收

即 the reference count of this record

当然维护的开销也变大了，而且没法回收环垃圾

Chapter13.pdf 49 页有例子

image-20250519174119571

Copying Collection

将 mem 分为两部分：

  • from-space: 给系统用的
  • to-space: 不给系统用的

当 from-space is exhausted 时，copy all reachable records to to-space，反转两者角色，这使得复制后得到的 to space 是紧凑的，没有 fragmentation

复制的时候有个问题，我们需要更新所有 record 的指针指向的地址，指向新的被复制过来的 record，而不是仍指向旧的 record

我们每复制一个 record，就在其旧的 record 里设置一个 forwarding pointer 指向新的 record，借此确认该 record 有被复制

然后使用 Cheney’s Algorithm，用 BFS 遍历，其引入了特殊指针 scan，对已复制的 record 进行遍历，检查并更新所有指针

image-20250615171822686

image-20250519174054526