Paging 问题

缓存满时，在线策略必须为一个尚未知晓的未来选择牺牲哪一页；命中虽不付成本，却会改变 LRU 等策略对页面新鲜度的内部状态。离线 Belady 把未来最晚使用作为答案，只承担基准角色，不能成为在线淘汰动作的隐含信息。

系统边界 ​

现实缓存还有写回、预取、非均匀页面和不同容量。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 的竞争分析公理库竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。 ​

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

相邻 phases 的并集至少含 $k+1$ 个不同页，OPT 即使跨边界安排，也至少在相应跨度内 fault 一次。对全部 phase 求和可得

这是一项总成本比较，不表示每段或每次淘汰都与 Belady 对齐。

现实扩展边界 ​

脏页写回、预取和不同页面成本产生 weighted caching 等变体。LRU 的 stack property 也依相同请求序列与标准单位页模型；换成带费用或可变大小对象后，需要新的算法与竞争分析。随机化版本可从标记算法公理库分页的随机 Marking 算法randomized marking algorithm · Marking paging按 phase 标记请求页，并从未标记缓存页中随机淘汰，以调和数期望竞争比处理分页。继续阅读，但其对手模型与期望量词必须单独声明。