【转】页面替换算法
在虚拟存储器中,当发生页面失效时,需要从磁盘存储器中调入一页(或一段)到主存储器中。在段式和段页式虚拟存储器中,由于多用户虚页数比主存储器的实页数要多得多。在段式虚拟存储器中,虚存空间中能容纳的程序段数要比主存空间中能存放的相同长度的程序段数多得多。因此,必然会出现当主存中所有页面都已经被占用,或者所有主存空间都已经被占用,而又要从磁盘存储器中调入新页的情况。这时,必须从主存储器中淘汰掉一个不常用的页面,以便腾出主存空间来存放新调入的页面。那么,按照什么样的规则替换主存储器中的页面呢?这就是页面替换算法要解决的问题。
以下,为了叙述方便,主要介绍页式和段页式虚拟存储器中的页面替换算法及其实现方法,在这两种虚拟存储器中都是以页面为单位进行调度的。而段式虚拟存储器是以程序段为单位进行调度的,但是它所采用的替换算法及算法的实现方法都是相同的。
评价一个页面替换算法好坏的标准主要有两个,一是命中率要高,二是算法要容易实现。要提高一个页面替换算法的命中率,首先要使这种算法能正确反映程序的局部性,其次是这种算法要能够充分利用主存中页面调度情况的历史信息,或者能够预测主存中将要发生的页面调度情况。
页面替换算法主要用于如下几个地方:
(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算法最接近,那么,它就是一种比较好的页面替换算法。
分享到:
相关推荐
理解页面替换算法的作用和不同的页面替换算法确定被替换页面的原则
自己写的页面置换算法,分别实现了最佳置换算法,随机置换算法,LRU算法,FIFO算法,CLOCK算法,并计算了各算法的缺页率,便以比较各算法的优劣。
页面替换算法opt+fifo+lru+clock页面替换算法opt+fifo+lru+clock
页面替换算法,包含fifo lru clock,采用c++编写,操作系统的同学可以看看
3.3 引用串的生成实验三页面替换算法 • LRU 算法则需要一个尺寸为F 的数组,该数组用来实现排队功能: 每次处理一个新的页面引用时,则把该页放置在队列的末尾。这样, 每当需要淘汰一个页面时,从队首取到的即最长...
vc++ 6.0实现页面替换算法FIFO和LRU,界面优美,实现了功能。
通过模拟页面管理中各种页面替换算法,进一步理解各种算法的性能,并且进一步理解各种页面替换算法的优缺点。
包含FIFO,最优替换算法,随机替换算法,clock替换算法,LRU替换算法的c++项目
页面替换算法,内存管理优化策略,基于LRU,OPT, CLOCK等。
lru页面替换算法的模拟实现程序。 操作系统实验课上做的
操作系统 页面替换算法(OPT最佳置换算法与LRU最近最久未使用算法)
页面置换算法模拟实验报告.pdf
(1)采用页式分配存储方案,通过分别计算不同算法的命中率来比较算法的优劣,同时也考虑页面大小及内存实际容量对命中率的影响 。 (2)实现对FIFO,LRU算法的模拟
操作系统第三次实验报告_页面替换算法.docx
页面置换算法 #pragma once #include #include "Pclass.h" using namespace std; class Allocation { private: int pnum;//页面数 int bnum;//分配块数 //int ID; int num;//访问页面次数 Pclass * block;/...
基于C++的请求分页虚拟页面替换算法
操作系统第三次实验报告_页面替换算法.pdf
本程序主要用于模拟LRU算法(内存单元在10个以内);支持动态输入数字 和内存单元个数;输出结果为每步的内存存储情况及缺页统计情况。
简单的clock页面置换算法 采用CLOCK置换算法仿真请求分页系统 1、设计目的:用高级语言编写和调试一个内存分配程序,加深对内存分配算法的理解。 2、设计要求: 1) 实现请求分页存储管理方式的页面置换算法:...
本课题的目的是要实现缺页处理程序...为了减少缺页和将页面从内存淘汰到磁盘的次数,要求你实现五种页面替换算法。 NRU(Not Recently Used)算法 SC(Second Chance)算法 Clock算法 Working Set算法 Aging算法