实验 4 内存管理实验4内存管理学校：FJUT 学号：3131903229 班级：计算机1302姓名：姜峰注：其中LFU和NRU算法运行结果可能与其他人不同，只是实现方式不同，基本思路符合就可以。

.实验学时与类型学时：2,课外学时：自定实验类型：设计性实验二.实验目的模拟实现请求页式存储管理中常用页面置换算法，理会操作系统对内存的调度管理。

三•实验内容要求：各算法要给出详细流程图以及执行结果截图。

假设有一程序某次运行访问的页面依次是：0,124,3,4,5,1,2,5,1,2,3,4,5,6 ，请给出采用下列各页面置换算法时页面的换进换出情况，并计算各调度算法的命中率（命中率二非缺页次数/总访问次数），初始物理内存为空，物理内存可在4〜20页中选择。

（1）FIFO :最先进入的页被淘汰；（2）LRU :最近最少使用的页被淘汰；（3）OPT :最不常用的页被淘汰；（选做）⑷LFU :访问次数最少的页被淘汰（LFU）。

（选做）源代码：#i nclude <stdio.h>#include <string.h>#in elude <limits.h>#i nclude <malloc.h>#defi ne 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<strle n( PageStr);i++)pri ntf("%c ",*(PageStr+i));pri ntf("\n");for(i=0;i<strle n( PageStr);i++)pri ntf("--");pri ntf("\n");for(i=0;i<Phy_PageNum;i++){for(j=0;j<strle n(PageStr);j++){prin tf("%c ",*(OutPut+i*strle n(PageStr)+j));}prin tf("\n");}printf("缺页数为:%d\n",absenee);printf("总访问次数为:%d\n",strlen(PageStr));printf("缺页率为%.2f\n",(double)absence/strlen(PageStr));}int lsExist(char *Temp,i nt Phy_PageNum){ // 判断某页面是否存在于物理内存中int i;for(i=0;i<Phy_PageNu m&&(Phy_Page+i)->Page!=*Temp;i++);if(i<Phy_PageNum) return i+1; //找到返回此页面位置加1return 0;}void FIFO(char *PageStr,i nt Phy_PageNum){ // 利用时间计数器方式，还可以用栈来实现char *Temp=PageStr; // 定义Temp 指针指向PageStr 首地址int i,num ,locati on, abse nce=0;int Flag=0; //定义一个标记变量，标记插入位置while(*Temp!='\0'){ // 页面未访问完num=0;if(Flag<Phy_PageNum){ // 若物理内存未满if(!lsExist(Temp,Flag)){ // 若此页面未被访问(Phy_Page+Flag)->Page=*Temp;Flag++;abse nce++;}}else{ 若物理内存已满if(!lsExist(Temp,Phy_PageNum)){ // 若此页面未被访问for(i=0;i<Flag;i++){ //找到驻留时间最长的页if(num <(Phy_Page+i)->time){locati on=i; num=(Phy_Page+i)->time;} _}(Phy_Page+locati on)->Page=*Temp;(Phy_Page+locati on)->time=0;abse nce++;}}for(i=0;i<Flag;i++){ //将当前物理内存数组列放入二维数组中(Phy_Page+i)->time++;*(OutPut+i*strle n(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;} _Temp++;}Prin t(PageStr,Phy_PageNum,abse nee);} _void LRU(char *PageStr,int Phy_PageNum){ // 依旧利用计数器方式，也可用栈来实现char *Temp=PageStr; // 定义Temp 指针指向PageStr 首地址int i,num ,locatio n, abse nce=O;int Flag=O; //定义一个标记变量，标记插入位置while(*Temp!='\O'){ // 页面未访问完num=O;if(Flag<Phy_PageNum){ // 若物理内存未满if(location=lsExist(Temp,Phy_PageNum)){ // 若此页面已被访问(Phy_Page+locati on-1)->time=0;} _else{ 若此页面未被访问(Phy_Page+Flag)->Page=*Temp;Flag++;abse nce++;}}else{ 若物理内存已满if(location=lsExist(Temp,Phy_PageNum)){ // 若此页面已被访问(Phy_Page+locati on-1)->time=0;} _else{ 若此页面未被访问for(i=0;i<Flag;i++){ //找到最近最久未使用的页if(num <(Phy_Page+i)->time){locati on=i; num=(Phy_Page+i)->time;} _}(Phy_Page+locati on)->Page=*Temp;(Phy_Page+locati on)->time=0;abse nce++;}}for(i=0;i<Flag;i++){ //将当前物理内存数组列放入二维数组中(Phy_Page+i)->time++;*(OutPut+i*strle n(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;}Temp++;}Prin t(PageStr,Phy_PageNum,abse nee );} _int Distance(char *PageStr,ehar *Temp,ehar Now){ // 计算距离函数(OPT 算法中使用)int i;for(i=1;*(Temp+i)!='\0'&&*(Temp+i)!=Now;i++);if(*(Temp+i)!='\O')return i;return INT_MAX;} _void OPT(char *PageStr,int Phy_PageNum){ // 实际中无法实现，知道访问串后顺序遍历char *Temp=PageStr; // 定义Temp 指针指向PageStr 首地址int i,nu m,Size,locati on, abse nce=0;int Flag=0; //定义一个标记变量，标记插入位置while(*Temp!='\O'){ // 页面未访问完num=0;if(Flag<Phy_PageNum){ // 若物理内存未满if(!lsExist(Temp,Flag)){ // 若此页面未被访问(Phy_Page+Flag)->Page=*Temp;Flag++;abse nce++;}}else{ 若物理内存已满if(!lsExist(Temp,Phy_PageNum)){ // 若此页面未被访问for(i=0;i<Flag;i++){ //淘汰在访问串中将来再也不会出现的或离当前最远的位置上出现的页Size=Distance(PageStr,Temp,(Phy_Page+i)->Page); 〃调用distanee函数返回值为与当前位置物理页面相同页号的距离if(num <Size){locati on=i; num=Size;}} (Phy_Page+locati on)->Page=*Temp;abse nce++;} _}for(i=0;i<Flag;i++) //将当前物理内存数组列放入二维数组中*(OutPut+i*strle n(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;Temp++;}Prin t(PageStr,Phy_PageNum,abse nee);} _char *Create(char *PageStr){ //根据访问串建立计数字符数组(LFU算法使用)int i,j,Size,Num=0;char *Temp1,*Temp2;in t le ngth=strle n( PageStr);char *NowPage=(char *)malloc(le ngth);for(i=0;i<length;i++) *( NowPage + i ) = *( PageStr + i );Tempi = Temp2 = NowPage;while((Temp1-NowPage)v=length+1){ // 去除访问串中重复串if(*Temp1!='\0'){ for(Temp2=Temp1+1;(Temp2-NowPage)v=length+1;Temp2++){ if(*Temp1==*Temp2){*Temp2='\0';Num++;}}}Temp1++;}Size=le ngth-Num;char *Cou nt=(char *)malloc(Size*2);for(i=0;i<length;i++){ //将不重复的访问页置于计数器中if(*(NowPage+i)!='\0'){*(Cou nt+Size-1)=*(NowPage+i);Size--;}}Size=le ngth-Num;for(i=Size;i<2*Size;i++){ // 计数位置零*(Cou nt+i)='0';}return Count;}void Add(char *Ptr,char Str,int Size){ // 相应计数器加一(LFU 算法使用)int i;for(i=0;*(Pt r+i)!=Str;i++);*(Pt r+i+Size)+=1;}int Fi nd(char *Ptr,char Str,i nt Size){ // 在计数器中找到相应页面并返回其计数值(LFU算法使用)int i;for(i=0;*(Pt r+i)!=Str;i++);return (*(Pt 叶i+Size)-'O');}void Zero( char *Ptr, int Size ){ //将所有计数器清零(LFU算法使用)int i;for(i=Size;i<2*Size;i++) *(Pt r+i )='0';}void LFU(char *PageStr,int Phy_PageNum){ // 对每一页面设置一个计数器，每次选出最小的淘汰char *Temp=PageStr; // 定义Temp 指针指向PageStr 首地址char *Cou nt=Create(PageStr);int i,Size,time,num,location,absence=0;int Flag=0; //定义一个标记变量，标记插入位置Size=strle n(Cou nt)/2;while(*Temp!='\0'){ // 页面未访问完num=INT_MAX;if(Flag<Phy_PageNum){ // 若物理内存未满if(location=lsExist(Temp,Phy_PageNum)){ // 若此页面已被访问Add(Cou nt,(Phy_Page+locati on-1)->Page,Size);} _else{ 若此页面未被访问(Phy_Page+Flag)->Page=*Temp;Flag++;abse nce++;}}else{ 若物理内存已满if(location=lsExist(Temp,Phy_PageNum)){ // 若此页面已被访问Add(Cou nt,(Phy_Page+locati on-1)->Page,Size);} _else{ 若此页面未被访问for(i=0;i<Flag;i++){ //找到被访问次数最少的一页time=Fin d(Co un t,(Phy_Page+i)->Page,Size);if(num >time){locati on=i; num=time;}}(Phy_Page+locati on)->Page=*Temp;Zero(Co un t,Size);abse nce++;}}for(i=0;i<Flag;i++) //将当前物理内存数组列放入二维数组中*(OutPut+i*strle n(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;Temp++;int j; //打印每次访问后的计数器值for(i=0;i<2;i++){for(j=0;j<Size;j++)prin tf("%c ",*(Cou nt+i*Size+j));prin tf("\n");}prin tf("\n");}Prin t(PageStr,Phy_PageNum,abse nee);} _void NRU(char *PageStr,int Phy_PageNum){ // 对每个物理页设置一个标识(0/1),用指针循环访问淘汰标识为零的页面char *Temp=PageStr; // 定义Temp 指针指向PageStr 首地址int i,locati on, abse nce=0;int Flag=0; //定义一个标记变量，标记插入位置struct Phy_Memory *Clock = Phy_Page; //定义一个结构体指针指向物理内存首地址while(*Temp!='\O'){ // 页面未访问完if(Flag<Phy_PageNum){ // 若物理内存未满if(location=lsExist(Temp,Phy_PageNum)){ // 若此页面已被访问(Phy_Page+locati on-1)->time=1;} _else{ 若此页面未被访问(Phy_Page+Flag)->Page=*Temp;(Phy_Page+Flag)->time=1;Flag++;abse nce++;Clock++; if((Clock-Phy_Page)>=Phy_PageNum)Clock=Phy_Page;} ~ ~ 一}else{ 若物理内存已满if(location=lsExist(Temp,Phy_PageNum)){ // 若此页面已被访问(Phy_Page+locati on-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;abse nce++;}}for(i=0;i<Flag;i++){ //将当前物理内存数组列放入二维数组中*(OutPut+i*strle n(PageStr)+(Temp-PageStr))=(Phy_Page+i)->Page;}Temp++;}Prin t(PageStr,Phy_PageNum,abse nee );} _int mai n(){char *Str;i nt i,n,Num;Str=(char*)malloc(MAXNUM);printf("输入程序运行时访问的页面次序以及物理内存的分页数:\n");scan f("%s%d",Str,&Nu m);Phy_Page=(struct Phy_Memory*)malloc(Num*sizeof(struct Phy_Memory)); //初始化物理内存结构体OutPut=(char*)malloc(Num*strle n(Str));for(i=0;i<Num;i++)(Phy_Page+i )->time=0;printf("选择置换算法:\n1.FIFO 2.LRU 3.OPT 4丄FU 5.NRU\n");scan f("%d",&n);switch (n){case 1:pri ntf("\n以下为FIFO 算法图解:\n");FIFO(Str,Num);break;case 2:pri ntf("\n 以下为LRU 算法图解:\n");LRU(Str,Num);break;case 3:pri ntf("\n 以下为OPT 算法图解:\n");OPT(Str,Num);break;case 4:pri ntf("\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进行运行截图择置枠算法:头验截图:输入禮序运行时访间的页面次序以及報理内存的分页姝0124345125123456 4选择萱换算法：1.FIFO 2P LRU 3.OPT 4.LFU 5.NBU罠下対F 】FO 算法图解=012434E12&123456 3030333333333444111115555SSS55t22222111111111 4444422222222If 可迩数为祗献页率为日-阳Process returned 0 <0xB> execution tine : 17+786 s Press anjf key to continue^H12+345125123456 4选择置换算法： 1 -FIFO 2.LRIJ 3.OPT 4,LFII S.NRU以下为LRU 算法图解：»12434^12S12345&GQQ333322222211111555555542222211111114 4 6 1 4 二 4 2、/]75 4:1数0. 33 4 4 ^DCESS returned 0 <0x6) execLit ion rime*r-ess any hev to continue.以下冇OPTlp 去rotes% returned S <0x0> iuorest any key to continue5555545B 11111111 2222222Z "roc;css i^dbumad B <0x0> cxccut;loin itunc - 24.149* s *ress anu key to continue.邀缺总缺5 12 4 61 0 1 z咗为+认为FIFO算法流程图:次数最 否 断此页面是否被访 冋？ 淘汰被访冋 少的一页并缺页中 断，将当前页面入 内存，缺页数加 一，所有计数器清 零，相应页面计数 器加一四.思考与总结⑴针对上述页面访问顺序，请比较上述各页面置换算法的性能对于访问顺序0,124,3,4,5,1,2,5,1,2,3,4,5,6当分页数为4时：随着分页数增加它们的缺页数均降低FIFO算法对此访问串无Belady现象。