实验五存储管理常用页面置换算法模拟实验

实验5 页面置换算法模拟实验一．实验目的1.进一步掌握虚拟存储器的实现方法。

2.掌握各种页面置换算法。

3.比较各种页面置换算法的优缺点。

二．实验内容模拟实现页面置换算法，步骤为：①使用产生随机数函数得到一个随机的数列，作为将要载入的页面序列。

②使用先进先出（FIFO）算法、最近最久未使用（LRU）置换算法和最佳（OPT）置换算法，列出所需淘汰的页面号序列。

③列出缺页中断次数。

三．参考源程序如下：#include <stdio.h>#include <stdlib.h>#include <time.h>#define N 10#define B 4/*------------------------------------------------------------------------函数名：IsInBuf()，返回某个数X在不在缓冲Buf[],如在，返回位置，否则返回－1--------------------------------------------------------------------------*/int IsInBuf(int buf[],int x){int i,j=-1;for(i=0;i<B;i++){if(buf[i]==x){ j=i;break; }else if(buf[i]==-1){ buf[i]=x;j=i;break; } }return j;}/*------------------------------------------------------------------------函数名：oldest()，返回最近最久未使用的页面位置--------------------------------------------------------------------------*/int oldest(int f[]){int i,j=0,max=-1;for(i=0;i<B;i++){if(f[i]>max){ max=f[i]; j=i; }f[i]++; }return j;}/*------------------------------------------------------------------------函数名：oldest2()，返回未来最久未使用的页面位置--------------------------------------------------------------------------*/int oldest2(int list[],int buf[],int f[],int start){int i,j;for(i=0;i<B;i++){for(j=start;j<N;j++){ if(buf[i]==list[j]) break; }f[i]=j; }return oldest(f);}int main(void){int list[N];int buf[B],f[B],i,j ;int old=0;int change=0;srand((int)time(NULL)); /*生成一系列随机数并初始化环境*/for(i=0;i<B;i++) {buf[i]=f[i]=-1;}printf("\nThe Random List:\n");for(i=0;i<N;i++){ list[i]=(int)rand()%10; printf("%2d",list[i]); } printf("\nFIFO\n");/*显示FIFO淘汰的页面序列*/change=0;for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];old=(old+1)%(int)B;change++;}else printf(" "); }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/printf("\nLRU\n");/*显示LRU淘汰的页面序列*/change=0;for(i=0;i<B;i++) {buf[i]=f[i]=-1;}for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);old=oldest(f);if(j==-1){printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++;}else{ f[j]=0; printf(" "); } }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/printf("\nOPT\n");/*显示OPT淘汰的页面序列*/change=0;for(i=0;i<B;i++) {buf[i]=f[i]=-1;}for(i=0;i<N;i++){j=IsInBuf(buf,list[i]);if(j==-1){old=oldest2(list,buf,f,i);printf("%2d",buf[old]);buf[old]=list[i];f[old]=0;change++; }else{ f[j]=0; printf(" "); } }printf("\n changes %2d\n",change); /*显示有多少个缺页中断*/ getch();return 0; }（假设当前随机产生的页面序列为：7 1 0 4 2 5 8 6 9 1)四.填表题(1).在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数分别为4时，试计算采用先进先出淘汰算法时的缺页率(假设开始执行时主存中没有页面)，并将所得结果填表。

实验编号４名称页面置换算法模拟实验目的通过请求页式存储管理中页面置换算法模拟设计，以便：1、了解虚拟存储技术的特点2、掌握请求页式存储管理中页面置换算法实验内容与步骤设计一个虚拟存储区和内存工作区，并使用FIFO和LRU算法计算访问命中率。

<程序设计>先用srand()函数和rand()函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算相应的命中率。

<程序1>#include <windows.h> //Windows版，随机函数需要，GetCurrentProcessId()需要//#include <stdlib.h>//Linux版，随机函数srand和rand需要#include <stdio.h> //printf()需要#define TRUE 1#define FALSE 0#define INV ALID -1#define NULL 0#define total_instruction 320 //共320条指令#define total_vp 32 //虚存页共32页#define clear_period 50 //访问次数清零周期typedef struct{//定义页表结构类型〔页面映射表PMT〕int pn, pfn, counter, time;//页号、页框号(块号)、一个周期内访问该页面的次数、访问时间}PMT;PMT pmt[32];typedef struct pfc_struct{//页面控制结构int pn, pfn;struct pfc_struct *next;}pfc_type;pfc_type pfc[32];pfc_type *freepf_head,*busypf_head,*busypf_tail;//空闲页头指针，忙页头指针，忙页尾指针int NoPageCount; //缺页次数int a[total_instruction];//指令流数组int page[total_instruction], offset[total_instruction];//每条指令的页和页内偏移void initialize( int );void FIFO( int );//先进先出void LRU( int );//最近最久未使用void NRU( int );//最近最不经常使用/****************************************************************************main()*****************************************************************************/ void main(){int i,s;//srand(10*getpid());//用进程号作为初始化随机数队列的种子//Linux版srand(10*GetCurrentProcessId());//用进程号作为初始化随机数的种子//Windows版s=rand()%320;//在[0，319]的指令地址之间随机选取一起点mfor(i=0;i<total_instruction;i+=4){//产生指令队列if(s<0||s>319){printf("when i==%d,error,s==%d\n",i,s);exit(0);}a[i]=s;//任意选一指令访问点m。

存储管理模拟实现On March 12, 2022, study standards and apply standards.一、实验目的存储管理的主要功能之一是合理地分配空间;请求页式管理是一种常用的虚拟存储管理技术;本实验的目的是通过请求页式存储管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式管理的页面置换算法;二、实验内容编程实现页面置换算法,要求输出页面的置换过程,具体可以编程实现OPT、FIFO和LRU算法;1．过随机数产生一个指令序列,共320条指令;其地址按下述原则生成：①50%的指令是顺序执行的；②25%的指令是均匀分布在前地址部分；③25%的指令是均匀分布在后地址部分；具体的实施方法是：A.在0,319的指令地址之间随机选区一起点M;B.顺序执行一条指令,即执行地址为M+1的指令；C.在前地址0,M+1中随机选取一条指令并执行,该指令的地址为M’;D.顺序执行一条指令,其地址为M’+1；E.在后地址M’+2,319中随机选取一条指令并执行；F.重复A—E,直到执行320次指令;2．指令序列变换成页地址流设：1页面大小为1K；（2）用户内存容量为4页到32页；（3）用户虚存容量为32K;在用户虚存中,按每K存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为：第0条—第9条指令为第0页对应虚存地址为0,9；第10条—第19条指令为第1页对应虚存地址为10,19；;;;;;;;;;;;;;;;;;;;;;第310条—第319条指令为第31页对应虚存地址为310,319；按以上方式,用户指令可组成32页;3. 计算并输出下述各种算法在不同内存容量下的命中率;A.FIFO先进先出的算法B.LRU最近最少使用算法C．LFU最少访问页面算法三、实验要求1、需写出设计说明；2、设计实现代码及说明3、运行结果；四、主要实验步骤1、分析算法结构；画出算法的流程图,即设计说明；根据画出的流程图使用C语言编写相应的代码代码过长,放到最后；程序主要由main函数和以下几个函数组成：void initialization;初始化内存数据void FIFO;FIFO先进先出算法；void LRU;LRU最久未使用算法；void LFU;LFU最近最久未使用算法：流程图如下：页面置换算法整体结构FIFO页面置换算法LRU页面置换算法LFU页面置换算法2、设计说明及源代码FIFO算法设计说明：按照所要求的产生随机指令序列,存放在order320这个数组中;通过循环产生这些随机指令,每产生一条都要进行下列判断：是否和内存中即mem _volume4中存放的页面相同,如果相同则不做任何操作,如果不相同,则产生缺页,相应的缺页次数加一,按照fcfs将最先进入内存的页数淘汰,并将该页写到内存中去;重复上面的操作直到完成这320条指令;源代码：pp : 定义控制台应用程序的入口点;.3fpp : 定义控制台应用程序的入口点;.3fpp : 定义控制台应用程序的入口点;//include ""int _tmainint argc, _TCHAR argv{return 0;}include <>include <>include <>define N 5 //定义运行次数void main{int order320,count32={0},compare4={0},mem_volume4={100,100,100,100};//compare数组中存放了每次要比较的四个内存块中页数的调用次数int l=0,i=0,j,k=0,cx=0;int min,num=0,n,sign=0,add=0;float value=0,sum=0;srandtimeNULL;forcx=0;cx<N;cx++{whilei<320{orderi=rand%320;forj=0;j<4;j++iforderi+1/10==mem_volumej{n=orderi+1/10;countn+=1;sign=1; //相同执行加1操作}ifsignsign=0;else{l++;ifmem_volume3==100{mem_volume3=orderi+1/10;n=orderi+1/10;countn+=1;}else{ min=1000;fornum=0;num<4;num++{k=mem_volumenum;comparenum=countk;ifcomparenum<min{min=comparenum;j=num; //通过比较确定最少使用的页数,}}mem_volumej=orderi+1/10;}}i++;orderi=rand%orderi-1+2;forj=0;j<4;j++iforderi/10==mem_volumej{n=orderi/10;countn+=1;sign=1;}ifsignsign=0;else {l++;ifmem_volume2==100{mem_volume2=orderi+1/10;n=orderi+1/10;countn+=1;}else{ min=1000;fornum=0;num<4;num++{k=mem_volumenum;comparenum=countk;ifcomparenum<min{min=comparenum;j=num;}}mem_volumej=orderi+1/10;}}i++;orderi=orderi-1+1;forj=0;j<4;j++iforderi/10== mem_volumej{n=orderi/10;countn+=1;sign=1;}ifsignsign=0;else{l++;ifmem_volume1==100{mem_volume1=orderi+1/10;n=orderi+1/10;countn+=1;}else{ min=1000;fornum=0;num<4;num++{k=mem_volumenum;comparenum=countk;ifcomparenum<min{min=comparenum;j=num;}}mem_volumej=orderi+1/10;}}i++;orderi=rand%319-orderi-1-2+orderi-1+2;forj=0;j<4;j++iforderi/10==mem_volume0{n=orderi/10;countn+=1;sign=1;}ifsignsign=0;else {l++;ifmem_volume0==100{mem_volume0=orderi+1/10;n=orderi+1/10;countn+=1;}else{ min=1000;fornum=0;num<4;num++{k=mem_volumenum;comparenum=countk;ifcomparenum<min{min=comparenum;j=num;}}mem_volumej=orderi+1/10;}}i++;}value=l/100;add=add+l;sum=sum+value;}printf" LFU页面置换算法 \n";printf" 最后一次指令序列 ";fori=0;i<320;i++{ifi%10==0printf"\n";printf"%5d",orderi;}printf"\n";printf"\n";printf"\t%d次的平均缺页数为%d\n\t%d次的平均缺页率为%.3f%%",N,add/10,N,sum/10;printf"\n";}五、实验数据及处理结果FIFO页面置换算法运行结果：LRU页面置换算法运行结果：LFU页面置换算法运行结果：。

实验5页⾯置换算法实验5 页⾯置换算法⼀、实验题⽬：页⾯置换算法（请求分页）⼆、实验⽬的：进⼀步理解⽗⼦进程之间的关系。

1）理解内存页⾯调度的机理。

2）掌握页⾯置换算法的实现⽅法。

3）通过实验⽐较不同调度算法的优劣。

4）培养综合运⽤所学知识的能⼒。

页⾯置换算法是虚拟存储管理实现的关键，通过本次试验理解内存页⾯调度的机制，在模拟实现FIFO、LRU等经典页⾯置换算法的基础上，⽐较各种置换算法的效率及优缺点，从⽽了解虚拟存储实现的过程。

将不同的置换算法放在不同的⼦进程中加以模拟，培养综合运⽤所学知识的能⼒。

三、实验内容及要求这是⼀个综合型实验，要求在掌握⽗⼦进程并发执⾏机制和内存页⾯置换算法的基础上，能综合运⽤这两⽅⾯的知识，⾃⾏编制程序。

程序涉及⼀个⽗进程和两个⼦进程。

⽗进程使⽤rand()函数随机产⽣若⼲随机数，经过处理后，存于⼀数组Acess_Series[]中，作为内存页⾯访问的序列。

两个⼦进程根据这个访问序列，分别采⽤FIFO和LRU两种不同的页⾯置换算法对内存页⾯进⾏调度。

要求：1）每个⼦进程应能反映出页⾯置换的过程，并统计页⾯置换算法的命中或缺页情况。

设缺页的次数为diseffect。

总的页⾯访问次数为total_instruction。

缺页率= disaffect/total_instruction命中率= 1- disaffect/total_instruction2）将为进程分配的内存页⾯数mframe 作为程序的参数，通过多次运⾏程序，说明FIFO算法存在的Belady现象。

四、程序流程图开始创建⼦进程1创建⼦进程2结束⼦进程1命中？N内存页⾯满？Y 最先进⼊的进程退出内存页⾯N当前调⼊页⾯进⼊内存页⾯Y 命中次数+1N完？退出Y⼦进程2命中？N内存页⾯满？Y 被访问次数最少的进程退出内存页⾯N当前调⼊页⾯进⼊内存页⾯Y 命中次数+1，命中页⾯访问数+1N逻辑页⾯读完？退出Y五、运⾏结果及其说明FIFO:LRU:：六、回答以下问题：①⽗进程、⼦进程之间的并发执⾏的过程⽗进程与⼦进程之间的并发执⾏宏观并⾏，微观串⾏。

实验五虚拟内存页⾯置换算法实验五虚拟内存页⾯置换算法⼀：实验⽬的通过这次实验，加深对虚拟内存页⾯置换概念的理解，进⼀步掌握先进先出FIFO、最佳置换OPI和最近最久未使⽤LRU页⾯置换算法的实现⽅法。

⼆：实验内容问题描述：设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使⽤LRU页⾯置换算法的⼯作过程。

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

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

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

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

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

实现提⽰：⽤C++语⾔实现提⽰：1）程序中变量定义参考如下：int PageOrder[MaxNumber];int Time[MaxNumber];int Simulate[MaxNumber][MaxNumber];int PageCount[MaxNumber];int PageNum,LackNum,PageMin;double LackPageRate;bool found;2）页⾯置换的实现过程如下：变量初始化；接收⽤户输⼊最⼩物理块数m，页⾯个数n，页⾯序列P1, … ,P n，选择算法1-FIFO，2-OPI，3-LRU；根据⽤户选择的算法进⾏页⾯的分配和置换，输出页⾯置换算法的模拟过程；计算选择算法的缺页次数和缺页率；输出选择算法的缺页次数和缺页率。

三：概要设计输⼊函数void input()初始化函数void Initial()最佳置换算法的函数void OPI()最近最久未使⽤置换算法void LRU()主函数void main(){input();int s=0;while(s!=4){cout<<"请选择算法："<cout<<"1：先进先出；2：最佳值换算法；3：最近最久未使⽤置换算法；4：退出"< cin>>s;switch(s){case 1:FIFO();show();break;case 2:OPI();show();break;case 3:LRU();show();break;case 4:return;default:cout<<"输⼊数字不对，请重新输⼊：";break;}}}页⾯数列7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1系统为进程分配的物理块：3输出结果如截图所⽰：先进先出算法：2.最佳置换算法3.LRU算法说明：—1表⽰的是物理块中没有页⾯。

计算机科学系实验报告书课程名：《操作系统》题目：虚拟存储器管理页面置换算法模拟实验班级：学号：姓名：一、实验目的与要求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值，表示该虚页的最后一次被访问时间。