要完全实现最近最少用置换算法是一件非常困难的事情因为.ppt
《要完全实现最近最少用置换算法是一件非常困难的事情因为.ppt》由会员分享,可在线阅读,更多相关《要完全实现最近最少用置换算法是一件非常困难的事情因为.ppt(21页珍藏版)》请在三一文库上搜索。
1、要完全实现最近最少用置换算法是一件非常困难的事情。因为需要对每一页被访问的情况进行实时记录和更新,这显然要花费巨大的系统开销,所以在实际系统中往往使用LRU的近似算法。 LRU近似算法是在页表中为每一页增加一个“引用位”,当该页被访问时,由硬件将它的引用位置为“1”,操作系统选择一个时间周期T,每隔一个周期T,将页表中所有页面的引用位置“0”,这样,在时间周期T内,被访问过的页面,其引用位为1,而没有被访问过的页面,其引用位仍为0。这样,当产生缺页中断时,可以从引用位为0的页面中选择一页调出,同时将所有页面的引用位全部置零。这种近似算法实现比较简单,但关键在于时间周期T大小的确定。T太大,可能
2、所有的引用位都变成1,找不出最近最少使用的页面淘汰;T太小,引用位为0的页面可能很多,而无法保证所选择的页面是最近最少使用的。图3-39给出了以OPT算法中的例子采用LRU近似算法时,保留在主存中页面的变化情况,该进程执行过程中,共产生了12次缺页中断,缺页中断率为60%,页面淘汰的顺序为7,1,2,3,0,4,0,3,2。,(4)最近最不常用页面置换算法(Least Frequently UsedLFU) 最近最不常用置换算法总是选择被访问次数最少的页面调出,即认为在过去的一段时间里被访问次数多的页面可能经常需要访问。 一种简单的实现方法是为每一页设置一个计数器,页面每次被访问后其对应的计数
3、器加1,每隔一定的时间周期T,将所有计数器全部清零。这样,在发生缺页中断时,选择计数器值最小的对应页面淘汰,显然它是最近最不常用的页面,同时把所有计数器清零。这种算法实现比较简单,但代价很高,同时有一个关键问题是如何选择一个合适的时间周期T。,3缺页中断率分析 虚拟存储系统解决了有限主存贮器的容量限制问题,能使更多的作业同时多道运行,从而提高了系统的效率,但缺页中断处理需要系统的额外开销,影响系统效率,因此应尽可能地减少缺页中断的次数,降低缺页中断率。 假定一个作业共有n页,系统分配给它的主存块是m块(m、n均为正整数,且1mn)。因此,该作业最多有m页可同时被装入主存。如果作业执行中访问页面
4、的总次数为A,其中有F次访问的页面尚未装入主存,故产生了F次缺页中断。现定义: fF/A, 则f称为“缺页中断率”。 显然,缺页中断率与缺页中断的次数有关。因此影响缺页中断率的因素有:,(1)分配给作业的主存块数 系统分配给作业的主存块数多,则同时装入主存的页面数就多,那么缺页中断次数就少,缺页中断率就低,反之,缺页中断率就高。,从理论上说,在虚拟存储器的环境下,每个作业只要获得一块主存空间就可以开始执行,这样可以增加在主存中多道执行的作业数,但是每个作业将频繁地发生缺页中断,效率非常低下,如图3-40示出了处理器的利用率与多道程序之间的关系。如果为每个作业分配很多主存块,则减少了可同时多道执
5、行的作业数,影响系统的吞吐量。模拟试验表明,一个程序运行时发生的缺页中断次数是存放页 面的实际存储容量的函数,图3-41所示存储容量与缺页中断次数的关系。,当然图3-41的曲线是与程序的结构有关的,每个程序均有自己唯一的曲线。但图3-41的曲线形状十分典型,一个程序面对较小的主存容量时,发生的缺页中断次数就多,当主存容量增加时,缺页中断次数就减少。但从图中可以看出,主存容量增加到80K以后,随着主存容量的增加,缺页中断次数的减少就不明显了。大多数程序都有一个特定点,在这个特定点以后再增加主存容量,缺页中断次数的减少并不明显。据试验分析表明,对每个程序来说,要使其有效工作,它在主存中的页面数应不
6、低于它的总页面数的一半。如果一个有n页的作业,当主存至少分配n/2主存空间块时进入主存执行,系统可以获得高效率。,(2)页面的大小 页面的大小影响页表的长度、页表的检索时间、置换页面的时间、可能的页内零头的大小等,对缺页中断的次数也有一定的影响。如果划分的页面大,一个作业的页面数就少,页表所占用的主存空间少且查表速度快,在系统分配相同主存块的情况下,发生缺页中断的次数减少,降低了缺页中断率,但是一次换页需要的时间延长,可能产生的页内零头所带来的空间浪费较大。反之,页面小,一次换页需要的时间就短,可能产生的页内零头少,空间利用率提高,但是一个作业的页面数多,页表所占用的主存空间长且查表速度慢,在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完全 实现 最近 最少 置换 算法 一件 非常 困难 事情 因为
链接地址:https://www.31doc.com/p-3309861.html