《实验4-内存管理.doc》由会员分享，可在线阅读，更多相关《实验4-内存管理.doc（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 string。hinclude limits。hinclude malloc。hdefine MAXNUM 100struct Phy_Memory /定义一个物理内存结构体 char Page; int time；;char OutPut;struct Phy_Memory Phy_Page；void Print(ch
3、ar 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
4、)； 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(itime） location=i；num=（Phy_Page+i）time； （Phy_Page+location)-Page=*Temp； (Phy_Page+location）tim
5、e=0; absence+； for（i=0;itime+； （OutPut+istrlen(PageStr）+(TempPageStr）=(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!
6、=0） /页面未访问完 num=0； if（Flagtime=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+loca
7、tion）-Page=Temp； (Phy_Page+location)time=0； absence+； for（i=0；iFlag；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
8、)!=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(FlagPage=*Temp;absence+； for（i=0；iFlag;
9、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+） （ N
10、owPage + i ） = ( PageStr + i )； Temp1 = Temp2 = NowPage； while(（Temp1-NowPage）=length+1） /去除访问串中重复串 if(Temp1！=0） for（Temp2=Temp1+1；(Temp2NowPage）=length+1；Temp2+） if（Temp1=Temp2) *Temp2=0；Num+; Temp1+; Size=length-Num； char Count=（char )malloc(Size2）; for（i=0;ilength;i+) /将不重复的访问页置于计数器中 if（*(NowPage
11、+i)!=0） （Count+Size-1）=*(NowPage+i）； Size； Size=lengthNum； for（i=Size；iPage，Size）； else /若此页面未被访问 for（i=0;itime) location=i；num=time; （Phy_Page+location）Page=Temp； Zero（Count，Size）； absence+; for(i=0；iFlag；i+） /将当前物理内存数组列放入二维数组中 *（OutPut+istrlen（PageStr)+(TempPageStr）=(Phy_Page+i）-Page； Temp+； int j
12、; /打印每次访问后的计数器值 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; /定义一个标记变
13、量,标记插入位置 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（Clock-Phy_Page）
14、=Phy_PageNum) Clock=Phy_Page; else /若物理内存已满 if(location=IsExist(Temp，Phy_PageNum）) /若此页面已被访问 (Phy_Page+location-1）time=1； else /若此页面未被访问 while（Clocktime） Clocktime=0；Clock+； if(ClockPhy_Page）=Phy_PageNum) Clock=Phy_Page； ClockPage=*Temp； Clocktime=1；Clock+； if（(ClockPhy_Page）=Phy_PageNum） Clock=Phy_
15、Page； absence+； for(i=0；iFlag;i+) /将当前物理内存数组列放入二维数组中 (OutPut+istrlen(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（”%sd，Str，Num）; Phy_Page=(struct Phy_Memory）ma
16、lloc(Num*sizeof（struct Phy_Memory)）； /初始化物理内存结构体 OutPut=(char）malloc(Num*strlen（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)；bre
17、ak； 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) 针对上述页面访问顺序，请比较上述各页面
18、置换算法的性能.对于访问顺序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算法一致.结论：对于这些算法,我们不能说谁是最优的，具体我们还是要看实际访问串以及分页数情况.不过在
19、实际系统中我们还应该考虑到哪一种算法更容易实现，将系统开销尽可能的降低。(2) 对于LRU，程序中采用什么方法来体现“最近这一时间要素？我将物理内存的每一页都用time来计数,当访问过这一页时,将time置为0.内存中没有这一页时选择计数最少的淘汰即可。并且每访问一页后，所有物理内存页面的计数器都加一.(3) LRU和LFU有什么异同?LRU/LFU可以称为近似OPT算法吗？LRU算法是总是选择最近一段时间内最长时间没有被访问过的页面调出，而LFU算法是考虑到每个页面的访问次数，二者在本质上个人认为还是不同的，不能说近似FIFO.在实际系统中实现起来均比较困难.它们都要用到计数器，大大降低系统开销，所以实际系统中还是使用LRU的近似算法，即CLOCK（NRU）算法.