http://hi.baidu.com/ilovehaley/blog/item/c6d850805a0c2fdd9123d981.html
在虚拟存储器中,当发生页面失效时,需要从磁盘存储器中调入一页(或一段)到主存储器中。在段式和段页式虚拟存储器中,由于多用户虚页数比主存储器的实页数要多得多。在段式虚拟存储器中,虚存空间中能容纳的程序段数要比主存空间中能存放的相同长度的程序段数多得多。因此,必然会出现当主存中所有页面都已经被占用,或者所有主存空间都已经被占用,而又要从磁盘存储器中调入新页的情况。这时,必须从主存储器中淘汰掉一个不常用的页面,以便腾出主存空间来存放新调入的页面。那么,按照什么样的规则替换主存储器中的页面呢?这就是页面替换算法要解决的问题。
以下,为了叙述方便,主要介绍页式和段页式虚拟存储器中的页面替换算法及其实现方法,在这两种虚拟存储器中都是以页面为单位进行调度的。而段式虚拟存储器是以程序段为单位进行调度的,但是它所采用的替换算法及算法的实现方法都是相同的。
评价一个页面替换算法好坏的标准主要有两个,一是命中率要高,二是算法要容易实现。要提高一个页面替换算法的命中率,首先要使这种算法能正确反映程序的局部性,其次是这种算法要能够充分利用主存中页面调度情况的历史信息,或者能够预测主存中将要发生的页面调度情况。
页面替换算法主要用于如下几个地方:
(1) 虚拟存储器中,主存页面(或程序段)的替换。
(2) Cache中的块替换。
(3) 虚拟存储器的快慢表中,快表的替换。
(4) 虚拟存储器中,用户基地址寄存器的替换。
在虚拟存储器中常用的页面替换算法有如下几种:
(1) 随机算法,即RAND算法(Random algorithm)。利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单,而且容易实现。但是,这种算法完全没有利用主存储器中页面调度情况的历史信息,也没有反映程序的局部性,所以命中率比较低。
(2) 先进先出算法,即FIFO算法(First-In First-Out algorithm)。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现,能够利用主存储器中页面调度情况的历史信息,但是,没有反映程序的局部性。因为最先调入主存的页面,很可能也是经常要使用的页面。
(3) 近期最少使用算法,即LFU算法(Least Frequently Used algorithm)。这种算法选择近期最少访问的页面作为被替换的页面。显然,这是一种非常合理的算法,因为到目前为止最少使用的页面,很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息,又正确反映了程序的局部性。但是,这种算法实现起来非常困难,它要为每个页面设置一个很长的计数器,并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时,要从所有计数器中找出一个计数值最大的计数器。因此,通常采用如下一种相对比较简单的方法。
(4) 最久没有使用算法,即LRU算法(Least Recently Used algorithm)。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无",因此,实现起来比较容易。
(5) 最优替换算法,即OPT算法(OPTimal replacement algorithm)。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的,它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然,这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面,这种替换算法的命中率一定是最高的,它就是最优替换算法。
要实现OPT算法,唯一的办法是让程序先执行一遍,记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然,这样做是不现实的。因此,OPT算法只是一种理想化的算法,然而,它也是一种很有用的算法。实际上,经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下,哪一种页面替换算法的命中率与OPT算法最接近,那么,它就是一种比较好的页面替换算法。
分享到:
相关推荐
共四种:FIFO\LRU\LFU\OPT 。在VC环境下运行完全成功。 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储...
操作系统课设 分页式存储管理(内含OPT,FIFO,LRU,LFU四种算法,用到了线程),用eclipse打开,我给的是创建的整个源包,打开就可以运行,这个是经过最佳改正过的
操作系统页面置换算法模拟实现,fifo、lfu、lru、opt,界面由MFC实现
(1)输入一个逻辑页面访问序列和随机产生逻辑页面访问序列,由四个线程同时完成每个算法; (2)能够设定驻留内存页面的个数、内存的存取时间、缺页中断的时间、快表的时间,并可以暂停和继续系统的执行; (3)...
操作系统页面置换LRU,FIFO,OPT,LFU算法实现代码,使用C#动态实现,有TLB快表,可设置页面数量、驻留集大小、自动生成十六进制地址码,分析页号,可设置TLB时间,访问内存时间。
C语言 页面置换算法 OPT FIFO LRU clock
带有界面的算法,视自己需求下载。 主界面选择使用三种算法的一个。在创建中输入页面数,随机生成页面。在指定物理块中实现置换。点击查看将置换的过程显示出来。
这是一个自己完成软件工程的操作系统课程课程设计题目:此程序用于模拟虚拟磁盘页面置换算法,实现了FIFO页面置换算法和LRU页面置换算法,获得课程设计优秀的好成绩
设计一个虚拟存储区和内存工作区 , 并使用下述算法计算访问命中率。...(1) 先进先出的算法 (FIFO) (2 )最近最少使用算法 (LRU) (3) 最佳淘汰算法 (OPT) (4) 最少访问页面算法 (LFU) (5 )最近最不经常使用算法 (NUR)
模拟仿真请求分页调度算法OPT、FIFO、LRU、LFU、CLOCK等模拟页面调度算法,并提供性能比较分析功能。用MFC界面实现
(3) 最佳淘汰算法(OPT)(4) 最少访问页面算法(LFU) (5) 最近最不经常使用算法(NUR) 命中率=1-页面失效次数/页地址流长度 <程序设计> 本实验的程序设计基本上按照实验内容进行。即首先用 srand()和 rand()函数定 义和...
感谢csdn上的关于opt算法的前辈的资源,这个是对原来的改进,设为3分是为了不想抢原作者生意orz,希望对大家有用。tks
OPT算法、FIFO算法、LRU算法、LFU算法的具体实现
写了八个页面替换的算法,算是比较全了,包括MFC,clock,FIFO,LRU等算法,并且用模块化的思路,输出也用表格
输入页号数 再输入页号序列 选择相应的算法执行
(1) 输入一个逻辑页面访问序列和随机产生逻辑页面访问序列,由四个线程同时完成每个算法; //(2) 能够设定驻留内存页面的个数; (3) 能够随机输入存取的逻辑页面的页号序列; (4) 能够随机产生存取的逻辑页面的页号...
页面淘汰算法采用 FIFO页面淘汰算法,并且在淘汰一页时,判断它是否被改写过,如果被修改过,将它写回到辅存。 开始,创建页表,输入一条指令:是否修改以及逻辑地址,执行指令,取指令中的页号,查页表中相应的表...
通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求式页式存储管理的页面置换算法。运用到FIFO算法、LRU算法、OPT算法、LFU算法。
操作系统课程设计报告-页面置换算法模拟系统,模拟了进先出的算法(FIFO),最佳淘汰算法(OPT),最近最久未使用算法(LRU),最少访问页面算法(LFU),并含有DOS界面的菜单选择模块
置换算法:OPT、FIFO、LRU、LFU和NRU算法。 用C语言设计一个程序,模拟一作业的执行过程。设该作业共有320条指令,即它的地址空间为32页,目前它的所有页面都还未调入内存。在模拟过程中,如果所访问的指令已经在...