实验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)。

(选做)源代码：#include <stdio.h>#include <string.h>#include <limits.h>#include <malloc.h>#define MAXNUM 100struct Phy_Memory{ //定义一个物理内存结构体char Page;int time;};char *OutPut;struct Phy_Memory *Phy_Page;void Print(char *PageStr,int Phy_PageNum,int absence){ //打印图解函数int i,j;for(i=0;i<strlen(PageStr);i++)printf("%c ",*(PageStr+i));printf("\n");for(i=0;i<strlen(PageStr);i++)printf("--");printf("\n");for(i=0;i<Phy_PageNum;i++){for(j=0;j<strlen(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));}int IsExist(char *Temp,int Phy_PageNum){ //判断某页面是否存在于物理内存中int i;for(i=0;i<Phy_PageNum&&(Phy_Page+i)->Page!=*Temp;i++);if(i<Phy_PageNum) return i+1; //找到返回此页面位置加1 return 0;}void FIFO(char *PageStr,int Phy_PageNum){ //利用时间计数器方式，还可以用栈来实现char *Temp=PageStr; //定义Temp指针指向PageStr首地址int i,num,location,absence=0;int Flag=0; //定义一个标记变量，标记插入位置while(*Temp!='\0'){ //页面未访问完num=0;if(Flag<Phy_PageNum){ //若物理内存未满if(!IsExist(Temp,Flag)){ //若此页面未被访问(Phy_Page+Flag)->Page=*Temp;Flag++;absence++;}}else{ //若物理内存已满if(!IsExist(Temp,Phy_PageNum)){ //若此页面未被访问for(i=0;i<Flag;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;i<Flag;i++){ //将当前物理内存数组列放入二维数组中(Phy_Page+i)->time++;*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;}Temp++;}Print(PageStr,Phy_PageNum,absence);}void LRU(char *PageStr,int Phy_PageNum){ //依旧利用计数器方式，也可用栈来实现char *Temp=PageStr; //定义Temp指针指向PageStr首地址int i,num,location,absence=0;int Flag=0; //定义一个标记变量，标记插入位置while(*Temp!='\0'){ //页面未访问完num=0;if(Flag<Phy_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;i<Flag;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;i<Flag;i++){ //将当前物理内存数组列放入二维数组中(Phy_Page+i)->time++;*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;}Temp++;}Print(PageStr,Phy_PageNum,absence );}int Distance(char *PageStr,char *Temp,char Now){ //计算距离函数（OPT算法中使用）int i;for(i=1;*(Temp+i)!='\0'&&*(Temp+i)!=Now;i++);if(*(Temp+i)!='\0')return i;return INT_MAX;}void OPT(char *PageStr,int Phy_PageNum){ //实际中无法实现，知道访问串后顺序遍历char *Temp=PageStr; //定义Temp指针指向PageStr首地址int i,num,Size,location,absence=0;int Flag=0; //定义一个标记变量，标记插入位置while(*Temp!='\0'){ //页面未访问完num=0;if(Flag<Phy_PageNum){ //若物理内存未满if(!IsExist(Temp,Flag)){ //若此页面未被访问(Phy_Page+Flag)->Page=*Temp;Flag++;absence++;}}else{ //若物理内存已满if(!IsExist(Temp,Phy_PageNum)){ //若此页面未被访问for(i=0;i<Flag;i++){ //淘汰在访问串中将来再也不会出现的或离当前最远的位置上出现的页Size=Distance(PageStr,Temp,(Phy_Page+i)->Page); //调用distance 函数返回值为与当前位置物理页面相同页号的距离if(num<Size){location=i;num=Size;}}(Phy_Page+location)->Page=*Temp;absence++;}}for(i=0;i<Flag;i++) //将当前物理内存数组列放入二维数组中*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;Temp++;}Print(PageStr,Phy_PageNum,absence);}char *Create(char *PageStr){ //根据访问串建立计数字符数组（LFU算法使用）int i,j,Size,Num=0;char *Temp1,*Temp2;int length=strlen(PageStr);char *NowPage=(char *)malloc(length);for(i=0;i<length;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;i<length;i++){ //将不重复的访问页置于计数器中if(*(NowPage+i)!='\0'){*(Count+Size-1)=*(NowPage+i);Size--;}}Size=length-Num;for(i=Size;i<2*Size;i++){ //计数位置零*(Count+i)='0';}return Count;}void Add(char *Ptr,char Str,int Size){ //相应计数器加一（LFU算法使用）int i;for(i=0;*(Ptr+i)!=Str;i++);*(Ptr+i+Size)+=1;}int Find(char *Ptr,char Str,int Size){ //在计数器中找到相应页面并返回其计数值（LFU算法使用）int i;for(i=0;*(Ptr+i)!=Str;i++);return (*(Ptr+i+Size)-'0');}void Zero( char *Ptr, int Size ){ //将所有计数器清零（LFU算法使用）int i;for(i=Size;i<2*Size;i++) *(Ptr+i)='0';}void LFU(char *PageStr,int Phy_PageNum){ //对每一页面设置一个计数器，每次选出最小的淘汰char *Temp=PageStr; //定义Temp指针指向PageStr首地址char *Count=Create(PageStr);int i,Size,time,num,location,absence=0;int Flag=0; //定义一个标记变量，标记插入位置Size=strlen(Count)/2;while(*Temp!='\0'){ //页面未访问完num=INT_MAX;if(Flag<Phy_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;i<Flag;i++){ //找到被访问次数最少的一页time=Find(Count,(Phy_Page+i)->Page,Size);if(num>time){location=i;num=time;}}(Phy_Page+location)->Page=*Temp;Zero(Count,Size);absence++;}}for(i=0;i<Flag;i++) //将当前物理内存数组列放入二维数组中*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;Temp++;int j; //打印每次访问后的计数器值for(i=0;i<2;i++){for(j=0;j<Size;j++)printf("%c ",*(Count+i*Size+j));printf("\n");}printf("\n");}Print(PageStr,Phy_PageNum,absence);}void NRU(char *PageStr,int Phy_PageNum){ //对每个物理页设置一个标识（0/1），用指针循环访问淘汰标识为零的页面char *Temp=PageStr; //定义Temp指针指向PageStr首地址int i,location,absence=0;int Flag=0; //定义一个标记变量，标记插入位置struct Phy_Memory *Clock = Phy_Page; //定义一个结构体指针指向物理内存首地址while(*Temp!='\0'){ //页面未访问完if(Flag<Phy_PageNum){ //若物理内存未满if(location=IsExist(Temp,Phy_PageNum)){ //若此页面已被访问(Phy_Page+location-1)->time=1;}else{ //若此页面未被访问(Phy_Page+Flag)->Page=*Temp;(Phy_Page+Flag)->time=1;Flag++;absence++;Clock++;if((Clock-Phy_Page)>=Phy_PageNum) Clock=Phy_Page;}}else{ //若物理内存已满if(location=IsExist(Temp,Phy_PageNum)){ //若此页面已被访问(Phy_Page+location-1)->time=1;}else{ //若此页面未被访问while(Clock->time){Clock->time=0;Clock++;if((Clock-Phy_Page)>=Phy_PageNum) Clock=Phy_Page;}Clock->Page=*Temp;Clock->time=1;Clock++;if((Clock-Phy_Page)>=Phy_PageNum) Clock=Phy_Page;absence++;}}for(i=0;i<Flag;i++){ //将当前物理内存数组列放入二维数组中*(OutPut+i*strlen(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;}Temp++;}Print(PageStr,Phy_PageNum,absence );}int main(){char *Str;int i,n,Num;Str=(char*)malloc(MAXNUM);printf("输入程序运行时访问的页面次序以及物理内存的分页数:\n");scanf("%s%d",Str,&Num);Phy_Page=(struct Phy_Memory*)malloc(Num*sizeof(struct Phy_Memory)); //初始化物理内存结构体OutPut=(char*)malloc(Num*strlen(Str));for(i=0;i<Num;i++)(Phy_Page+i )->time=0;printf("选择置换算法:\n1.FIFO 2.LRU 3.OPT 4.LFU 5.NRU\n");scanf("%d",&n);switch (n){case 1:printf("\n以下为FIFO算法图解:\n");FIFO(Str,Num);break;case 2:printf("\n以下为LRU算法图解:\n");LRU(Str,Num);break;case 3:printf("\n以下为OPT算法图解:\n");OPT(Str,Num);break;case 4:printf("\n以下为LFU算法图解:\n各时期计数器如下:\n");LFU(Str,Num);break;case 5:printf("\n以下为NRU算法图解:\n");NRU(Str,Num);break;}free(Phy_Page);free(OutPut);return 0;}注：这里只对分页数为4进行运行截图实验截图：FIFO算法流程图：LRU算法流程图：OPT算法流程图：LFU算法流程图：NRU算法流程图：四. 思考与总结(1)针对上述页面访问顺序，请比较上述各页面置换算法的性能。