Knuth GC栈溢出预防算法工作原理相关技术问询

存疑语句准确翻译 #

因此，标记流程完成前栈就可能变空，因为那些指针在标记栈中被覆盖的节点，其下属的存活对象图可能还没完成标记。

机制运行逻辑 #

首先先明确标记阶段辅助栈的基础作用：存储已完成自身标记、但还未遍历其子引用字段的对象指针。常规标记流程为：

• 从GC根节点出发，给所有根引用的对象打标记，压入辅助栈
• 循环弹出栈顶节点，遍历该节点的所有引用字段，给未标记的子对象打标记后压入栈
• 栈为空时默认标记完成

Knuth提出的固定大小循环栈溢出处理规则为：
栈大小固定为h，新指针压入时，栈下标按(当前下标 + 1) % h计算，栈满时新条目直接覆盖最早入栈的旧条目，不会触发报错或扩容。

提前空栈的原因 #

你疑惑的核心是为什么栈不会一直保持<=h的条目，核心原因是被覆盖的旧条目相当于直接从栈中丢失了，不会参与后续的弹出处理流程，举个简单例子：

• 假设栈大小h=2，先后压入节点A、B，此时栈满
• 新增节点C要压入，按模2规则覆盖最早入栈的A，当前栈有效条目为B、C
• 开始弹栈处理：先弹出C，遍历完C的所有子节点并压入相关新节点后，栈剩余B
• 再弹出B处理完成，栈剩余0个条目，此时栈已经空了
• 但最早被覆盖的节点A从未被弹出处理，它的所有子引用都还没被遍历、标记，标记流程实际未完成

简单来说：栈的弹出逻辑是正常消耗现存条目的，被覆盖的旧条目不会再被计入栈的有效内容，所以当所有现存条目都被处理完后，栈自然会变空，和有没有丢失未处理的旧条目无关。

补充说明 #

这种循环栈设计不会真的把栈空当成标记完成的信号，栈空后会触发一次全堆扫描，找到所有「已标记、但未处理子引用」的节点重新压栈继续标记，直到没有遗漏节点为止，牺牲部分扫描性能来避免栈溢出风险。

内容的提问来源于stack exchange，提问作者Chlebik