高速缓存调度问题
问题重述:
假设有 n 个页面驻留在内存中,且有一个能容纳 k 个页面的高速缓存。现有
依次访问内存中 m 个页面的请求序列 I=I
1
,I
2
,…,I
i
,…,I
m
,其中 m>k。我们必
须确定任何时刻哪 k 个页面放在高速缓存中。对某个访问请求 I
i
,若该页面
在高速缓存中,则可很快完成访问。否则发生一次缺页,必须将其调入高速
缓存。这时,若高速缓存未满,则直接将其调入,否则必须确定将高速缓存
中哪个页面置换出来以便为 I
i
腾出空间。高速缓存调度问题是指如何调度页
面使得缺页的总数尽可能少。
设计思路:
因为刚学完操作系统,所以这道题采取 OPT 算法。虽然 OPT 策略被誉为驻
留集固定策略中的最优策略,但是由于控制页面调度时需预先知道整个访问
串,而在大多数情况下,访问串是不可知的,故难以付诸实用。在现实情况
下并不能完全知晓整个请求序列,但假设我们事先已经知道,这样采取 OPT
就是最优的。
缓存调度采用 OPT 策略,OPT 策略是驻留集大小固定策略中的最优策略。
它淘汰下次访问距当前最远的那些页中序号最小的一页。称 OPT 为驻留集
固定类策略中的最优策略理由是,OPT 策略对任意一个访问串的控制均有最
小的时空积(所占空间与时间的乘积)。就驻留集固定这类策略而言,由于
所占空间为一常数,因此评判策略的性能时只需比较处理同一访问串各自所
花费的时间量,即也故障的次数。
设计的关键点:
首先在缓存中遍历寻找是否有相应的页面,如果有责结束。否则,如果缓存
内还有空间,则无条件调入内存。当缓存已满,则进行淘汰,用 times 记录
最远的距离,Index 记录最远者的下标。然后用当前页替换被淘汰页。
复杂度分析
数据结构中最多只用到一维数组,故而空间复杂度为
( )O n k+
。
由关键函数
()attemper
中复杂度最大的是嵌套的两层 for 循环可知,时间复杂
度的数量级为
( )O m k×