操作系统常用页面置换算法课程设计.doc

。摘 要 在linux中，为了提高内存利用率，提供了内外存进程对换机制，内存空间的分配和回收均以页为单位进行，一个进程只需要将其一部分调入内存便可运行；当操作系统发生缺页中断时，必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。因而引入一种用来选择淘汰哪一页的算法页面置换算法。页面置换算法是操作系统中虚拟存储管理的一个重要部分。页面置换算法在具有层次结构存储器的计算机中，为用户提供一个比主存储器容量大得多的可随机访问的地。常见的页面置换算法有先来先服务算法(FIFO)，最近最久未使用算法(LRU)和最佳适应算法(OPT)。关键字：操作系统；FIFO；LRU；OPT；Linux-可编辑修改-目 录1 绪论11.1 设计任务11.2设计思想11.3设计特点11.4基础知识21.4.1 先进先出置换算法(FIFO)21.4.2 最近最久未使用算法(LRU)31.4.3最佳置换算法(OPT)32 各模块伪代码算法42.1伪代码概念42.2伪代码算法42.2.1主函数伪代码算法42.2.2延迟时间函数伪代码算法62.2.3 FIFO算法的伪代码72.2.4 LRU算法的伪代码72.2.5 OPT算法的伪代码103 函数调用关系图123.1函数声明123.1.1主要算法函数123.1.2辅助函数123.2程序函数调用关系图134 测试结果144.1数据初始化144.2页面调度算法144.2.1先进先出算法154.2.2最近最久未使用LRU154.2.3最佳置换算法OPT175 源程序186 设计总结30参考文献31致 谢321 绪论1.1 设计任务 1、了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，练习并掌握UNIX提供的vi编辑器来编译C程序，学会利用gcc、gdb编译、调试C程序。 2、设计一个虚拟存储区和内存工作区，并使用最佳淘汰算法（OPT）、先进先出算法（FIFO）、最近最久未使用算法（LRU）计算访问命中率。（命中率页面失效次数页地址流长度=1-缺页率）1.2设计思想 在进程运行过程中，若期所有要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证进程正常进行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。置换算法的好坏将直接影响到系统的性能。 不适当的算法可能会导致进程发生“抖动”，即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，有需将它调入，如此频繁地更换页面，以致一个进程在运行中把大部分的时间都花费在页面置换工作上。通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。改进页面置换算法,可以降低页面失败率,从而有效地提高系统性能。从理论上讲，应将那些以后不再会访问的页面置换出来，或把那些在较长时间内不会再访问的页面调出。目前已有多种置换算法，它们都试图更接近于理论上的目标。1.3设计特点 本设计作品主要用C语言编写而成，结构简单，语言易懂，条理清晰。本作品兼容性也非常的高，可以在各种可以编译C语言的编译软件上运行，并能够在cygwin中运行，经多次调试，暂时未发现有何不足。本程序的另一个优点是，程序可以计算大数量数据。如，本程序可以计算的最大物理块个数达到了10000个，用户输入的页面引用串个数也能达到10000个以上。但是，实际生活中系统的物理块个数一般不会达到10000个。因此，我们在提示用户输入页面引用串个数是，只提示最大输入100个。但是代码不足在于使用到了较多的static全局变量使得整个代码质量不是很好，而且也只是简单的根据算法设计来模拟实现整个过程。我通过先查找该页面是否在页帧中存在，若不存在则需要页面置换，通过刷新每个页帧的time值来得到每次的最小值来进行页面的置换，最小值即代表着最近最少使用的页面。 经过测试，这个系统已经达到了题目中的全部要求。这个程序有很多优点有一个是界面简明，简洁明了的程序菜单；一个是智能化的模块设计，减少了许多人工操作，如功能模块操作结束后，均会返回主菜单进行下一模板的运行，并提示是否再进行类似的操作，这样给用户带来了操作的方便，大大提高了学生选课的效率还有就是提示语言既简洁又明确，层次分明等等；当然也有缺点如程序仍然存在不合理的地方，例如程序某些部分输入错误不能立刻返回改正；信息表达方式不丰富，比较单一，缺少图片、音乐等元化表达方式。 FIFO算法总是选择在内存驻留时间最长的一页将其淘汰。这种算法基于CPU按线性顺序访问地址空间的这个假设上，许多时候，CPU不是按吸纳型顺序访问地址空间的。所以，那些在内存中停留时间最长的页往往被访问到。这就造成FIFO算法的缺页率不太理想。并且，FIFO还有一个缺点就是Belady奇异现象。实现FIFO算法无需硬件提供新的帮助，只采用循环数组管理驻留集即可。OPT算法被誉为“最佳算法”，因为他淘汰下次访问距当前最远的那些页中序号最小的一页。所以，OPT算法得出的缺页率是最小的。但是，OPT算法在使用前必须先得知整个访问串，这很难实现。因此，OPT算法知识一种概念中的算法。LRU算法的实现耗费较高，并且需要硬件的支持，但是效果较好。就缺页率而言，OPT算法最佳，FIFO算法最差。1.4基础知识1.4.1 先进先出置换算法(FIFO) FIFO算法是最早出现的算法。该算法总是淘汰最先进入内存的页面，即选择在内存驻留时间最久的页面予以淘汰。该算法实现简单，只需要把一个进程已调入内存的页面按先来后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但是该算法与进程实际运行的规律不相符合，因为在进程中，有些页面经常被访问。1.4.2 最近最久未使用算法(LRU) 选择最近一段时间最长时间没有被访问过的页面予以淘汰。LRU算法是根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况，采取“最近的过去”作为“最近的将来”的近似。选择最近最久未使用的页面予以淘汰。实现：赋予每个页面一个方位字段，用来记录一个页面自上次被访问以来所经历的时间T，当要淘汰一个页面的，选择现有页面中其T值最大的，即最近最久未使用的页面予以淘汰。1.4.3最佳置换算法(OPT)最佳置换算法所选择的被淘汰掉的页面，将是以后永久不再使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置算法，通常可保证获得最低的缺页率。本模拟算法中，最佳页面置换算法实现所采用的思想是：循环读入每个页表项，若该页表在内存中，则读取下一个页表项。若页表不存在内存中：一种情况是内存不满，则将页表放入内存中；若内存块已满，刚分别计算内存中各个页表再次被使用的时间，并将最久不被访问的调出，放入当前读入页表项。-可编辑修改-2 各模块伪代码算法 根据程序提示，用户先将需要计算的页面号引用串，物理块数量和引用串个数输入到文件流中。待程序加载数据完成后，用户继续选择页面置换算法的类型，程序根据用户输入的信息来判断采用哪一种算法进行计算。结构如图2.1所示。图 2.1 总体结构图2.1伪代码概念 伪代码（英语：pseudocode），又称为虚拟代码，是高层次描述算法的一种方法。使用伪代码的目的是让被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，介于自然语言与编程语言之间。以编程语言的书写形式指明算法职能。使用伪代码，不用拘泥于具体实现。它是半角式化、不标准的语言。可以把整个算法运行过程的结构用接近自然语言的形式（可以使用任何一种你熟悉的文字，关键是把程序的意思表达出来）描述出来。2.2伪代码算法2.2.1主函数伪代码算法 该程序是按自上而下，自顶向下的设计思想进行设计的。程序各个功能的实现之间的联系采用函数调用与函数嵌套。main()函数是整个程序的入口，程序的开始就是从这里开始的，然后通过main()函数调用其他函数来实现各个功能。具体流程如图2.2所示。图2.2 主函数流程图Begin /*算法开始*/调用designBy()显示出设计者信息Scanf mSIZE，pSIZE，page100 /*mSIZE表示物理块，pSIZE表示页面号引用串个数，page100表示一个引用串的页面号*/do Printf pageiScanf code /*code是一个标记，用来判断用户输入是否符合要求*/Switch(code)case 1: FIFO() /*先进先出算法*/case 2: LRU() /*最近最久未使用算法*/case 3: OPT() /*最佳置换算法*/case 4: exit(0) /*退出程序*/default: 重新输入while(code!=4)Getch（用户输入）End2.2.2延迟时间函数伪代码算法begin变量定义while delay0while i124退格end图2.3 延迟时间函数流程图 延迟时间函数主要由两个for循环构成。延迟时间函数在程序中主要起延迟时间的作用，相当于一个定时器，给程序数据加载，数据处理等提供时间保证。使程序能够正常的进行。其具体流程如图2.3所示。2.2.3 FIFO算法的伪代码 begin 定义变量 while imSIZEpagei0memeryi, itimeiwhile jmSIZEmemeryjtempij while ipSIZEwhile jmSIZEif 新页面号不在物理块中k+if k=mSIZE 则，计算换出页，记录该页进入物理块的时间否则，tempij=memeryjprint 置换次数End FIFO算法是操作系统中最简单最容易实现的一种页面置换算法，它的实现主要运用了两个循环结构。第一个循环的功能是将页面串中的前mSIZE页面直接放入物理块中；第二个循环主要判断当前页面是否在物理块中，若在物理块中，则继续读取下一个页面。否则，将最先进入物理块的页面写入到物理块中。其主要执行流程如图2.4所示。2.2.4 LRU算法的伪代码 LRU算法是将最近进入物理块且未使用的页面首先换出物理块。LRU函数主要也运用了两个循环来实现其算法，首先将前mSIZE个页面置换到物理块中，然后再按具体算法进行置换页面。其执行流程如图2.5所示。图2.4 FIFO流程图 begin 定义变量 while imSIZE pageimemeryi, itimeiwhile jmSIZEmemeryjtempij while imSIZE前mSIZE个数直接放入while ipSIZE while jmSIZEif 新页面号不在物理块中k+判断新页面号是否在物理块中if k=mSIZE 则，计算换出页，记录该页进入物理块的时间否则，max=flag0flag1?0:1memeryjtempij调用 print(置换次数)End图2.5 LRU流程图2.2.5 OPT算法的伪代码 begin 定义变量 while imSIZEpageimemeryi, itimeiwhile jmSIZEmemeryjtempij 前mSIZE个数直接放入 while ipSIZEwhile jmSIZEif memeryj!=pagei判断新页面号是否在物理块中k+if k=mSIZE 则，计算换出页，记录该页进入物理块的时间否则，max=flag0flag1?0:1tempij=memeryj得到物理块中各页下一次访问时间if memerym=page1退出循环nextm=1调用 print(置换次数)End OPT算法是将内存中最长时间内不会用的页面置换出去，这种算法的优点是系统利用率，内存利用率都非常的高。但是这种算法目前无法实现，因为实际中，系统根本无法预知哪一个页面最先执行，哪一个页面最后执行，各个页面的执行顺序都无法确定根本就不能确定页面换出的次序。OPT算法主要用于对其他算法效率的评估。OPT函数的执行情况如图2.6所示。图2.6 OPT流程图3 函数调用关系图3.1函数声明3.1.1主要算法函数主要算法函数包括FIFO()、LRU()和OPT()三种，它们都是无返回值类型，不带任何参数。各个函数的具体声明情况如下：void FIFO(); /*先来先服务调度算法函数*/返回值类型：无返回值形参：无void LRU(); /*最近最久未使用算法函数*/返回值类型：无返回值形参：无void OPT(); /*最佳调度算法函数*/返回值类型：无返回值形参：无3.1.2辅助函数辅助函数是为了实现某些功能而特意设置的一些辅助函数。本程序主要有显示引用串函数、显示设计者信息函数、数据加载函数和延迟时间函数，它们有的有形式参数，有的没有，但是它们都是无返回值类型的函数。各个函数的具体声明情况如下：void print(unsigned int t); /*显示引用串函数*/返回值类型：无返回值形参：无符号整型void designBy(); /*显示设计者信息*/返回值类型：无返回值形参：无void download(); /*数据加载*/返回值类型：无返回值形参：无void mDelay(unsigned int Delay); /*延迟时间*/返回值类型：无返回值形参：无符号整型3.2程序函数调用关系图 程序以main( )函数为入口，通过主函数main( )进行调用其他函数，以此实现函数的各个功能。在本程序中，main( )函数调用了designBy( )函数，用以显示设计者信息；main( )函数还分别调用了FIFO( )、LRU( )和OPT( )三种算法函数，实现三种算法。FIFO( )、LRU( )和OPT( )又分别调用了print( )和compute( )函数，print( )显示了用户输入的页面引用串，compute( )则主要计算了用户选择的算法的结果。在计算过程中，为了保证逻辑上合理，我们在compute( )函数中调用了mDelay( )时间延迟函数；main( )函数也调用了download( )数据加载函数，主要功能是加载用户输入的数据以供各种算法使用。在调用download( )过程中，也调用了时间延迟函数mDelay( )。具体函数调用关系如图3.1所示。图3.1 函数调用关系4 测试结果4.1数据初始化 用户根据程序提示，按照要求输入相应的数据。例如，本次测试中我们设置物理块个数为4，页面引用串个数为20，一个页面号引用串中各个页面号之间用空格(“ ”)隔开。值得注意的是，物理块个数可以是几个，几十个，甚至几百个，但是考虑到系统的效率，一般取物理块个数在10个以内；页面号引用串个数也和物理块个数一样，页面引用串个数取100个以内。用户输入情况如图4.1所示。图 4.1 界面初始化4.2页面调度算法 选择一个合适的页面置换算法对提高内存的利用率会有很大的帮助。当用户将数据初始化结束后，就要进行页面调度算法的选择了。下面本书将逐一说明先进先出算法FIFO、最近最久未使用LRU和最佳置换算法的具体调试情况。 用户输入的页面引用串为：2 12 43 2 15 23 21 2 4 23 21 20 32 3 21 23 20 2 32 12，物理块个数为：4，页面号引用串个数为：20。FIFO算法的缺页次数为19，置换次数为16，缺页率为19/20，访问率为5%；LRU算法的缺页次数为19，置换次数为16,缺页率为19/20,访问率为5%；OPT算法的缺页次数为14,置换次数为16,缺页率为14/20，访问率为30%。4.2.1先进先出算法 由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头的页面并把新调入的页面加到表尾。具体计算结果如图4.2所示。图 4.2 FIFO算法4.2.2最近最久未使用LRU 用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组temp10标记页面的访问时间。每当使用页面时，刷新访问时间。发生缺页时，就从物理块中页面标记最小的一页，调出该页，换入所缺的页面。具体计算结果如图4.3所示。图 4.3 LRU算法图 4.4 OPT算法4.2.3最佳置换算法OPT 用一维数组pagepSIZE存储页面号序列，memerymSIZE是存储装入物理块中的页面。数组tempmSIZE记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。具体计算结果如图4.4所示。5 源程序#include #include #include /*全局变量*/int mSIZE; /*物理块数*/int pSIZE; /*页面号引用串个数*/static int memery10=0; /*物理块中的页号*/static int page100=0; /*页面号引用串*/static int temp10010=0; /*辅助数组*/*置换算法函数*/void FIFO();/先进先出置换算法void LRU();/最近最久未使用算法void OPT();/最佳置换算法/*辅助函数*/void print(unsigned int t);void designBy();/显示设计者信息void download();/数据加载void mDelay(unsigned int Delay);/延迟时间/*主函数*/void main() int i,k,code;system(color 0F);designBy();printf(请按任意键进行初始化操作. n);printf(n);printf( );getchar();system(cls);system(color 0B);printf(请输入物理块的个数：);scanf(%d,&mSIZE);printf(请输入页面号引用串的个数(P=100)：);scanf(%d,&pSIZE);puts(请依次输入页面号引用串(请用 隔开)：);for(i=0;ipSIZE;i+) scanf(%5d,&pagei);download();system(cls);system(color 0E); do puts(输入的页面号引用串为：);for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i);getch();system(cls); while (code!=4);getch();/*载入数据*/void download()int i;system(color 0D);printf(n);printf( 能不能给我一首歌的时间。 n);printf(n);printf(Loading.n);printf( );for(i=0;i51;i+)printf(b);for(i=0;i);printf(nFinish.nOK!已唱完.按任意键进入置换算法选择界面：);getch();/*设置延迟*/void mDelay(unsigned int Delay) unsigned int i; for(;Delay0;Delay-) for(i=0;i124;i+) printf( b); /*显示设计者信息*/ void designBy()printf(n);printf( 研究题目：页面置换算法 n);printf( 许可证号：13480144 n);printf( 版权所有：朱 强 n);printf(n);/*显示页面号引用串*/void print(unsigned int t)int i,j,k,l;int flag;for(k=0;k=(pSIZE-1)/20;k+)for(i=20*k;(ipSIZE)&(i20*(k+1);i+)if(i+1)%20=0)|(i+1)%20)&(i=pSIZE-1)printf(%dn,pagei);elseprintf(%d ,pagei);for(j=0;jmSIZE;j+)for(i=20*k;(imSIZE+20*k)&(i=j)printf( |%d|,tempij);elseprintf( | |);for(i=mSIZE+20*k;(ipSIZE)&(i20*(k+1);i+)for(flag=0,l=0;lmSIZE;l+)if(tempil=tempi-1l)flag+;if(flag=mSIZE)/*页面在物理块中*/printf( );elseprintf( |%d|,tempij);/*每行显示20个*/if(i%20=0)continue;printf(n);printf(-n);printf(缺页次数：%dtt,t+mSIZE);printf(缺页率：%d/%dn,t+mSIZE,pSIZE);printf(置换次数：%dtt,t);printf(访问命中率：%d%n,(pSIZE-(t+mSIZE)*100/pSIZE);printf(-n);/*计算过程延迟*/void compute()int i;printf(正在玩命计算，请稍候);for(i=1;i20;i+)mDelay(15);if(i%4=0)printf(bbbbbb bbbbbb);elseprintf(.);for(i=0;i+30;printf(b);for(i=0;i+30;printf( );for(i=0;i+30;printf(b);/*先进先出页面置换算法*/void FIFO() int memery10=0; int time10=0; /*记录进入物理块的时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; timei=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=time0time1?0:1;for(m=2;mmSIZE;m+)if(timemtimemax)max=m; memerymax=pagei; timemax=i; /*记录该页进入物理块的时间*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最近最久未使用置换算法*/void LRU() int memery10=0; int flag10=0; /*记录页面的访问时间*/ int i,j,k,m; int max=0; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; flagi=i; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; else flagj=i; /*刷新该页的访问时间*/ if(k=mSIZE) /*如果不在物理块中*/ count+;/*计算换出页*/ max=flag0flag1?0:1;for(m=2;mmSIZE;m+)if(flagmflagmax)max=m; memerymax=pagei; flagmax=i; /*记录该页的访问时间*/ for(j=0;jmSIZE;j+)tempij=memeryj; else for(j=0;jmSIZE;j+)tempij=memeryj; compute();print(count);/*最佳置换算法*/void OPT() int memery10=0; int next10=0; /*记录下一次访问时间*/ int i,j,k,l,m; int max; /*记录换出页*/ int count=0; /*记录置换次数*/*前mSIZE个数直接放入*/ for(i=0;imSIZE;i+) memeryi=pagei; for(j=0;jmSIZE;j+)tempij=memeryj; for(i=mSIZE;ipSIZE;i+) /*判断新页面号是否在物理块中*/ for(j=0,k=0;jmSIZE;j+) if(memeryj!=pagei) k+; if(k=mSIZE) /*如果不在物理块中*/ count+;/*得到物理快中各页下一次访问时间*/for(m=0;mmSIZE;m+)for(l=i+1;lpSIZE;l+)if(memerym=pa