第四讲存储管理.pptVIP

(一) FIFO替换算法(替换最早进入的页) 举例：驻留集大小为3，访问串为： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2… 7 7 0 7 0 1 2 0 1 2 0 1 2 3 1 2 3 0 4 3 0 4 2 0 4 2 3 0 2 3 0 2 3 0 2 3 O O O O O O O O O O 1、FIFO方法的特点： 实现方便。不需要额外硬件。 效果不好，有Belady奇异。 2、Belady奇异：指替换策略不满足随着驻留集的增大，页故障数（缺页中断次数）一定减少的规律。 FIFO替换算法的Belady奇异现象举例： 对于如下的页面访问序列：1，2，3，4，1，2，5，1，2，3，4，5当内存块数量分别为3和4时，试问：使用FIFO置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断） 内存块为3时，缺页中断次数为9次。 内存块为3时，缺页中断次数为9次。 否 是 是 否 否 是 是 是 是 是 是 是 是否缺页 5 2 1 4 3 2 1 3 5 2 1 4 3 2 1 4 3 5 2 1 4 3 2 1 页面分配情况 5 4 3 2 1 5 2 1 4 3 2 1 次序 内存块为4时，缺页中断次数为10次。 3 2 1 5 4 3 2 1 是 是 是 是 是 是 否 否 是 是 是 是 是否缺页 2 1 5 4 3 2 1 4 3 2 1 5 4 3 2 1 5 4 3 2 1 5 4 3 2 1 页面分配情况 5 4 3 2 1 5 2 1 4 3 2 1 次序 (二) OPT(Optimal replacement) 举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 7 7 0 7 0 1 2 0 1 2 0 1 2 0 3 2 0 3 2 4 3 2 4 3 2 4 3 2 0 3 2 0 3 2 0 3 O O O O O O O 淘汰下次访问距当前访问最远的那些页或很久以后才使用的页。 OPT方法特点： 是最优的页面替换策略。 OPT策略对任意一个访问串的控制均有最小的时空积（进程所占空间与时间的乘积）。 是不可实现的策略 由于需要预先得知整个访问串的序，故不能用于实践,仅作为一种标准，用以测量其他可行策略的性能。 (三) LRU(Least Recently Used) 淘汰上次使用距当前最远的页或最近很少使用的页。 举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 7 7 0 7 0 1 2 0 1 2 0 1 2 0 3 2 0 3 4 0 3 4 0 2 4 3 2 0 3 2 0 3 2 0 3 2 O O O O O O O O O LRU策略的特点： LRU没有Belady奇异。即随着驻留集的增大,页故障一定减少. 要硬件配合，实现费用高，但效果适中。 实现方法1：给每个页帧设一个计数器，每访问一页，对应页帧计数清0，其余页帧计数加1，淘汰计数最大的页帧。 实现方法2：用类似栈的结构来管理和实现LRU。 实现方法1举例： LRU策略用计数器方法记录,则驻留集和计数器的变化如下: 若：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 0/7 1/7 0/0 2/7 1/0 0/1 0/2 2/0 1/1 1/2 0/0 2/1 2/2 1/0 0/3 3/2 0/0 1/3 0/4 1/0 2/3 1/4 2/0 0/2 2/4 0/3 1/2 0/0 1/3 2/2 1/0 0/3 3/2 2/0 1/3 0/2 O O O O O O O O O 四、页面替换算法解题举例 例:在页式管理中，设主存大小为三页，已知页面走向为：4，3，2，1，4，3，5，4，3，2，l，5（共12次）。调页时分别采用先进先出（FIFO）和最佳（OPT）算法，问缺页率各是多少？ ???解：1、先进先出算法。 页面调度情况如下表所示。其中，缺页次数为9次；缺页中断率f= 9/12＝75%.? 否 是 是 否 否 是 是 是 是