资源增广

在线策略不知道未来，因而可能淘汰下一刻正好需要的页；额外缓存让它可以保留更多候选。比较 $LR{U}_k$ 与 $OP{T}_h$ 问的是：较多空间能在多大程度上抵偿信息劣势。它不会证明同容量的 $LR{U}_k$ 也具有相同常数，因为 $OP{T}_k\le OP{T}_h$，把右侧基准换成 $OP{T}_k$ 会使要求更强。

证明的关键是找一段互不重叠的请求区间：在线每付 $k$ 次缺页，离线至少付 $k-h+1$ 次。多出的 $k-h$ 个槽并不保证每条短序列上在线更便宜，却能在每个完整计费块里提高离线必须承担的最低账单。

同一请求，两种容量 ​

令 $k=3,h=2$，两侧都从空缓存出发，请求为 $a,b,c,a,b,c$。LRU 栏按最近使用到最久未用排序；离线栏只表示集合。

离线在请求 $c$ 时淘汰 $b$，因为 $a$ 更早再被请求；请求 $b$ 时淘汰以后不再使用的 $a$。前三种页面至少各装入一次；服务第三次请求后，两槽不可能同时保存 $a,b,c$，而尾部还要逐个请求它们，所以还需至少一次缺页。表中四次达到此下界，确实是 $OP{T}_2$。LRU 的三次更少，但这个短例子只展示资源差异，不证明最坏竞争系数紧致。

不重叠缺页块的证明 ​

若 LRU 从不缺页，结论立即成立。否则先单独保留第一次 LRU 缺页；它之前的请求不计入后续块。此后按请求顺序，每累积恰好 $k$ 次 LRU 缺页就结束一个完整块，末尾可留下不足 $k$ 次缺页的尾块。完整块连续且互不重叠，命中请求也属于相应块。

固定一个完整块，令 $q$ 是块开始前刚服务的页。它此刻在两侧缓存中，而且是 LRU 最近使用的页。LRU 的基本不变量是：一个刚请求过的页，只有在其后出现至少 $k$ 个其他不同页面的请求，才会从 $k$ 槽缓存被淘汰。因此分以下情形：

1. 某页在块内两次导致 LRU 缺页。 两次之间为了淘汰它，必须请求至少 $k$ 个其他不同页；所以块内至少出现 $k+1$ 个不同页。
2. $q$ 在块内导致 LRU 缺页。 从块首前的最后一次请求 $q$ 到它被淘汰，同样必须经历至少 $k$ 个其他不同页；块内连同 $q$ 至少出现 $k+1$ 页。
3. 上述情形均不发生。 块中 $k$ 次 LRU 缺页对应 $k$ 个不同页，且都不是 $q$。

前两种情形里，OPT 开始时最多保存 $h$ 页，因此块内 $k+1$ 个不同页中至少 $k+1-h$ 个最初不在它的缓存，各自首次请求必然缺页。第三种情形里，OPT 初态的一个槽被 $q$ 占据，因而至多预存 $h-1$ 个这些缺页页；它仍至少要为 $k-(h-1)$ 个页付费。三种情形统一得到每个完整块

若完整块数为 $p$，第一次 LRU 缺页加尾块至多共 $k$ 次，于是

消去 $p$ 即得所述不等式。特别地，$q$ 不是额外收费的请求：它只用于确定块初态中已占据一个槽。所有下界收费都发生在完整块内部，所以没有将某次离线缺页同时计给左右相邻两块。若改用相邻两个“最多含 $k$ 个不同页”的阶段并计费，区间会重叠，必须另行处理，不能直接套用这份系数。

取 $h=k$ 恢复熟悉的 $k$-竞争界；取 $k=2h$ 得到 $2h/(h+1)<2$。例如离线 $h=4$、在线 $k=6$ 时，系数为 $6/(6-4+1)=2$；若双方都只有四槽，给出的系数则为 $4$。它们使用不同资源，不能把前者称为“四槽 LRU 的二竞争保证”。

更一般地，若 $k\ge \lceil (1+\epsilon )h\rceil$ 且 $\epsilon >0$，则

因而固定比例的容量冗余给出与 $h$ 无关的常数。常数仍依赖 $\epsilon$；把它趋于零，会失去这个统一界。

k-Server 问题公理库k-Server 问题k-server problem · k 服务器问题在度量空间中在线移动 k 台服务器响应请求，以总移动距离同预知未来的最优策略比较。在一致度量上对应分页，比较不同服务器数时同样要保留双方的资源下标；一般度量的移动成本不能直接套用本页的缺页分块论证。在线模型公理库在线算法模型Online algorithm model输入逐步揭示，算法必须在未知未来时作出通常不可撤回的决策。中的预测、额外信息与提前揭示请求，也不是缓存增广的同义词。可以用本页作自测：复算六次请求，指出三个分块情形中的初始页 $q$ 各起什么作用，再说明为什么增广界不能推出同容量的常数界。