《操作系统中页面置换算法的对比研究.pdf》由会员分享，可在线阅读，更多相关《操作系统中页面置换算法的对比研究.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2 7 卷第3 期广西民族师范学院学报VoL27N o 32 0 10 年6 月J O U R N A LO FG U A N G X lN O R M A LU N I V E R S I T YF O RN A T I O N A L I T I E SJ u n e 2 0 10操作系统中页面置换算法的对比研究江波(贺州学院计算机科学与工程系，广西贺州5 4 2 8 0 0)摘要：在操作系统的页面置换过程中，采取何种算法，需要进行分析，才能提高系统的性能。在W i n d o w sX P 中，用V i s u a lC+实现先进先出页面置换算法和最少使用页面置换算法，并用数据对这两种
2、页面置换算法进行仿真实验，对实验结果进行了分析和比较。关健词：先进先出页面置换算法；最近最少使用页面置换算法；操作系统；缺页率中图分类号：T P 3 1 6 7文献标识码：A文章编号：1 6 7 4 8 8 9 1(2 0 1 0)0 3-0 0 5 6-0 4C o m p a r a t i v eR e s e a r c ho nP a g eR e p l a c e m e n tA l g o r i t h m si nO p e r a t i n gS y s t e mJ I A N GB o(D e p a r t m e n to fC o m p u t e rS
3、c i e n c ea n dE n g i n e e 血g，H e z h o uU n i v e r s i t y，G u a n g x iH c z h o u，5 4 2 8 0 0，c l l i r 曲A b s t r a c t：1 1 l i sp a p e rs t u d i e st h eu s eo fV i s u a lC+toa c h i e v et h et w op a g er e p l a c e m e n ta l g o r i 山螂i nW i n d o w sX F。a n dt h ed a t at os i m u
4、l a t et h e s et w op a g er e p l a c e m e n ta g o,i t h m 诹山e x p e r i m e n t a lr e s u l t sa n a l y z e dc o m p a r e d K e yW o r d s：f i r s ti n6 域o u tp a g er e p l a c e m e n ta g o,i t 嘁l e a s tr e c e n d yu s e dp a g er e p l a c e m e n ta 1 9 0 t i d l m；o p m t i n gs y s
5、t e m；p a g ef a u l tr a o e引言页面置换算法 t-7 塌一研研确1 0 1 0-1 0 1 4,3 3 删-4 1。4 3,6 3-6 4，删主要是记录内存的忙闲状态。为进程分配和释放内存。当主存的空间太小而无法装入所有的进程时就需要在内存和硬盘之间进行调度操作。多数操作系统只采用某种特定的页面置换算法进行置换无法预先探测当前运行进程的页面访问模式。因此不能根据不同的页面访问模式，选用不同的页面置换算法。当然，如果能对不同的访问模式选取相应的页面置换算法。将提高操作系统的调度能力。进而提高整个系统的性能。1 页面置换算法在操作系统的运行过程中，若发现内存已无空闲的
6、空间。为了确保系统中的进程能正常运行，就涉及到内存和磁盘的程序或数据交换。然而将哪些页面调入和调出，就需要根据算法来确定。这些算法被称为页面置换算法(p a g er e p l a c e m e n ta l g o-r i t h m s)。1 1 先进先出页面置换算法先进先出(f i r s ti nf i r s to u t，F I F O)算法的基本思想是：每次置换最先调入内存的页面。即将内存中等待时间最长的页面进行置换。此算法的适用范围是顺序结构程序。因为在这种程序中。最先进入内存的页面不再被访问的可能性最大。但在实际应用中。由于程序的局部性原理，经常会出现程序的某段或者数据的
7、某个区域，在进程生命周期期间频繁地被调用。此种情况下，假如采用F I F O 算法，这些页面就会被反复调入调出。极大地影响了系统的性能。1 2 最近最少使用页面置换算法最近最少使用(1 e a s tr e c e n t l yu s e d，L R U)算法【1】1 5 3-L V,3 11 0 1 0 1 4 的基本思想是：依据物理块中最近使用页面情况预测未来使用情况。选择最近最少使用的页面进行置换。即置换最长时间未被使用的页面。根据程序的局部性原理在过去一段时间里不经常被访问的页面，在将来被访问的可能性会很收稿日期：2 0 1 0 0 4 1 6作者简介：江波(1 9 7 0 一)。男
8、，广西贺州市人。贺州学院讲师，主要研究方向为数据挖掘、计算机教育和网络安全。一5 6 万方数据2 0 1 0 年第3 期江波操作系统中页面置换算法的对比研究6 月2 5 日出版一一 内 厅 ，P小。L R U 算法考虑到程序运行的动态性，并根据对情况。页面在执行过程中的使用情况来推测将来页面的使用情况。2 页面置换算法的仿真只有通过仿真实验，才能比较F I F O 算法和L R U 算法的优劣。以此分析两种算法是否符合各自思想，同时对仿真的结果进行分析，找出影响两种算法的因素和两种算法的差别。仿真系统为W i n d o w sx p。编程工具为M i c r o s o f tV i s u
9、 a lC+6 0。2 1 仿真实验步骤仿真实验的过程必须涉及到各方面的数据以便对算法更好的进行测试。对于这两种算法，本文采用黑盒测试的方法，只对是否能实现这两个算法的功能以及它们的运行结果是否和预知的结果一致。对两种算法进行仿真实验的步骤：(1)输入物理块的数值比进程要访问的页面总数大时，如果显示出错信息，表明达到预期的结果；反之，表明不满足预期的结果，需要对程序进行修改。(2)输入物理块的数值等于进程要访问的页面总数时，预期的结果没有产生出错信息。并且选择执行任何一种算法时，缺页率都为1，能够显示每一轮的置换过程。(3)输人物理块的数值小于或等于进程要访问的页面总数。且输入的进程要访问的页
10、面序列不变时不断增大物理块的数值。分别使用F I F O 算法和L R U 分析结果是否符合预期的结果以及变化的情况。(4)输入物理块的数值小于或等于进程要访问的页面总数，且物理块的数值和进程要访问的页面序列总数不变时，分别使用F I F O 算法和L R U 分析结果是否符合预期的结果以及变化的情况。(5)在输入物理块的数值小于或等于进程要访问的页面总数且物理块的数值不变时。改变进程要访问的页面序列和总数，分别使用F I F O 算法和L R U 分析结果是否符合预期的结果以及变化的(6)输入物理块的数值小于或等于进程要访问的页面总数和进程要访问的页面序列相同时，分别使用两种算法进行测试。分
11、析所得的结果。2 2 仿真实验结果(1)当不输入任何数据直接点击F I F O 算法或者L R U 算法时，将会出现提示输入数据。显示提示输入数据如图1 所示。圈1 显示提示输入数据(2)由于一些变量在开始的时候赋予了初值，某些数据显示是初值。页面置换算法模拟界面如图2 所示。图2 页面置换算法模拟界面(3)当输人物理块的数值比进程要访问的页面总数大时，假设物理块数为5，进程要访问的页面总数为3。根据所显示的结果表明测试的结果达到预期的结果。测试的结果如图3 所示。一5 7 万方数据第2 7 卷广西民族师范学院学报(总第7 0 期)、一一，(5)当输入的物理块数为3，进程的页面总数为1 2，进
12、程访问页面序列为0，1，2，3，0，l，4，0，1，2，3，4 时，采用兀F O 算法所显示的结果如图4 所示。圈3 出错提示信息(4)当物理块的数值小于或等于进程要访问的页面总数并且输入的进程要访问的页面序列不变时，不断增大物理块的数值，使用F I F O 算法对所得的数据分析结果如表1 所示，使用L R U 算法对所得的数据分析结果如表2 所示。裹1F I F O 算法对所得的数据分析结果访问次数序列Ol2 3 4 5 6 7 891 0l i1 2页面访问序列0l2 3 0l4012 3 40 0 0 3 3 3444444M=3-1l110 000 02 2 2-1-12 2 21l1
13、1l3 3缺页次数为9 次。缺页中断率F=7 5 访问次数序列012 3 4 5 6 7 8 9l O 1 1 1 2页面访问序列012 3 014O12 3 4OO0O0044443 3M-4一lllllll0OO04-1-12 2 2 2 2lll33缺页次数为1 0 次。缺页中断率F=8 3 3 裹2L F I U 算法对所得的数据分析结果访问次数序列Ol2 3 4 5 6 7 8 91 01 11 2页面访问序列Ol2 3 Ol40l2 3 40 003 3344 4 2 2 2M=3-1lllOO0OO03 31-12 2 2 2111ll4缺页次数为1 0 次缺页中断率F=8 3
14、3 访问次数序列O12 3 4 5 6 7 8 91 0 1 1 1 2页面访问序列012 3 O140l2 34O0O 0 0 000 0O0 4M-4-1一l2 2 2 244443 3-1一l-13 3 3 3 3 3 2 2 2缺页次数为8 次。缺页中断率F=6 6 6 7 一5 8 一圈4F I F O 算法所显示的结果(6)只改变进程要访问的页面序列但总数不变的情况下。使用F I F O 算法对数据分析结果如表3所示。襄3 改变页面序列使用F I F O 算法对数据分析结果访问次数序列Ol23 45 67891 0页面访问序列012 010l234000 00 0003 3M=3-
15、11llllll14-1-12 22 2222 2缺页次数为5 次。缺页中断率F=5 0 访问次数序列0l23 456 7891 0页面访问序列0l2 O1O123400O3 33 322 2M=3-1l1l10 0O33-1-12 2221l14缺页次数为9 次缺页中断率F=9 0 4 仿真实验结果分析通过仿真实验结果以及对更多的数据进行测试的结果分析和比较，得出如下结论：(1)由表1 的数据显示当在进程页面的访问序列不变的情况下，物理块数为3 时，缺页率为7 5；而物理块数为4 时。缺页率约为8 3 3。因此。F I F O 算法可能发生B e l a d y 异常现象。虽然通过表2 的数
16、据以及大量的数据对L R U 算法进行验证没有出现B e l a d y 异常现象。但是并不能说明其不可能产生B e l a d y 异常现象。实际上大量的研究表明L R U 算法不会出现B e l a d y 异常现象。万方数据2 0 1 0 年第3 期江波操作系统中页面置换算法的对比研究6 月2 5 日出版、阀 疗 一 一 ，(2)影响缺页率的因素有分配给进程的物理块面置换算法的基本思想。在W i n d o w sX P 中，用数、页面置换算法和进程对页面的访问序列。虽然V i s u a lC+实现这两种页面置换算法，并用数据对由以上的数据分析得出了几种影响缺页率的因素但是实际上影响缺
17、页率的因素还有页面大小、快表的设置等。(3)通过仿真实验可以看出，虽然有时H F O算法的缺页率比L R U 算法的缺页率低但是在大多情况下，L R U 算法的缺页率都比F I F 0 算法的缺页率低。(4)L R U 算法的优点是其最接近最优的页面置换算法，即它缺页率是比较低的，缺点是实现L R U算法需要硬件的支持，增加了系统的成本。(5)F I F O 算法的优点是其实现起来比较简单，可以不需要硬件的支持，因而不需要增加系统的成本。其缺点是在大多少情况下，缺页率比较低或会产生B e l a d y 异常现象。5 结论论述先进先出页面置换算法和最近最少使用页这两种页面置换算法进行仿真实验，
18、对实验结果进行了分析，比较两种算法的性能。参考文献：【1】李占胜，半会娟，李艳平，张立松一种对L R F U 置换策略的自适应改进田计算机工程与应用，2 0 0 8，4 4(1 7)【2】高蔹蛟，蒋泽军，王丽芳文件C a c h e 自适应策略研究I J 计算机工程与应用，2 0 0 9，4 5(2 4)【3】缸俊清，郑浩然，李恒等一种基于有限记忆多L I K U 的W e b 缓存替换算法田小型微型计算机系统，2 0 0 8，2 9(6)【4】田小波，陈蜀宇基于最小效用的流媒体缓存替换算法【I】计算机应用，2 0 0 7，2 70)【5】罗益辉，谢长生，张成峰存储系统的集中式C a c h
19、e 替换算法华中科技大学学报：自然科学版，2 0 0 6，3 4(1 1)【6】郭丙轩，张京莉，张志超基于内存池的空问数据调度算法】计算机工程，2 0 0 8，3 40)阴王明路，王希敏，王哲嵌入式系统中池式内存分配方法的分析田计算机与数字工程，2 0 0 8，3 6(责任编辑：罗瑞宁责任校对：施扬铃)一5 9 万方数据操作系统中页面置换算法的对比研究操作系统中页面置换算法的对比研究作者：江波，JIANG Bo作者单位：贺州学院,计算机科学与工程系,广西,贺州,542800刊名：广西民族师范学院学报英文刊名：JOURNAL OF NANNING TEACHERS COLLEGE年，卷(期)：2
20、010,27(3)参考文献(7条)参考文献(7条)1.王明路;王希敏;王哲 嵌入式系统中池式内存分配方法的分析期刊论文-计算机与数字工程 2008(2)2.邦丙轩;张京莉;张志超 基于内存池的空间数据调度算法 2008(03)3.罗益辉;谢长生;张成峰 存储系统的集中式Cache替换算法期刊论文-华中科技大学学报(自然科学版)2006(11)4.田小波;陈蜀宇 基于最小效用的流媒体缓存替换算法期刊论文-计算机应用 2007(03)5.缸俊清;郑浩然;李恒 一种基于有限记忆多LRU的Web缓存替换算法期刊论文-小型微型计算机系统 2008(06)6.高薇蛟;蒋泽军;王丽芳 文件Cache自适应策略研究期刊论文-计算机工程与应用 2009(24)7.李占胜;毕会娟;李艳平;张立松 一种对LRFU置换策略的自适应改进期刊论文-计算机工程与应用 2008(17)本文链接：http:/