“本页与增量强边标记是两个独立执行模型。前者冻结堆并精确求条件闭包；后者允许强边变化并容许浮动垃圾。把弱槽、条件记录塞进后者，必须重新设计阶段与屏障，不能由两篇各自正确就推出联合收集器正确。”
形式陈述
把暂停分成哪些步骤
标记清扫理路标记清扫垃圾回收Mark-sweep garbage collection · Mark-and-sweep · 标记清除先从全部根标记可达对象，再遍历已分配对象释放未标记者；对象不搬家，但清扫与碎片都有成本。在停止世界的堆上沿强边遍历。本页保留原址对象和最后清扫，把中间标记拆成小步，让执行程序的 mutator 在这些步骤之间继续更新堆。这里的“增量”指分次完成标记：只有一个执行线程，一次 mutator 命令或一次收集步骤运行到底，期间不插入另一方操作。没有多核内存序、并发释放、弱引用、终结器或对象复活。
堆 null。ID 是观察标签，不是造引用的权限：程序取指针必须提交一条从已登记根开始的有限字段路径。store(base_path,i,value_path) 在同一原子命令中先读两条路径，再写目标槽；源路径可以直接是 B.child，不在命令之间留下未登记临时值。空路径值参数 None 表示写空，不表示任意对象。
一轮开始时暂停程序，把已有对象设白、扫描所有根并将白根染灰。每个灰对象带游标
四个完整操作
内部操作 shade(p) 遇白对象才把它改灰、入队一次；空、灰、黑都不改。字段及根的发布遵守以下规则。
text
store(base, slot, source):
在当前堆中沿两条登记根路径求出 x 和 p，验证槽合法
shade(p)
H[x][slot] = p
root_store(slot, source):
沿登记根路径求出 p，验证根槽合法
shade(p)
roots[slot] = p
mark_step():
若灰队列为空，返回“没有标记工作”
x = 队首；i = cursor[x]
若 i < 字段数：shade(H[x][i])；cursor[x] += 1
若游标到末尾：将 x 改黑并出队1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
写屏障是发布新边前的 shade。它不只检查黑色源：本版对每次指针字段写入都执行，包括写入灰对象已扫描的字段。清空槽不会染灰任何对象。旧目标已经染灰或染黑时也不回白，删除引用不撤销标记。
第四个操作是分配：验证新 ID 和根槽，建立指定数量的全空字段，把新对象设黑并立即发布到该根槽；初始化和发布之间不允许收集。以后填非空字段仍走 store。本页不从本轮白对象中挑选“空闲块”，新 ID 必须不在当前堆中。已经完成回收的名字以后可以重新分配，因为裸 ID 不能作为读写入口。分配失败或非法路径应在改变逻辑状态前拒绝；参考程序的输入检查如此处理，实际内存耗尽的恢复策略不在模型内。
当灰队列为空时，暂停程序，遍历当前对象表并释放仍白的对象，才结束本轮。初始清标、根扫描和最终清扫仍是停止世界操作；这里没有给出固定暂停上界。
直觉
收集器像拿着清单检查房间。程序可能在检查完 A 后，把一个物品从还没检查的 B 搬到 A；等检查 B 时，旧位置已经空了。仅记住“我检查过 A”会漏掉这个物品。插入屏障让搬运者同时补一张待查单。
一个大对象也像有多个抽屉的房间。对象还灰，不代表所有字段都将在未来重读：游标左侧已经检查过。因而正确性需要记住已扫描前缀，而不能只背一句“黑色不能指白色”。
例子与边界
将 C 从 B 搬到已经扫描的 A
初始根依次指 A、B。字段为 A=[null]、B=[C]，C 和无根 U 都没有字段。开始后 A、B 灰，C、U 白，队列 [A,B]。
| 动作 | A / B / C | 灰队列 | 关键边 |
|---|---|---|---|
| 扫 A 的字段并完成 A | 黑 / 灰 / 白 | B | B→C |
A[0] := B[0] |
黑 / 灰 / 灰 | B,C | A→C，B→C |
B[0] := null |
黑 / 灰 / 灰 | B,C | 只剩 A→C |
| 扫 B 并完成 | 黑 / 黑 / 灰 | C | A→C |
| 完成零字段 C | 黑 / 黑 / 黑 | 空 | A→C |
清扫只释放 U。没有字段屏障的版本不把 C 放入队列，B 随后又变空，于是清扫释放 C，A 留下悬空字段。全过程每次取值都来自合法根路径，问题不能归咎于伪造 ID 或漏登记临时引用。
灰对象的已扫描前缀
把 A 改成 [null,null]。第一次 mark_step 只处理字段 0，A 仍灰，游标为 1，队列仍以 A 开头。现在执行同样的 A[0]:=B[0]、B[0]:=null。若屏障只在源对象为黑时运行，C 不会染灰。随后收集器只读 A 的字段 1，再读已清空的 B，C 同样被误删。
本版无条件对新目标 shade 后，C 入队，A 的已扫前缀保持安全。这是实际扫描粒度带来的义务；若另一算法原子扫描整个对象，就应重新按其原子边界证明，而不是机械移用本页反例。
浮动垃圾不是误删
标记期间分配黑对象 Fresh，把它放入一个根，然后清空该根。Fresh 已不可达，但本轮不会重新变白，所以被保留；没有再次引用它时，下轮重新从白开始，便会释放它。删除普通已标记对象的最后一条入口也可能产生这种“本轮多留、下轮再判”的浮动垃圾。
因此输出保证是“清扫时可达集包含在保留集内”，不是“保留集恰好等于本轮开始的可达集”，也不是“恰好等于本轮结束的可达集”。若 mutator 根本不给收集器运行机会，本算法也不承诺完成一轮。
推论与应用
为什么前缀不变量足够
每个步骤边界保持三项性质：根没有白目标；黑对象所有字段没有白目标；灰对象已扫描前缀没有白目标。队列恰好包含灰对象，各对象至多入队一次。初始化时只有根被染灰、前缀为空，因此成立。
扫描一步先染灰当前字段目标，再推进前缀；最后一个字段完成后，整个前缀覆盖所有字段，转黑安全。写字段先染灰新目标，所以无论写到未扫后缀、已扫前缀还是黑对象，都不破坏性质。写根也先染灰；全空新黑对象没有白出边。各操作都不把灰或黑改白。
队列为空时没有灰对象，根均黑，沿任意强边从黑对象仍到黑对象。对路径长度归纳，当前所有可达对象都黑，释放白对象因而安全。这个证明不要求保存所有曾经可达的对象，也没有把“新边只指向已经可达者”误写成“新边只能指向已经标记者”：主例的 C 在写入前可达却仍白。
设一轮开始有
费用与两个不同的屏障目标
采用定长 ID、散列表期望常数操作模型。设本轮新对象数为
颜色、游标与灰队列额外空间为 mark_step 为期望常数工作，分配有 invariant、reachable 和完整快照会扫描堆或复制状态，不能算作常数步骤的一部分；总测试时间还应加入这些诊断的实际工作与日志字节。
分代写屏障理路分代回收与写屏障Generational garbage collection · Remembered set · Generational write barrier在双代停止世界模型中维护老到幼的槽记忆集，用幼代局部跟踪保持全堆可达对象，并核对提升和失败协议。记录老→幼入口槽，解决“只扫描幼代时如何进入”的问题；本页屏障染灰新目标，解决“标记观察与写入交错时如何不漏”的问题。一个运行时可以同时需要两者，但正确实现须分别保持两种不变量。
终点见变化的强边与有条件保留，配套标准库参考程序。迁移时保留两步 B.child→A.field 与清旧槽，再改变 A 的字段数、游标位置或增添共享根；交付各步颜色与最终悬空边检查，不能只检查收集器是否正常返回。
参考资料
[1] E. W. Dijkstra、Leslie Lamport、A. J. Martin、C. S. Scholten、E. F. M. Steffens，On-the-fly garbage collection: an exercise in cooperation，CACM 21(11)，1978，966–975，EWD630 §4 的 M1、P1 与队列实现注3。本页使用插入染灰思路，另证明逐字段游标、新黑分配和停止世界清扫的单线程模型；原文 §5 的细粒度并发协议不在此实现中。