操作系统常用页面置换算法专业课程设计.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;l=next1?0:1;for(m=2;mnextmax)max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一种*/memerymax=pagei;for(j=0;jmSIZE;