分页的随机 Marking 算法

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

一 phase 图像 ​

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

对手边界 ​

随机竞争保证通常针对 oblivious adversary，即请求序列不根据本轮随机淘汰结果调整。能观察缓存再选下一请求的 adaptive 对手可专门请求刚被淘汰页，破坏分析。$H_k$ 随 $k$ 增长，不是常数。phase 边界、命中是否标记、何时清空都属于不变量。

OPT 下界与 phase 衔接 ​

相邻两个 phases 的并含至少 $k+1$ 个不同页：新 phase 的第一个 clean 页正是触发边界的页。容量 $k$ 的 OPT 在这段请求中至少 fault 一次。更精细分析把每 phase clean 页数 $\ell$ 与 OPT fault 配对，算法期望 fault 为 $O(\ell H_k)$，从而得到调和竞争比。

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

一阶段缓存怎样变化 ​

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

分析把当前 phase 首次出现、且上一 phase 未出现的页称 clean，其余首次出现页称 stale。每个 clean 请求必 miss；stale 页在到来前是否已被随机淘汰，由尚未请求的 stale 页之间对称性控制，调和和由此出现。对 oblivious 对手，期望 fault 数是 $O(H_k)$ 倍 OPT 的 phase 下界。

若对手能看到每次随机淘汰结果后自适应选择下一请求，对称性可能被破坏，保证模型必须另写。随机数也应在未标记缓存页上均匀抽取，按物理槽编号但未过滤标记会产生非法淘汰。