操作系统原理课程设计-页面置换算法模拟程序

页面置换算法模拟程序页面置换算法模拟程序PAGE数学与计算机学院课程设计说明书课程名称:操作系统原理-课程设计课程代码:题目:页面置换算法模拟程序年级/专业/班:学生姓名:学号:开始时间:完成时间:课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日目录TOC\o"1-2"\h\z1引言 11.1问题的提出 11.2国内外研究的现状 11.3任务与分析 22需求分析 23开发平台 23.1开发工具 23.1开发语言 24概要设计 34.1总体设计框图 35详细设计 45.1代码分析结果 65.11数据结构 65.12FIFO具体函数及设计实现 65.13LRU具体函数及设计实现 95.14调用关系图 146测试 146.1进入界面及产生页面走向 146.2FIFO算法及查看结果 156.3LRU算法及查看结果 166.4继续进入主界面及产生页面走向 166.5调度算法及结果 177总结与体会 18参考文献 19

摘要在地址映射过程中，若在页面中发现所要访问的页面不再内存中，则产生缺页中断。当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。常用的算法有先进先出置换算法（FIFO）,最近最久未使用置换算法（LRU）和最佳置换算法（OPT），该设计是在VC++6.0环境下分别用LRU和FIFO来实现页面置换算法的模拟程序，并测试。关键词：操作系统;页面置换算法模拟;进程调度;FIFO;LRU页面置换算法模拟程序页面置换算法模拟程序课程设计题目（改为黑色）课程设计题目（改为黑色）1引言1.1问题的提出随着硬件技术的发展，各式各样的大容量存储设备相继出现，一台计算机上可能存在多种外存储设备。不同存储设备有着不同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写速度的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性能会有很大的提高。在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。如果能够很好的使用页面置换将大大节省内存的额外开销。1.2国内外研究的现状1966年Belady在理论上提出最优页面置换算法（OPT）,此外还有先进先出（FIFO），最少使用置换算法（LRU）。不同存储设备有着不同的读写速度，同一种设备的读写速度有可能也会相差很大。因此在多种具有不同读写速度的外存储设备的环境下，选择一种合适的页面淘汰算法，对整个系统的性能会有很大的提高。1.3任务与分析本课题主要的目的是编制页面置换算法FIFO和LRU的模拟程序,并模拟其在内存的分配过程。同时根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。2需求分析本程序实现了操作系统中页式虚拟存储管理中缺页中断理想型淘汰算法，该算法在访问串中将来再也不出现的或是在离当前最远的位置上出现的页淘汰掉。这样，淘汰掉该页将不会造成因需要访问该页又立即把它调入的现象。该程序能按要求随机确定内存大小，随机产生页面数，进程数，每个进程的页数，给进程分配的页数等，然后运用理想型淘汰算法对每个进程进行计算缺页数，缺页率，被淘汰的序列等功能。3开发平台3.1开发工具VC++6.03.1开发语言VC++语言

4概要设计4.1总体设计框图进入程序进入程序输入页面数输入页面数页面走向最少使用置换先进先出置换随即产生用户输入

5详细设计页面走向最少使用置换先进先出置换随即产生用户输入开始开始输入页面数0手动输入1随机产生(0)FIFO(1)OPT输入数据输入个数输出FIFO结果输出OPT结果是否输入Y/y结束输出另外一种结果是否继续(N/n)图5.1详细设计框图开始开始初始化数据，确定页面走向判断页号是否等于页面流号算出内存中各个页号相对于当前位置，并置换了学校,也不免想到自己明年将要离开的情景,心里也感觉到一种凄凉.原来一直都想着要考研的,经过几个月的考虑,发现自己或许不适合考研吧,

复习总是那么得不尽人意。离开了老师的约束和同学的相互促进，我发现自己学

习总是静不下心来，效率一直不高。而且我觉得自己对本专业不是很感兴趣，害

怕自己又浪费掉三年，而学不到什么东西。一直就这样犹豫着，从三月到六月，

现在终于决定放弃我的考研路。考研或许真的就不适合我吧！决定不考研之后，我就面临着工作的问题，可是我拿什么来面对工作呢？回想

起这几年，感觉自己真的学到的太少了。今天和一个老同学聊天，他也这么说，

感觉自己在大学又白混了三年。暑假快要到了，我想在学校学点东西，可是具体

的又不知道学什么。又怕武汉的天气太热，学不了什么。不过怎么来说，我一定

要为工作好好准备一下。的距离淘汰距离最大的那个页号，并进行换页距离是否相等比较出现的次数淘汰出现次数少的页号，并进行换页输出淘汰的页号模块结束否是是否 图5.2为置换方法的流程图5.1代码分析结果5.11数据结构intm,intneed[],intn,result[10][20],intstate[],intcount1[];5.12FIFO具体函数及设计实现FIFO流程图开始开始页面大小m页面大小m，页面走向放在head[]结果表result[][]和状态表count[]赋值为-1结果表result[][]和状态表count[]赋值为-1RResult[][]是否为空 有是否在页表内装入页表中，缺页次数count++ 是否在页表内装入页表中，缺页次数count++ 不在 替换出先进入结果表中的页面 在替换出先进入结果表中的页面步数page++步数page++ 统计缺页数和缺页率统计缺页数和缺页率输出过程及结果输出过程及结果结束结束FIFO函数实现voidFIFO(intm,intneed[],intn)//m分配物理页面大小，n需要页面数组的最大值{ intp=0; //当前请求的页面 intdel=0;//步数 intcount1[20]; doublecount=0; //缺页数 doubleque=0; //缺页率 intresult[10][20]; //结果表 for(inti=0;i<=m;i++)for(intj=0;j<=n;j++) { result[i][j]=-1; count1[j]=-1; }while(n>=p){intk=need[p];if(p>0){ for(inti=0;i<=m;i++){ result[i][p]=result[i][p-1]; }}intf1=0;//首先看是否有空位置或者已经存在请求的页面for(inti=0;i<=m;i++){if(result[i][p]==-1) { result[i][p]=k; f1=1; i=m+1; count1[p]=k; count=count+1; p=p+1; } elseif(result[i][p]==k){f1=1;p=p+1;i=m+1;}}if(f1==1)continue;//这里发生替换result[del][p]=k; count1[p]=k; count=count+1;p=p+1; del=(del+1)%(m+1);}cout<<"*******************FIFO过程如下表************************"<<endl;for(intt3=0;t3<=n;t3++)//输出原来的页面 cout<<need[t3]<<"";cout<<endl;for(intt0=0;t0<=m;t0++)//判断页表是否填满{for(intt1=0;t1<=n;t1++) { if(result[t0][t1]!=-1) cout<<result[t0][t1]<<""; elsecout<<""<<""; } cout<<endl;}for(intj1=0;j1<=n;j1++)//对于缺页的打×，否则打√{ if(count1[j1]!=-1) cout<<"×"; elsecout<<"√";} cout<<endl; que=count/(n+1);//统计缺页次数和缺页率 cout<<"缺页次数为:"<<count<<endl; cout<<"缺页率"<<count<<"/"<<n+1<<"="<<que<<endl; cout<<"**************************************************"<<endl;}5.13LRU具体函数及设计实现LRU流程图开始开始页面大小m，页面走向放在head[]页面大小m，页面走向放在head[]给表result[][]和状态表state[]分配空间给表result[][]和状态表state[]分配空间RResult[][]是否为空 有是否在页表内装入页表中，缺页次数num++ 是否在页表内装入页表中，缺页次数num++ 不在 替换出最久没使用结果表中的页面 在替换出最久没使用结果表中的页面赋值给赋值给hsive[k] 统计缺页数和缺页率统计缺页数和缺页率输出过程及结果输出过程及结果结束结束LRU函数实现voidLRU(intm,intneed[],intn){ m++; n++; inti,j,min,num=1,k,flag; intstate[10],count[20],hsive[10]; intresult[10][20]; memset(state,0,sizeof(state));//初始化内存空间，给三个数组分配内存 memset(count,-1,sizeof(count)); memset(hsive,-1,sizeof(hsive)); memset(result,-1,sizeof(result)); for(i=0;i<n;i++)//将need数组值赋给result result[0][i]=need[i]; cout<<"*****************LRU过程如下表*********************"<<endl; for(i=0;i<n;i++) { flag=0;//标志位，如果页面和页表内的熄灯则赋值 for(j=1;j<num;j++) { if(result[0][i]==hsive[j]) { flag=1; state[j]=-1; break; } } if(flag==0)//替换 { if(num<=m) hsive[num]=result[0][i]; else { min=-1; for(j=1;j<=m;j++) { if(state[j]>min) { k=j; min=state[j]; } } hsive[k]=result[0][i]; state[k]=-1; } count[i]=1; num++; } for(j=1;j<=m;j++) { result[j][i]=hsive[j]; state[j]++; } } for(j=0;j<=m;j++)//输入个页面替换情况 { for(i=0;i<n;i++) { if(result[j][i]==-1) cout<<""; else cout<<result[j][i]<<""; } cout<<endl; } for(i=0;i<n;i++) { if(count[i]!=-1) cout<<"×"; else cout<<"√"; } cout<<endl;//统计各页面缺页次数和缺页率 cout<<"缺页次数为:"<<num-1<<endl; cout<<"缺页率"<<num-1<<"/"<<n<<"="<<double(num-1)/n<<endl; cout<<"**************************************************"<<endl;}主方法intmain(){ cout<<"*********************************************"<<endl; cout<<"*页式存储管理*"<<endl; cout<<"*********************************************"<<endl; intm; intn=0; intchoose=2; intneed[20]; charflag; while(1) { cout<<"指定内存分配页面数:"; while(flag<'0'||flag>'9') { cin>>flag; } m=flag-'0'-1; flag=''; cout<<"请选择页面序列产生方式:"<<endl; cout<<"(0)手动输入"<<endl; cout<<"(1)随机产生"<<endl; while(flag<'0'||flag>'1') { cin>>flag; }choose=flag-'0'; flag=''; if(choose==0){ cout<<"输入页面走向！以s结尾"<<endl; while(1) { while((flag<'0'||flag>'9')&&flag!='s') { cin>>flag; } if(flag=='s')break;need[n]=flag-'0'; flag=''; n=n+1; } flag=''; n=n-1; } else{ cout<<"随机产生的页面个数:"; cin>>n; n=n-1;for(inti=0;i<=n;i++) { need[i]=rand()%10; } } system("cls"); cout<<"选择页面置换算法:"<<endl; cout<<"0-FIFO1-LRU"<<endl; while(flag<'0'||flag>'1') { cin>>flag; }choose=flag-'0'; flag=''; if(choose==0){ FIFO(m,need,n); } else{ LRU(m,need,n); } cout<<"输入Y/y可以看另外一种置换算法的执行过程"<<endl; cin>>flag;if(flag=='Y'||flag=='y') { system("cls");if(choose==0) LRU(m,need,n); else FI