Paging 问题

接口与基准 ​

作为在线算法公理库在线算法模型Online algorithm model输入逐步揭示，算法必须在未知未来时作出通常不可撤回的决策。，paging 的缓存最多放 (k) 页。请求命中成本 0；缺页则装入，并在已满时淘汰一页，成本 1。离线 Belady 淘汰未来最晚再使用的页面。

(k+1) 个页面循环会持续制造压力，但具体 fault 数依策略与初态；不能凭一个循环断言 LRU 等于 OPT。

系统边界 ​

现实缓存还有写回、预取、非均匀页面和不同容量。Resource augmentation 允许在线算法使用更大缓存，必须明确 ALG 与 OPT 两侧容量。Paging 研究在线淘汰策略；ideal-cache 模型通常假定最优替换来分析布局，问题不同。

FIFO 虽有同阶竞争界，却不具 stack property，可能出现 Belady anomaly：增大缓存反而增加 fault。相同竞争比不表示两种策略的缓存状态具有包含关系。

LRU 的状态轨迹 ​

容量 (k=3)，请求 a,b,c,a,d。前三次装满缓存，a 命中后最近性次序变为 a,c,b；请求 d 时 LRU 淘汰 b，缓存为 d,a,c。FIFO 不因 a 命中改变装入队列，会淘汰最早装入的 a。相同前缀已经让两种策略状态分叉。

对序列 a,b,c,d,a,b,c,d 循环，fault 数仍须从初态逐步计算。Belady 知道未来并淘汰下一次使用最晚者，只作为离线 OPT 基准，不是 LRU 每一步的隐含行为。

Phase 竞争证明 ​

把请求序列切成 maximal phases，每个 phase 至多出现 (k) 个不同页。LRU 在一 phase 内对每个新页至多 fault 一次，故每段成本不超过 (k)。

相邻 phases 的并集至少含 (k+1) 个不同页，OPT 即使跨边界安排，也至少在相应跨度内 fault 一次。对全部 phase 求和可得 [ \operatorname{LRU}\le k\operatorname{OPT}+O(k). ] 这是一项总成本比较，不表示每段或每次淘汰都与 Belady 对齐。

现实扩展边界 ​

脏页写回、预取和不同页面成本产生 weighted caching 等变体。LRU 的 stack property 也依相同请求序列与标准单位页模型；换成带费用或可变大小对象后，需要新的算法与竞争分析。

参考资料

• Sleator, Tarjan, 1985.
• Fiat et al., “Competitive Paging Algorithms,” J. Algorithms, 1991.