“分代回收把已分配对象划为老代 O 与幼代 Y，minor collection 只回收 Y。本页老代不移动，幼代用复制回收，整个收集过程停止 mutator。根与字段均为精确基址指针；无并发…”
形式陈述
固定半空间模型
堆有两个等大的半空间，每半容量为 H 字节。程序只在当前一半顺序分配；收集时它成为 from-space，另一半成为 to-space。收集全程暂停程序，根位置理路运行时根与堆可达性Runtime roots and heap reachability · GC root set · Heap object graph从可改写的根槽和有身份的指针字段建立具体堆图，说明哪些不可达对象可安全删除，以及可达为何不等于未来必用。完整且可写，对象指针均为基址，没有未登记外部引用、弱引用或终结器。
对象按描述符理路堆对象布局与分配Heap object layout and allocation · Object descriptor · Bump-pointer allocation用对象头、字段偏移与指针描述符规定可扫描的堆布局，并给出带溢出检查和初始化约束的顺序分配器。给出大小和指针槽。新对象先完整复制原头与字段；旧对象头随后改成带标签的转发地址。转发头与描述符头必须可区分。例如原描述符地址低位为 0，利用对齐空出的低位将转发地址标记为 1；解码时恢复原新地址。整数和代码字段不作此解释。
to-space 有三个区间，scan 与 free 都落在对象边界：[base,scan) 已扫描，[scan,free) 已复制但尚未扫描，[free,limit) 未使用。中间这段对象本身就是队列，因此 Cheney 算法不另建递归遍历栈。
先定义唯一的转发操作
text
forward(p):
if p == null: return null
require p is an object base in from-space
if header(p) is Forward(q): return q
d = descriptor(p)
s = d.size
require s <= to_limit - free
q = free
copy s bytes from p to q
free = free + s
header(p) = Forward(q)
return q
collect(root_slots):
scan = free = to_base
for each root slot s:
value(s) = forward(value(s))
while scan < free:
d = descriptor(scan)
for each managed pointer field slot f of object scan:
value(f) = forward(value(f))
scan = scan + d.size
make to-space the active allocation space
next = free
discard all contents of old from-space1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
本版每个 to-space 字段只扫描一次，扫描前它仍含从旧对象复制来的 from-space 地址；已扫描的根槽也不再重复扫描。同一值可出现在许多不同槽中，它们都调用 forward 并由旧头查到相同新址。根槽列表本身应去除同一物理位置的重复项，或者让实现显式允许输入已经位于 to-space 的地址；本文采用前者，避免第二次把已改写槽误认作非法 from-space 输入。
等容量半空间中，复制总量不超过收集前已使用量，而后者不超过 H，所以合法堆的本次复制能装下。完成后新请求大小 s 仍须检查 live_bytes+s≤H，不满足就报告内存不足。若使用更小的目标区，必须预先证明装得下或提供可靠失败协议；已经改写根与转发头后，不能简单“取消”并恢复旧程序。
直觉
复制式回收让活对象搬到一块连续空间，再整体丢弃旧空间。搬家时最容易出错的不是字节复制，而是同一个旧对象只能有一个新家，所有仍要使用它的引用都必须指向那里。两个计数器闭包共享的单元如果被复制两次，程序的状态共享就被拆开了。
例子与边界
四轮扫描算到 2072
使用计数器快照。from-space 起点 1000；对象依次为 C(16字节)、Ei(16)、A(24)、Ep(16)、B(24)、P(24)、U(16)，总量 136。根槽顺序固定为 main.b=B@1072，随后 inc.env=Ei@1016。B 指 Ep，Ei、Ep 同指 C，C 内为整数 7。
to-space 从 2000 开始。处理根后，B 复制到 2000，占 [2000,2024)；Ei 复制到 2024，占 [2024,2040)。此时 scan=2000, free=2040，两个根槽已经分别改为 2000 与 2024。
| 扫描对象 | 处理的指针字段 | 新动作 | 扫描后 scan | free |
|---|---|---|---|---|
| B@2000 | env=1056 | 复制 Ep 到 2040，改 env | 2024 | 2056 |
| Ei@2024 | cell=1000 | 复制 C 到 2056，改 cell | 2040 | 2072 |
| Ep@2040 | cell=1000 | 查转发，改为已有 2056 | 2056 | 2072 |
| C@2056 | 无指针字段 | 不解释整数 7 | 2072 | 2072 |
扫描结束，存活映射为
只复制 72 字节，A、P、U 从未遇到，旧空间整体弃用时一并消失。Ei 的 +8 字段与 Ep 的 +8 字段都保存 2056；闭包的代码地址原样保留。根槽从“旧址仍在”变为“新址可用”，正是对象移动而行为不变的接口。
环与错误变体
给一个对象 X 的指针字段写 X 自身，并让根指 X。第一次 forward 建立 X′ 并立刻在 X 写转发头；扫描 X′ 的字段时再次遇 X，直接得到 X′，于是新对象仍自指。若等扫描全部子对象后才安装转发地址，会在自环上无限递归或反复复制。
两个环境若分别复制 C 且不查转发，会得到 C₁、C₂。复制刚结束时两者都为 7，单次 peek 甚至可能看不出错误；再经 inc 把 C₁ 改成 10，peek 从 C₂ 仍读 7，才暴露共享丢失。测试应继续执行可变状态操作，不能只比较 GC 刚结束时的数值。
另一个错误只改根而不改堆字段。B′ 仍指旧 Ep，旧空间复用后就悬空。反过来，只改堆字段而漏改 main 的根槽，也会在返回调用者时读取旧 B。已死亡的位模式可以留在不再读取的槽里；以后还要用的指针副本必须改写或弃用后从已改写位置重载。
推论与应用
三个不变量保证不会拆散对象图
第一，每个带转发头的旧对象恰好对应一个已分配的新对象；只有首次访问才推进 free，之后都返回同一地址。因此映射 f 是单射，不同旧对象不会挤在同一区间，同一个旧对象不会产生两个副本。
第二，[base,scan) 内全部受管理指针已指向对应的新对象，[scan,free) 中的对象内容已经复制，字段待修正。扫描一个对象时，对其每个非空字段执行 forward，既修正边，又把尚未遇见的目标加入队尾。处理完后推进 scan，两个区间的含义保持。
第三，所有改写后的根指向对应新对象，任何已经发现对象的未完成出边都在待扫描区中等待处理。每轮至少完成一个正大小对象，每个旧对象至多复制一次，有限堆保证终止。scan=free 时没有待修正字段，所以对任一活字段 o.field=p，新堆满足 f(o).field=f(p)。再结合根对应与普通整数、代码字段不变，图结构与共享可变状态得以保留。
成本与迁移
设根槽数为 r、存活对象总字节为 L、其中指针字段数为 E_L。若复制一个字节计常数，收集工作为 O(r+L+E_L)，在定宽字段模型下可写 O(r+L)。不扫描全部死亡对象是它与原址清扫理路标记清扫垃圾回收Mark-sweep garbage collection · Mark-and-sweep · 标记清除先从全部根标记可达对象，再遍历已分配对象释放未标记者；对象不搬家，但清扫与碎片都有成本。的重要区别。额外的遍历队列为常数个指针，但保留两个半空间本身需要 2H 容量，不能据此称总额外空间为常数。
复制结束后有效空闲区连续，外部碎片得到消除；搬动全部活数据也带来带宽和暂停成本。活集接近 H 时，每次只腾出少量空间，频繁收集可能很贵。单次线性成本不等于每次分配都只付常数代价。
迁移题：在主例再加一个不同根槽 alias=B。它应与 main.b 都变为 2000，复制量仍为 72 字节。再把 root_slots 的顺序倒过来，新地址顺序可能变化，但活对象数量、整数结果和“两个环境指向同一个 C”的关系必须不变；不能把一种遍历顺序的地址当作语义保证。
分代回收理路分代回收与写屏障Generational garbage collection · Remembered set · Generational write barrier在双代停止世界模型中维护老到幼的槽记忆集，用幼代局部跟踪保持全堆可达对象，并核对提升和失败协议。把本页复制算法限制在幼代，但必须额外登记每个老→幼入口槽，扫描并改写它们。只换成较小的幼代空间而忽略跨代槽，会在根仍能经老对象到达幼对象时误删活对象；提升产生的新跨代边同样需要登记。
参考资料
[1] C. J. Cheney，A Nonrecursive List Compacting Algorithm，CACM 13(11)，1970，677–678，非递归复制收集的原始算法。
[2] Andrew Myers，Cornell CS 4120/5120，Memory Management and Garbage Collection，§8 “Copying collection”，尤其页 6–7 的扫描边界与转发讨论。本文以此核对算法，使用自己的根槽与地址算例。