11算法设计与分析---在线算法

1 .东南大学计算机学院 方效林 在线算法

2 .本章内容 在线算法基本概念 页面调度问题 2

3 .在线 算法基本概念 前面介绍的算法 在 算法执行之前整个 输入数据 实际 应用存在不满足上述条件的 情况 磁盘 调度问题 操作系统的页面调度问题 Data streams 3

4 .在线 算法基本概念 竞争比 设在线算法代价为 ，离线最优算法代价为 ， 若存在非负常数 和 ，使得 ，则称 为该在线算法的竞争比 ( -competitive) 当在线算法的 竞争比不可能再改进时， 称其为最 优在线算法   4

5 .页面调度问题 问题： 高速缓存可放 k 个页面；低速内存有多个页面 给定一个页面请求序列 ，当高速缓存占满的情况下，在高速缓存出现页面缺失时，选择哪个页面与低速内存页面交换，使得遇到缺失的次数最少   5

6 .页面调度问题 LIFO(Last In First Out, 后进先出 法 ) 将 最后放入高速缓存的 页面交换 出去 该方法不是 - competitive 算法 例如页面请求序列为 < a,b,a,b,a,b > ， 假设高速缓存中页面 不含 a,b LIFO 中，每次 a 被交换进马上又被交换出， b 也一样 最优解 OPT 里只需将 a,b 与高速缓存中 2 页面交换   6

7 .页面调度问题 LFU ( Least Frequently Used , 最少访问法 ) 将高速缓存中访问次数最少的 页面交换 出去 该方法不是 - competitive 算法 例如页面请求序列为 < a,b,a,b,a,b > ， 假设高速缓存中页面 访问次数均大于 1 ，且不含 a,b LFU 中，每次 a 被交换进马上又被交换出， b 也 一样 最优解 OPT 里只需将 a,b 与高速缓存中 2 页面交换   7

8 .页面调度问题 LRU ( Least Recently Used , 最旧访问 法 ) 将高速缓存中最早访问的 页面交换 出去 k=3 ，页面请求序列 <4,3,4,2,3,1,4,2> ， LRU 过程 4 4 3 3 4 3 4 2 4 2 3 2 3 1 3 1 4 1 4 2

9 .页面调度问题 LRU ( Least Recently Used , 最旧访问 法 ) 将 高速缓存中最早访问的页面交换 出去 该方法是 - competitive 算法 证明： 将 LRU 算法调度过程分为多个阶段 ，第 1 个阶段页面缺失数不多于 k ，后面所有阶段页面缺失数等于 k 只要证明 OPT 中每一阶段至少需要交换 1 次，就可得证明 -competitive          

10 .页面调度问题 LRU ( Least Recently Used , 最旧访问 法 ) 将 高速缓存中最早访问的页面交换 出去 该方法是 - competitive 算法 证明： 在第 1 阶段 , 初始时高速缓存为空， OPT 至少缺失一次 在第 阶段，分两种情况 情况 1 ： LRU 算法在第 阶段对某同一页面 p 存在多于一次缺失的情况。页面 p 第一次缺失后，再一次缺失时，说明 LRU 算法在 第 阶段至少遇到 k+1 次互不同页面 的缺失 (p 的两次缺失只算一次 ) 。 由于有 k+1 个互不相同 页面的 缺失， OPT 算法至少也会缺失一次  

11 .页面调度问题 LRU ( Least Recently Used , 最旧访问 法 ) 将 高速缓存中最早访问的页面交换 出去 该方法是 - competitive 算法 证明： 在第 1 阶段 , 初始时高速缓存为空， OPT 至少缺失一次 在第 阶段，分两种情况 情况 2 ： LRU 算法在第 阶段对任一页面 p 只有不多于一次缺失的情况。令 p 为前阶段 ( 第 阶段 ) 最后访问页面，又分两种情况 情况 2.1 ，本阶段再缺失页面 p ，与情况 1 相同，需要 k+1 次不同页面缺失， OPT 算法至少也会缺失一 次  

12 .页面调度问题 LRU ( Least Recently Used , 最旧访问 法 ) 将 高速缓存中最早访问的页面交换 出去 该方法是 - competitive 算法 证明： 在第 1 阶段 , 初始时高速缓存为空， OPT 至少缺失一次 在第 阶段，分两种情况 情况 2 ： LRU 算法在第 阶段对任一页面 p 只有不多于一次缺失的情况。令 p 为前阶段 ( 第 阶段 ) 最后访问页面，又分两种情况 情况 2.2 ，本 阶段不缺失 页面 p 。说明本阶段有 k 个互不同，且与 p 不同的页面缺失， OPT 算法至少也会缺失一 次