实验4内存管理

1、实验 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 P

3、rint(char *PageStr,int Phy_PageNum,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,abse

4、nce);printf( 总访问次数为 :%dn,strlen(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;/ 找到返回此页面位置加 1return 0;void FIFO(char *PageStr,int Phy_PageNum) / 利用时间计数器方式，还可以用栈来实现 char *Tem

5、p=PageStr;/定义 Temp 指针指向 PageStr 首地址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)

6、-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);void LRU(char *PageStr,int Phy_PageNum)/ 依旧利用计数器方式，也可用栈来实现char *Temp=PageStr;/定义 Temp 指针指向 PageStr 首地址int i,num,location,absence=0;int F

7、lag=0;/定义一个标记变量，标记插入位置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;(Phy

8、_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+);if(*(T

9、emp+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+;/若物理内存已满/若此页面未被访问/淘汰在访问串中将来再也不会出现的或e

10、lseif(!IsExist(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=(char *

11、)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=

12、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)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+);r

13、eturn (*(Ptr+i+Size)-0);void Zero( char *Ptr, int Size )int i; for(i=Size;i2*Size;i+) *(Ptr+i)=0;void LFU(char *PageStr,int Phy_PageNum) 器，每次选出最小的淘汰char *Temp=PageStr;char *Count=Create(PageStr);/将不重复的访问页置于计数器中/计数位置零/ 相应计数器加一（ LFU 算法使用）/在计数器中找到相应页面并返回其计数值/ 将所有计数器清零（ LFU 算法使用）/对每一页面设置一个计数/定义 Temp 指针指

14、向 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)/若此页面已被访问Add(Count,(Phy_Page+location-1)

15、-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);Print(PageStr,Phy_PageNum,absence);void NRU(ch

16、ar *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=1; else/若此页面未被访问(Phy_Page+Flag)-Page=*Temp;(Phy_P

17、age+Flag)-time=1;Flag+;absence+;Clock+;if(Clock-Phy_Page)=Phy_PageNum) Clock=Phy_Page;elseif(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=

18、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,&Num);/初Phy_Page=(struct Phy_Memory*)malloc(Num*sizeof(struct Phy_M

19、emory); 始化物理内存结构体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(Str,Num);break;case 3:printf(n 以下为 OPT 算法图解:n);OPT(Str,Num);brea

20、k;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进行运行截图实验截图：输入程序运行时访间的页面次序以及做理内存的分页蛛312434512512345 4选择置换算法：l.FIFO 2.LRU 3-OPT 4,LFU 5川刑罠下为F】FO算法图解；01243451251234S6 00303333333334441111

21、15555SSS556 22222111111111 4444422222222獻页率为日-殆Process returned S execution tine : l?+706 s Press anu key to continue输人程序运行时访间的页面次序以及物理内存的分页数,M12434512S123456 4选择置换算送：1.FIFO 2.LHU 3,OPT 4-LFU 5,NRU2以下为LRU算法图解；B 1243451251234564衣为 数问率 K谊贞612 加75:1数乩2忘142 2 2 25 E S G11114 4 4 32 2 64 4 415 53 3 3*irp

22、cess returned u execut ion tine - 2tf - 015 s *r-ess any key to continue.5 15 15 13 13 10 10 10 10222222222222224I 4P 3 4 07- 6 皿:1魏0 九務为 数间率 页访页 缺ln-礁LErncess returned U execut ion t line - 24.149 s LPi*ess any key t-D continue -输入程序云行吋访问的页面次序以及物理内存的分页数:B12434512512345G 4选择萱换算法二1.F1FO 2.LRU 3.OPT 4

23、.LFU 5.NRU5认下为丽U算袪圉解：012434S12512345nJ4 4 45 5 51162 2 23 3 3 3 %石“ 11112 2 2 2Ln-3 0 4Z6 :1数n. 凄为 数冋率 页访页 缺总缺Process returned 0 execut:lon tlne - 16 .34? s Press any key to continue.FIFO算法流程图:LRU算法流程图:OPT算法流程图:LFU算法流程图:NRU算法流程图:开始四.思考与总结(1) 针对上述页面访问顺序，请比较上述各页面置换算法的性能。对于访问顺序 0,1,2,4,3,4,5,125,1,2,3,

24、4,5,6当分页数为4时： 随着分页数增加它们的缺页数均降低。FIFO算法对此访问串无Belady现象。OPT算法表现最好，实际上我们将OPT算法当做最优的评判标准。LRU算法理论上是优于 FIFO算法的，但此时缺页率却高于 FIFO算法，主要是受访问串以及 分页数的影响。只能说此访问串更适合FIFO算法。所以在实际中，我们要选择最适合的算法考虑。当分页数为5时，各算法情况：触入程序运行时访间的页面枕序以及物理内存的分页数匕 陆择置换算法：1,FIFO 2.LRU OPT 4-LFM 5.MRU以下为丽疇袪图解;124J451251234b6aRnnE5弓弓555g511111111111111622222222222222444444444444433333333333输入程序运行时访问的页面试序叹及物理内存的分页数;012434512512M