实验4-内存管理.doc

实验4 内存管理学校:FJUT 学号：3131903229 班级：计算机1302 姓名：姜峰注:其中LFU和NRU算法运行结果可能与其他人不同,只是实现方式不同,基本思路符合就可以。一. 实验学时与类型学时：2，课外学时：自定实验类型：设计性实验二. 实验目的模拟实现请求页式存储管理中常用页面置换算法，理会操作系统对内存的调度管理。三. 实验内容要求：各算法要给出详细流程图以及执行结果截图。假设有一程序某次运行访问的页面依次是：0，1，2，4，3，4，5,1，2,5,1，2,3,4,5，6，请给出采用下列各页面置换算法时页面的换进换出情况，并计算各调度算法的命中率(命中率=非缺页次数/总访问次数)，初始物理内存为空,物理内存可在420页中选择.(1）FIFO：最先进入的页被淘汰;（2)LRU：最近最少使用的页被淘汰；（3)OPT:最不常用的页被淘汰；（选做）(4）LFU:访问次数最少的页被淘汰（LFU）。（选做） 源代码：#include stdio。h#include #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;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+istrlen(PageStr）+j)）； printf（”n）; printf(”缺页数为：dn”，absence）； printf（”总访问次数为:%dn,strlen(PageStr）)； printf（”缺页率为。2fn”，(double)absence/strlen(PageStr）);int IsExist（char Temp，int Phy_PageNum） /判断某页面是否存在于物理内存中 int i; for(i=0;iPhy_PageNum(Phy_Page+i)Page！=*Temp；i+)； if(iPhy_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（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（numtime） 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+istrlen（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（FlagPhy_PageNum) /若物理内存未满 if（location=IsExist(Temp，Phy_PageNum)） /若此页面已被访问 （Phy_Page+location1)-time=0； else /若此页面未被访问 （Phy_Page+Flag）-Page=Temp； Flag+;absence+； else /若物理内存已满 if（location=IsExist（Temp,Phy_PageNum）) /若此页面已被访问 （Phy_Page+location1)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；itime+； （OutPut+istrlen（PageStr)+(TempPageStr)=(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(FlagPhy_PageNum） /若物理内存未满 if(!IsExist（Temp,Flag） /若此页面未被访问 (Phy_Page+Flag）Page=Temp； Flag+；absence+; else /若物理内存已满 if（！IsExist（Temp,Phy_PageNum)） /若此页面未被访问 for（i=0；iPage）； /调用distance函数返回值为与当前位置物理页面相同页号的距离 if(numSize） location=i；num=Size； （Phy_Page+location）Page=*Temp；absence+； for（i=0；iFlag;i+) /将当前物理内存数组列放入二维数组中 (OutPut+istrlen（PageStr）+（TempPageStr)=(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;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=lengthNum； char Count=（char *）malloc（Size2)； for（i=0；ilength;i+） /将不重复的访问页置于计数器中 if（NowPage+i）！=0) *（Count+Size1）=（NowPage+i）； Size-； Size=lengthNum; for（i=Size；i2Size;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;i2Size;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（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；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（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（FlagPhy_PageNum） /若物理内存未满 if（location=IsExist(Temp，Phy_PageNum） /若此页面已被访问 (Phy_Page+location1）-time=1； else /若此页面未被访问 （Phy_Page+Flag）Page=*Temp； （Phy_Page+Flag）-time=1； Flag+;absence+；Clock+; if（ClockPhy_Page）=Phy_PageNum） Clock=Phy_Page； else /若物理内存已满 if（location=IsExist（Temp，Phy_PageNum） /若此页面已被访问 （Phy_Page+location1)-time=1； else /若此页面未被访问 while（Clocktime) Clock-time=0；Clock+； if(（ClockPhy_Page）=Phy_PageNum） Clock=Phy_Page； ClockPage=Temp; Clocktime=1；Clock+； if（(ClockPhy_Page）=Phy_PageNum) Clock=Phy_Page； absence+; for（i=0；iFlag;i+） /将当前物理内存数组列放入二维数组中 *（OutPut+i*strlen（PageStr)+(TempPageStr）=(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（Numstrlen（Str）)； for（i=0；iNum;i+)(Phy_Page+i )time=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）;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) 针对上述页面访问顺序，请比较上述各页面置换算法的性能。对于访问顺序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算法一致。结论:对于这些算法，我们不能说谁是最优的，具体我们还是要看实际访问串以及分页数情况。不过在实际系统中我们还应该考虑到哪一种算法更容易实现,将系统开销尽可能的降低。(2) 对于LRU，程序中采用什么方法来体现“最近这一时间要素？我将物理内存的每一页都用time来计数,当访问过这一页时，将time置为0。内存中没有这一页时选择计数最少的淘汰即可。并且每访问一页后，所有物理内存页面的计数器都加一。(3) LRU和LFU有什么异同？LRU/LFU可以称为近似OPT算法吗?LRU算法是总是选择最近一段时间内最长时间没有被访问过的页面调出，而LFU算法是考虑到每个页面的访问次数,二者在本质上个人认为还是不同的，不能说近似FIFO。在实际系统中实现起来均比较困难。它们都要用到计数器，大大降低系统开销，所以实际系统中还是使用LRU的近似算法，即CLOCK(NRU）算法。