实验4-内存管理

实验4内存管理学校：FJUT学号：3131903229班级：计算机1302姓名：姜峰注：其中LFU和NRU算法运行结果可能与其他人不同，只是实现方式不同，基本思路符合就可以。一.实验学时与类型学时：2，课外学时：自定实验类型：设计性实验二.实验目的模拟实现请求页式存储管理中常用页面置换算法，理会操作系统对内存的调度管理。三.实验内容要求：各算法要给出详细流程图以及执行结果截图。假设有一程序某次运行访问的页面依次是：0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6，请给出采用下列各页面置换算法时页面的换进换出情况，并计算各调度算法的命中率（命中率=非缺页次数/总访问次数），初始物理内存为空，物理内存可在4～20页中选择。(1)FIFO：最先进入的页被淘汰；(2)LRU：最近最少使用的页被淘汰；(3)OPT：最不常用的页被淘汰；(选做)(4)LFU：访问次数最少的页被淘汰(LFU)。(选做)源代码：#includestdio.h#includestring.h#includelimits.h#includemalloc.h#defineMAXNUM100structPhy_Memory{//定义一个物理内存结构体charPage;inttime;};char*OutPut;structPhy_Memory*Phy_Page;voidPrint(char*PageStr,intPhy_PageNum,intabsence){//打印图解函数inti,j;for(i=0;istrlen(PageStr);i++)printf(%c,*(PageStr+i));printf(\n);for(i=0;istrlen(PageStr);i++)printf(--);printf(\n);for(i=0;iPhy_PageNum;i++){for(j=0;jstrlen(PageStr);j++){printf(%c,*(OutPut+i*strlen(PageStr)+j));}printf(\n);}printf(缺页数为:%d\n,absence);printf(总访问次数为:%d\n,strlen(PageStr));printf(缺页率为%.2f\n,(double)absence/strlen(PageStr));}intIsExist(char*Temp,intPhy_PageNum){//判断某页面是否存在于物理内存中inti;for(i=0;iPhy_PageNum&&(Phy_Page+i)-Page!=*Temp;i++);if(iPhy_PageNum)returni+1;//找到返回此页面位置加1return0;}voidFIFO(char*PageStr,intPhy_PageNum){//利用时间计数器方式，还可以用栈来实现char*Temp=PageStr;//定义Temp指针指向PageStr首地址inti,num,location,absence=0;intFlag=0;//定义一个标记变量，标记插入位置while(*Temp!='\0'){//页面未访问完num=0;if(FlagPhy_PageNum){//若物理内存未满if(!IsExist(Temp,Flag)){//若此页面未被访问(Phy_Page+Flag)-Page=*Temp;Flag++;absence++;}}else{//若物理内存已满if(!IsExist(Temp,Phy_PageNum)){//若此页面未被访问for(i=0;iFlag;i++){//找到驻留时间最长的页if(num(Phy_Page+i)-time){location=i;num=(Phy_Page+i)-time;}}(Phy_Page+location)-Page=*Temp;(Phy_Page+location)-time=0;absence++;}}for(i=0;iFlag;i++){//将当前物理内存数组列放入二维数组中(Phy_Page+i)-time++;*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)-Page;}Temp++;}Print(PageStr,Phy_PageNum,absence);}voidLRU(char*PageStr,intPhy_PageNum){//依旧利用计数器方式，也可用栈来实现char*Temp=PageStr;//定义Temp指针指向PageStr首地址inti,num,location,absence=0;intFlag=0;//定义一个标记变量，标记插入位置while(*Temp!='\0'){//页面未访问完num=0;if(FlagPhy_PageNum){//若物理内存未满if(location=IsExist(Temp,Phy_PageNum)){//若此页面已被访问(Phy_Page+location-1)-time=0;}else{//若此页面未被访问(Phy_Page+Flag)-Page=*Temp;Flag++;absence++;}}else{//若物理内存已满if(location=IsExist(Temp,Phy_PageNum)){//若此页面已被访问(Phy_Page+location-1)-time=0;}else{//若此页面未被访问for(i=0;iFlag;i++){//找到最近最久未使用的页if(num(Phy_Page+i)-time){location=i;num=(Phy_Page+i)-time;}}(Phy_Page+location)-Page=*Temp;(Phy_Page+location)-time=0;absence++;}}for(i=0;iFlag;i++){//将当前物理内存数组列放入二维数组中(Phy_Page+i)-time++;*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)-Page;}Temp++;}Print(PageStr,Phy_PageNum,absence);}intDistance(char*PageStr,char*Temp,charNow){//计算距离函数（OPT算法中使用）inti;for(i=1;*(Temp+i)!='\0'&&*(Temp+i)!=Now;i++);if(*(Temp+i)!='\0')returni;returnINT_MAX;}voidOPT(char*PageStr,intPhy_PageNum){//实际中无法实现，知道访问串后顺序遍历char*Temp=PageStr;//定义Temp指针指向PageStr首地址inti,num,Size,location,absence=0;intFlag=0;//定义一个标记变量，标记插入位置while(*Temp!='\0'){//页面未访问完num=0;if(FlagPhy_PageNum){//若物理内存未满if(!IsExist(Temp,Flag)){//若此页面未被访问(Phy_Page+Flag)-Page=*Temp;Flag++;absence++;}}else{//若物理内存已满if(!IsExist(Temp,Phy_PageNum)){//若此页面未被访问for(i=0;iFlag;i++){//淘汰在访问串中将来再也不会出现的或离当前最远的位置上出现的页Size=Distance(PageStr,Temp,(Phy_Page+i)-Page);//调用distance函数返回值为与当前位置物理页面相同页号的距离if(numSize){location=i;num=Size;}}(Phy_Page+location)-Page=*Temp;absence++;}}for(i=0;iFlag;i++)//将当前物理内存数组列放入二维数组中*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)-Page;Temp++;}Print(PageStr,Phy_PageNum,absence);}char*Create(char*PageStr){//根据访问串建立计数字符数组（LFU算法使用）inti,j,Size,Num=0;char*Temp1,*Temp2;intlength=strlen(PageStr);char*NowPage=(char*)malloc(length);for(i=0;ilength;i++)*(NowPage+i)=*(PageStr+i);Temp1=Temp2=NowPage;while((Temp1-NowPage)=length+1){//去除访问串中重复串if(*Temp1!='\0'){for(Temp2=Temp1+1;(Temp2-NowPage)=length+1;Temp2++){if(*Temp1==*Temp2){*Temp2='\0';Num++;}}}Temp1++;}Size=length-Num;char*Count=(char*)malloc(Size*2);for(i=0;ilength;i++){//将不重复的访问页置于计数器中if(*(NowPage+i)!='\0'){*(Count+Size-1)=*(NowPage+i);Size--;}}Size=length-Num;for(i=Size;i2*Size;i++){//计数位置零*(Count+i)='0';}returnCount;}voidAdd(char*Ptr,charStr,intSize){//相应计数器加一（LFU算法使用）inti;for(i=0;*(Ptr+i)!=Str;i++);*(Ptr+i+Size)+=1;}intFind(char*Ptr,charStr,intSize){//在计数器中找到相应页面并返回其计数值（LFU算法使用）inti;for(i=0;*(Ptr+i)!=Str;i++);return(*(Ptr+i+Size)-'0');}voidZero(char*Ptr,intSize){//将所有计数器清零（LFU算法使用）inti;for(i=Size;i2*Size;i++)*(Ptr+i)='0';}voidLFU(char*PageStr,intPhy_PageNum){//对每一页面设置一个计数器，每次选出最小的淘汰char*Temp=PageStr;//定义Temp指针指向PageStr首地址char*Count=Create(PageStr);inti,Size,time,num,location,absence=0;intFlag=0;//定义一个标记变量，标记插入位置Size=strlen(Count)/2;while(*Temp!='\0'){//页面未访问完num=INT_MAX;if(FlagPhy_PageNum){//若物理内存未满if(location=IsExist(Temp,Phy_PageNum)){//若此页面已被访问Add(Count,(Phy_Page+location-1)-Page,Size);}else{//若此页面未被访问(Phy_Page+Flag)-Page=*Temp;Flag++;absence++;}}else{//若物理内存已满if(location=IsExist(Temp,Phy_PageNum)){//若此页面已被访问Add(Count,(Phy_Page+location-1)-Page,Size);}else{//若此页面未被访问for(i=0;iFlag;i+