运行时根与堆可达性

一个函数返回了，并不说明它创建的全部对象都可释放；一个对象形成了引用环，也不说明它一定要保留。运行时收集的判断入口是：暂停中的程序还能从哪里拿到对象引用，并沿哪些字段继续找到其他对象？

一个不能漏掉调用者的快照 ​

共享计数器有如下已分配对象，箭头都表示字段内保存的引用：

P -> A, B       A -> Ei       B -> Ep
Ei -> C         Ep -> C       C.value = 7
U.value = 999

P 是 (inc,peek) 对，A、B 为两个闭包，Ei、Ep 为各自环境。make 已返回。main 从 P 取出 a、b 后不再需要 P；调用 a(3) 已进入 inc，A 本身也不再被以后指令使用，因为当前代码位置与环境已经保存。inc 写完 7、尚未返回时暂停；main 返回后仍要调用 b。

在固定根映射下，槽 main.b 保存 B，槽 inc.env 保存 Ei；其余旧位模式即使还留在死槽，也不是本次根。起点是 {B,Ei}，从 B 到 Ep，从 Ei 和 Ep 到同一个 C，所以

A、P、U 已无从取得，可以回收。C 不必直接放在根槽中；经环境间接可达就足够。反之，若只扫描当前 inc 的环境，得到的仅是 {Ei,C}，B 与 Ep 就被错误遗漏。调用者还没执行的 b(0) 是根活跃的原因，不能只搜索当前函数体出现的变量名。

按对象布局理路堆对象布局与分配Heap object layout and allocation · Object descriptor · Bump-pointer allocation用对象头、字段偏移与指针描述符规定可扫描的堆布局，并给出带溢出检查和初始化约束的顺序分配器。，B 占 24 字节，其余三个各占 16 字节，存活部分为 72 字节；全部已分配对象为 136 字节，所以本次可释放 64 字节。可达性计的是对象身份，Ei 和 Ep 同指 C 不会把 C 计费两次。

物理回收与静态分析不同 ​

抽象垃圾回收理路抽象垃圾回收Abstract garbage collection · Abstract GC在静态分析中删除已不可能被访问的抽象存储内容，为什么会让后续结果更精确。使用相似的可达闭包，目的是从某个分析状态中删掉失效的抽象存储事实，提高静态精度。本页 H 的节点是这次执行的具体对象，根是实际暂停位置，删除会释放实际存储。抽象槽可能合并多次分配的值，不能把它当作一个可直接释放的物理块。

在精确运行时模型里，描述符与根映射告诉我们哪些位置真是引用。保守扫描则可能把“看起来像地址”的整数也当根，因此通常多保留对象；它不能仅凭数值猜测任意改写这些位置，否则可能把普通整数改坏。本页移动收集不采用这种猜测。

弱引用、终结器、对象复活以及与外部代码的交互需要补充可达阶段和句柄协议。多线程或并发收集还需要协调快照与新写入。本页将它们排除，是为了让上述首次读取论证有可检查的前提，而不是把它当作所有 GC 的完整规范。

不可达为什么足以删除 ​

安全论证需要一条明确的“引用从哪里来”规则：以后获得旧对象引用，只能复制现有根值、从可达对象的字段中读出，或从已经登记的外部句柄取得；新分配只产生新对象身份。计算期间不得从整数、悬空指针、未登记的外部代码中重新造出旧对象引用。

假设未来第一次读取某个被删对象 O。用于这次读取的指针不可能凭空出现；沿其来源回溯，若来自暂停时的根，则 O 已可达；若来自字段读取，则先得到该字段所属对象，再沿字段到 O，同样形成根路径；若来自新分配，它指向的是新身份而非旧 O。三种情况都与 O 在暂停时不可达矛盾。因此删除 H\R 不改变后续合法读取结果。

写入也不会突然把一个不可达旧对象救活：要把它的地址写入可达对象，程序必须先持有那个地址，而持有的位置本来就应算根或可达字段。地址数值可以被重用，但新分配产生的是新身份；一个允许读取悬空地址的语言不满足上述前提。

这个引理证明的是安全性，不是“全部未来无用对象都会被收走”。令 keep 指向一个大数组，随后无限执行不再读取它的循环；只要所用根映射仍把 keep 保留，数组就可达，收集器会留下它。静态活跃性、环境裁剪可以减少这类保留，但仅凭图遍历无法解决所有未来是否使用的问题。

计算任务与迁移 ​

给定 r 个根槽、v 个可达对象、e 个可达指针字段，用带已访问标记的队列或栈，每个根读一次、每个可达对象扫描一次，时间为 O(r+v+e)，辅助空间至多 O(v)。这是求 R 的成本；标记清扫理路标记清扫垃圾回收Mark-sweep garbage collection · Mark-and-sweep · 标记清除先从全部根标记可达对象，再遍历已分配对象释放未标记者；对象不搬家，但清扫与碎片都有成本。再遍历已分配对象找死亡者，复制收集理路复制式垃圾回收Copying garbage collection · Cheney algorithm · Semispace collection · 半空间复制收集用 Cheney 的扫描区间与转发地址把存活对象复制到另一半空间，同时更新全部根和字段，保持共享与环。则迁移活对象并整体弃用旧区。维护可分配空间的成本由各自算法承担。

迁移题一：删掉 main.b，但新增一个全局槽 g=B。结果仍是四个活对象；变化的是根位置，不是堆图。再让 g=null，只剩 {Ei,C}。

迁移题二：增加一个不可达环 X.next=Y, Y.next=X。它们各有一个入引用，仍都不可从根取得，因而都可回收。给 X 添加一个根以后，X、Y 同时进入 R。再试只有 X 且 X.next=X 的单点自环，结论同样由是否有根决定。若图算法排除了自环，或把“有入边”误当作活跃判据，就会在这些变体上失败。