“标记清扫会在全根跟踪中回收这个环；普通 RC 不会。自环 X.next=X 也会在最后一个根离开后保持 rc(X)=1。若 X 还指向一个尾链 X→Z→W，Z、W 虽不在环上，也可能被环的出…”
形式陈述
算法接受什么状态
输入是一份停止世界的堆快照：已分配对象表 H、精确根槽集合 S、每个对象的大小和指针字段描述符，以及可管理空闲区间的分配器。普通程序在标记和清扫全部结束前保持暂停。对象起始地址可以在常数期望时间的表查询中检验；这里不讨论保守指针猜测。
每个对象有一个收集器专用标记位，所有位初始为 0。工作队列保存“已经发现、尚未扫描完字段”的对象。对象表包含所有已分配对象，包括不可达对象；清扫不能只遍历标记队列，因为队列恰好没有那些需要释放的对象。这里释放的是本次执行中的物理存储，不是抽象GC从静态分析状态删除旧事实。
text
discover(p):
if p == null: return
require p is an allocated object base
if mark[p] == 0:
mark[p] = 1
work.push(p)
mark_phase:
work = empty queue
for each root slot s: discover(value(s))
while work is not empty:
p = work.pop()
for each managed pointer field slot f in object p:
discover(value(f))
sweep_phase:
for each object p in the original allocated-object list:
if mark[p] == 0:
s = size(p)
remove p from object table
return interval [p, p+s) to free-space manager
else:
mark[p] = 0删除对象表项前读取对象大小；若空闲表复用对象头保存链接，更不能先覆盖头再找大小。原始对象列表可由旁表提供，也可通过保留大小的块头顺序遍历，本页采用旁表。遍历期间不得因删除当前项而跳过下一对象。
先标记再入队保证重复边和环不会造成重复入队。队列空间不够、出现非法指针或描述符不一致时，禁止继续清扫；未完成的标记不构成释放证据。实现可以扩大工作区或报告运行时失败，但不能把队列中“还没处理”的对象当垃圾。
直觉
标记清扫把两个问题分开：先回答哪些对象必须留下，再把其他对象的地址区间交回分配器。与复制式回收不同，它不移动活对象，所以活指针的地址保持不变；代价是死亡对象之间留下的洞未必能满足下一次较大的分配。
例子与边界
一次完整的标记与清扫
复用计数器快照：根按顺序为 main.b=B、inc.env=Ei。B 指 Ep，Ei 与 Ep 同指 C。不可达对象有 A、P、U；其中 A 指 Ei，P 指 A、B，但从不可达对象向活对象的边不会让起点反向变活。
选择先进先出的工作队列，手算如下。
| 操作完成后 | 队列 | 已扫描完 |
|---|---|---|
| 发现两个根 | B，Ei | 空 |
| 扫描 B，发现 Ep | Ei，Ep | B |
| 扫描 Ei，发现 C | Ep，C | B，Ei |
| 扫描 Ep，C 已标记 | C | B，Ei，Ep |
| 扫描 C，无指针字段 | 空 | B，Ei，Ep，C |
清扫按地址顺序看 C、Ei、A、Ep、B、P、U，保留 C、Ei、Ep、B，释放 A、P、U。沿用布局页地址，释放区间先为 [1032,1056)、[1096,1120)、[1120,1136)；合并相邻后得到 24 字节与 40 字节的两个洞，共 64 字节。活对象仍在原地址，Ei.cell 与 Ep.cell 仍都等于 1000。
现在申请一个 48 字节的连续对象仍可能失败：24 和 40 各自都太小。总空闲 64 大于请求 48 并不够，除非分配器还能从其他区域取得空间或运行压缩算法。这是外部碎片的可复算例，不是标记错误。
推论与应用
不变量怎样给出安全性
把未标记者叫白，已入队未扫描完者叫灰，字段全部扫描完成者叫黑。灰与黑共享同一个标记位，队列和处理状态区分二者。每个已标记对象都沿根路径发现；处理一个灰对象时，先发现全部白色后继，再令该对象成为黑色，因此黑对象不指向白对象。
根扫描完成后，每条从根进入尚未发现区域的路径都必须经过一个灰对象。队列为空时灰色消失，路径不能从黑色跨到白色，所以所有根可达对象都已标记。反方向也成立：只有根对象及已发现对象的后继会被标记，所以标记集合恰为本次可达集合。清扫只释放白对象，结合根可达性安全引理，就不会删掉后续合法读取需要的旧对象。
这一论证依赖堆边在两阶段间不变。若程序同时运行，一个黑对象可能新写入指向白对象的边，直接破坏不变量。并发或增量版本需要屏障与额外证明；给这个停止世界算法加一个后台线程并不会自动得到正确并发 GC。
环、漏根与开销
另建 X.next=Y, Y.next=X，两者没有根路径。标记阶段不访问它们，清扫把整个环释放；不需要等某个入度先变成零。若给 X 一个根，先标记 X，再标记 Y，扫描 Y 时 X 已标记，队列终止，两者都保留。
若漏掉主例的 main.b，算法本身会忠实地只标记 Ei、C，并错误释放 B、Ep。循环不变量只能证明“相对输入根的可达性算对了”，不能替调用者证明根集合完整。根映射属于独立接口，必须和收集器一起验收。
设根槽数为 r，已分配对象数为 N，活对象数为 L，活对象指针字段数为 E_L。在上述旁表与常数时间对象查询模型下，标记期望需 O(r+L+E_L)，清扫需 O(N)，总计期望 O(r+N+E_L)；工作队列最坏 O(L)，标记旁表需 O(N)。若实现逐字扫描整片容量为 H 的堆，清扫应记 O(H)，不能换用对象表的界。
这些界不包括给空闲块排序、通用分配器搜索，以及按大小清零回收块。即使长期总成本可以摊还，一次全堆清扫仍可能造成长暂停；“不移动对象”不等于“没有暂停”。
迁移题：让 P 仍在一个根槽中，而不另存 B。此时 P 能到 A、B，随后到两个环境与 C，六个计数器对象全部存活，只有 U 被释放。写出从 P 开始的队列轨迹，说明 A 的代码已经执行过不是回收它的充分理由。
引用计数通过持续维护强引用槽的多重入度触发局部释放，与本页每轮从根向前标记不同。无根环的成员可各有正计数，普通 RC 因而保留环及可能的下游对象；本页完整根跟踪仍能将它们一起回收。
参考资料
[1] Andrew Myers，Cornell CS 4120/5120，Memory Management and Garbage Collection，§4 “Garbage collection via traversal”、§6 “Mark and sweep”、§1.2 “Freelist allocation”。三色遍历与清扫机制据此核对；对象表算法、地址账本和失败轨迹是本页明确模型下的展开。