赞
踩
请求分页存储管理与基本分页存储管理的主要区别:
最佳置换算法(OPT,Optimal):
每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面,
这样可以保证最低的缺页率。
整个过程缺页中断发生了9次,页面置换发生了6次。缺页率:9/20= 45%
注意:
最佳置换算法可以保证最低的缺页率,但实际上,
只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。
操作系统无法提前预判页面访问序列。
因此,最佳置换算法是无法实现的。
先进先出置换算法(FIFO):每次选择淘汰的页面是最早进入内存的页面。
把调入内存的页面根据调入的先后顺序排成一个队列,需要换出页面时选择队头页面即可。
队列的最大长度取决于系统为进程分配了多少个内存块。
最近最久未使用置换算法(LRU,least recently used):每次淘汰的页面是最近最久未使用的页面
赋予每个页面对应的页表项中,用访问字段记录该页面自上次被访问以来所经历的时间t。
当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面。
最佳置换算法性能最好,但无法实现;
先进先出置换算法实现简单,但算法性能差;
最近最久未使用置换算法性能好,是最接近OPT算法性能的,但是实现起来需要专门的硬件支持,算法开销大。
时钟置换算法是一种性能和开销较均衡的算法,又称CLOCK算法,
或最近未用算法(NRU,NotRecently Used)
假设系统为某进程分配了五个内存块,并考虑到有以下页面号引用串:1,3,4,2,5,6,3,4,7
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。
事实上,如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。
只有被淘汰的页面被修改过时,才需要写回外存。
因此,除了考虑一个页面最近有没有被访问过之外,操作系统还应考虑页面有没有被修改过。
在其他条件都相同时,应优先淘汰没有修改过的页面,避免I/O操作。
这就是改进型的时钟置换算法的思想。
修改位=0,表示页面没有被修改过;修改位=1,表示页面被修改过。
为方便讨论,用(访问位,修改位)的形式表示各页面状态。
将所有可能被置换的页面排成一个循环队列
由于第二轮已将所有帧的访问位设为0,因此经过第三轮、第四轮扫描一定会有一个帧被选中,因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。