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

本章主要讲述在线算法,其中包括实际应用存在不满足在算法执行之前整个输入数据条件的情况:磁盘调度问题,操作系统的页面调度问题,Data streams;在线算法基本概念:在线算法的竞争比不可能再改进;页面调度问题:高速缓存可放k个页面;低速内存有多个页面;后进先出法,最少访问法,最旧访问法
展开查看详情

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 算法至少也会缺失一 次