操作系统页面置换算法模拟实验

实验五. 请求页式存储管理的模拟[实验内容]:熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。

[实验要求]：1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。

2、执行2个页面置换模拟程序，分析缺页率的情况。

最好页框数和访问序列长度可调节，在使用同一组访问序列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。

3、在每次产生置换时要求显示分配状态和缺页率。

程序的地址访问序列通过随机数产生，要求具有足够的长度。

最好页框数和访问序列长度可调节。

实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）：程序源代码： #include <libio.h> #include "windows.h" #include <conio.h>#include <stdlib.h>#include <fstream.h>#include <io.h>#include <string.h>#include <stdio.h>void initialize(); //初始化相关数据结构void createps(); //随机生成访问序列void displayinfo(); //显示当前状态及缺页情况void fifo(); //先进先出算法int findpage(); //查找页面是否在内存void lru(); //最近最久未使用算法int invalidcount = 0; // 缺页次数int vpoint; //页面访问指针int pageframe[10]; // 分配的页框int pagehistory[10]; //记录页框中数据的访问历史int rpoint; //页面替换指针int inpflag; //缺页标志，0为不缺页，1为缺页struct PageInfo //页面信息结构{int serial[100]; // 模拟的最大访问页面数，实际控制在20以上int flag; // 标志位，0表示无页面访问数据int diseffect; // 缺页次数int total_pf; // 分配的页框数int total_pn; // 访问页面序列长度} pf_info;//////////////////////////////////////////////////////////////////////// //初始化相关数据结构void initialize(){int i,pf;inpflag=0; //缺页标志，0为不缺页，1为缺页pf_info.diseffect =0; // 缺页次数pf_info.flag =0; // 标志位，0表示无页面访问数据printf("\n请输入要分配的页框数："); // 自定义分配的页框数scanf("%d",&pf);pf_info.total_pf =pf;for(i=0;i<100;i++) // 清空页面序列{pf_info.serial[i]=-1;}}///////////////////////////////////////////////////////////////////// 随机生成访问序列void createps(void ){int s,i,pn;initialize(); //初始化相关数据结构printf("\n请输入要随机生成访问序列的长度："); //自定义随机生成访问序列的长度scanf("%d",&pn);srand(rand()); //初始化随机数队列的"种子"s=((float) rand() / 32767) * 50 + pn; // 随机产生页面序列长度pf_info.total_pn = s;for(i=0;i<s;i++) //产生随机访问序列{pf_info.serial[i]=((float) rand() / 32767) * 16 ; //随机数的大小在0-15之间}}////////////////////////////////////////////////////////////////////////// 显示当前状态及缺页情况void displayinfo(void){int i,n;if(vpoint==0){printf("\n=============页面访问序列=============\n");for(i=0; i<pf_info.total_pn; i++){printf("%4d",pf_info.serial[i]);if ((i+1) % 10 ==0) printf("\n"); //每行显示10个}printf("\n======================================\n"); }printf("访问%3d : 内存<",pf_info.serial[vpoint]);for(n=0;n<pf_info.total_pf;n++) // 页框信息{if (pageframe[n] >=0)printf("%3d",pageframe[n]);elseprintf(" ");}printf(" >");if(inpflag==1) //缺页标志，0为不缺页，1为缺页{printf(" ==>缺页");printf("缺页率%3.1f",(float)(pf_info.diseffect)*100.00/vpoint);}printf("\n");}//////////////////////////////////////////////////////////////////////// // 查找页面是否在内存，1为在内存，0为不在即缺页int findpage(int page){int n;for(n=0;n<pf_info.total_pf;n++){pagehistory[n] ++; // 访问历史加1}for(n=0;n<pf_info.total_pf;n++){if (pageframe[n]==page ){inpflag=0 ; //inpflag缺页标志，0为不缺页，1为缺页pagehistory[n]=0; //置访问历史为0return 1;}}inpflag=1; //页面不存在，缺页return 0;}//////////////////////////////////////////////////////////////////////// // FIFO页面置换算法void fifo(void){int n,count,pstate;rpoint=0; // 页面替换指针初始化为0invalidcount = 0; // 缺页数初始化为0createps(); // 随机生成访问序列count=0; // 是否装满是所有的页框for(n=0;n<pf_info.total_pf;n++) // 清除页框信息{pageframe[n]=-1;}inpflag=0; //缺页标志，0为不缺页，1为缺页for(vpoint=0;vpoint<pf_info.total_pn;vpoint++) // 执行算法{pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存if(count<pf_info.total_pf) // 开始时不计算缺页{if(pstate==0) // 页不存在则装入页面{pageframe[rpoint]=pf_info.serial[vpoint];rpoint=(rpoint+1) % pf_info.total_pf;count++;}}else // 正常缺页置换{if(pstate==0) // 页不存在则置换页面{pageframe[rpoint]=pf_info.serial[vpoint];rpoint=(rpoint+1) % pf_info.total_pf;pf_info.diseffect++; // 缺页次数加1 }}Sleep(10);displayinfo(); // 显示当前状态} // 置换算法循环结束getch();return;}/////////////////////////////////////////////////////////////////// // LRU页面置换算法void lru(void){int n,count,pstate,max;rpoint=0; // 页面替换指针invalidcount = 0; // 缺页次数初始化为0createps(); // 随机生成访问序列count=0; // 是否装满所有的页框for(n=0;n<pf_info.total_pf;n++){pageframe[n]=-1; // 清除页框信息pagehistory[n]=0; // 清除页框历史}inpflag=0; //缺页标志，0为不缺页，1为缺页for(vpoint=0;vpoint<pf_info.total_pn;vpoint++) // 执行算法{pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存if(count<pf_info.total_pf) // 开始时不计算缺页{if(pstate==0) // 页不存在则装入页面{pageframe[rpoint]=pf_info.serial[vpoint]; //把要调入的页面放入一个空的页框里rpoint=(rpoint+1) % pf_info.total_pf;count++;}}else // 正常缺页置换{if(pstate==0)// 页不存在则置换页面{max=0;for(n=1;n<pf_info.total_pf;n++){if(pagehistory[n]>pagehistory[max]){max=n;}}rpoint=max;pageframe[rpoint]=pf_info.serial[vpoint];pagehistory[rpoint]=0;pf_info.diseffect++; // 缺页次数加1 }}Sleep(10);displayinfo(); // 显示当前状态} // 置换算法循环结束_getch();return;}/////////////////////最佳置换算法自己完成/////////////////////////////////////////////////////////////////// // 主函数int main(){char ch;system("cls") ;while ( true ){printf("*******************************************\n");printf(" 若要执行FIFO页面置算法请按1\n");printf(" 若要执行LRU 页面置算法请按2\n");printf(" 若要退出请按3\n") ;printf("*******************************************\n");printf( "Enter your choice (1 or 2 or 3): ");do{ //如果输入信息不正确，继续输入ch = (char)getch() ;}while(ch != '1' && ch != '2'&& ch != '3');printf("\n\n你按的是：%c ,现在为你执行对应操作。

实验二页面置换算法实现一、实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。

（5）了解页面大小和内存实际容量对命中率的影响。

二、实验内容采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响，设计一个虚拟存储区和内存工作区，并使用下述算法来模拟实现页面的置换：1. 先进先出的算法（FIFO）2. 最近最久未使用算法（LRU）3. 最佳置换算法（OPT）实验分析在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。

但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。

一个好的页面置换算法，应该有较低的页面更换频率。

2.1 先进先出（FIFO ）页面置换算法当需要访问一个新的页面时，首先查看物理块中是否就有这个页面，若要查看的页面物理块中就有，则直接显示，不需要替换页面；如果要查看的页面物理块中没有，就需要寻找空闲物理块放入，若存在有空闲物理块，则将页面放入；若没有空闲物理块，则替换页面。

并将物理块中所有页面 timer++。

2.2 最近久未使用 (LRU) 置换算法的思路最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进行淘汰。

2.3 最佳（OPT）置换算法的思路其所选择的被淘汰的页面，是以后不使用的，或者是在未来时间内不再被访问的页面，采用最佳算法，通常可保证获得最低的缺页率。

三、实验流程3.1 系统功能图图3-1 系统功能图3.2 算法流程图1）先进先出（FIFO ）页面置换算法流程图图3-2 先进先出页面置换算法流程图2）最近久未使用 (LRU) 置换算法图3-3 最近久未使用置换算法流程图3）最佳（ OPT ）置换算法图3-4 最佳置换算法流程图四、源程序#include<iostream.h>#include <stdlib.h>#include <time.h>#include <stdio.h>#define L 20 //页面长度最大为20int M; //内存块struct Pro//定义一个结构体{int num,time;};Input(int m,Pro p[L])//打印页面走向状态{cout<<"请输入页面长度(10～20)：";do{cin>>m;if(m>20||m<10){ cout<<endl;cout<<"页面长度必须在10～20之间"<<endl<<endl;cout<<"请重新输入L：";}else break;}while(1);int i,j;j=time(NULL);//取时钟时间srand(j);//以时钟时间j为种子，初始化随机数发生器cout<<endl;cout<<"输出随机数: "<<endl;cout<<endl;for(i=0;i<m;i++){p[i].num=rand( )%10;//产生0到9之间的随机数放到数组p中p[i].time=0;cout<<p[i].num<<" ";}cout<<endl<<endl;return m;}void print(Pro *page1)//打印当前的页面{Pro *page=new Pro[M];page=page1;for(int i=0;i<M;i++)cout<<page[i].num<<" ";cout<<endl;}int Search(int e,Pro *page1 )//寻找内存块中与e相同的块号{Pro *page=new Pro[M];page=page1;for(int i=0;i<M;i++)if(e==page[i].num)return i;//返回i值return -1;}int Max(Pro *page1)//寻找最近最长未使用的页面{Pro *page=new Pro[M];page=page1;int e=page[0].time,i=0;while(i<M) //找出离现在时间最长的页面{if(e<page[i].time) e=page[i].time;i++;}for( i=0;i<M;i++)if(e==page[i].time)return i;//找到离现在时间最长的页面返回其块号return -1;}int Count(Pro *page1,int i,int t,Pro p[L])//记录当前内存块中页面离下次使用间隔长度{Pro *page=new Pro[M];page=page1;int count=0;for(int j=i;j<L;j++){if(page[t].num==p[j].num )break;//当前页面再次被访问时循环结束else count++;//否则count+1}return count;//返回count的值}int main(){int c;int m=0,t=0;float n=0;Pro p[L];m=Input(m,p);//调用input函数，返回m值cout<<"请输入分配的物理块m(2～6): ";cout<<endl<<endl;do{cin>>M;if(M>6||M<2){ cout<<endl;cout<<"物理块m必须在2～6之间"<<endl<<endl;cout<<"请重新输入m： ";}else break;}while(1);Pro *page=new Pro[M];do{for(int i=0;i<M;i++)//初始化页面基本情况{ page[i].num=0;page[i].time=m-1-i;}i=0;cout<<endl;cout<<"1:FIFO页面置换2:LRU页面置换"<<endl;cout<<"3:OPT页面置换4:退出"<<endl;cout<<"请选择页面置换算法："<<endl;cin>>c;if(c==1)//FIFO页面置换{n=0;cout<<" FIFO算法页面置换情况如下: "<<endl;cout<<endl;while(i<m){if(Search(p[i].num,page)>=0) //当前页面在内存中{cout<<p[i].num<<" "; //输出当前页p[i].numcout<<"不缺页"<<endl;i++; //i加1}else //当前页不在内存中{if(t==M)t=0;else{n++; //缺页次数加1page[t].num=p[i].num; //把当前页面放入内存中cout<<p[i].num<<" ";print(page); //打印当前页面t++; //下一个内存块i++; //指向下一个页面}}}cout<<endl;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl<<endl; }if(c==2)//LRU页面置换{n=0;cout<<" LRU算法页面置换情况如下: "<<endl;cout<<endl;while(i<m){int a;t=Search(p[i].num,page);if(t>=0)//如果已在内存块中{ page[t].time=0;//把与它相同的内存块的时间置0 for(a=0;a<M;a++)if(a!=t)page[a].time++;//其它的时间加1cout<<p[i].num<<" ";cout<<"不缺页"<<endl;}else //如果不在内存块中{n++; //缺页次数加1t=Max(page); //返回最近最久未使用的块号赋值给tpage[t].num=p[i].num; //进行替换page[t].time=0; //替换后时间置为0cout<<p[i].num<<" ";print(page);for(a=0;a<M;a++)if(a!=t) page[a].time++; //其它的时间加1 }i++;}cout<<endl;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl<<endl; }if(c==3)//OPT页面置换{n=0;cout<<" OPT算法置换情况如下:"<<endl;cout<<endl;while(i<m){if(Search(p[i].num,page)>=0)//如果已在内存块中{cout<<p[i].num<<" ";cout<<"不缺页"<<endl;i++;}else//如果不在内存块中{int a=0;for(t=0;t<M;t++)if(page[t].num==0)a++;//记录空的内存块数if(a!=0) //有空内存{int q=M;for(t=0;t<M;t++)if(page[t].num==0&&q>t)q=t;//把空内存块中块号最小的找出来page[q].num=p[i].num;n++;cout<<p[i].num<<" ";print(page);i++;}else{int temp=0,s;for(t=0;t<M;t++)//寻找内存块中下次使用离现在最久的页面if(temp<Count(page,i,t,p)){temp=Count(page,i,t,p);s=t; }//把找到的块号赋给spage[s].num=p[i].num;n++;cout<<p[i].num<<" ";print(page);i++;}}}cout<<endl;cout<<"缺页次数："<<n<<" 缺页率："<<n/m<<endl<<endl;}if(c == 4) break;}while(c==1||c==2||c==3);return 0;}五、实验结果5.1 程序主界面运行程序后，将会提示用户输入页面长度，长度在10到20之间。

计算机科学系实验报告书课程名：《操作系统》题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：一、实验目的与要求1.目的：请求页式虚存管理是常用的虚拟存储管理方案之一。

通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。

2.要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。

其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。

要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。

程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。

二、实验说明1．设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。

在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。

pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。

time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。

在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。

pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。

next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。

2．关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。

为此，程序应设置一个计数器count，来统计虚页命中发生的次数。

每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。

最终命中率=count/20*100%。

3．LRU算法中“最近最久未用”页面的确定为了能找到“最近最久未用”的虚页面，程序中可引入一个时间计数器countime，每当要访问一个虚页面时，countime的值加1，然后将所要访问的虚页的time项值设置为增值后的当前countime值，表示该虚页的最后一次被访问时间。

实验四页面置换算法模拟一、实验内容简要描述开发语言及实现平台或实验环境C++/JA V ATurbo C / Microsoft Visual Studio 6.0 / Microsoft Visual Studio .NET 2010实验目的（1）了解内存分页管理策略（2）掌握调页策略（3）掌握一般常用的调度算法（4）学会各种存储分配算法的实现方法。

（5）了解页面大小和内存实际容量对命中率的影响。

【实验内容】编程实现页面置换算法，最少实现两种算法，比较算法的优劣，并将调试结果显示在计算机屏幕上，并检测机算和笔算的一致性。

【实验要求】（1）采用页式分配存储方案，通过分别计算不同算法的命中率来比较算法的优劣，同时也考虑页面大小及内存实际容量对命中率的影响；（2）实现OPT 算法(最优置换算法) 、LRU 算法(Least Recently) 、FIFO 算法(First IN First Out)的模拟；（3）使用某种编程语言模拟页面置换算法。

二、报告主要内容1．设计思路A、设计页面走向、物理块数等初值。

B、编制程序，使用多种算法实现页面置换。

C、计算和比较缺页率。

最佳置换算法OPT(Optimal)它是由Belady于1966年提出的一种理论上的算法。

其所选择的被淘汰页面，将是以后永不使用的或许是在最长(未来)时间内不再被访问的页面。

采用最佳置换算法，通常可保证获得最低的缺页率。

但由于人目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是可以利用此算法来评价其它算法。

如果编写程序模拟该算法，可以提前设定页面访问次序，获知某个页面是否在未来不再被访问。

2．画流程图3.实验结果（输入、输出截图）程序运行结果4.主要代码#include "stdio.h"#include "stdlib.h"#include "math.h"#include "conio.h"#include "time.h"#define TRUE 1#define FALSE 0#define NULL 0#define total_instruction 20#define total_vp 10typedef struct{ int pn,pfn;}pv_type;pv_type pv[10];typedef struct pf_struct{ int pn,pfn;struct pf_struct *next;}pf_type;pf_type pf[20],*free_head,*busy_head,*busy_tail,*q; int page[total_instruction];int total_pf;int count;void initialiaze(){ int i;count=0;for(i=0;i<total_vp;i++){ pv[i].pn=i;pv[i].pfn=-1;}printf("请输入实页数目:");scanf("%d",&total_pf);for(i=0;i<=total_pf-1;i++){ pf[i].next=&pf[i+1];pf[i].pfn=i+1;pf[i].pn=-1;}pf[total_pf-1].next=NULL;free_head=&pf[0];printf("随机产生的页地址流为：\n");for(i=0;i<total_instruction;i++){ page[i]=rand()%10;printf("%2d",page[i]);}}void FIFO(){ int i,j;pf_type *p;q=busy_head=busy_tail=NULL;for(i=0;i<=total_instruction-1;i++){ printf("\n第%d次执行:",i+1);if(pv[page[i]].pfn==-1){ count+=1;printf("缺页，缺页次数count=%d,",count);if(free_head==NULL){printf("实页%d中的页面%d将被置换出去",busy_head->pfn,busy_head->pn);p=busy_head->next;pv[busy_head->pn].pfn=-1;free_head=busy_head;free_head->next=NULL;busy_head=p;}p=free_head->next;free_head->next=NULL;free_head->pn=page[i];pv[page[i]].pfn=free_head->pn;if(busy_tail==NULL)busy_head=busy_tail=free_head;else{ busy_tail->next=free_head;busy_tail=free_head;}free_head=p;}else printf("命中，缺页次数不变，仍为count=%d",count);printf("\npfn pn");for(j=0;j<=total_pf-1;j++){if(pf[j].pn!=-1)printf("\n%d%8d",pf[j].pfn,pf[j].pn);}}printf("\n先进先出算法的命中率为:%6.4f\n缺页总次数为%d\n",1-(float)count/20,count);}void main(){srand((unsigned)time(NULL));initialiaze();FIFO();三、实验心得(实验中遇到的问题及解决过程、实验中产生的错误及原因分析、实验的体会及收获、对做好今后实验提出建设性建议等。

操作系统实验报告四【实验题目】虚拟内存页面置换算法【实验目的】通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。

【实验内容】问题描述：设计程序模拟先进先出FIFO，最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。

假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, …,Pn，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。

程序要求如下：1）利用先进先出FIFO，最佳置换OPI和最近最久未使用LRU三种页面置换算法模拟页面访问过程。

2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。

3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,Pn，算法选择1-FIFO，2-OPI，3-LRU。

4）输出：每种算法的缺页次数和缺页率。

【实验要求】1) 上机前认真复习页面置换算法，熟悉FIFO，OPI，LRU三种页面分配和置换算法的过程；2) 上机时独立编程、调试程序；3) 根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。

【源代码】//--------------- YeMianZhiHuan.cpp -----------------#include "iostream.h"const int DataMax=100;const int BlockNum = 10;int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示//int Data[DataMax]={4,3,2,1,4,3,5,4,3,2,1,5,6,2,3,7,1,2,6,1}; // 测试数据//int N = 20; // 输入页面个数int Data[DataMax]; // 保存数据int Block[BlockNum]; // 物理块int count[BlockNum]; // 计数器int N ; // 页面个数int M;//最小物理块数int ChangeTimes;void DataInput(); // 输入数据的函数void DataOutput();void FIFO(); // FIFO 函数void Optimal(); // Optimal函数void LRU(); // LRU函数///*int main(int argc, char* argv[]){DataInput();// DataInput();// FIFO();// Optimal();// LRU();// return 0;int menu;while(true){cout<<endl;cout<<"* 菜单选择*"<<endl;cout<<"*******************************************************"<<endl;cout<<"* 1-FIFO *"<<endl;cout<<"* 2-Optimal *"<<endl;cout<<"* 3-LRU *"<<endl;cout<<"* 0-EXIT *"<<endl;cout<<"*******************************************************"<<endl;cin>>menu;switch(menu){case 1: FIFO();break;case 2: Optimal();break;case 3: LRU();break;default: break;}if(menu!=1&&menu!=2&&menu!=3) break;}}//*/void DataInput(){cout<<"请输入最小物理块数：";cin>>M;while(M > BlockNum) // 大于数据个数{cout<<"物理块数超过预定值，请重新输入："; cin>>M;}cout<<"请输入页面的个数：";cin>>N;while(N > DataMax) // 大于数据个数{cout<<"页面个数超过预定值，请重新输入："; cin>>N;}cout<<"请输入页面访问序列："<<endl;for(int i=0;i<N;i++)cin>>Data[i];}void DataOutput(){int i,j;for(i=0;i<N;i++) // 对所有数据操作{cout<<Data[i]<<" ";}cout<<endl;for(j=0;j<M;j++){cout<<" ";for(i=0;i<N;i++) // 对所有数据操作{if( DataShowEnable[j][i] )cout<<DataShow[j][i]<<" ";elsecout<<" ";}cout<<endl;}cout<<"缺页次数: "<<ChangeTimes<<endl;cout<<"缺页率: "<<ChangeTimes*100/N<<"%"<<endl; }void FIFO(){int i,j;bool find;int point;int temp; // 临时变量ChangeTimes = 0;for(j=0;j<M;j++)for(i=0;i<N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据for(i=0;i<M;i++){count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段}for(i=0;i<N;i++) // 对有所数据操作{// 增加countfor(j=0;j<M;j++)count[j]++;find = false; // 表示块中有没有该数据for(j=0;j<M;j++){if( Block[j] == Data[i] ){find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据ChangeTimes++; // 缺页次数++if( (i+1) > M ) // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1 {//获得要替换的块指针temp = 0;for(j=0;j<M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0; // 更新计数值// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"FIFO => "<< endl;DataOutput();}void Optimal(){int i,j,k;bool find;int point;int temp; // 临时变量，比较离的最远的时候用ChangeTimes = 0;for(j=0;j<M;j++)for(i=0;i<N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据// for(i=0;i<M;i++)// {// count[i] = 0 ; //// }for(i=0;i<N;i++) // 对有所数据操作{find = false; // 表示块中有没有该数据for(j=0;j<M;j++){if( Block[j] == Data[i] )find = true;}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据，最优算法ChangeTimes++; // 缺页次数++for(j=0;j<M;j++){// 找到下一个值的位置find = false;for( k =i;k<N;k++){if( Block[j] == Data[k] ){find = true;count[j] = k;break;}}if( !find ) count[j] = N;}if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 {//获得要替换的块指针temp = 0;for(j=0;j<M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"Optimal => "<< endl;DataOutput();}void LRU(){int i,j;bool find;int point;int temp; // 临时变量ChangeTimes = 0;for(j=0;j<M;j++)for(i=0;i<N;i++)DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据for(i=0;i<M;i++){count[i] = 0 ;}for(i=0;i<N;i++) // 对有所数据操作{// 增加countfor(j=0;j<M;j++)count[j]++;find = false; // 表示块中有没有该数据for(j=0;j<M;j++){if( Block[j] == Data[i] ){count[j] = 0;find = true;}}if( find ) continue; // 块中有该数据，判断下一个数据// 块中没有该数据ChangeTimes++; // 缺页次数++if( (i+1) > M ) // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1 {//获得要替换的块指针temp = 0;for(j=0;j<M;j++){if( temp < count[j] ){temp = count[j];point = j; // 获得离的最远的指针}}}else point = i;// 替换Block[point] = Data[i];count[point] = 0;// 保存要显示的数据for(j=0;j<M;j++){DataShow[j][i] = Block[j];DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据}}// 输出信息cout<< endl;cout<<"LRU => "<< endl;DataOutput();}【效果截图】以作业为测试数据：。

《计算机操作系统》课外实践报告题目：页面置换算法模拟班级： 13级物联网工程一班姓名：王铎学号： 130911044指导老师: 王蕾设计时间: 2014.6一、实验目标：通过设计请求页面存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页面存储管理的页面置换算法。

二、实验要求1通过随机数产生一个指令序列320条指令。

指令的地址按下述原则生成50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在地址部分。

2将指令序列换成为页地址流。

3计算并输出下述各种算法在不同内存容量下的命中率。

1）先进先出的算法FIFO2）最近最少使用算法LRU3）最近最不经常使用算法NUR三．实践内容简要描述1、实践环境windows XP/7，visual C++ 6.02、算法思路与算法原理2.1、先进先出算法（FIFO）：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单，只需要把一个进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，成为替换指针，使它总是指向最老的页面。

2.2、最近最久未使用页面置换算法（LRU）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近一段时间内最久没有使用过的页先淘汰。

该算法的出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页长时间未被访问，则它在最近一段时间不会被访问。

3概要设计3.1 总体设计框图4系统流程图图4.1详细设计框图图4.2为置换方法的流程图5代码分析结果5.1 数据结构int m, int need[],int n, result[10][20],int state[],int count1[];5.2 FIFO具体函数及设计实现FIFO流程图FIFO函数实现void FIFO(int m, int need[],int n) //m分配物理页面大小，n需要页面数组的最大值{int p=0; //当前请求的页面int del=0; //步数int count1[20];double count=0; //缺页数double que=0; //缺页率int result[10][20]; //结果表for(int i =0;i<=m;i++)for(int j=0;j<=n;j++){result[i][j]=-1;count1[j]=-1;}while(n>=p){int k=need[p];if(p>0){for(int i=0;i<=m;i++){result[i][p]=result[i][p-1];}}int f1=0;//首先看是否有空位置或者已经存在请求的页面for(int i =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;}else if(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(int t3=0;t3<=n;t3++)//输出原来的页面cout<<need[t3]<<" ";cout<<endl;for(int t0 =0;t0<=m;t0++)//判断页表是否填满{for(int t1=0;t1<=n;t1++){if(result[t0][t1]!=-1)cout<<result[t0][t1]<<" ";else cout<<" "<<" ";}cout<<endl;}for(int j1=0;j1<=n;j1++)//对于缺页的打×，否则打√{if(count1[j1]!=-1)cout<<"×";else cout<<"√";}cout<<endl;que=count/(n+1);//统计缺页次数和缺页率cout<<"缺页次数为:"<<count<<endl;cout<<"缺页率"<<count<<"/"<<n+1<<"="<<que<<endl;cout<<"**************************************************"<<endl;}5.3LRU具体函数及设计实现LRU流程图LRU函数实现void LRU(int m, int need[],int n){m++;n++;int i, j, min, num = 1, k, flag;int state[10], count[20], hsive[10];int result[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数组值赋给resultresult[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 << " ";elsecout << result[j][i] << " ";}cout << endl;}for(i = 0; i < n; i++){if(count[i] != -1)cout<<"×";elsecout<<"√";}cout << endl;//统计各页面缺页次数和缺页率cout << "缺页次数为:" << num - 1 << endl;cout << "缺页率" << num - 1 << "/"<<n << "=" << double(num - 1) / n <<endl;cout<<"**************************************************"<<endl; }主方法int main(){cout<<" *********************************************"<<endl;cout<<" * 页式存储管理*"<<endl;cout<<" ********************************************* "<<endl;int m;int n=0;int choose=2;int need[20];char flag;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(int i=0;i<=n;i++){need[i]=rand()%10;}}system("cls");cout<<"选择页面置换算法:"<<endl;cout<<"0-FIFO 1-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 FIFO(m, need,n);}else flag=' ';cout<<"输入N/n退出否则输入任意键继续"<<endl;cin>>flag;if(flag=='N'||flag=='n') break;else{system("cls");flag=' ';}}return 0;}5.4调用关系图6测试6.1进入界面及产生页面走向运行结果如下图6.1 进入管理界面图6.2产生页面走向6.2FIFO算法及查看结果图6.3选择FIFO算法结果6.3LRU算法及查看结果图6.4选择LRU结果6.4继续进入主界面及产生页面走向图6.5按y继续回到主界面设置页面为46.5调度算法及结果图6.6选择LRU算法结果图6.7选择FIFO算法结果7 总结与体会通过这次实验，我基本了解了页面置换算法的基本设置与要求，懂得了先进先出算法（FIFO）、最近最久未使用页面置换算法（LRU）的基本编程及算法原理。

操作系统实验报告_页面置换算法模拟学生实验报告姓名: 年级专业班级学号成绩验证设计实验3 请求分页系统的页面实验类型课程名称实验名称操作系统综合创新置换算法【实验目的、要求】1.通过编程实现请求分页存储管理系统的Optimal、FIFO、LRU调度算法，使学生掌握计算机虚拟存储管理中有关缺页处理方法等内容，巩固有关虚拟存储管理的知识。

2.了解Windows2000/XP中内存管理机制，掌握页式虚拟存储技术。

3.理解内存分配原理，特别是以页面为单位的虚拟内存分配方法。

【实验内容】在Windows XP或Windows 2000等操作系统环境下，使用VC、VB、Delphi、java或C等编程语言，实现请求分页存储管理系统的Optimal、FIFO、LRU调度算法。

【实验环境】(含主要设计设备、器材、软件等)计算机 C语言编程软件【实验步骤、过程】(含原理图、流程图、关键代码，或实验过程中的记录、数据等)1.启动计算机，运行C语言编程软件。

2.分析理解页面的几种基本算法的特点和原理，在纸上画出原理图。

3.编辑源程序，关键代码如下。

(1)先进先出页面置换算法。

#include<stdio.h>void main(){int i,n,t,k=3,a[100];scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&a[i]);for(i=3;i<n;i++)if(a[i]!=a[0]&&a[i]!=a[1]&&a[i]!=a[2]) //该页面在内存中，不需要置换。

{t=a[i];a[i]=a[k%3]; //通过对k值对3取余的值来确定需要置换的当前页面。

a[k%3]=t;k++; //仅当发生了页面置换时，k的值才发生改变。

printf("%d %d %d\n",a[0],a[1],a[2]);}else{printf("%d %d %d\n",a[0],a[1],a[2]);}}(2)最佳置换算法#include<stdio.h>void main(){int i,j,,n,a[100];int c1,c2,c3; // 标志该页面再次被访问时在引用串中的位置int p,k,r;printf("请输入页面数:\n");scanf("%d",&n);printf("请输入页面号引用串:\n");for(i=0;i<n;i++)scanf("%d",&a[i]);for(j=3;j<n;j++){if((a[j]!=a[0])&&(a[j]!=a[1])&&(a[j]!=a[2])) //页面在内存不发生置换～{for(p=j;p<n;p++)if(a[0]==a[p]){ c1=p;break; //跳出循环，直接置c1=n!} else c1=n; //标志该页面再次被访问时在引用串中的位置～若该页面不会再次被访问，则将c1置为最大n!for(k=j;k<n;k++)if(a[1]==a[k]){ c2=k;break; }elsec2=n;for(r=j;r<n;r++)if(a[2]==a[r]){ c3=r;break;}else c3=n; //通过比较c1,c2,c3的大小确定最长时间内不再访问的页面～if((c1>c2)&&(c1>c3)||(c1==c3)||(c1==c2)) //当前a[0]页面未来最长时间不再访问!{t=a[j];a[j]=a[0];a[0]=t; //把当前访问页面和最佳页面交换～printf("%d %d %d\n",a[0],a[1],a[2]);}if((c2>c1)&&(c2>c3)||(c2==c3)) //当前a[1]页面未来最长时间不再访问!{t=a[j];a[j]=a[1];a[1]=t;printf("%d %d %d\n",a[0],a[1],a[2]);}if((c3>c1)&&(c3>c2)) //当前a[2]页面未来最长时间不再访问!{t=a[j];a[j]=a[2];a[2]=t;printf("%d %d %d\n",a[0],a[1],a[2]); //输出置换后页框中的物理块组成～}}elseprintf("%d %d %d\n",a[0],a[1],a[2]);}}(3)LRU算法。

模拟操作系统的页面置换实验报告（模板）一、综设计实验题目：模拟操作系统的页面置换二、中文摘要：了解页面置换的概念。

理解页面置换的算法。

加深对页面置换算法的理解。

锻炼知识的运用能力和实践能力。

掌握用随机数生成满足一定条件的指令地址流的方法。

关键词：页面置换先进先出置换算法（FIFO）OPT 算法RLU算法C++三、前言实验目的1、掌握操作系统的页面置换过程，加深理解页式虚拟存储器的实现原理。

2、掌握用随机数生成满足一定条件的指令地址流的方法。

3、掌握页面置换的模拟方法。

实验要求与内容1、采用一种熟悉的语言，如C、PASCAL 或C++等，编制程序，最好关键代码采用C/C++，界面设计可采用其它自己喜欢的语言。

2、模拟操作系统采用OPT、FIFO 和LRU 算法进行页面置换的过程。

3、设程序中地址范围为0 到32767，采用随机数生成256 个指令地址，满足50%的地址是顺序执行，25%向前跳，25%向后跳。

为满足上述条件，可采取下列方法：设d0=10000，第n个指令地址为dn，第n+1 个指令地址为dn+1，n的取值范围为0 到255。

每次生成一个1 到1024 范围内的随机数a，如果a落在1 到512 范围内，则dn+1=dn+1。

如果a落在513 到768范围内，则设置dn+1为1 到dn范围内一个随机数。

如果a落在769 到1024范围内，则设置dn+1为dn到32767 范围内一个随机数。

例如：srand();初始化一个随机函数。

a[0]＝10*rand()/32767*255+1;a[1]=10*rand()/32767*a[0]…语句可用来产生a[0]与a[1]中的随机数。

或采用以下方式：（1）通过随机数产生一个指令序列，共320 条指令。

指令的地址按下述原则生成：A：50%的指令是顺序执行的B：25%的指令是均匀分布在前地址部分C：25%的指令是均匀分布在后地址部分具体的实施方法是：A：在[0，319]的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1 的指令C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m'D：顺序执行一条指令，其地址为m'+1E：在后地址[m'+2，319]中随机选取一条指令并执行F：重复步骤A-E，直到320 次指令（2）将指令序列变换为页地址流设：页面大小为1K；用户内存容量4 页到32 页；用户虚存容量为32K。

《计算机操作系统》课外实践报告题目：页面置换算法模拟班级： 13级物联网工程一班姓名：王铎学号： 130911044指导老师: 王蕾设计时间: 2014.6一、实验目标：通过设计请求页面存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页面存储管理的页面置换算法。

二、实验要求1通过随机数产生一个指令序列 共320条指令。

指令的地址按下述原则生成50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在地址部分。

2将指令序列换成为页地址流。

3计算并输出下述各种算法在不同内存容量下的命中率。

（1）先进先出的算法 FIFO（2）最近最少使用算法 LRU（3）最近最不经常使用算法 NUR三．实践内容简要描述1、实践环境windows XP/7，visual C++ 6.02、算法思路与算法原理2.1、先进先出算法（FIFO）：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

该算法实现简单，只需要把一个进程已调入内存的页面，按先后次序连接成一个队列，并设置一个指针，成为替换指针，使它总是指向最老的页面。

2.2、最近最久未使用页面置换算法（LRU）：算法的基本思想：当需要淘汰某一页时，选择离当前时间最近一段时间内最久没有使用过的页先淘汰。

该算法的出发点是，如果某页被访问了，则它可能马上还被访问。

或者反过来说，如果某页长时间未被访问，则它在最近一段时间不会被访问。

3概要设计3.1 总体设计框图4系统流程图图4.1详细设计框图图4.2为置换方法的流程图5代码分析结果5.1 数据结构int m, int need[],int n, result[10][20],int state[],int count1[];5.2 FIFO具体函数及设计实现FIFO流程图FIFO函数实现void FIFO(int m, int need[],int n) //m分配物理页面大小，n需要页面数组的最大值{int p=0; //当前请求的页面int del=0; //步数int count1[20];double count=0; //缺页数double que=0; //缺页率int result[10][20]; //结果表for(int i =0;i<=m;i++)for(int j=0;j<=n;j++){result[i][j]=-1;count1[j]=-1;}while(n>=p){int k=need[p];if(p>0){for(int i=0;i<=m;i++){result[i][p]=result[i][p-1];}}int f1=0;//首先看是否有空位置或者已经存在请求的页面for(int i =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;}else if(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(int t3=0;t3<=n;t3++)//输出原来的页面cout<<need[t3]<<" ";cout<<endl;for(int t0 =0;t0<=m;t0++)//判断页表是否填满{for(int t1=0;t1<=n;t1++){if(result[t0][t1]!=-1)cout<<result[t0][t1]<<" ";else cout<<" "<<" ";}cout<<endl;}for(int j1=0;j1<=n;j1++)//对于缺页的打×，否则打√{if(count1[j1]!=-1)cout<<"×";else cout<<"√";}cout<<endl;que=count/(n+1);//统计缺页次数和缺页率cout<<"缺页次数为:"<<count<<endl;cout<<"缺页率"<<count<<"/"<<n+1<<"="<<que<<endl;cout<<"**************************************************"<<endl;}5.3LRU具体函数及设计实现LRU流程图LRU函数实现void LRU(int m, int need[],int n){m++;n++;int i, j, min, num = 1, k, flag;int state[10], count[20], hsive[10];int result[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数组值赋给resultresult[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 << " ";elsecout << result[j][i] << " ";}cout << endl;}for(i = 0; i < n; i++){if(count[i] != -1)cout<<"×";elsecout<<"√";}cout << endl;//统计各页面缺页次数和缺页率cout << "缺页次数为:" << num - 1 << endl;cout << "缺页率" << num - 1 << "/"<<n << "=" << double(num - 1) / n <<endl;cout<<"**************************************************"<<endl; }主方法int main(){cout<<" *********************************************"<<endl;cout<<" * 页式存储管理*"<<endl;cout<<" ********************************************* "<<endl;int m;int n=0;int choose=2;int need[20];char flag;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(int i=0;i<=n;i++){need[i]=rand()%10;}}system("cls");cout<<"选择页面置换算法:"<<endl;cout<<"0-FIFO 1-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 FIFO(m, need,n);}else flag=' ';cout<<"输入N/n退出否则输入任意键继续"<<endl;cin>>flag;if(flag=='N'||flag=='n') break;else{system("cls");flag=' ';}}return 0;}5.4调用关系图6测试6.1进入界面及产生页面走向运行结果如下图6.1 进入管理界面图6.2产生页面走向6.2FIFO算法及查看结果图6.3选择FIFO算法结果6.3LRU算法及查看结果图6.4选择LRU结果6.4继续进入主界面及产生页面走向图6.5按y继续回到主界面设置页面为46.5调度算法及结果图6.6选择LRU算法结果图6.7选择FIFO算法结果7 总结与体会通过这次实验，我基本了解了页面置换算法的基本设置与要求，懂得了先进先出算法（FIFO）、最近最久未使用页面置换算法（LRU）的基本编程及算法原理。

“计算机操作系统”课程设计大作业页面置换算法模拟实验(含完整资料，可直接提交)一、题目: 页面置换算法模拟实验二、目的分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法对用户输入的页面号请求序列进行淘汰和置换，从而加深对页面置换算法的理解。

三、内容和要求请用C/C++语言编一个页面置换算法模拟程序。

用户通过键盘输入分配的物理内存总块数，再输入用户逻辑页面号请求序列，然后分别采用最佳(Optimal)置换算法、先进先出(FIFO)页面置换算法和最近最少使用(LRU)置换算法三种算法对页面请求序列进行转换，最后按照课本P150页图4-26的置换图格式输出每次页面请求后各物理块内存放的虚页号，并算出总的缺页率（缺页次数/总的请求次数）。

最后三种页面置换算法的优缺点。

三种页面置换算法的思想可参考教材P149-P152页。

假设页面号请求序列为4、3、2、1、4、3、5、4、3、2、1、5，当分配给某进程的物理块数分别为3块和4块时，试用自己编写的模拟程序进行页面转换并输出置换图和缺页次数、缺页率。

!四、提交内容本大作业每个人必须单独完成。

最后需提交的内容包括：源程序（关键代码需要注释说明）、可运行程序、运行结果、算法思路及流程图、心得体会。

大作业严禁抄袭。

发现抄袭一律以不及格论。

请大家严格按照大作业题目来编写程序，不要上交以前布置的大作业。

如果提交的大作业题目与本文档要求不符，成绩一律为及格。

目录摘要 (2)%正文 (2)1、设计思路 (3)2、各模块的伪码算法 (6)3、函数的调用关系图 (14)4、测试 (20)设计总结 (21)参考文献 (22)致谢 (23)附录：部分源程序代码 (24)'摘要UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。

实验4 页面置换算法（2学时）一、实验目的通过实验加强对虚拟存储管理中页面置换算法的理解和掌握。

二、实验内容编写程序实现虚拟存储管理中OPT,FIFO,LRU页面置换算法。

三、实验要求1、任意给出一组页面访问顺序（如页面走向是1、2、5、7、5、7、1、4、3、5、6、4、3、2、1、5、2）。

2、分配给该作业一定的物理块（如3块、4块等）。

3、利用OPT,FIFO,LRU页面置换算法模拟页面置换过程并计算其缺页率。

4、每访问一个页面均需给出内存中的内容（内存中的页面号），若有淘汰还需给出淘汰的页面号。

5、通过给出特殊的页面访问顺序，分配不同的物理块，利用FIFO 算法计算其缺页率，进一步理解Belady现象。

6、（附加）实现CLOCK置换算法，修改位可在确定页面号时直接任意给出。

代码部分：#include <stdlib.h>#include <iostream.h>#include <time.h>void rand(int n,int p[])//这函数是产生n个1~10的随机数放到p[]数组里面{int START=1;int END=10;int v;int i;int a;srand(time(NULL));for(i=0; i<n; i++){v=rand()%(END-START+1)+START;p[i]=v;cout<<v;}}struct Pro{int num,time;//num存放具体的内容，time在不同算法里面有不同的意义}; //它们是物理块和页面的数据结构int Input(int m,int N,Pro *p,Pro *page)//完成p[]数组和page[]的初始化工作{ //p[]数组是存放页面的空间，m是页面的长度//page[]是可以使用的物理块，N是物理块的大小cout<<endl<<"请输入各页面号"<<endl;int *p2=new int[m];rand(m,p2);for(int i=0;i<m;i++){p[i].num=p2[i];p[i].time=0;}for(i=0;i<N;i++)//初试化页面基本情况{page[i].num=0;page[i].time=N+2-i;}return m;}int Search(int e,Pro *page,int N)//算法里面都要用到它。

淮海工学院计算机科学系实验报告书课程名：《操作系统原理》题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：一、实验目的与要求1.目的：请求页式虚存管理是常用的虚拟存储管理方案之一。

通过请求页式虚存管理中对页面置换算法的模拟，有助于理解虚拟存储技术的特点，并加深对请求页式虚存管理的页面调度算法的理解。

2.要求：本实验要求使用C语言编程模拟一个拥有若干个虚页的进程在给定的若干个实页中运行、并在缺页中断发生时分别使用FIFO和LRU算法进行页面置换的情形。

其中虚页的个数可以事先给定（例如10个），对这些虚页访问的页地址流（其长度可以事先给定，例如20次虚页访问）可以由程序随机产生，也可以事先保存在文件中。

要求程序运行时屏幕能显示出置换过程中的状态信息并输出访问结束时的页面命中率。

程序应允许通过为该进程分配不同的实页数，来比较两种置换算法的稳定性。

二、实验说明1．设计中虚页和实页的表示本设计利用C语言的结构体来描述虚页和实页的结构。

在虚页结构中，pn代表虚页号，因为共10个虚页，所以pn的取值范围是0—9。

pfn代表实页号，当一虚页未装入实页时，此项值为-1；当该虚页已装入某一实页时，此项值为所装入的实页的实页号pfn。

time项在FIFO算法中不使用，在LRU中用来存放对该虚页的最近访问时间。

在实页结构中中，pn代表虚页号，表示pn所代表的虚页目前正放在此实页中。

pfn代表实页号，取值范围（0—n-1）由动态指派的实页数n所决定。

next是一个指向实页结构体的指针，用于多个实页以链表形式组织起来，关于实页链表的组织详见下面第4点。

2．关于缺页次数的统计为计算命中率，需要统计在20次的虚页访问中命中的次数。

为此，程序应设置一个计数器count，来统计虚页命中发生的次数。

每当所访问的虚页的pfn项值不为-1，表示此虚页已被装入某实页内，此虚页被命中，count加1。

最终命中率=count/20*100%。

操作系统—页面置换算法实验报告本报告旨在介绍操作系统中的页面置换算法，包括实验的目的和背景以及页面置换算法的概念和作用。

本实验旨在描述实验环境以及所使用的页面置换算法，包括FIFO、LRU、OPT等。

同时，还会详细介绍实验步骤和设置的参数。

实验环境操作系统：Windows 10编程语言：C++开发环境：Visual。

2019页面置换算法FIFO（First-In-First-Out）算法：按照先进先出的原则置换页面，最早进入内存的页面会被置换出去。

LRU（Least Recently Used）算法：根据页面的使用情况，置换最长时间没有被访问过的页面。

OPT（Optimal）算法：理论上最优的页面置换算法，根据未来一段时间内页面的访问情况，选择最少使用的页面进行置换。

实验步骤创建一个模拟操作系统的C++程序。

设定内存大小、页面大小和页面数等参数。

实现FIFO算法，将其应用于模拟操作系统中的页面置换过程。

实现LRU算法，将其应用于页面置换过程。

实现OPT算法，将其应用于页面置换过程。

运行模拟程序，观察不同页面置换算法的效果。

分析比较不同算法的页面置换结果，评估其优缺点。

参数设置内存大小：512MB页面大小：4KB页面数：128以上是本次实验的实验设计，将通过创建模拟操作系统程序，实现FIFO、LRU和OPT等页面置换算法，并对其结果进行比较和评估。

本实验展示了页面置换算法的不同性能，并分析了各种算法的优缺点。

实验结果表明，不同的页面置换算法对系统性能有显著影响。

以下是对各种算法的性能分析：先进先出(FIFO)算法：该算法将最早进入内存的页面置换出去。

优点是简单易实现，缺点是无法适应程序的访问模式变化，容易产生"Belady异常"。

先进先出(FIFO)算法：该算法将最早进入内存的页面置换出去。

优点是简单易实现，缺点是无法适应程序的访问模式变化，容易产生"Belady异常"。

湖南师范大学树达学院操作系统课程实验报告题目编程模拟页面置换算法理工系09级电子商务专业姓名学号指导教师张楚才2011年5月 5 日实验题目：编程模拟页面置换算法实验要求：利用C语言分别实现先进先出置换算法FIFO、最佳置换算法OPT、最近最久未使用置换算法LRU。

要求在任意给定的页面访问序列和内存的物理块数下，输出每种算法下的缺页率。

例如，假定系统为某进程分配了3个物理块，进程运行时的页面走向为7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，开始时3个物理块均为空，分别求出每种算法下的缺页率。

#include<stdio.h>void Print(int bc[],int blockCount){for(int i=0;i<blockCount;i++){printf("%d ",bc[i]);}printf("\n");}bool Travel(int bc[],int blockCount,int x){bool is_found=false;int i;for(i=0;i<blockCount;i++){if(bc[i]==x){is_found=true;break;}}return is_found;}void FIFO(int pc[],int bc[],int pageCount,int blockCount)printf("0：FIFO置换算法\n");int i;if(pageCount<=blockCount){printf("缺页次数为0\n");printf("缺页率为0\n");}else{int noPage=0;int p=0;for(i=0;i<pageCount;i++){//printf("引用页：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}else{if(p==blockCount){p=0;}bc[p]=pc[i];p++;}noPage++;//printf("物理块情况：\n");//Print(bc,blockCount);}//printf("\n");}printf("FIFO缺页次数为:%d\n",noPage);printf("FIFO缺页率为:%.2f%%\n",(float)noPage/pageCount*100);}}int FoundMaxNum(int a[],int n){int k,j;k=a[0];j=0;for (int i=0;i<n;i++){if(a[i]>=k){k=a[i];j=i;}}return j;}void LRU(int pc[],int bc[],int pageCount,int blockCount) {printf("1：LRU置换算法\n");if(pageCount<=blockCount){printf("缺页次数为0\n");printf("缺页率为0\n");}else{int noPage=0;int i,j,m;int bc1[100];for(i=0;i<blockCount;i++){bc1[i]=0;}for(i=0;i<pageCount;i++){// printf("引用页：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];for(int p=0;p<=i;p++){bc1[p]++;}}else{for(j=0;j<blockCount;j++){bc1[j]++;}int k=FoundMaxNum(bc1,blockCount);bc[k]=pc[i];bc1[k]=1;}noPage++;//printf("物理快情况：\n");//Print(bc,blockCount);}else if(Travel(bc,blockCount,pc[i])){if(i<blockCount){for(j=0;j<=i;j++){bc1[j]++;}for(m=0;m<=i;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}else{for(j=0;j<blockCount;j++)bc1[j]++;}for(m=0;m<blockCount;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}}//printf("\n");}printf("LRU缺页次数为:%d\n",noPage);printf("LRU缺页率为:%.2f%%\n",(float)noPage/pageCount*100);}}void Optiomal(int pc[],int bc[],int pageCount,int blockCount){printf("2：最佳置换算法\n");if(pageCount<=blockCount){printf("缺页次数为0\n");printf("缺页率为0\n");}else{int noPage=0;int i,j,k;for(i=0;i<pageCount;i++){// printf("引用页：%d\n",pc[i]);if(!Travel(bc,blockCount,pc[i])){if(i<blockCount){bc[i]=pc[i];}{int max=0;int blockIndex;;for(j=0;j<blockCount;j++){for(k=i;k<pageCount;k++){if(bc[j]==pc[k]){break;}}if(k>=max){max=k;blockIndex=j;}}bc[blockIndex]=pc[i];}noPage++;//printf("物理快情况：\n");//Print(bc,blockCount);}//printf("\n");}printf("OPT缺页次数为:%d\n",noPage);printf("OPT缺页率为:%.2f%%\n",(float)noPage/pageCount*100);}}int main(){int pageCount,blockCount,i,pc[100];printf("输入页面数\n");scanf("%d",&pageCount);printf("输入页面走向\n");for(i=0;i<pageCount;i++){scanf("%d",&pc[i]);}blockCount=3;//物理块数int bc1[100];printf("\n");FIFO(pc,bc1,pageCount,blockCount);int bc2[100];printf("\n");LRU(pc,bc2,pageCount,blockCount);int bc3[100];printf("\n");Optiomal(pc,bc3,pageCount,blockCount);return 0;}。

页面置换算法实验实验一、实验目的通过编写和调试页面置换算法的模拟程序以加深对虚拟存储管理技术的理解，掌握几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。

二、实验要求编写程序用来模拟虚拟页式存储管理中的页面置换算法，要求至少采用两种不同的页面置换算法分别进行模拟。

要求：1. 物理块固定为4块2. 从键盘输入N个页面号3. 输出每次物理块中的页面号和缺页次数，缺页率三、实验方法内容1.算法设计思路在内存运行过程中，若其所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。

但应将那个页面调出，需根据一定的算法来确定。

通常，把选择换出页面的算法成为页面置换算法。

置换算法的好坏，将直接影响到系统的性能。

一个好的页面置换算法，应具有较低的页面更换频率。

从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会在访问的页面调出。

目前存在着许多种置换算法（如FIFO，OPT，LRU），他们都试图更接近理论上的目标。

2.算法流程图开始void PageReplacement ::Start (int tactics )PageReplacement构造函数得到页面序列，调用Init()初始化各项数据根据选择的页面置换算法开始执行计算输出缺页率结束void PageReplacement ::PageFaultRate ()#define _OPT 0//最佳页面置换#define _FIFO 1//先进先出#define _LRU 2//最近最少使用开始判断当前页面序列是否已到末尾N判断当前访问页面是否缺页页面序列加1，开始下一个页面输出当前页面和页框状态N缺页数加1Y选择相应页面置换算法，计算出应被置换出的物理块号根据上一步得到的页块号进行置换输出当前页面和页框状态，并输出缺页信息结束Ym_CurrentPage != PAGELENGTHif (ABSENT == JudgeAbsent ())m_AbsentCount ++;int replaceNo =OPT ();或int replaceNo = FIFO ();或int replaceNo = LRU ();Replace (replaceNo );Display (replaceNo );Display (int statue = NOABSENT );3. 算法中用到的数据结构用到了排序相关的算法4. 主要的常量变量#define mSIZE 4 #define pSIZE 20static int memery[mSIZE]={0,0,0}; int process[pSIZE];5. 主要模块void FIFO(); void LRU(); void OPT(); void get();int main()四、实验代码五、实验结果#include <stdio.h>#include <stdlib.h>#include<iostream.h>#define mSIZE 4#define pSIZE 20static int memery[mSIZE]={0,0,0};int process[pSIZE];void FIFO();void LRU();void OPT();void get();int main(){int code;cout<<"(物理块固定为4块)请您从键盘输入20个页面号:"<<endl;for(int i=0;i<pSIZE;i++){cout<<"\t\t第"<<(i+1)<<"个页面号为:";cin>>process[i];}cout<<endl;do{printf("|------------------------------------------------------|\n");printf("| 实验三页面置换算法实验|\n");printf("| 1.FIFO 先进先出页面替换算法|\n");printf("| 2.LRU 最近最少使用页面替换算法|\n");printf("| 3.OPT 最佳页面替换算法|\n");printf("| 4.EXIT 退出实验步骤|\n");printf("|------------------------------------------------------|\n");cout<<endl;printf("请输入您的选择:(例如: 1) ");scanf("%d",&code);switch(code){case 1:{FIFO();}break;case 2:{LRU();}break;case 3:{OPT();}break;case 4:{}break;}}while (code!=4);system("PAUSE");return 0;}void get(){int i;for(i=0;i<20;i++){printf("%d ",process[i]);}printf("\n");}void FIFO(){int memery[mSIZE]={0,0,0};int time[mSIZE]={0,0,0};int i,j,k;int max=0;int count=0;get();for(i=0;i<mSIZE;i++){memery[i]=process[i];time[i]=i;for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");} /*前mSIZE个数直接放入*/ for(i=mSIZE;i<pSIZE;i++){for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=process[i])k++;}/*判断新页面号是否在物理块中*/ if(k==mSIZE)/*如果都不在物理块中*/{count++;if(time[0]<time[1])max=0;else max=1;if(time[2]<time[max])max=2;memery[max]=process[i];time[max]=i;for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");}else{for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");}}printf("time:%d\n",count);printf("min zhong lv=%d%",(20-count)*100/20);get();}void LRU(){int memery[mSIZE]={0,0,0};int flag[mSIZE]={0,0,0};int i,j,k;int max=0,maxflag=0;int count=0;get();for(i=0;i<mSIZE;i++){memery[i]=process[i];flag[i]=i;for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");} /*前mSIZE个数直接放入*/for(i=mSIZE;i<pSIZE;i++){for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=process[i])k++;else flag[j]=i;}/*判断新页面号是否在物理块中*/ if(k==mSIZE)/*如果都不在物理块中*/{count++;if(flag[0]<flag[1])max=0;else max=1;if(flag[2]<flag[max])max=2;memery[max]=process[i];flag[max]=i;for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");}else{for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");}}printf("time:%d\n",count);printf("min zhong lv=%d%",(20-count)*100/20);get();}void OPT(){int memery[mSIZE] = {0,0,0};int next[mSIZE]={0};int i,j,k,l;int count=0,max;get();for(i=0;i<mSIZE;i++){memery[i]=process[i];for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");} /*前mSIZE个数直接放入*/ for(i=mSIZE;i<pSIZE;i++){for(j=0,k=0;j<mSIZE;j++){if(memery[j]!=process[i])k++;}/*判断新页面号是否在物理块中*/ if(k==mSIZE)/*如果都不在物理块中*/{count++;for(l=i+1;l<pSIZE;l++){if(memery[0]==process[l]){next[0]=l;goto lin1;}}next[0]=l;goto lin1;lin1:for(l=i+1;l<pSIZE;l++){if(memery[1]==process[l]){next[1]=l;goto lin2;}}next[1]=l;goto lin2;lin2:for(l=i+1;l<pSIZE;l++){if(memery[2]==process[l]){next[2]=l;goto lin3;}}next[2]=l;goto lin3;lin3:if(next[0]>=next[1])max=0;else max=1;if(next[2]>=next[max])max=2;memery[max]=process[i];for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");}else {for(j=0;j<mSIZE;j++){printf("%d ",memery[j]);}printf("\n");}}printf("time=%d\n",count);printf("min zhong lv=%d%",(20-count)*100/20);get();}1.执行结果2.结果分析显而易见，LRU算法的效率最高。