Paging 问题

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

系统边界 ​

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

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

LRU 的状态轨迹 ​

容量 $k=3$，初始缓存为空，依次请求 a,b,c,a,d。下表按“最近使用到最久未用”排列 LRU 缓存；命中虽不收费，仍改变次序。

FIFO 按装入顺序淘汰，a 的命中不更新队列，因此最后一步淘汰 a。这段前缀中两者都缺页四次，状态却已不同：下一请求若是 a，LRU 命中而 FIFO 缺页；若是 b，结果相反。只比较一个前缀的总缺页数，不能推断后续行为相同。

对 a,b,c,d 的反复循环，容量三的 LRU 从空缓存开始每次都缺页；离线策略可以按未来访问次序保留更有用的页。循环压力并不意味着两者成本相同。

按缺页分段的竞争分析理路竞争分析Competitive analysis在同一请求序列上比较在线算法总成本与预知未来的离线最优。 ​

证明 $k$-竞争界时，分段的边界必须避免重复计算同一次 OPT 缺页。先把 LRU 的第一次缺页单独留下；此后从它刚服务完的位置开始，每累计 $k$ 次 LRU 缺页就结束一段。除最后不足 $k$ 次的尾段外，每段恰有 $k$ 次 LRU 缺页。

设一段开始前刚请求的页面为 $q$，它此刻同时在 LRU 与 OPT 缓存中。若该段中某页两次让 LRU 缺页，两次请求之间必有至少 $k$ 个其他不同页面被请求，才能把它从 LRU 淘汰。因此本段涉及至少 $k+1$ 页，OPT 不可能全程命中。

若本段的 $k$ 次缺页分别属于不同页面，则分两种情况：它们包括 $q$ 时，要使初始在缓存中的 $q$ 被淘汰，段内已经请求过至少 $k$ 个其他页面；它们不包括 $q$ 时，OPT 从含 $q$ 的缓存出发，也装不下这 $k$ 个缺页页面。两种情况都迫使 OPT 在本段至少缺页一次。

各完整段互不重叠，故这次计费不会重复。若有 $p$ 个完整段，加上第一次缺页与尾段，得到

另一种常见分段是“每段最多 $k$ 个不同页”；它能解释 LRU 每段至多缺页 $k$ 次，但仅说相邻两段有 $k+1$ 页还不够推出上述系数，因为相邻区间重叠，必须额外处理计费。

现实扩展边界 ​

脏页写回、预取和不同页面成本产生 weighted caching 等变体。LRU 的 stack property 也依相同请求序列与标准单位页模型；换成带费用或可变大小对象后，需要新的算法与竞争分析。随机标记算法理路分页的随机 Marking 算法randomized marking algorithm · Marking paging按 phase 标记请求页，并从未标记缓存页中随机淘汰，以调和数期望竞争比处理分页。是这一单位页接口的具体实现：保护本阶段已请求页，缺页时从未标记缓存页均匀选择淘汰者；其期望竞争保证针对预先固定请求序列的对手。

把缓存页视为服务器位置、不同页面间距离设为 $1$，每次缺页的淘汰装入就是移动一台服务器。因此本模型也是k-Server 问题理路k-Server 问题k-server problem · k 服务器问题在度量空间中在线移动 k 台服务器响应请求，以总移动距离同预知未来的最优策略比较。在一致度量、互异缓存位置与需求式服务下的特例。空槽可填入永不请求的互异虚拟页，保留装入成本。