操作系统实验--虚拟存储管理-最佳置换先进先出最近最久未使用

学号P71514032专业计算机科学与技术姓名实验日期2017/11/30教师签字成绩实验报告【实验名称】虚拟存储管理【实验目的】模拟请求分页虚拟存储管理技术中的硬件地址变换、缺页中断以及页式淘汰算法，处理缺页中断。清楚认识请求分页管理。采用最佳置换算法实现分页管理的缺页调度。采用先进先出算法实现分页管理的缺页调度。采用LRU算法实现分页管理的缺页调度。【实验原理】C语言程序设计数据结构最佳置换算法：其所选择的淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。先入先出置换算法：该算法总是淘汰最先进入内存的页面。最近最久未被访问算法：选取过去中最久未被访问的页面进行替换。【实验内容】数据结构和符号说明a)数据结构②structPAGE_LIST③{④intid;//块号⑤intflag;//自适应标志⑥}page_list[MAX];⑦intN=0;//页面表大小⑧intorder[MAX];//调用串⑨//调用长度⑩intM=0;//定义输出内容⑪intG[MAX][MAX];//输出置换图⑫intI,J;//置换图扫描指针⑬intLL[MAX];//缺页序列⑭intLI;//缺页序列扫描指针⑮intRL[MAX];//置换序列⑯//置换序列扫描指针⑰intRI;函数说明：voidinit();//初始化函数voidprint();//输出函数voidOptimal();//最佳置换算法voidFIFO()//先进先出算法voidLRU();//最近最久未使用算法流程图最佳置换算法：开始初始化，设置第一个字符为当前字符页表是否有空位插入到页表空位，更新置换图和缺页序列该字符是否存在页表里标志位初始化扫描当前位置后序列，寻找最后用到的字符，替换替换扫描是否完成输出置换图、缺页序列，置换序列结束当前字符为输入的下一个字符是否是是否否先进先出置换算法：开始初始化，设置第一个字符为当前字符该字符是否存在页表中更新pos指针扫描是否完成输出置换图、缺页序列，置换序列结束当前字符为输入的下一个字符是是否POS指针指向的页调换，同时更新置换图、缺页序列置换序列否是最近最久未被访问算法：开始初始化，设置第一个字符为当前字符，所有标志位为0该字符是否存在页表中寻找最久未被访问的位置，即标志位最大的位置扫描是否完成输出置换图、缺页序列，置换序列结束当前字符为输入的下一个字符是否更新页表，更新置换图，缺页序列和置换图否是页表该位置标志位置0将所有此次未被访问到的节点标志位+1是代码：#includestdio.h#defineMAX100structPAGE_LIST{intid;//块号intflag;//自适应标志}page_list[MAX];intN=0;//页面表大小intorder[MAX];//调用串//调用长度intM=0;//定义输出内容intG[MAX][MAX];//输出置换图intI,J;//置换图扫描指针intLL[MAX];//缺页序列intLI;//缺页序列扫描指针intRL[MAX];//置换序列//置换序列扫描指针intRI;//初始化函数voidinit(){inti;I=0;J=0;LI=0;RI=0;for(i=0;i100;i++){page_list[i].id=-1;page_list[i].flag=999;}printf(请输入页表的大小：);scanf(%d,&N);printf(请输入调用长度：);scanf(%d,&M);printf(请输入调用串：\n);for(i=0;iM;i++)scanf(%d,&order[i]);}//输出函数voiddisplay(){inti,j;floatx;printf(置换图为：\n);for(i=0;iN;i++){printf(\n);for(j=0;jJ;j++)printf(===);printf(\n);for(j=0;jJ;j++)printf(%3d,G[i][j]);printf(\n);}printf(\n缺页序列为：\n);for(i=0;iLI;i++)printf(%3d,LL[i]);printf(\n置换序列为：\n);for(i=0;iRI;i++)printf(%3d,RL[i]);x=(float)J/(float)M;x*=100;printf(\n缺页率为：\n%3.2f%%\n,x);}//判断页是否在页表内intIsExist(intx){inti;for(i=0;iN;i++){if(page_list[i].id==x){return1;}}return0;}//最佳置换算法//此算法中自适应标志代表后面序列中是否访问到了此位置voidOptimal(){inti,j,k;intcou;init();for(i=0;iN;i++){page_list[i].id=order[i];for(j=0;jN;j++){G[I][J]=page_list[j].id;I++;}I=0;J++;LL[LI]=order[i];LI++;}for(;iM;i++){if(!IsExist(order[i])){cou=0;for(j=i+1;jM;j++){if(cou==N-1)break;for(k=0;kN;k++)if(page_list[k].id==order[j]&&page_list[k].flag!=0){page_list[k].flag=0;cou++;}}for(j=0;jN;j++)if(page_list[j].flag!=0){page_list[j].id=order[i];break;}for(j=0;jN;j++){G[I][J]=page_list[j].id;I++;}I=0;J++;LL[LI]=order[i];LI++;RL[RI]=order[i];RI++;}for(j=0;jN;j++)page_list[j].flag=999;}}//先进先出算法//此算法中自适应标志不需要使用voidFIFO(){inti,j;intpos=0;init();for(i=0;iM;i++){if(!IsExist(order[i])){page_list[pos].id=order[i];pos=(pos+1)%N;for(j=0;jN;j++){G[I][J]=page_list[j].id;I++;}I=0;J++;LL[LI]=order[i];LI++;if(i=N){RL[RI]=order[i];RI++;}}}}//最近最久未使用算法//此算法中自适应标志为起未被使用的次数voidLRU(){inti,j;intpos,max;init();for(i=0;iM;i++){if(!IsExist(order[i])){pos=0;max=0;for(j=0;jN;j++){if(page_list[j].flagmax){pos=j;max=page_list[j].flag;}}page_list[pos].id=order[i];page_list[pos].flag=0;for(j=0;jN;j++){G[I][J]=page_list[j].id;I++;}I=0;J++;LL[LI]=order[i];LI++;if(i=N){RL[RI]=order[i];RI++;}}else{for(j=0;jN;j++)if(page_list[j].id==order[i]){page_list[j].flag=0;break;}}for(j=0;jN;j++)if(page_list[j].id==order[i])continue;elsepage_list[j].flag++;}}intmain(){intselect;do{printf(页面置换算法\n);printf(1.最佳置换算法（Optimal）\n2.先进先出算法（FIFO）\n);printf(3.最近最久未使用算法（LRU）\n4.退出程序\n);printf(请输入您想要执行的操作：);scanf(%d,&select);switch(select){case1:Optimal();display();break;case2:FIFO();display();break;case3:LRU();display();break;case4:return0;default:printf(输入有误，请重新输入！\n);}}while(1);return0;}结果截图最佳置换算法先进先出算法:最近最久未使用算法：【小结或讨论】三种算法的主要区别是确定替换物理块的方式不同：1、对于先进先出置换算法，设置一个指针，循环从block的首元素指到block的尾元素，就是物理块置换顺序2、对于LRU置换算法，遍历页表中的页号，根据这些页号最近被引用的顺序，找到最久未被引用的页号，即在输入序列中向前查找离当前页最远的页号，将其所在的物理块置换掉。3、对于LRU置换算法，遍历输入序列中的页号，根据这些页号将来被引用的顺序，找到将来最长时间未被引用的页号，即在输入序列中向后查找离当前页最远的页号，将其所在的物理块置换掉。4、通过本次实验，我对于虚拟存储中的分页管理有了更加深入的了解。理解了最佳页面置换算法、先入先出页面置换算法以及最近最久未被使用页面置换算法的中心思想。同时发现，最佳页面置换算法得到的缺页率最低，但其要求也更加严格，必须要求知道未来调用的所有序列。先进先出算法最为简单，但是缺页率最高。最近最久未被访问算法居中。