存储管理

-1-昆明理工大学信息工程与自动化学院学生实验报告（201—201学年第二学期）课程名称：操作系统开课实验室：年月日年级、专业、班学号姓名成绩实验项目名称存储管理指导教师教师评语教师签名：年月日一、实验目的存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。通过本次实验，要求学生通过编写和调试地址转换过程的模拟程序以加强对地址转换过程的了解，通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式存储管理的页面置换算法。二、实验原理及基本技术路线图（方框原理图）用C或C++语言模拟实现请求式分页管理。要求实现：页表的数据结构、分页式内存空间的分配及回收（建议采用位图法）、地址重定位、页面置换算法（从FIFO,LRU,NRU中任选一种）。提示：可先用动态申请的方式申请一大块空间，然后假设该空间为内存区域，对该空间进行页框的划分、分配等。FIFO页面置换算法:-2-开始内存数据初始化，物理块0mi中页面停留时间time[m]=m+1n=0用户内存中是否已存在要调用的页面用户内存中是否存在空物理块N将页面调入空物理块中，该物理块time[m]=0比较所有物理块的time[m]，找到最大值，将页面调入最大值所在物理块，该物理块time[m]=0所有已经存入页面的内存time[m]++，n++NYYn320?结束将页面p[n]调入内存YNLRU页面置换算法:-3-开始内存数据初始化，物理块0mi中页面停留时间time[m]=m+1n=0用户内存中是否已存在要调用的页面用户内存中是否存在空物理块N将页面调入空物理块中，该物理块time[m]=0比较所有物理块的time[m]，找到最大值，将页面调入最大值所在物理块，该物理块time[m]=0所有已经存入页面的内存time[m]++，n++NYYn320?结束将页面p[n]调入内存YN存在该页面的物理块timg[m]=0全局变量：-4-constintmaxn=320;//序列个数constintmax=maxn+20;//数组大小constintmaxp=max/10;//最大页数intinst[max];//指令序列intpage[max];//页地址流intsize;//内存能容纳的页数boolin[maxp];//该页是否在内存里，提高效率intpin[maxp];//现在在内存里的页其中in[]数组是为了方便直接判断该页是否在内存里，而不用遍历内存里所有页来判断。fault_n用来记录缺页次数。随机指令序列的产生：voidproduce_inst(){intm,n;intnum=0;while(nummaxn){m=rand()%maxn;inst[num++]=(m+1)%maxn;if(num==maxn)break;m=(m+2)%maxn;if(m==0)m=160;n=rand()%m;inst[num++]=(n+1)%maxn;if(num==maxn)break;-5-n=(n+2)%maxn;m=maxn-n;if(m==0)m=160;m=rand()%m+n;inst[num++]=m;}}FIFO算法：定义变量ptr。一开始先预调页填满内存。在这一部分，ptr指向下一个要存放的位置。之后继续执行剩下的指令。此时，ptr表示队列最前面的位置，即最先进来的位置，也就是下一个要被替换的位置。Ptr用循环加，即模拟循环队列。LRU算法：定义数组ltu[],即last_time_use来记录该页最近被使用的时间。定义变量ti模拟时间的变化，每执行一次加一。若当前需要的页没在内存里，就寻找最近最少使用的页，也就是ltu[]最小的页，即最近一次使用时间离现在最久的页，然后替换掉它。或者在内存还未满时，直接写入，这个我以初始化内存里所有页为-1来实现。若已经在内存里了，则只遍历内存内的页，把当前页的最近使用时间改一下即可。OPT算法：定义数组ntu[],即next_time_use来记录下一次被使用的时间，即将来最快使用时间。-6-初始化为-1.开始时预调页填满内存里的页。同样利用变量ptr来表示下一个要存放的位置从而控制预调页的过程。接着初始化ntu数组为-1。然后求出每一页下一次被使用的指令号，以此代替使用时间。如果所有剩下的序列都没有用该页时，则还是-1.这种值为-1的页显然是最佳替换对象。然后执行所有剩下的指令。当该页不在内存里时，遍历ntu数组，遇到-1的直接使用该页，没有则用ntu[]值最大的，也就是最晚使用的。无论该页在不在内存里，因为这一次已经被使用了，所以都应该更新这个页的ntu[]，只需往前看要执行的页流，记录下第一个遇到的该页即可。如果没有找到同样添-1即可。三、所用仪器、材料（设备名称、型号、规格等）。计算机一台四、实验方法、步骤#includestdio.h#includestdlib.h#includetime.h#includestring.hconstintmaxn=320;//序列个数constintmax=maxn+20;//数组大小constintmaxp=max/10;//最大页数intinst[max];//指令序列intpage[max];//页地址流intsize;//内存能容纳的页数boolin[maxp];//该页是否在内存里，提高效率-7-intpin[maxp];//现在在内存里的页voidinput_hint(){printf(1--createnewinstructionsequence2--setmemorypagenumber(4to32)\n);printf(3--solvebyFIFOalgorithm4--solvebyLRUalgorithm\n);printf(5--solvebyOPTalgorithm0--exit\n);printf(PleaseinputYourchoice:);}/*通过随机数产生一个指令序列，共320条指令*/voidproduce_inst(){intm,n;intnum=0;while(nummaxn){m=rand()%maxn;inst[num++]=(m+1)%maxn;if(num==maxn)break;m=(m+2)%maxn;if(m==0)m=160;n=rand()%m;inst[num++]=(n+1)%maxn;if(num==maxn)break;-8-n=(n+2)%maxn;m=maxn-n;if(m==0)m=160;m=rand()%m+n;inst[num++]=m;}}/*将指令序列变换成为页地址流*/voidturn_page_address(){for(inti=0;imaxn;i++)page[i]=inst[i]/10;}voidFIFO_solve(){memset(in,false,sizeof(in));intfault_n=0;//缺页率intptr,i;//预调页填满空间ptr=0;//下一个要放的位置for(i=0;imaxn&&ptrsize;i++)if(!in[page[i]]){pin[ptr++]=page[i];in[page[i]]=true;fault_n++;}-9-//继续执行剩下的指令ptr=0;//队列里最先进来的位置，即下一个要被替换的位置for(;imaxn;i++)if(!in[page[i]]){in[pin[ptr]]=false;in[page[i]]=true;pin[ptr]=page[i];fault_n++;ptr=(ptr+1)%size;}printf(\nByFIFOalgorithm,thefault-pagenumberis:%d\n,fault_n);printf(thehitratiois:%.2lf\n,(1-(fault_n+0.0)/320.0));}voidLRU_solve(){intltu[maxp];//last_time_useintti=1;//模拟时间intfault_n=0;memset(ltu,0,sizeof(ltu));memset(in,false,sizeof(in));memset(pin,-1,sizeof(pin));intmin,ptr,i,j;for(i=0;imaxn;i++){-10-if(!in[page[i]]){//寻找lrumin=1000000;ptr=0;for(j=0;jsize;j++){if(ltu[j]min){min=ltu[j];ptr=j;}}//替换或写入if(pin[ptr]!=-1)in[pin[ptr]]=false;in[page[i]]=true;pin[ptr]=page[i];fault_n++;ltu[ptr]=ti++;}else//已经在内存里则只需更改最近使用时间{for(j=0;jsize;j++)if(pin[j]==page[i]){ltu[j]=ti++;break;}}-11-}printf(\nByLRUalgorithm,thefault-pagenumberis:%d\n,fault_n);printf(thehitratiois:%.2lf\n,(1-(fault_n+0.0)/320.0));}voidOPT_solve(){intntu[maxp];//next_time_useintfault_n=0;inti,j;memset(in,false,sizeof(in));memset(ntu,-1,sizeof(ntu));//预调页填满intptr=0;for(i=0;imaxn&&fault_nsize;i++){if(!in[page[i]]){in[page[i]]=true;pin[ptr]=page[i];fault_n++;ptr++;}}//初始化ntu数组ptr=0;-12-for(j=i;jmaxn&&ptr32;j++){if(ntu[page[j]]==-1){ntu[page[j]]=j;ptr++;}}intmax;for(;imaxn;i++){if(!in[page[i]]){max=0;ptr=0;for(j=0;jsize;j++){if(ntu[pin[j]]==-1){ptr=j;break;}if(ntu[pin[j]]max){max=ntu[pin[j]];ptr=j;}}in[pin[ptr]]=false;in[page[i]]=true;-13-pin[ptr]=page[i];fault_n++;}ntu[page[i]]=-1;for(j=i+1;jmaxn;j++)if(page[j]==page[i]){ntu[page[i]]=j;break;}}printf(\nByOPTalgorithm,thefault-pagenumberis:%d\n,fault_n);printf(thehitratiois:%.2lf\n,(1-(fault_n+0.0)/320.0));}intmain(){printf(\t\t\t\t**********\n);printf(\t\t\t\t*存储管理*\n);printf(\t\t\t\t**********\n);srand(time(NULL));intchoice;while(1){input_hint();scanf(%d,&choice);printf(\n);-14-if(choice==0){printf(BYE-BYE!!!\n);break;}if(choice==1){produce_inst();turn_page_address();printf(Newpageaddresssequenceisset!\n);}elseif(choice==2){printf(Pleaseinputt