动机
缓存之所以有用,是因为最近被请求过的页面很可能再次被需要。然而,当所请求的页面不在缓存中时,缓存必须在看到后续请求之前先腾出空间。这个决策是在线的:只能依据迄今已见到的请求序列来作出。离线基准则知道整个序列,因而可以据此规划其驱逐。
竞争分析把在线算法的代价与离线最优算法在同一请求序列上的代价相比较。本章给出标记算法 上界的一个清晰的阶段式证明,并另行给出确定性算法 的对抗性下界。这里的上界是有意取得初等的;它并不意味着 是最近最少使用(LRU)分页所能达到的最佳保证。
定义
定义 7.3.1
(分页模型:命中、缺页与代价)
给定一个页面全集和容量为 的缓存。对缓存中页面的请求称为命中,代价为零。对不在缓存中的页面的请求称为缺页,代价为一:被请求的页面会被载入,若缓存已满,则驱逐一个页面。在线算法与离线最优算法都从同一个指定的、含 个互异页面的缓存开始。我们考虑有限的请求序列;离线算法在决定驱逐哪个页面时可以利用未来的信息。
定义 7.3.2
(带加性常数的竞争比)
若对每个有限序列 都有
则称算法 是带加性常数 的 -竞争的,其中 依赖于 和固定的初始缓存,但不依赖于 。加性项对短序列很重要;若不带加性项,则当离线最优代价为零时,比值没有定义。
定义 7.3.3
(请求序列的阶段)
把一个非空请求序列贪心地划分为阶段。第一个阶段从第一个请求开始。只要下一个请求属于该阶段最初的 个互异页面名之一,该阶段就继续;对第 个互异新页面的请求则开启下一个阶段。因此除了可能的最后一个阶段外,每个阶段恰好包含 个互异页面。
定义 7.3.4
(标记算法)
标记算法在每个阶段开始时清除所有标记,并对每个被请求的页面加上标记。发生缺页时,它驱逐一个未被标记的页面。这样的页面总是存在的:在一个阶段内处理一个新的互异页面之前,被标记的不同页面少于 个,而缓存持有 个页面。最近最少使用(LRU)是一种标记算法,因为每个被标记的页面都在当前阶段被使用过,而每个未被标记的缓存页面最后一次使用都在更早的时候。
定理
定理 7.3.5
(一个简单的标记算法上界)
对于任何被划分为 个阶段的请求序列,标记算法至多产生 次缺页,而离线最优算法至少产生 次缺页。因此每个标记算法都是带加性常数 的 -竞争的。
定理 7.3.6
(确定性算法的下界)
对于缓存大小为 的每个确定性在线分页算法,以及每个 ,都不存在常数 使得其代价在每个序列上至多为 。即使页面全集只有 个页面,只要初始缓存包含于该全集中,这一结论依然成立。
证明
证明:标记阶段
证明
(标记算法的阶段计数)
在一个阶段内,标记算法绝不会驱逐一个已被请求并被标记的页面。因此每个互异页面在该阶段内至多缺页一次,故至多发生 次缺页。对 个阶段求和即得在线上界。
对于相邻两个阶段之间的每个边界,后一阶段的第一个请求是前一阶段中未被请求过的页面。由于前一阶段含有 个互异页面,这两个阶段的并集至少含有 个互异页面。若离线最优算法在这个两阶段区间内没有任何缺页,则其缓存在整个区间内保持不变,并且包含所有这些页面,而这与容量为 矛盾。因此每一对相邻阶段中至少包含一次离线缺页。
一次缺页只属于单个阶段,因此至多落在两个相邻阶段对中。对 个阶段对计数,得 。结合两个界即得
这种配对论证把每次缺页至多计两次,而不是恰好计两次。它是有意保守的,只证明了所述的因子,而并不声称这是一个紧的上界。
证明透视
因子二从何而来
标记规则与缓存容量各自发挥作用。在线一侧,仅凭标记规则,每个互异页面在每个阶段至多缺页一次,故每个阶段至多缺页 次;这里没有用到离线调度的任何性质。离线一侧,关键的一步是凭证:阶段 的 个页面加上阶段 的第一个请求,共是 个互异页面名,而容量为 且不发生变化的缓存无法容纳它们,所以这一对阶段之中必有缺页。相邻的阶段对相互重叠:阶段 同时属于 与 ,因此内部阶段中的一次离线缺页可以同时为两个阶段对作证。于是阶段对的数目至多是离线缺页次数的两倍。若把这些见证缺页自动视为互不相同,就会得到 ,这是没有根据的更强断言,并会把因子 错误地变成 。
证明:针对任意确定性算法的对手
证明
(针对确定性算法的自适应对手)
固定一个确定性在线算法,以及恰含 个页面且包含其初始缓存的页面全集 。不断请求 中不在该算法当前缓存里的页面。这样的页面总是至少有一个。该算法在每个请求上都缺页。由于算法是确定性的,一旦固定长度 ,这个自适应过程就确定了一个特定的有限序列;所得序列可作为针对该算法的固定最坏情形输入。
为了界定该序列上的离线最优代价,把它划分为同样的阶段。每个完整阶段含有 个互异请求,因此至少含有 个请求。所以阶段数 满足 。
若 ,请求的不同页面至多有 个;每个页面首次请求后将其保留即可,因此离线最优代价至多为 。现在假设 ,则第一个阶段包含恰好 个互异页面。一个知道各阶段的离线策略在第一个阶段至多缺页 次:它保留该阶段所请求的每个页面,并在缺页时驱逐一个不属于第一阶段页面集合的页面。需要空间时,总是存在这样的页面。到该阶段结束时,其缓存恰好含有该阶段的 个互异页面。
元全集的任意两个 元子集至多相差一个页面。在下一个完整阶段,离线策略保留两者共有的页面,并且若那个新页面被请求,就驱逐不属于新阶段集合的那一个页面。因此它在该阶段至多缺页一次,并以整个集合都在缓存中而结束。对于最后一个不完整的阶段,把其被请求的集合任意扩充为 的一个 元子集,并使用同样的论证。所以
在线代价恰为 。若对某个 有一个固定的不等式 成立,则对每个 都有 。右边 的系数严格小于一,因此足够大的 会与该不等式矛盾。这就证明了下界,并且包含了加性常数的约定。
例题详解
例题 7.3.7
(一个两页面的 LRU 轨迹)
取缓存 ,容量为二,请求为 。LRU 在 上命中,在 上缺页并驱逐 ,在 上缺页并驱逐 ,然后在 上缺页并驱逐 。其代价为三。各阶段为 与 ,各含两个互异页面。它们的并集含有三个互异页面,因此任何离线调度在这两个阶段中至少要缺页一次。
例题 7.3.8
(一个简短的离线比较)
对同样的缓存和请求,一个离线策略在 上命中,然后载入 并驱逐 ,因为下一个请求是 。它在 上命中,然后载入 ,共缺页两次。一次缺页不可能足够:在请求 时,缓存必须驱逐 或 ,而被驱逐的页面稍后会被请求,其间没有任何零代价的方式把它载入。因此离线最优恰为二。
例题 7.3.9
(容量为一时的确定性对手)
页面全集为 ,初始缓存为 ,先请求 ,然后请求 中缺失的那一个。容量为一迫使序列交替为 ,在线算法与离线算法在每个请求上都缺页。下界为 ,与这个特例一致。
例题 7.3.10
(两个阶段集合高度重叠)
取 ,页面全集为 ,相邻的完整阶段集合可以是 与 。持有第一个集合的离线缓存,只需在第二阶段首次请求 时把 换成 。请求的内部顺序可以是任意的;一旦这三个页面为该阶段载入,离线策略就会保留全部三个。
常见错误
反例模式
驱逐已标记页面的规则
断言:每个确定性的按需分页规则都满足 保证。缺少标记性质时这是错的。取 ,初始缓存为 (按此次序载入),规则是永远驱逐最近载入的页面。对长度为 的请求 ,每次请求都缺页:载入 时驱逐 ,载入 时驱逐 ,依此类推,代价为 。离线调度在第一个请求时驱逐 ,保留 和 ,总代价为 。界 在 时就已被违反,任何常数都补救不了。这条规则不是标记算法:在第一阶段中 与 都已被请求之后,它却驱逐已标记的页面 。补救之道就在定理的假设:只驱逐未标记的页面。
常见错误
(把对手论证推广到随机化算法)
对于确定性算法和固定长度,一旦模拟该构造,其选择就事先决定了唯一的一个序列,因此可以作为固定的最坏情形输入。这一推理不会自动推广到面对不经意对手的随机化算法:缓存中缺失的页面可能取决于私有的随机选择,因此量词与期望必须另行说明。
常见错误
(把两个界之间的差距当作确切竞争比)
上界与 下界并不吻合。它们表明的是一个有效的保证和一个普适的障碍,而不是某条在线规则的确切竞争比。更精细的分析也许能缩小这一差距,但本章并未证明。
为什么阶段是有用的
阶段记录的是近期请求的工作集,而不是固定数目的时间步。如果同样的少数页面反复出现,阶段可以非常长,但标记算法在一个阶段内对其中任何一个页面至多付出一次代价。这使得上界对重复命中不敏感。
离线比较更困难,因为最优算法进入一个阶段时,其页面可能是借助未来信息选定的。它不必在每个单独的阶段都缺页。考察两个连续阶段则提供了一个凭证:它们合起来的请求超出了缓存容量。这个简单凭证的代价是,一次离线缺页可以支持两个相邻的凭证。
下界用到的是另一个事实。在含 个页面的全集上,两个完整阶段集合至少重叠 个页面。知道下一个集合,使离线策略每个阶段至多改动一次即可做好准备。与此同时,在线算法被迫在每个请求上都缺页。重叠和离线知识这两者对该论证都是必不可少的。
总结
标记算法把在线算法限制在每个阶段每个互异页面至多缺页一次。连续的阶段之间必然有一次离线缺页,由此得到带加性常数 的 竞争保证。 个页面上的确定性对手则迫使任何确定性在线算法面对渐近下界 。
练习
快速检查
(对 ,把 划分为阶段,并给出每个阶段中互异页面的个数。)
解答 · 答案
各阶段为 、 和 。它们的互异页面个数分别为二、二和一。请求 开启第二阶段,因为它会是第一阶段中的第三个互异页面;同理 开启第三阶段。
快速检查
(在同一序列中,为什么即使一个阶段含有许多请求,标记算法在每个阶段中至多缺页两次?)
解答 · 答案
一个页面在该阶段中第一次被请求之后即被标记,在该阶段内不能被驱逐。每个阶段至多含有两个互异页面,因此每个页面至多缺页一次,总共至多缺页两次。
快速检查
(取 ,,离线缓存持有 ,下一个完整阶段使用 。描述一个至多缺页一次的策略。)
解答 · 答案
保留 。若请求 ,则缺页一次,载入 并驱逐 。此时该阶段所请求的全部页面都在缓存中,因此之后的请求都命中。若 没有被请求,则该阶段集合并不像题设所说是完整的。
快速检查
(对 ,确定性对手产生一个长度为 的序列。根据证明陈述离线代价的一个上界,并解释为什么在线代价为 。)
解答 · 答案
证明给出 。在每个请求上,对手都选取一个不在在线缓存中的页面,因此在线算法在全部 个请求上都缺页。离线上界不必是整数;它是对一个整数代价的上界。