常用页面置换算法实现

PAGE摘要随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机最重要的环节之一，也是计算机专业学生的重要的一门专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用，一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性，由于操作系统中各种软硬件资源的管理，内容比较繁琐，具有很强的实践性。页面置换算法（也称页面淘汰算法）是用来确定应该淘汰哪一页的一种策略。页面置换算法的优劣直接影响到系统的效率，若选用的算法不合适，可能会出现这种现象：刚被淘汰出去的页，过后不久又要访问它，需要再次调入，而调入后不久又再次被淘汰，然后又要访问，如此反复，使得系统把大部分时间用在了页面的调进与调出上，这种现象称为抖动或颠簸。比较常用的置换算法有以下几种：最佳置换算法（OPT）；先进先出算法（FIFO）；最近最就未使用算法（LRU）。关键词：页面置换；FIFO算法；LRU算法目录TOC\o"1-3"\h\u171001绪论 1293801.1问题的提出 11631.2问题的描述 1149432需求分析 2279183总体设计 3224103.1设计要求 3271183.2设计目的 3289033.3相关知识 4180473.3.1虚拟存储器的引入 4223673.3.2虚拟存储器的定义 4154153.3.3虚拟存储器的实现方式 486993.3.4页面分配 4255333.3.5页面置换算法 5300753.3.6运行环境 5272984详细设计 6158034.1算法思想 6224544.2设计流程图 738755程序调试 9233445.1主界面 9227115.2进行初始化 9207495.3载入数据 1049905.4进入置换算法选择界面 1139055.5运算中延迟操作 11169915.6三种算法演示结果 1299195.7退出界面 1328069136566设计总结 1424508参考文献 156150致谢 1621753附录 171绪论1.1问题的提出在存储器管理方式中，有一个特点，就是当要求作业全部装入内存才能运行。但是这样就存在两种情况：有的作业很大，不能全部装入内存，致使作业无法进行。有大量作业要求运行时，内存容量不足容纳所有作业，而虚拟内存技术正是在逻辑上扩充内存容量，将会解决以上两个问题，所以，可以当进程开始运行时，先将一部分程序装入内存，另一部分暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时系统自动选择部分内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其它进程使用。通常，把选择换出页面的算法称为页面置换算法，模拟页面置换算法用以客观解决内存不足的矛盾。1.2问题的描述1966年Belady在理论上提出最优页面置换算法（OPT）,此外还有先进先出（FIFO），最少使用置换算法（LRU）。不同存储设备有着不同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写速度的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性能会有很大的提高。操作系统的虚拟存储器管理技术中，有一项比较重要的分支叫分页存储管理。分页管理是在页架中装入一些需要使用或过去使用过的页面，但是页架的数量是有限的，这里就会用到一些页面置换算法，使得页面访问的效率提高。判断一个置换算法优劣的指标就是缺页率，缺页是指当前的页架中没有需要访问的页面，而需要将该页面加入其中一个页架。缺页率＝访问缺页次数/访问总次数。

2需求分析所谓页面置换算法，是操作系统中对于页式存储管理中的一种软件虚拟存储管理方式实现的一种具体的算法操作，页面置换算法的优劣将会影响虚拟存储系统的性能，进而影响整个系统的性能。页面置换算法是用来确定应该淘汰哪一页的一种策略。在进程的运行过程中，若所要访问的页面不在内存中，需要调入页面时，选择内存中的那个物理页面将其调出，通常只能在局部性原理的指导下，把未来不在使用的页面调出，如何选择页面调度策略即页面置换算法至关重要，置换算法的好坏，直接影响着系统的性能，因此我们有必要将常见的FIFO、LRU、OPT三种算法进行比较，分析性能，因此我们需要选择一种好的算法来对内存进行虚拟扩充，提高内存利用率。

3总体设计3.1设计要求设计一个虚拟存储区和内存工作区，编程序演示下述算法的具体实现过程，并计算访问命中率：要求设计主界面以灵活选择某算法，且以下算法都要实现：（1）最佳置换算法(OPT)：置换策略是将以后永不使用的的页面换出，若无这样的页面存在，则应选择最长时间不需要访问的页面，最佳置换算法本身不是一种实际的方法，因为页面访问的未来顺序是不知道的。（2）先进先出算法(FIFO)：这种算法的思想是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。这种算法的出发点是最早调入主存中的页，其不再使用的可能性会大一些，先进先出置换算法的实现比较简单，对具有按现象顺序访问的程序比较合适，而对其他情况则效率不高，因为经常被访问的页，往往在主存中也停留的最久，结果这些常用的页终因变老而不得不被淘汰。（3）最近最久未使用算法(LRU)：这种算法的思想是选择最近一段时间内最长时间没有被访问过的页淘汰，这种算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问，或者反过来说，如果某页很长时间未被访问，则他在最近一段时间也不会被访问。利用局部性原理，根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问。所以，这种算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。

3.2设计目的（1）用C语言编写OPT、FIFO、LRU三种置换算法。（2）熟悉内存分页管理策略。（3）了解页面置换的算法。（4）掌握一般常用的调度算法。（5）根据方案使算法得以模拟实现。（6）锻炼知识的运用能力和实践能力。3.3相关知识3.3.1虚拟存储器的引入在几乎所有程序的执行中，在一段时间内往往呈现出高度的局部性，即程序对内存的访问时不均匀的，表现在时间与空间两方面：时间局部性是一条指令被执行后，那么它可能很快会被再次执行。程序设计中经常使用的循环、子程序、堆栈、计数活累计变量等程序结构都反映了时间局部性。空间局部性是指若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问。程序代码的顺序执行，对线性数据结构的访问或处理，以及程序中往往把常用变量存放在一起等都反映出空间局部性。局部性原理使得虚拟存储技术的实现成为可能。3.3.2虚拟存储器的定义所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体的说，虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。实际上，用户所看到的大容量只是一种感觉，是虚的，故称之为虚拟存储器。其逻辑容量由内存和外存容量之和所决定，其运行速度接近于内存速度，成本又接近于外存。可见，虚拟存储器是一种性能非常卓越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。但虚拟存储器并非可以无限大，其容量受外存大小和指令中地址长度两方面的限制。3.3.3虚拟存储器的实现方式分页请求系统，它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页面形式虚拟存储系统。请求分段系统，它是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式虚拟存储系统。3.3.4页面分配平均分配算法，是将系统中所有可供分配的物理块，平均分配给各个进程。按比例分配算法，根据进程的大小按比例分配物理块。考虑优先的分配算法，把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据个进程的优先权，适当的增加其相应份额后，分配给各进程。3.3.5页面置换算法常用的页面置换算法有最佳置换算法（OPT）、先进先出置换算法（FIFO）、最近最久未使用置换算法（LRU）、时钟置换算法（Clock）、最近最少使用算法（LFU）、页面缓冲算法（PBA）等。3.3.6运行环境VisualC++6.0由Microsoft开发,它不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境。VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。Microsoft的主力软件产品。VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++6.0已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用有很大的局限性，只适用于Windows2000,WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。VisualC++6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。

4详细设计4.1算法思想

在置换算法中，主要涉及了先来先服务、最近最久未使用和最佳淘汰算法。选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：OPT基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组next[mSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。FIFO基本思想：是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。LRU基本思想：是用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。数组flag[10]标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。

4.2设计流程图分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第一页等。相应地，也把内存空间分成与页面相同大小的若干个存储快，称为（物理）快或页框（frame），也同样为它们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应是2的幂，通常为512B—8KB。在编写程序时，我们需要画出其流程图，然后根据流程图来编写程序，所以流程图是必不可少的一环，在页面置换算法中，首先设置全局变量，确定物理块和页面的大小，然后载入数据，进入置换算法，选择所要执行的算法运行，当运行结束后，退出完成，这就是流程图的大体框架。具体的流程图如下图4.1所示。将页号放入物理块中，编号加1将页号放入物理块中，编号加1引用串编号大于物理块数?载入页号序列，从第0个得到页号开始页号在物理块中?根据选择的置换算法完成置换页号序列载完?结束是否是是是是图4.1程序流程图5程序调试5.1主界面刚开始程序运行时，产生初始界面，显示了我们所设计的课题以及我和搭档的学号和姓名，如下图5.1所示：图5.1主界面5.2进行初始化对物理块和页面号进行初始化，输入所需的物理块的个数、页面号引用串的个数和页面号，界面如下图5.2所示：图5.2初始化界面

5.3载入数据对所输入的页面号进行载入并且进入页面置换的选择界面，如下图5.3、图5.4所示：图5.3数据载入界面图5.4进入算法界面

5.4进入置换算法选择界面在该界面对置换算法进行选择，有三种置换算法，依据所需的置换算法进行选择，界面如下图5.5所示：图5.5算法选择界面5.5运算中延迟操作用先进先出的算法进行页面置换算法，因为系统要进行相关计算，所以处于延迟状态，如图5.6所示：图5.6运算延迟界面

5.6三种算法演示结果用FIFO算法计算出缺页次数为15，缺页率为15/20，并且访问命中率为25%，如图5.7所示：图5.7FIFO算法界面用LRU算法进行相同的操作，其缺页次数为12，缺页率为12/20，访问命中率为40%，如图5.8所示：图5.8LRU算法界面用OPT算法进行与前两种相同的操作，其缺页次数为9，访问的命中率为55%，如图5.9所示：图5.9OPT算法界面5.7退出界面当对置换算法完成后，进行退出操作，如图5.10所示：图5.10退出界面

6设计总结页面置换算法是操作系统中对虚拟存储技术中必不可少的一种置换算法，本次课程设计就页面置换算法中的三种算法进行了编译，而这次课程设计的主要是最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）的页面置换算法进行编译，因此对其它的一些算法没有涉及到，但是在学习操作系统的时候，都有涉及一些其它的算法，这是在完成课程的同时需要掌握的内容，页面走向是根据用户输入页面走向长度和页表长度随机的布局产生的，在编程时要确保把算法写对。通过本次课程设计知道了存储管理的主要功能之一是合理地分配空间，请求页式管理是一种常用的虚拟存储技术。刚开始时由于编译代码是在书上找到的资料按照要求编译进去会出现一些没有定义的变量和字符，以及各种函数的运用，出现问题时主要通过上网去查或者问同学，通过这次课程设计我觉得团队要互相合作才能做出好的东西出来，对于不懂的应该立刻去查，这样自己才能学到很多，并且不容易忘记。参考文献[1]严蔚敏,吴伟民.数据结构.清华大学出版社,2005[2]谭浩强.C语言程序设计.清华大学出版社,2005[3]于帆,赵妮.程序设计基础.清华大学出版社,2006[4]汤小丹,梁红兵,哲凤屏,汤子瀛.计算机操作系统.西安电子科技大学出版社,2007[5]汤子瀛，哲凤屏.计算机操作系统.西安电子科技大学学出版社，1996[6]王万森.计算机操作系统原理.高等教育出版社，2001[7]周长林，左万历.计算机\o"操作系统教程"操作系统教程.高等教育出版社，1994[8]黄廷辉，王宇英.\o"Linux操作系统应用教程"计算机操作系统实践教程.清华大学出版社，2007[9]殷兆麟.计算机操作系统.清华大学出版社，2007[10]张尧学，史美林，张高.计算机操作系统教程.清华大学出版社，1993[11]刘振鹏，张明.操作系统.中国铁道出版社，2007[12]曾平.操作系统考研指导.清华大学出版社，2003致谢首先感谢学校为我们安排的这次课程设计，通过这次课程设计的安排和老师为我们讲解的一些知识，解决的一些问题，我收获了很多，在很多方面得到了锻炼、提高。例如，对于计算机是如何利用很小的内存空间运行很大的应用程序，以前对这个概念是懵懵懂懂，但要自己真正的描述出来肯定是摸不着头脑的，只知道是利用了虚拟存储技术，但是通过此次课程设计对典型的虚拟存储技术的描绘、模拟，深深理解了它的方式方法及其所有优点、可行性，并通过不断地调试加深了印象，同时也要感谢叫我们课程设计的陈老师和知道我们课程设计的马老师，没有对课程的学习我是不会这么顺利的完成的，还要感谢帮助过我的同学，让我受益颇多。

附录#include<stdio.h>#include<stdlib.h>#include<conio.h>/*全局变量*/intmSIZE;/*物理块数*/intpSIZE;/*页面号引用串个数*/staticintmemery[10]={0};/*物理块中的页号*/staticintpage[100]={0};/*页面号引用串*/staticinttemp[100][10]={0};/*辅助数组*//*置换算法函数*/voidFIFO();voidLRU();voidOPT();/*辅助函数*/voidprint(unsignedintt);voiddesignBy();voiddownload();voidmDelay(unsignedintDelay);/*主函数*/voidmain(){inti,k,code; system("color0A"); designBy(); printf("┃请按任意键进行初始化操作...┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n"); printf(">>>"); getch(); system("cls"); system("color0B"); printf("请输入物理块的个数(M<=10)："); scanf("%d",&mSIZE); printf("请输入页面号引用串的个数(P<=100)："); scanf("%d",&pSIZE); puts("请依次输入页面号引用串(连续输入，无需隔开)："); for(i=0;i<pSIZE;i++)scanf("%1d",&page[i]); download(); system("cls"); system("color0E");do{ puts("输入的页面号引用串为："); for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++) { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf("%d\n",page[i]); else printf("%d",page[i]); } } printf("***********************\n");printf("*请选择页面置换算法：\t\t\t*\n"); printf("**\n");printf("*1.先进先出(FIFO)2.最近最久未使用(LRU)*\n"); printf("*3.最佳(OPT)4.退出*\n"); printf("***********************\n");printf("请选择操作：[]\b\b");scanf("%d",&code);switch(code){case1:FIFO();break;case2:LRU();break;case3:OPT();break;case4: system("cls"); system("color0A"); designBy();/*显示设计者信息后退出*/ printf("┃谢谢使用页面置换算法演示器!正版授权㊣┃\n"); printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");exit(0); default: printf("输入错误，请重新输入：");} printf("按任意键重新选择置换算法：>>>"); getch(); system("cls");}while(code!=4); getch();}/*载入数据*/voiddownload(){ inti; system("color0D"); printf("╔════════════╗\n"); printf("║正在载入数据，请稍候!!!║\n"); printf("╚════════════╝\n"); printf("Loading...\n"); printf("O"); for(i=0;i<51;i++) printf("\b"); for(i=0;i<50;i++) { mDelay((pSIZE+mSIZE)/2); printf(">"); } printf("\nFinish.\n载入成功，按任意键进入置换算法选择界面：>>>"); getch();}/*设置延迟*/voidmDelay(unsignedintDelay){unsignedinti;for(;Delay>0;Delay--) { for(i=0;i<124;i++) { printf("\b"); } }}/*显示设计者信息*/voiddesignBy(){ printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n"); printf("┃㊣课题二：页面置换算法㊣┃\n"); printf("┃学号：1273010312730104┃\n"); printf("┃姓名：韩国娟蒋永平┃\n"); printf("┣━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");}voidprint(unsignedintt){ inti,j,k,l; intflag; for(k=0;k<=(pSIZE-1)/20;k++) { for(i=20*k;(i<pSIZE)&&(i<20*(k+1));i++) { if(((i+1)%20==0)||(((i+1)%20)&&(i==pSIZE-1))) printf("%d\n",page[i]); else printf("%d",page[i]); } for(j=0;j<mSIZE;j++) { for(i=20*k;(i<mSIZE+20*k)&&(i<pSIZE);i++) { if(i>=j) printf("|%d|",temp[i][j]); else printf("||"); } for(i=mSIZE+20*k;(i<pSIZE)&&(i<20*(k+1));i++) { for(flag=0,l=0;l<mSIZE;l++) if(temp[i][l]==temp[i-1][l]) flag++; if(flag==mSIZE)/*页面在物理块中*/ printf(""); else printf("|%d|",temp[i][j]); } /*每行显示20个*/ if(i%20==0) continue; printf("\n"); } } printf("\n"); printf("缺页次数：%d\t\t",t+mSIZE); printf("缺页率：%d/%d\n",t+mSIZE,pSIZE); printf("置换次数：%d\t\t",t); printf("访问命中率：%d%%\n",(pSIZE-(t+mSIZE))*100/pSIZE); printf("\n"); }/*计算过程延迟*/voidcompute(){ inti; printf("正在进行相关计算，请稍候"); for(i=1;i<20;i++) { mDelay(15); if(i%4==0) printf("\b\b\b\b\b\b\b\b\b\b\b\b"); else printf("Θ"); } for(i=0;i++<30;printf("\b")); for(i=0;i++<30;printf("")); for(i=0;i++<30;printf("\b"));}/*先进先出页面置换算法*/voidFIFO(){intmemery[10]={0};inttime[10]={0};/*记录进入物理块的时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*/ /*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];time[i]=i;for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;}if(k==mSIZE)/*如果不在物理块中*/{count++; /*计算换出页*/max=time[0]<time[1]?0:1; for(m=2;m<mSIZE;m++) if(time[m]<time[max]) max=m;memery[max]=page[i];time[max]=i;/*记录该页进入物理块的时间*/for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}else{for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}} compute(); print(count);}/*最近最久未使用置换算法*/voidLRU(){intmemery[10]={0};intflag[10]={0};/*记录页面的访问时间*/inti,j,k,m;intmax=0;/*记录换出页*/intcount=0;/*记录置换次数*/ /*前mSIZE个数直接放入*/for(i=0;i<mSIZE;i++){memery[i]=page[i];flag[i]=i;for(j=0;j<mSIZE;j++) temp[i][j]=memery[j];}for(i=mSIZE;i<pSIZE;i++){ /*判断新页面号是否在物理块中*/for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=page[i])k++;else flag[j]=i;/*刷新该页的访问时间*/