动机
阶段(phase)论证可以给出标记类算法一个简单的 竞争界。该论证把每次离线缺页至多计入两个相邻的阶段对,因此有意留下了一段差距。最近最少使用(LRU)分页算法有更精确的保证:在初始缓存相同的条件下,离线算法每缺页一次,LRU 至多缺页 次。
证明的做法是在每次请求之后比较两个缓存。仅仅统计两者不同的页面个数,不足以说明一次命中如何改变 LRU 的新近程度顺序。加权势函数则同时记录两件事:哪些在线页面不在离线缓存中,以及每个这样的页面最近被使用的程度。权重的取法使得 LRU 的每次缺页都能通过势函数的下降来自行抵偿。
定义
定义 7.4.1
(与离线调度比较的按需分页)
页面全集可以是有限集或无限集,两个缓存的容量均为 。两者从相同的 个页面开始;LRU 另外给定一个固定的初始新近程度顺序。命中的代价为零。缺页时,被请求的页面被载入,同时逐出一个已缓存的页面,代价为一。离线调度知道整个有限的请求序列,但和 LRU 一样,只在处理缺页时才改变缓存。这一按需分页(demand paging)模型包含了本问题的离线最优解。
定义 7.4.2
(LRU 缓存与新近排名)
记 为 LRU 的缓存, 为离线缓存。将 中的页面排名:最近使用的为第 位,最久未使用的为第 位。一次请求把所请求的页面移到第一位,位于其前的页面各向后移一位。缺页时,LRU 逐出第 位的页面,并把被请求的页面插入第一位。
定义 7.4.3
(按新近程度加权的势函数)
定义非负的势函数
最近使用的在线页面权重为 ,最久未使用的权重为一。一个页面只有在属于 LRU 的缓存而不属于离线缓存时才产生贡献。初始缓存相同时,势函数为零。
定理
定理 7.4.4
(LRU 是 k-竞争的)
对于每个有限请求序列,以及每个初始缓存相同的离线按需分页调度,LRU 的缺页次数至多是该调度缺页次数的 倍。特别地,。
定理 7.4.5
(确定性算法中的精确性)
任何确定性在线分页算法的竞争比都不可能严格小于 ,即使允许加上一个与请求序列无关的加性常数。因此,在此模型中,LRU 定理中的因子 对确定性算法而言是最优的。
证明
先计入离线步骤
证明
(先计离线一步,再计 LRU 一步)
把每个请求分成两个概念上的步骤来处理。先让离线调度处理该请求,同时保持 LRU 的缓存和排名不变;再让 LRU 处理该请求,同时保持更新后的离线缓存不变。这只是记账的顺序;两个调度仍然相互独立,且面对同一个请求。
如果离线步骤是命中,则两个缓存和势函数都不变。如果是缺页,则被请求的页面进入 ,并且至多有一个页面离开 。把一个页面加入 只可能去掉势函数中的一项。把一个页面从 中移出至多增加一项,该项的权重至多为 。因此一次离线缺页使 至多增加 。这一步之后,被请求的页面属于 。
现在考虑 LRU 步骤。如果该请求在 中命中,则其页面在 中,不贡献任何项。把它移到第一位,会使另一些页面各向后移一位,它们的权重各减一,其余权重不变。势函数不会增加;LRU 的代价为零。
如果 LRU 缺页,则被请求的页面在 中但不在 中。LRU 逐出其第 位的页面 ,再把被请求的页面插入第一位。若 ,则被移除的那一项权重为一。若 ,由于两个缓存大小相等,且被请求的页面属于 ,故必有某个页面属于 。该页面不是 ,并向后移一位,权重减一。无论哪种情形,新插入的被请求页面贡献为零,其他项都不增加, 至少减少一。这一减少抵偿了 LRU 的一次缺页。
设 分别为第 个请求上的两个缺页指示量, 为两个概念步骤合起来的势函数总变化量。上述各种情形给出
对整个序列求和,势函数的变化量相互抵消(裂项求和)。初始势函数为零,最终势函数非负。因此 LRU 的总缺页次数至多是离线总缺页次数的 倍。由于该离线调度是任意的,取一个最优调度即得定理。
证明透视
为什么 LRU 缺页会使势函数下降
如果被逐出的页面不在离线缓存中,则它那一项权重为一,随之消失。否则,被请求的页面是仅在离线缓存中的页面,缓存大小相等就迫使存在另一个仅在线的页面;该页面的新近程度降低一位,权重减少一个单位。
确定性下界的证明
证明
(缺页对手与阶段)
配套的分页章节针对任意确定性在线算法构造了一个由 个页面组成的请求序列:每次都请求当前缓存中缺失的那个页面。于是在线算法对全部 个请求都缺页。把由此得到的固定序列划分成每段至多含 个不同页面的阶段,就得到一个代价至多为 的离线调度:第一个阶段之后,相邻阶段的页面集合至多相差一个页面。
因此,对任意 和固定的加性常数 ,当 足够大时,不等式 不成立。算法和 一旦给定,该构造就是确定的。它证明了没有确定性算法能有更小的竞争比,而势函数的证明则说明 LRU 达到了 。
例题详解
例题 7.4.6
(两次请求、一次离线缺页)
设 ,初始时两个缓存都含有 ,对 LRU 而言 最近使用。请求 。假设离线逐出 ,而 LRU 逐出 。两者都缺页。新的缓存是 和 ,LRU 的顺序为 。只有 有贡献,它位于第二位,所以 。接着请求 。离线命中;LRU 缺页并逐出 ,势函数降为零。LRU 缺页两次,离线调度缺页一次,恰好达到因子二的界。
例题 7.4.7
(离线缺页可能使势函数增加)
设 ,两个缓存初始时一致,LRU 的顺序为 。请求为 。若离线先逐出 ,则保持不变的 LRU 缓存含有 而离线缓存不含,于是势函数从零升到三。随后 LRU 缺页,逐出 并插入 ,这个势函数降为二。离线造成的增加至多为 ,与证明所允许的完全一致。
例题 7.4.8
(LRU 命中不一定改变势函数)
设 ,,LRU 的顺序为 。对 的请求在两个调度中都是命中。LRU 把顺序改为 ,但 仍为空,势函数保持为零。即使没有缺页,新近程度也可能改变。
例题 7.4.9
(被逐出的页面可能属于离线缓存)
设 ,LRU 的顺序为 ,离线缓存为 。由于 是仅在线页面且位于第一位,势函数为二。请求 :离线命中,LRU 逐出 ,而 在离线缓存中。仅在线页面 后移到第二位,权重从二降为一。即使被逐出的页面本身没有贡献任何势,这一下降也抵偿了 LRU 的这次缺页。
常见错误
反例模式
LRU 缺页时,仅看基数可能保持不变
在上一个例子中,请求之前 ,请求之后它仍然是 ,基数保持为一。然而按新近程度加权的势函数却从二降为一。可见,仅仅统计缓存之间的差异个数,并不能说明本证明所用的“减少一个单位”。
常见错误
(记账的次序并不是信息优势)
比较的对象是同一个请求序列上的一个固定离线调度。两个更新在概念上的先后顺序,并不意味着 LRU 能看到离线缓存或其逐出的页面。这只是在两个决策都已确定之后使用的分析手段。
常见错误
(把因子 当成预测)
因子 是对所有序列的最坏情形保证。它并不意味着 LRU 的代价总是最优代价的 倍,也没有解决随机化算法的竞争性问题。若对手是能观察随机缓存内容的自适应对手,则需要单独陈述的模型。
为什么这样安排新近程度权重
一个新近的仅在线页面很可能在今后许多次 LRU 逐出中幸存。给它较大的权重,就提供了一笔储备,可以随着它新近程度的降低而逐步花掉。对不同页面的每一次请求至多使它后移一位,并使其贡献减一。在顺序的最末位,它的权重恰为一,因此逐出它就取走了最后一个单位。
相反,当被请求的页面已在离线缓存中时,把它移到最前面不会为它自己增加任何贡献。这正是证明先更新离线一方的原因。离线缺页可以增加储备,但只是暴露了离线调度所逐出的那一个在线页面;该页面的权重至多为 。把这些局部变化在整个序列上平衡起来,就得到代价的比较。
初始顺序的约定会影响 LRU 在早期遇到平局时逐出哪个页面,但不等式对每个固定的初始顺序都成立。两个缓存以相同的页面集合开始时,势函数为零。若初始缓存不同,同样的计算会多出一个加性的初始势函数项,至多为 ;对于彼此无关的初始状态,本节并不断言去掉该项后的不等式仍然成立。
理解摊还不等式
势函数是一个记账量,并非任何一方实际支付的钱。单个请求可以使表达式 为负:一次 LRU 命中可能使好几个仅在线页面同时在顺序中后移。负的摊还代价是无害的,因为在整个执行过程中势函数不会降到零以下。它表示先前累积的储备被释放。
证明中的离线调度本身不必是最优的。例如,若某个调度缺页十次,而 LRU 至多缺页 次,则不等式成立,但可能很弱。在对每个调度都证明了不等式之后,再选取代价最小的离线调度,就得到与 的比较。这种推理次序避免了对最优解逐出哪个页面作任何假设。
实现时需要维护成员关系和新近程度顺序,例如用字典加双向链表。其实际运行时间取决于字典的操作和计算模型。该定理只统计缺页次数;它不统计维护链表的 CPU 开销,也不声称任何特定的字典时间界。
面对不知情的对手,随机标记算法的因子只有对数阶。
自然的下一个问题
随机化能胜过因子 k 吗?
面对不知情的对手,随机标记算法的因子只有对数阶。
下界 能击败所有确定性算法,是因为对手看得见它的缓存。若请求序列必须事先固定,随机标记算法的期望代价与最优值之比,只是 的量级。这在随机标记一节中展开。
总结
按新近程度加权的势函数在每次离线缺页时至多上升 ,在离线步骤之后每次 LRU 缺页时至少下降一。从相同的初始缓存出发,求和抵消即证明了精确的因子 。另一个“请求缺失页面”的对手构造则排除了任何更小的确定性竞争比,即使允许加性常数。
练习
快速检查
(设 ,LRU 的顺序为 ,离线缓存为 ,计算势函数。)
找出在 LRU 缓存而不在离线缓存的页面。
解答 · 答案
只有 属于 ,且其排名为一。它的权重为 ,所以势函数为三。
快速检查
(从上一题的情形出发,请求 且离线命中。给出新的 LRU 顺序,并计算新的势函数。)
先判断 LRU 是命中还是缺页,再更新顺序。
解答 · 答案
LRU 缺页,逐出最久未使用的 ,并把 插入最前面,得到顺序 。唯一的仅在线页面仍是 ,现在排名第二,权重为二。势函数下降一,抵偿了这次缺页。
快速检查
(在同样的初始情形下,设 LRU 的顺序固定,而离线缓存从 变为 。计算势函数的变化量。)
更改之后哪个页面是仅在线的?它排第几?
解答 · 答案
初始时势函数为三。离线缓存改变之后, 属于 而 不属于,故唯一的贡献来自位于第二位的 ,权重为二。势函数的变化量为 。离线改变也可能使势函数增加,但在缺页时增加量绝不超过 。
快速检查
(解释为什么在裂项求和的证明中可以舍去最终势函数,而如果初始缓存不同则需要额外的一项。)
写出求和后的不等式,再看势函数的各项。
解答 · 答案
求和得到 。最终势函数非负,所以去掉它只会使不等式变弱。初始缓存相同时初始势函数为零;否则初始势函数作为加性上界项保留下来。