分页的随机 Marking 算法

算法与 phase ​

在分页问题公理库Paging 问题Paging problem在容量 k 的缓存中在线服务页面请求，并以缺页次数计成本。中，缓存容量为 $k$。一 phase 从所有标记清空开始，持续到请求将引入第 $k+1$ 个不同页之前；请求某页后把它标记。若 miss 且缓存未满就装入；若已满，从当前缓存中均匀选择一个未标记页淘汰。由于当前 phase 至多出现 $k$ 个不同页，发生 miss 时总有未标记受害者。

Clean 与 stale 分析 ​

本 phase 未在上一 phase 出现的页称 clean；上一 phase 出现但本 phase 尚未请求的页称 stale。clean 页首次请求必导致算法 fault，也迫使任意离线最优在相邻 phases 的并上付出一定成本。每出现一个 clean 页，随机淘汰会使 remaining stale 页被逐步污染；第 $j$ 次相关请求的 fault 概率形成

$$1+\frac{1}{2}+\cdots +\frac{1}{k}=H_k$$

型和。精确配对可得期望 $O(H_k)$-competitive，标准版本达到 $H_k$ 量级。

一 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 下界。

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

参考资料

• Amos Fiat et al., Competitive Paging Algorithms, Journal of Algorithms, 1991.
• Allan Borodin, Ran El-Yaniv, Online Computation and Competitive Analysis, 1998.