页面淘汰算法实验报告材料.doc

操作系统实验报告课题：页面淘汰算法专 业：班 级：学 号：姓 名：年 月 日目 录一实验目的3二实验要求3三背景知识3四 总体设计4五详细设计7六运行结果分析9七 心得体会13八 参考文献 14附：源代码 15一、实验目的本实验主要对操作系统中请求分页式存管理与其应用的一些关键算法进展模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统部的根本处理原理与过程也有很多益处。利用简单的数据结构，模拟实现操作系统中的页面置换机制，通过写程序模拟实现上述三种存页面置换算法，使学生进一步掌握存页面置换的方法。对操作系统中存的管理有一个实践上的认识。1、用C语言编写OPT、FIFO、LRU三种置换算法。2、熟悉存分页管理策略。3、了解页面置换的算法。4、掌握一般常用的调度算法。5、根据方案使算法得以模拟实现。6、锻炼知识的运用能力和实践能力。二、实验要求l 设计随机页面序号产生程序，并说明随机的性能和其性能可能对算法的影响l 编写页面淘汰算法(FIFO、OPT、LRU)l 结果数据的显示或提取l 结果数据的分析 几点说明：l 设计并绘制算法流程，附加说明所需的数据结构l 如何标记时间的先后、最久的将来、最久未被使用l 描述Clock算法的根本原理、必要的数据结构、算法执行流程图、编码实现。1初始化：输入作业可占用的总页框数，初始化置空。2输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；3Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。4显示当前分配淘汰序列：显示淘汰的页号序列。三、背景知识：在操作系统当中，在进程运行过程中，假如其访问的页面不在存中而需把他们调入存，但存已无空闲空间时，为了保证该进程能够正常的运行，系统必须从存中调出一页程序或数据送到磁盘的兑换区中，但是应该是哪个页面被调出，需根据一定的算法来确定。通常，我们把这一类的算法称为“页面置换算法，页面置换算法执行效率的上下，往往直接影响到操作系统的性能。存页面置换算法：1、 <1> 先进先出调度算法FIFO先进先出调度算法根据页面进入存的时间先后选择淘汰页面。本算法实现时需要将页面按进入存的时间先后组成一个队列，每次置换掉最早进入的页面。这是最早出现的置换算法，该算法总是淘汰最先进入存的页面，即选择在存中驻留时间最长的页面换出，予以淘汰。该算法实现简单只需把一个进程已调入存的页面，按先后次序成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。<2>最近最久未使用的置换算法LRU最近最久未使用的置换算法，是根据页面调入存后的使用情况进展决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去作为“最近的将来的近似，因此，LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t,，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。<3> 最优置换算法OPT最优置换算法是可以说的一种理想的页面置换算法，它是由Belady于1966 年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间不再被访问的页面。采用最优置换算法，通常可保证获得最低的缺页率。但由于人目前还无法预知一个进程在存的假如干个页面中，哪一个页面是未来最长时间不再被访问的，因而该算法是无法实现的，但可以利用此算法来评价其它算法。<4>时钟页面置换算法时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面，如下列图。 当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就去除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。四、 总体设计l 根据要求设计页面淘汰算法的活动图 运行程序进入主页面，在正上方，已经通过随机生成函数生成了页面号，在其下方，显示可选项：0、退出程序1、FIFO算法2、OPT算法3、LRU算法。根据需要，选择相应的法，程序自动生成页面淘汰的先后顺序，以与置换次数和缺页次数，并打印在下方，执行完以后，再次进入主页面，到输入0，退出程序。l 算法流程图Ø FIFO算法流程图：Ø OPT算法流程图Ø LRU算法流程图：五、 详细设计一、设计思想1、 最优置换算法(OPT)用数组Temppages存储当前物理块中页面信息，数组TimeArry存储当前在物理块中的页面的获得存时的时间，当页面不在存中时，根据当前已获得物理块数的页面在所有的页面当中将来不在请求存或者很少请求存的情况进展置换2、 先进先出算法(FIFO)用数组Temppages存储当前物理块中页面信息，变量temp记录存中物理块页面置换状态，每进展一次置换，页面置换状态变化，便于下一次的置换。3、 最近最久未使用算法(LRU)用数组Temppages存储当前物理块中页面信息，数组TimeArry存储当前在物理块中的页面的获得存时的时间，当页面不在存中时，选择TimeArry数组中值最小并且对应物理块中的页面进展置换。二、设计步骤首先根据程序要求，我们分别定义两个宏，用以存放我们的物理块数目以与页面数目，再定义一个结构体，用以物理块的存储，代码如下：#define MemPageCount 4 #define InstructionCount 20 struct page int serial; /页面号 int time; /时间计数mempageMemPageCount;其次，建立主函数，根据程序需要，定义相应的变量，建立switch语句，用以算法的选择，局部定义如下：int i,j,k,m,n;/指令页面集合,可以考虑让页面指令集合随机生成int instructionInstructionCount;int mem_counter; /存页面集合计数器int switch_counter; /置换次数最后，根据算法流程图，实现相应算法的代码编写。三、算法流程设计主函数流程:STEP1:输入分配的页框数，页面访问次数和要访问的页面号序列STEP2:存页面初始化。存中页面的数据结构为单循环链表，含有页号值yehao和访问位值a。开始时页号均为-1，访问位为0.STEP3：测试数据。具体算法是依要访问的页面号，调用find()函数查找是否已经存在于存中。假如存在，如此修改其访问位为1.假如不存在，触发缺页中断，调用tihuan()函数。最后，打印当前存状态。如此循环直至测试串都访问完毕。1) 主要函数实现a) Makenode(double)函数：用于初始化一个节点。b) Finddouble函数：依据输入的页号，查询存中是否已存在此页面。假如存在返回值1，不存在返回值0.c) Tihuandouble函数：在发生缺页中断时，时钟指针查找访问位为0的页面进展替换，指针扫过的页面访问位置0，新参加的页面访问位置1。替换后指针下移。d) Print_state()函数：打印当前存中存在的页面的状态以与当前时钟指针所指向的页面位置。2) 测试数据估计输入：输入分配的页框数3输入页面访问次数15输入要访问的页面号序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6输出仅最后一项：3) 结果分析以下是clock算法对应输入页面号序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6的分析表六、 运行结果分析：a) 开始界面2、 采用随机数产生的结果2、采用自定义页面信息产生结果自定义页面数为：15 物理块数为：4页面序列为：1 2 3 4 5 6 7 8 9 4 5 6 7 0 8根据结果，我们不难发现，OPT算法，是三种算法中性能最好的，它的置换次数最少，LRU次之，不过性能最差的还是FIFO，由于缺页率=缺页次数/总的页面数，所以我们不难发现，随着物理块数的增加，缺页率都相应有所增加，但是OPT算法的增加较为明显，即产生了belady现象。七、心得体会：这次课程设计，让我对算法的编写更加的熟练，同时更加了解页面置换的相关算法，也提高了我对算法设计的严密性，对以后的程序设计有很大帮助。我们不仅对常用的算法进展了编写，还对一些理想的算法也进展了编写，并且通过适当的方法，得以了验证。就该程序而言，随机性使得程序出现了更多的可能性，为我们验证算法提供很大的方便，电脑自动分配，大大的节约了我们的时间，但是我们通过实验不难发现，如果所设的页面项目过大，也会影响我们算法的性能执行效率。对我们所涉与的算法，让我有很大的感触。在FIFO 算法中，无论有无发生缺页或者置换，都需要对每个在存中的页面的time 值进展增加操作，以保持最先进入的那个页面的time 值是最大的；一个新进来的页面，其time值设置为0。当然，该算法也可以通过队列结构来实现，利用队列的先进先出FIFO特性完成，无需设置time字段。distance 用于记录存物理块集合中每个页面距离再次被使用的页面跨度，缺省值为9999，如果某个页面在后续指令集合中不再出现，如此用最大值9999 缺省取代；如果页面再次被使用，如此两次使用所跨的页面数，为页面跨度。用最大页面跨度表示以后永不使用或未来最长时间不再被访问。在LRU 算法中，无论是否发生缺页或者置换，除了命中刚刚被访问过的页面页面time 值清零之外，其它所有存中的页面的time 值都加一，以保证最近刚刚被访问的页面的time 值最小，相应time 值最大的页面就是最近最久没有被访问的页面。上述两种算法，是我们在进程调度中使用最多的两种，你可能会问？为什么要使用进程调度，因为当我们的程序在运行时，假如所访问的页面不再存而需把它调入存，但存已无空闲空间，这时，为了保证该程序能正常运行，系统就必须从存中调出一页程序或数据送到磁盘的兑换区中，但应将那个页面调出，我们就必须根据一定的算法来实现。所以，一个页面置换算法的好坏，将直接影响到我们系统的性能。相比拟而言，我们最常用的是LRU算法，因为它是根据页面调入存后的使用情况就行决策的，比FIFO算法要好很多。通过与其他算法的比拟，加深对clock算法的理解,也了解了他们的异同之处。Clock算法其实是一种改良的第二次机会算法，它通过设置访问位，找到最早最不常访问的页面，即标号为0的页面。之所以叫clock算法，依我理解是将存中的排列顺序附上时间的概念，clock指针扫过的页面要将他们1置0就是基于这个思想，因为他们都是没被访问的，且在时钟上的排列按照访问时间顺序。这样就保证了每次替换的都是最早进来的且不最常访问的页面。八、参考文献【1】计算机操作系统第三版汤小丹、梁红兵、汤子瀛、哲凤屏等 电子科技大学 2007-05 【2】C+ Primer中文版第4版美Stanley B. Lippman 等 著 师贤 等 译.人民邮电, 2006-03-01【3】 C+ Primer习题解答第4版蒋爱军，师贤，梅晓勇 著人民邮电 2007-02-01【4】 现代操作系统原书第3版塔嫩鲍姆 Tanenbaum.A.S，向群，马洪兵 著机械工业 2009-07-01【5】计算机操作系统教程尧学，史美林，高清华大学 2006-10-01【6】 数据结构STL框架王晓东 著清华大学2009-09-01附：源代码#include <stdio.h>#include <stdlib.h>#include <time.h>#define M_size 100int pageNum = 0;/全局变量页面数int pagesM_size;/存储页号int TemppagesM_size;/辅助数组int TimeArryM_size;/记录页在存中的时间int method;/产生结果的方法int AlgorithmStyle; /辅助变量，用于选择算法类型int Block;/记录物理块数int start;/辅助变量void Inition()/初始化函数int i;int t = time(NULL);/产生随机数种子srand(t);/用t初始化随机数种子pageNum = rand()%10+8;/随机产生4-14之的整数，保证页面数在4-14之for(i = 0 ; i < pageNum ; i+)pagesi = rand()%10+1;/初始化页号，初始值在1-10之Block = 4;/初始化物理块数位3void printDefaltResult()/缺省参数显示int i;printf("缺省页面数为: %dn",pageNum);printf("缺省页号分别为: ");for(i = 0 ; i < pageNum ; i+)printf("%d ",pagesi);printf("n");printf("可用物理块数为: %dn",Block);printf("按任意键继续:");getchar();void PrintCustomInfo()/显示用户自定义参数int i;printf("自定义页面数为: %dn",pageNum);printf("自定义页号分别为: ");for(i = 0 ; i < pageNum ; i+)printf("%d ",pagesi);printf("n");printf("可用物理块数为: %dn",Block);printf("按任意键继续:n");getchar();void printUserInfo()/显示个人信息system("color 0B");printf("n");printf("页面淘汰算法n");printf("学号：n");printf("班级：n");printf("：n");printf("n");printf("按任意键开始操作:");getchar();system("cls");system("color 0B");void ChioceDealmethod()/选择解决问题的方法"1"选择缺省值，"2"选择自定义值printf("n");printf("1、使用默认值产生结果 2、自定义页数和页号n");printf("n 请输入你的选择:n");scanf("%d",&method);system("color 0F");void PrintNotWithoutPages()/显示一定不用换页的局部start = Block;int i,j,k=0,key = 0;for(i = 0 ; i < start ; i+)int flag = 0;for(j = 0 ; j <= i-1 ; j+)if(Temppagesj = pagesi)TimeArryj = i;flag = 1;start = start+1;key+;if(flag = 0)TimeArryk = i;Temppagesk = pagesi;k+;for(j = 0 ; j <= i-key ; j+)printf(" %-7d",Temppagesj);printf("n");void PrintResult()/显示每次换页后的结果int i;for(i = 0 ; i < Block ; i+)printf(" %-7d",Temppagesi);printf("n");void FIFODealQuestion()/先进先出算法int i,j;int WithOutPages = 0;/记录缺页数printf("FIFO(先进先出算法)结果显示：n");PrintNotWithoutPages();int temp = 0;for(i = start ; i < pageNum ; i+)if(temp = Block)temp = 0;int key = 0 ;for(j = 0 ; j < Block ; j+)/判断该页是否在物理块中if(Temppagesj = pagesi)key = 1;break;if(key = 0)/如果不在Temppagestemp = pagesi;temp+;WithOutPages+;PrintResult();printf("置换次数为： %d ,页面总数为： %d ,置换率为: ",WithOutPages,pageNum);double re = (double)WithOutPages)/(double)pageNum);printf("%.2lfn",re);printf("缺页次数为： %d ,页面总数为： %d ,缺页率为: ",WithOutPages+Block,pageNum);re = (double)(WithOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void LRUDealQuestion()/最近最久未使用算法int i,j;int WithOutPages = 0;/记录缺页数printf("LRU(最近最久未使用算法)结果显示：n");PrintNotWithoutPages();for(i = start ; i < pageNum; i+)int key = 0;for(j = 0 ; j < Block ; j+)/判断该页是否在物理块中if(Temppagesj = pagesi)key = 1;TimeArryj = i;/更新时间break;if(key = 0)/假如该页不在存中WithOutPages+;int min = TimeArry0;int flag = 0;for(j = 1 ; j < Block ; j+)if(min > TimeArryj)min = TimeArryj;/找到最久的页面flag = j;TimeArryflag = i;/记录时间Temppagesflag = pagesi;PrintResult();printf("置换次数为： %d ,页面总数为： %d ,置换率为: ",WithOutPages,pageNum);double re = (double)WithOutPages)/(double)pageNum);printf("%.2lfn",re);printf("缺页次数为： %d ,页面总数为： %d ,缺页率为: ",WithOutPages+Block,pageNum);re = (double)(WithOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void OPTDealQuestion()int i,j,l;int WithOutPages = 0;/记录缺页数printf("OPT(最优置换算法)结果显示：n");PrintNotWithoutPages();for(i = start ; i<pageNum ; i+)int key = 0;for(j = 0 ; j < Block ; j+ )/判断该页是否在存中if(Temppagesj=pagesi)TimeArryj = i;key = 1;break;if(key = 0)/如果该页不在存中WithOutPages+;/缺页数加1/得到各物理块下一次访问的时间for(j = 0 ; j < Block ; j+)for(l = i+1; l < pageNum ; l+)if(Temppagesj=pagesl)break;TimeArryj = l;/得到下一次访问时间最长的一个页面，将当前页与其换掉int min = TimeArry0;int flag = 0;for(j = 1 ; j < Block ; j+)if(TimeArryj > min)min = TimeArryj;flag = j;Temppagesflag = pagesi;TimeArryflag = i;PrintResult();printf("置换次数为： %d ,页面总数为： %d ,置换率为: ",WithOutPages,pageNum);double re = (double)WithOutPages)/(double)pageNum);printf("%.2lfn",re);printf("缺页次数为： %d ,页面总数为： %d ,缺页率为: ",WithOutPages+Block,pageNum);re = (double)(WithOutPages+Block)/(double)pageNum);printf("%.2lfn",re);void ChioceAlgorithm(int AlgorithmStyle)switch(AlgorithmStyle)case 1:FIFODealQuestion();/先进先出算法解决问题break;case 2:LRUDealQuestion();/最近最久未使用算法解决问题break;case 3:OPTDealQuestion();/最优置换算法解决问题break;case 4:FIFODealQuestion();/先进先出算法解决问题LRUDealQuestion();/最近最久未使用算法解决问题OPTDealQuestion();/最优置换算法解决问题break;void DefaltDeal()/默认解决printf("n");printf("请选择算法：1为FIFO(先进先出) 2为LRU(最近最久未使用) 3为OPT(最优置换算法)n");printf(" 4三种算法一起实现n");printf("n");scanf("%d",&AlgorithmStyle);ChioceAlgorithm(AlgorithmStyle);void CustomDeal()/自定义解决int i;system("cls");printf("n");printf(" 自定义页面数和页号n");printf("n");printf("请输入页面数：");scanf("%d",&pageNum);printf("请输入页号：");for(i = 0 ; i < pageNum ; i+)int a;scanf("%d",&a);pagesi = a;getchar();printf("是否修改物理块数？ Y/N :");char change;scanf("%c",&change);if(change = 'Y')int a;scanf("%d",&a);Block = a;PrintCustomInfo();/显示自定义页面信息DefaltDeal();/使用自定义信息解决问题void DealQuestions()/判断解决问题方式switch(method)case 1:DefaltDeal();/默认解决问题break;case 2:CustomDeal();/自定义解决问题int main()printUserInfo();/输出个人信息printf("n");printf("请按任意键进展初始化操作. n");printf("n");printf(" >>>");getchar();Inition();/初始化函数，随机产生页面数和页号printDefaltResult();/输出默认信息ChioceDealmethod();/选择产生结果方式DealQuestions();/开始解决问题return 0;