分页的随机 Marking 算法

标记保护本 phase 已请求的页，只在尚未请求的旧页之间随机淘汰。随着 stale 页逐个被请求，仍可能被淘汰的对称候选数不断减少，fault 概率形成调和和；clean 页则连接相邻 phases，并为 OPT 提供不可避免的下界。

一 phase 图像 ​

缓存含上一 phase 的 $k$ 页。新 phase 首次请求一个 clean 页时随机淘汰某个未标记旧页；若该旧页稍后被请求就 fault 并再随机淘汰。随着页被请求并标记，可淘汰集合缩小，调和概率由此出现，而不是每次都在全部缓存中随机。

对手边界 ​

上述保证针对 oblivious adversary，即先固定请求序列，再对算法随机性取期望。若对手观察缓存后专门请求刚被淘汰的页，就会破坏 stale 页的对称性。$H_k$ 随 $k$ 以对数量级增长，所以这里的竞争比随缓存容量变化。

OPT 下界与 phase 衔接 ​

第 $i$ 阶段有 ${\ell }_i$ 个 clean 页时，它与前一阶段共请求了 $k+{\ell }_i$ 个不同页。OPT 在这两阶段开始时最多已缓存 $k$ 个，因此至少缺页 ${\ell }_i$ 次。把这些相邻阶段的不等式相加，每次 OPT 缺页至多被计算两次，故 $\sum _{i\ge 2}{\ell }_i\le 2OPT$。首阶段算法至多缺页 $k$ 次，由此得到

所有页都 marked 时不应立即随机淘汰 marked 页，而应在下一次将出现新 distinct 页时结束 phase、清标记，再按未标记规则处理。实现边界错一请求会破坏 clean/stale 定义。

一阶段缓存怎样变化 ​

设 $k=3$，新 phase 请求依次为 a,b,c,b,d。前三个不同页被标记；第二次 b 命中且仍保持标记。请求 d 会开启下一 phase，而不是在已有三个标记页中强行找“未标记页”淘汰；清空标记后再处理 d，算法不变量才成立。

随机抽样的候选集合应恰好是当前未标记的缓存页。最直接实现逐请求扫描至多 $k$ 个槽，维护命中与标记，缺页时列出候选并均匀抽样；长度 $T$ 的序列共用 $O((T+1)k)$ 次基本操作和 $O(k)$ 个页标识与标记。这个成本按页标识比较与抽取一个均匀候选为单位操作；若只有公平随机位，可用拒绝采样实现候选抽取，并另计随机位与预期抽样成本。输入结束后输出最终缓存及缺页账单；竞争比分析的是缺页数，独立于这些内部处理费用。