请求页式管理中的页面置换算法性能分析

1、请求页式管理中的页 面置换算法性能分析指导老师： 余宏生组 员：邓祥镭201041210123殷蝶 201041210124柯希杰 201041210125石贤主 201041210126尚晨曦 201041210141请求页式管理中的页面置换算法性能分析（湖北理工学院，黄石435000）摘要：随着虚拟存储技术在操作系统中的应用，大大提高了操作系统的性能，其 中页面置换算法是虚拟存储管理的重要组成局部，页面置换算法的优劣将直接影 响系统的整体性能。随着大量有着不同读写速度的外存设备共存于系统中，单一 置换算法同样影响着系统的整体性能。关键词：操作系统；虚拟存储；页面置换；算法The reque

2、st paging page replacement algorithm performanceanalysisAbstract： With virtual storage technology in the application of the operating system, greatly improve the performance of the operating system, including page replacement algorithm is an important part of virtual storage management page replacem

3、ent algorithm quality will directly affect the overall performance of the system. As the speed of read and write a lot of different peripheral storage devices coexist in the system, a single replacement algorithm also affects the overall performance of the system.Keyword： Operating stystem； Virtual

4、storage； Page replacement； Algorithm1、引言虚拟存储器的实现是建立在离散分 配存储管理方式的基础上的，一般采 用分页请求系统或分段请求系统来实 现。分页（段）请求系统是在分页（段） 系统的基础上，增加了请求调页（段） 功能、页面（分段）置换功能所形成 的页（段）式虚拟存储器系统。它允 许只装入假设干页面（分段）的用户程 序和数据（而非全部程序和数据），便 可以启动运行。以后，再通过调页（段） 功能及页面（分段）置换功能，把所 需要的页面（分段）调入内存，同时 把暂时不运行的页面（分段）换出到 外存上，置换时以页面（分段）为单 位。在请求分页式系统中，每当所要

5、访 问的页面不在内存时，便要产生一缺 页中断，请求操作系统将所缺之页面 调入内存。假设内存已无空间时，为了 保证该进程能正常运行，系统必须从 内存中调出一个页面，但应该将哪个 页面调出，那么必须根据一定的算法来 确定。通常，把选择换出页面的算法 称为页面置换算法（Page_Replacement Algorithms） o一个好的页面置换算法，应具有较 低的页面更换频率。从理论上讲，应 将那些以后不再会访问的页面换出， 或将那些在较长时间内不会再访问的 页面调出。2、传统的页面置换算法传统的页面置换算法主要有FIFO（First In First Out ，先进先出）、最正确 置换算法（Opt

6、imal）、LRU （ Least Recently Used,最近最久未使用）和 LFU （Least Frequently Used,最近最少使用）等算法。先进先出（FIFO）页面置换算法这是最早出现的置换算法。该算法 总是淘汰最先进入内存的页面，即选 择在内存中驻留时间最久的页面予以 淘汰。该算法实现简单只需把一个进 程已调入内存的页面，按先后次序链 接成一个队列，并设置一个指针，称 为替换指针，使它总是指向最老的页 面。但它所依据的条件是各个页面调 入内存的时间，而页面调入的先后并 不能反映页面的使用情况，故此算法 性能一般较差。最正确置换算法OPT（Optimal）它是由Belady

7、于1966年提出的一 种理论上的算法。其所选择的被淘汰 页面，将是以后永不使用的或者是在 最长（未来）时间内不再被访问的页面。 采用最正确置换算法，通常可保证获得 最低的缺页率。但由于人目前还无法 预知一个进程在内存的假设干个页面 中，哪一个页面是未来最长时间内不 再被访问的，因而该算法是无法实现 的，便可以利用此算法来评价其它算 法。最近最久未使用（LRU）置换算 法最近最久未使用（LRU）置换算法， 是根据页面调入内存后的使用情况进 行决策的。由于无法预测各页面将来 的使用情况，只能利用“最近的过去” 作为“最近的将来”的近似，因此， LRU置换算法是选择最近最久未使用 的页面予以淘汰。但

8、是页面的过去和 未来的走向之间并无必然的联系。最近最少使用（LFU）置换算法LFU页面置换算法假定在一段时 间内访问频率较高的页面与那些访问 频率较低的页面相比，更有可能在不 远的将来被访问，因而选择在一段时间内访问频率较低的页面予以淘汰， 即将最近时期使用最少的页面作为淘 汰页。3、程序清单参考实验步骤如下：include stdio.h” char find(int j); int findo(int j); int l(int j);intqueye;double queyelu;char z=%；chara420=7,0,T；270,3；0；4；2,3,0 ,32T；2”,T7OT;/

9、char a;void fifo()/先进先出算法int i=2,mj;queye=1;a10=a00;for(j=1 ;j3)i=1;if(fjnd(j)=,F)/调用查找函数(aij=aOj;for(m=1 ;m4;m+)if(m!=i)amj=amU-1; queye=queye+1;i+1;) else (a1j=a1U-1;a2U=a2j-1;a3U=a30-1；)for(i=0;i4;i+) 输出序列for0=O;j=3 & (a0j=a1j-1 | a0D=a2U-1 | aO0=a3D-1)return (T);elsereturnfF);)void opt()/OPT 置换算

10、法(inta10=a00;/a11=a00;for(j=1;j3;j+)(for(i=1 ;ij+2;i+)if(H)=1)aij=aOj;elseaij=aij-1;)queye=3;for(j=3;j20;j+)(if(find(j)=,F,)(t=findo(j);/ printf(nn%dnHJt);for(m=1 ;m4;m+) if(m!=t)amj=amj-1;/ aij=ai-1j;atU=aOj;queye=queye+1;else(a1j=a1j-1;a2U=a2j-1;a3U=a3U-1;)for(i=0;i4;i+) 输出序列(for(j=0;jj;m-)(if (a1

11、j-1=a0m)x=m;if (a2j-1=a0m)y=m;if (a3D-1=a0m)z=m;)/max=x;t=1;if (yx & yz)t=2;if(zx & zy)t=3;return (t);void lru() /LRU 置换算法void lru() /LRU 置换算法queye=queye+1;int ujj;int k;a10=a00;/a11=a00;for(j=1 ;j3;j+)(for(i=1 ;ij+2;i+)if(H)=1)aij=aOj;elseaij=aij-1;)queye=3;for G=3;j0;i-)(if(i!=u) akj=aij-1;k=k-1;)

12、a3D=a0j;)elsefor(i=0;i4;i+) 输出序列(for(j=0;j20;j+)(printf(%c -);)printf(HnH);)queyelu=queye*100/20;printf (缺页率：%4.1 f%cnn3queyelu,z);intl(intj)查找要替换的位置(if (a0j=a1U-1)return(1);if (a0D=a2j-1)return(2);if (a0j=a3j-1)return(3);void main()(printf(先进先出算法:n)卅。()；printf(最正确置换OPT算法佳) opt()；printf(nLRU 算法:n”)；

13、 lru();for(i=1 ;i3;i+)4.对不同算法的性能进行评价。FIFO算法较易实现，对具有线性 顺序特征的程序比拟适用，而对具有 其他特征的程序那么效率不高，此算法 还可能出现抖动现象(Belady)异常。 LRU算法基于程序的局部性原理，所 以适用用大多数程序，此算实现必须 维护一个特殊的队列一一页面淘汰队 列。OPT算法虽然产生的缺页数最少， 然而，却需要预测程序的页面引用串， 这是无法预知的，不可能对程序的运 行过程做出精确的断言，不过此理论 算法可用做衡量各种具体算法的标 准。5、结论本文首先对虚拟存储器存在的基 本原理进行了分析，知道分页系统存 在的可能性。然后对传统的几种页面 置换算法进行了介绍，利用编写的程 序分析各自的性能，比拟得出了每种 算法的优点和缺点。参考文献：11操作系统清华大学出版社6、附录(程序运行结果)0 17 0 10 17 0 10 0 7 7 71110 0先进先出算法:7 0 1 2 0 3 07 7 7 2 2 2 2缺页率：75.0Z隐佳亶换OPT算法:0 12