动机
对于大小为 的缓存,确定性分页算法的最坏情形竞争比为 。当请求序列独立于算法的随机选择而固定时,随机化可以改变这一比较。随机化标记算法在一个阶段内保护最近被请求的页面,并在必须逐出页面时,从其余候选页面中均匀随机地选择。
期望缺页次数由一个调和和控制。证明把必然缺页的新出现页面,与可能已被随机逐出的旧页面区分开来。证明同时明确陈述了对手模型:固定的序列不能在观察到算法私有的随机逐出之后才选定。
定义
定义 7.5.1
(按需分页与不经意对手)
采用按需分页模型,缓存容量为 ,在线调度与离线调度的初始缓存相同。每次缺页代价为一。输入是在任何随机选择之前就已固定的有限请求序列;这称为不经意对手(oblivious adversary)。下文的期望是针对该固定输入,对算法的随机选择取的期望。
定义 7.5.2
(随机化标记算法)
把序列贪心地划分为若干阶段:当某个请求将引入第 个不同页面时,开始新的阶段。因此除最后一个阶段外,每个阶段恰好含有 个不同页面。在每个阶段开始时清除所有标记。服务完一个请求后,标记其页面。发生缺页时,从缓存中未被标记的页面里均匀随机地选一个逐出。在本阶段内请求一个新页面之前,被标记的页面少于 个,因此存在未被标记的缓存页面。
定义 7.5.3
(全新页面与旧页面)
对于第一个阶段之后的阶段,若某个被请求的不同页面没有在前一阶段出现过,称其为全新页面(clean),否则称为旧页面(stale)。设 为第 个阶段中全新页面的个数。由于前一阶段是完整的,它的 个页面恰好就是下一阶段开始时的缓存内容:每个页面在被请求时都被标记,因此在该阶段其后不可能被逐出。
定义 7.5.4
(调和数)
记 。
定理
定理 7.5.5
(随机化标记算法的期望代价)
对于每个固定的有限请求序列,随机化标记算法满足
期望是对算法的选择而取的,而 是同一固定序列上离线算法的最小缺页次数。
定理 7.5.6
(单个阶段的期望缺页次数)
在固定请求序列的条件下,第一个阶段之后的任意阶段的期望缺页次数至多为 。
证明
证明:缺失旧页面构成均匀集合
证明
(一个阶段的期望代价)
固定第一个阶段之后的某个阶段,以及它的前一阶段的页面集合 ,该集合恰好含有 个页面。在当前阶段已请求 个不同的旧页面之后, 中有 个页面在本阶段尚未被请求。设 为已经被请求的不同全新页面的个数。所有已请求的页面都被标记并留在缓存中。 中未被请求的页面里恰有 个不在缓存中:缓存有 个槽位,被标记的全新页面占据了 个槽位,而这些槽位在阶段边界处原本由 中的页面占据。
在 的 个未被请求的页面中,缺失的 个页面构成一个均匀随机的 元子集。这一不变量在开始时成立,因为此时 。对一个新的全新页面的请求会缺页,并从 中未被标记的缓存页面里均匀随机地选一个逐出;把该被逐出的页面加入缺失集合,得到一个大小为 的均匀子集。对于一个新的旧页面请求:若所请求的页面在缓存中,标记它就把一个在缓存中的页面移出考虑范围;若它不在缓存中,则载入并标记它,把一个缺失页面移出考虑范围,同时从在缓存中且未被标记的页面里均匀随机地选一个逐出。无论哪种情形,在以该命中或未命中为条件时,剩余的缺失集合在相应剩余大小的子集中仍是均匀的。对已标记页面的重复请求不改变该不变量。
序列的固定独立于随机选择,所以它的下一个此前未被请求的旧页面并不是通过查看随机的缺失集合而选出的。因此它缺页的概率为 ,至多为 。不同的旧页面请求至多有 个。对其可能的位置把上界求和,得到旧页面的期望缺页次数至多为 。每个全新页面恰好缺页一次,而对已标记页面的重复请求都命中。因此该阶段的总期望代价至多为 。
证明透视
为什么下一个页面必须独立地固定
三个要素结合在一起,每个只用一次。计数:每个被请求的页面都被标记,因而留在缓存中,而缓存有 个槽位,所以在 个尚未被请求的旧页面中,恰有 个在缓存中, 个缺失。对称性:每次驱逐都在未被标记的缓存页面中均匀选择,所以没有哪个未被请求的旧页面比其他页面更可能属于缺失集合,下一个被请求的旧页面缺失的概率是 。不经意性:最后这一步用到下一个被请求的页面在掷硬币之前已经固定。若请求是看着缓存而选的,它总可以指名一个缺失的页面,概率就是一而不是 ,调和数的界便不成立。最后, 并对 的可能取值求和,便得到 。
证明:比较全新页面与离线缺页次数
证明
(把各阶段与离线最优相加)
对于 ,第 与第 个阶段的页面集合之并,包含第 阶段的 个页面加上 个全新页面。在这两个阶段中,大小为 的离线缓存至少要缺页 次:开始时至多有 个页面,每次缺页至多能多引入一个被请求的不同页面。
对各阶段边界把这个不等式求和,任何一次离线缺页至多被计入相邻阶段对中的两对。因此 。随机化算法在第一个阶段至多缺页 次,因为每个页面在首次被请求后即被标记。由期望的线性性和阶段上界得到
期望的线性性不需要各阶段之间相互独立。该不变量在每个阶段边界都成立,因为标记使整个前一阶段的页面集合都留在缓存中。附加的 用来容纳第一个阶段,而无需给它赋予一个虚构的前置请求集合。
例题详解
例题 7.5.7
(容量为二、含一个全新页面)
设前一阶段的页面集合为 ,下一阶段以对新页面 的请求开始。算法缺页,并以各一半的概率逐出 或 。若下一个请求是固定的旧页面 ,则它以二分之一的概率缺页。这两次请求的期望缺页次数为 。
例题 7.5.8
(容量为三时的调和估计)
当 且一个阶段中有一个全新页面时,。定理把该阶段的期望代价界定为 。这是一个上界,对于给定的请求次序并不一定是精确的期望值;证明中把到目前为止已请求的全新页面个数 替换为其最大值 。
例题 7.5.9
(不含全新页面的阶段)
若当前阶段只请求前一阶段的页面,则这些页面在阶段边界处全部在缓存中。没有任何请求缺页,所以该阶段的代价为零。这与上界 一致,对最后一个不完整的阶段也是如此。
例题 7.5.10
(离线的相邻阶段对证明)
取 ,设第 阶段请求 ,第 阶段请求 。全新页面有两个,即 ,这两个阶段共出现五个不同页面。一个在这一对阶段开始时仅含三个页面的离线缓存,无论其初始内容和逐出选择如何,在这一对阶段中都必须至少缺页两次。
常见错误
反例模式
观察随机逐出会改变博弈
设缓存为 ,,请求一个全新页面 。固定的下一个请求 以二分之一的概率缺页。若对手观察到 与 中哪个被逐出,然后请求被逐出的那个页面,则缺页概率为一。后一种序列依赖于随机选择,不在固定输入的计算范围之内。
常见错误
(把均匀性用于整个页面全集)
均匀子集的陈述针对的是前一阶段中尚未被请求的页面,而不是全体页面中的任意页面。已被请求的全新页面都已被标记并留在缓存中。一个被请求两次的旧页面只可能在第一次请求时缺页;此后直到下一个阶段,它一直处于被标记状态。
常见错误
(夸大对数界所表明的内容)
由于对 有 ,该定理给出 的上界。它并没有确立最优的随机化下界,也没有声称所给出的常数是紧的。离线最优值是在同一固定序列上计算的,而不是对响应随机缓存而生成的序列取平均。
理解均匀不变量
设想给尚未被请求的旧页面贴上标签,但不赋予它们不同的未来重要性。在一次全新页面的缺页处,当前每个在缓存中且未被标记的旧页面被逐出的可能性相同。原本均匀分布的缺失集合,在加入这个随机被逐出的页面之后仍保持均匀。在一次旧页面的缺页处,被请求的缺失页面被恢复,而均匀随机选出的被逐出页面在其余旧页面中取而代之。这些操作对其余未被请求的旧页面是对称的。
只要下一个旧页面的身份是在随机选择之前就已固定的,它可以是任意的。它本身不需要是均匀选出的。随机性体现在哪些页面缺失上,而对称性使每个特定的未被请求的旧页面具有相同的缺失概率。当把该论证用于任意固定序列、而不是随机输入分布时,这一区别至关重要。
调和和之所以出现,是因为随着不同的旧页面请求陆续到来,符合条件的旧页面数量不断减少。我们把缺失概率界定为剩余数量的倒数,并对可能的位置求和。这个界可能比较松,但它给出一个简单的上界,而无需假设缺失事件相互独立。
从倒数项到对数
对于每个整数 ,倒数 至多等于 在 到 上的积分。把这些不等式相加得到 ,其中包括 。所得的界随缓存大小对数增长,而确定性算法的下界则线性增长。这两个陈述使用了不同的对手假设,因此不带着量词就不应当比较它们。
阶段估计的证明所求和的是概率,而不是概率的乘积。设某个特定的首次旧页面请求缺页时指示变量为一,否则为零。它的期望就是其缺页概率。旧页面缺页的总次数是这些指示变量之和,所以即使一次逐出会影响之后的缺页,其期望仍是各期望之和。假设各次缺页相互独立既不必要,通常也是错误的。
一个阶段可能在所有旧页面都被请求之前就结束。分析仍然可以对全部 个可能的旧页面位置求倒数上界之和:不存在的位置不会产生实际缺页,而加上非负项只会使上界变松。这就是为什么该论证也能处理最后一个不完整的阶段,而不要求它含有 个不同的请求。
面对不经意对手,每个随机算法的比值至少为 H_k。
自然的下一个问题
对数增长可以避免吗?
面对不经意对手,每个随机算法的比值至少为 H_k。
不可以。已知面对不经意对手,没有随机分页算法的竞争比低于 ,所以像 那样增长的因子无法避免。因此标记算法的界 在量级上是正确的;对应的下界证明超出本单元范围。
总结
随机化标记算法保留一个阶段中被请求的页面,并使缺失的、未被请求的旧页面服从均匀分布。它们的边缘缺失概率之和给出一个调和界。随后通过相邻阶段的计数,把全新页面的个数与离线缺页次数联系起来,从而得到针对固定序列的 保证。
练习
快速检查
(计算 ,并在 、 时计算所给出的阶段上界。)
解答 · 答案
。上界为 。一个界可以超过该阶段中可能出现的最多两次缺页;它仍然有效,但并不紧。
快速检查
(在完整的前一阶段之后的阶段开始时,为什么前一阶段的所有页面都在缓存中?)
解答 · 答案
前一阶段恰好请求了 个不同页面。每个页面在被请求时都被标记,而被标记的页面在阶段结束之前不可能被逐出。由于缓存有 个槽位,在阶段边界处它恰好包含这些页面。
快速检查
(若相邻两个阶段共含有 个不同页面,为什么任何离线调度在这一对阶段中都必须至少缺页三次?)
解答 · 答案
离线缓存在这一对阶段开始之前至多含有 个不同页面。其余三个被请求的不同页面都必须在某次缺页时被载入缓存。一次缺页至多载入一个被请求的页面,因此至少需要三次缺页。
快速检查
(解释为什么对一个阶段中已被标记的页面的重复请求,在该阶段不会造成额外的缺页。)
解答 · 答案
第一次请求被服务之后,该页面即被标记。逐出规则只在未被标记的页面中选择,直到下一个阶段边界清除所有标记,所以该页面在当前阶段的其余时间一直留在缓存中。