实验4内存管理.docx

1、实验4内存管理实验4 存管理学校：FJUT 学号：3131903229 班级：计算机1302 ：峰注：其中LFU和NRU算法运行结果可能与其他人不同，只是实现方式不同，基本思路符合就可以。一. 实验学时与类型学时：2，课外学时：自定实验类型：设计性实验二. 实验目的模拟实现请求页式存储管理中常用页面置换算法，理会操作系统对存的调度管理。三. 实验容要求：各算法要给出详细流程图以及执行结果截图。假设有一程序某次运行访问的页面依次是：0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6，请给出采用下列各页面置换算法时页面的换进换出情况，并计算各调度算法的命中率（命中率=非缺页次数/总访问

2、次数），初始物理存为空，物理存可在420页中选择。(1) FIFO：最先进入的页被淘汰；(2) LRU：最近最少使用的页被淘汰；(3) OPT：最不常用的页被淘汰；(选做)(4) LFU：访问次数最少的页被淘汰(LFU)。(选做) 源代码：#include #include #include #include #define MAXNUM 100struct Phy_Memory /定义一个物理存结构体 char Page; int time;char *OutPut;struct Phy_Memory *Phy_Page;void Print(char *PageStr,int Phy_Pa

3、geNum,int absence) /打印图解函数 int i,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(缺页数为:%dn,absence); printf(总访问次数为:%dn,s

4、trlen(PageStr); printf(缺页率为%.2fn,(double)absence/strlen(PageStr);int IsExist(char *Temp,int Phy_PageNum) /判断某页面是否存在于物理存中 int i; for(i=0;iPage!=*Temp;i+); if(iPhy_PageNum) return i+1; /找到返回此页面位置加1 return 0;void FIFO(char *PageStr,int Phy_PageNum) /利用时间计数器方式，还可以用栈来实现 char *Temp=PageStr; /定义Temp指针指向Pag

5、eStr首地址 int i,num,location,absence=0; int Flag=0; /定义一个标记变量，标记插入位置 while(*Temp!=0) /页面未访问完 num=0; if(FlagPage=*Temp; Flag+;absence+; else /若物理存已满 if(!IsExist(Temp,Phy_PageNum) /若此页面未被访问 for(i=0;iFlag;i+) /找到驻留时间最长的页 if(numtime) location=i;num=(Phy_Page+i)-time; (Phy_Page+location)-Page=*Temp; (Phy_P

6、age+location)-time=0; absence+; for(i=0;itime+; *(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; /定义一个标

7、记变量，标记插入位置 while(*Temp!=0) /页面未访问完 num=0; if(Flagtime=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(numtime) location=i;num=(Phy_Page+i)-time; (

8、Phy_Page+location)-Page=*Temp; (Phy_Page+location)-time=0; absence+; for(i=0;itime+; *(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+

9、); 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(FlagPage=*Temp; Flag+;absence+; else /若物理存已满 if(!IsExist

10、(Temp,Phy_PageNum) /若此页面未被访问 for(i=0;iPage); /调用distance函数返回值为与当前位置物理页面相同页号的距离 if(numPage=*Temp;absence+; for(i=0;iPage; 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=(ch

11、ar *)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*

12、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; 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,cha

13、r 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;i2*Size;i+) *(Ptr+i)=0;void LFU(char *PageStr,int Phy_PageNum) /对每一页面设置一个计数器，每次选出最小的淘汰 char *Temp=PageStr; /定义Temp指针指向PageStr首

14、地址 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(FlagPage,Size); else /若此页面未被访问 (Phy_Page+Flag)-Page=*Temp; Flag+;absence+; else /若物理存已满 if(location=IsExist(Temp,Phy_PageNum) /若此页面已被访问 A

15、dd(Count,(Phy_Page+location-1)-Page,Size); else /若此页面未被访问 for(i=0;iPage,Size); if(numtime) location=i;num=time; (Phy_Page+location)-Page=*Temp; Zero(Count,Size); absence+; for(i=0;iPage; Temp+; int j; /打印每次访问后的计数器值 for(i=0;i2;i+) for(j=0;jSize;j+) printf(%c ,*(Count+i*Size+j); printf(n); printf(n);

16、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(Flagtime=

17、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_P

18、age)=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;iPage; Temp+; Print(PageStr,Phy_PageNum,absence );int main() char *Str;int i,n,Num; Str=(char*)malloc(MAXNUM); printf(输入程序运行时访问的页面次序以及物理存的分页数:n); scanf(%s%d,Str,

19、&Num); Phy_Page=(struct Phy_Memory*)malloc(Num*sizeof(struct Phy_Memory); /初始化物理存结构体 OutPut=(char*)malloc(Num*strlen(Str); for(i=0;itime=0; printf(选择置换算法:n1.FIFO 2.LRU 3.OPT 4.LFU 5.NRUn); scanf(%d,&n); switch (n) case 1:printf(n以下为FIFO算法图解:n);FIFO(Str,Num);break; case 2:printf(n以下为LRU算法图解:n);LRU(St

20、r,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) 针对上述页面访问顺序，

21、请比较上述各页面置换算法的性能。对于访问顺序0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6当分页数为4时：随着分页数增加它们的缺页数均降低。FIFO算法对此访问串无Belady现象。OPT算法表现最好，实际上我们将OPT算法当做最优的评判标准。LRU算法理论上是优于FIFO算法的，但此时缺页率却高于FIFO算法，主要是受访问串以及分页数的影响。只能说此访问串更适合FIFO算法。所以在实际中，我们要选择最适合的算法考虑。当分页数为5时，各算法情况：我们可以看到当分页数为5时，各算法缺页数均与OPT算法一致。结论：对于这些算法，我们不能说谁是最优的，具体我们还是要看实际访问串以及分

22、页数情况。不过在实际系统中我们还应该考虑到哪一种算法更容易实现，将系统开销尽可能的降低。(2) 对于LRU，程序中采用什么方法来体现“最近”这一时间要素？我将物理存的每一页都用time来计数，当访问过这一页时，将time置为0。存中没有这一页时选择计数最少的淘汰即可。并且每访问一页后，所有物理存页面的计数器都加一。(3) LRU和LFU有什么异同？LRU/LFU可以称为近似OPT算法吗？LRU算法是总是选择最近一段时间最长时间没有被访问过的页面调出，而LFU算法是考虑到每个页面的访问次数，二者在本质上个人认为还是不同的，不能说近似FIFO。在实际系统中实现起来均比较困难。它们都要用到计数器，大大降低系统开销，所以实际系统中还是使用LRU的近似算法，即CLOCK(NRU)算法.