第五讲存储管理之三虚拟存储.ppt

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次。 否 是 是 否 否 是 是 是 是 是 是 是 是否 缺页 2 1 4 3 2 1 换出 的页 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 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 淘汰的页： 7 1 0 4 缺页次数：7次 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 淘汰的页：7 1 2 3 0 4 缺页次数：9次 LRU策略的特点： LRU没有Belady奇异。即随着驻留集的增大,页故障一定减少. 要硬件配合，实现费用高，但效果适中。 LRU算法的实现方法： 实现方法1：用计数器实现LRU。 实现方法2：用栈实现LRU。 实现方法3：用矩阵实现LRU。 实现方法4：用寄存器实现LRU。 实现方法1—用计数器实现LRU： 每页增加一个计数器，用计数器方法记录情况。命中时，刚访问到的页计数器清0，其余计数器加1；淘汰时选择计数器值最大的页面，新换入的页计数器清0，其余页计数器加1。例如： 举例：若驻留集大小为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 7 1 2 3 0 4 实现方法2—用栈实现LRU： 可用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时便将该面页从栈中移出，然后将它压入栈顶。因此，栈顶始终是必威体育精装版的页号，而栈底则是最近最久未使用的页号。例如: 举例：驻留集大小为3，访问串为 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 7 0 7 1 0 7 2 1 0 0 2 1 3 0 2 0 3 2 4 0 3 2 4 0 3 2 4 0 3 2 3 0 2 2 3 0 淘汰的页：7 1 2 3