实验4内存管理.docx
《实验4内存管理.docx》由会员分享，可在线阅读，更多相关《实验4内存管理.docx（22页珍藏版）》请在冰点文库上搜索。
实验4内存管理
实验4存管理
学校：
FJUT学号：
3131903229班级：
计算机1302：
峰
注：
其中LFU和NRU算法运行结果可能与其他人不同，只是实现方式不同，基本思路符合就可以。
一.实验学时与类型
学时：
2，课外学时：
自定
实验类型：
设计性实验
二.实验目的
模拟实现请求页式存储管理中常用页面置换算法，理会操作系统对存的调度管理。
三.实验容
要求：
各算法要给出详细流程图以及执行结果截图。
假设有一程序某次运行访问的页面依次是：
0,1,2,4,3,4,5,1,2,5,1,2,3,4,5,6，请给出采用下列各页面置换算法时页面的换进换出情况，并计算各调度算法的命中率（命中率=非缺页次数/总访问次数），初始物理存为空，物理存可在4～20页中选择。
（1）FIFO：
最先进入的页被淘汰；
（2）LRU：
最近最少使用的页被淘汰；
（3）OPT：
最不常用的页被淘汰；（选做）
（4）LFU：
访问次数最少的页被淘汰（LFU）。
（选做）
源代码：
#include
#include
#include
#include
#defineMAXNUM100
structPhy_Memory{//定义一个物理存结构体
charPage;
inttime;
};
char*OutPut;
structPhy_Memory*Phy_Page;
voidPrint（char*PageStr,intPhy_PageNum,intabsence）{//打印图解函数
inti,j;
for（i=0;ifor（i=0;ifor（i=0;ifor（j=0;jprintf（"%c",*（OutPut+i*strlen（PageStr）+j））;
}
printf（"\n"）;
}
printf（"缺页数为:
%d\n",absence）;
printf（"总访问次数为:
%d\n",strlen（PageStr））;
printf（"缺页率为%.2f\n",（double）absence/strlen（PageStr））;
}
intIsExist（char*Temp,intPhy_PageNum）{//判断某页面是否存在于物理存中
inti;
for（i=0;iPage!
=*Temp;i++）;
if（ireturn0;
}
voidFIFO（char*PageStr,intPhy_PageNum）{//利用时间计数器方式，还可以用栈来实现
char*Temp=PageStr;//定义Temp指针指向PageStr首地址
inti,num,location,absence=0;
intFlag=0;//定义一个标记变量，标记插入位置
while（*Temp!
='\0'）{//页面未访问完
num=0;
if（Flagif（!
IsExist（Temp,Flag））{//若此页面未被访问
（Phy_Page+Flag）->Page=*Temp;
Flag++;absence++;
}
}
else{//若物理存已满
if（!
IsExist（Temp,Phy_PageNum））{//若此页面未被访问
for（i=0;iif（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;i（Phy_Page+i）->time++;
*（OutPut+i*strlen（PageStr）+（Temp-PageStr））=（Phy_Page+i）->Page;
}
Temp++;
}
Print（PageStr,Phy_PageNum,absence）;
}
voidLRU（char*PageStr,intPhy_PageNum）{//依旧利用计数器方式，也可用栈来实现
char*Temp=PageStr;//定义Temp指针指向PageStr首地址
inti,num,location,absence=0;
intFlag=0;//定义一个标记变量，标记插入位置
while（*Temp!
='\0'）{//页面未访问完
num=0;
if（Flagif（location=IsExist（Temp,Phy_PageNum））{//若此页面已被访问
（Phy_Page+location-1）->time=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;iif（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;i（Phy_Page+i）->time++;
*（OutPut+i*strlen（PageStr）+（Temp-PageStr））=（Phy_Page+i）->Page;
}
Temp++;
}
Print（PageStr,Phy_PageNum,absence）;
}
intDistance（char*PageStr,char*Temp,charNow）{//计算距离函数（OPT算法中使用）
inti;
for（i=1;*（Temp+i）!
='\0'&&*（Temp+i）!
=Now;i++）;
if（*（Temp+i）!
='\0'）returni;
returnINT_MAX;
}
voidOPT（char*PageStr,intPhy_PageNum）{//实际中无法实现，知道访问串后顺序遍历
char*Temp=PageStr;//定义Temp指针指向PageStr首地址
inti,num,Size,location,absence=0;
intFlag=0;//定义一个标记变量，标记插入位置
while（*Temp!
='\0'）{//页面未访问完
num=0;
if（Flagif（!
IsExist（Temp,Flag））{//若此页面未被访问
（Phy_Page+Flag）->Page=*Temp;
Flag++;absence++;
}
}
else{//若物理存已满
if（!
IsExist（Temp,Phy_PageNum））{//若此页面未被访问
for（i=0;iSize=Distance（PageStr,Temp,（Phy_Page+i）->Page）;//调用distance函数返回值为与当前位置物理页面相同页号的距离
if（numlocation=i;num=Size;
}
}
（Phy_Page+location）->Page=*Temp;absence++;
}
}
for（i=0;i*（OutPut+i*strlen（PageStr）+（Temp-PageStr））=（Phy_Page+i）->Page;
Temp++;
}
Print（PageStr,Phy_PageNum,absence）;
}
char*Create（char*PageStr）{//根据访问串建立计数字符数组（LFU算法使用）
inti,j,Size,Num=0;
char*Temp1,*Temp2;
intlength=strlen（PageStr）;
char*NowPage=（char*）malloc（length）;
for（i=0;iTemp1=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=0;iif（*（NowPage+i）!
='\0'）{
*（Count+Size-1）=*（NowPage+i）;
Size--;
}
}
Size=length-Num;
for（i=Size;i<2*Size;i++）{//计数位置零
*（Count+i）='0';
}
returnCount;
}
voidAdd（char*Ptr,charStr,intSize）{//相应计数器加一（LFU算法使用）
inti;
for（i=0;*（Ptr+i）!
=Str;i++）;
*（Ptr+i+Size）+=1;
}
intFind（char*Ptr,charStr,intSize）{//在计数器中找到相应页面并返回其计数值（LFU算法使用）
inti;
for（i=0;*（Ptr+i）!
=Str;i++）;
return（*（Ptr+i+Size）-'0'）;
}
voidZero（char*Ptr,intSize）{//将所有计数器清零（LFU算法使用）
inti;
for（i=Size;i<2*Size;i++）*（Ptr+i）='0';
}
voidLFU（char*PageStr,intPhy_PageNum）{//对每一页面设置一个计数器，每次选出最小的淘汰
char*Temp=PageStr;//定义Temp指针指向PageStr首地址
char*Count=Create（PageStr）;
inti,Size,time,num,location,absence=0;
intFlag=0;//定义一个标记变量，标记插入位置
Size=strlen（Count）/2;
while（*Temp!
='\0'）{//页面未访问完
num=INT_MAX;
if（Flagif（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;itime=Find（Count,（Phy_Page+i）->Page,Size）;
if（num>time）{
location=i;num=time;
}
}
（Phy_Page+location）->Page=*Temp;
Zero（Count,Size）;
absence++;
}
}
for（i=0;i*（OutPut+i*strlen（PageStr）+（Temp-PageStr））=（Phy_Page+i）->Page;
Temp++;
intj;//打印每次访问后的计数器值
for（i=0;i<2;i++）{
for（j=0;jprintf（"%c",*（Count+i*Size+j））;
printf（"\n"）;
}
printf（"\n"）;
}
Print（PageStr,Phy_PageNum,absence）;
}
voidNRU（char*PageStr,intPhy_PageNum）{//对每个物理页设置一个标识（0/1），用指针循环访问淘汰标识为零的页面
char*Temp=PageStr;//定义Temp指针指向PageStr首地址
inti,location,absence=0;
intFlag=0;//定义一个标记变量，标记插入位置
structPhy_Memory*Clock=Phy_Page;//定义一个结构体指针指向物理存首地址
while（*Temp!
='\0'）{//页面未访问完
if（Flagif（location=IsExist（Temp,Phy_PageNum））{//若此页面已被访问
（Phy_Page+location-1）->time=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_Page）>=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;i*（OutPut+i*strlen（PageStr）+（Temp-PageStr））=（Phy_Page+i）->Page;
}
Temp++;
}
Print（PageStr,Phy_PageNum,absence）;
}
intmain（）{
char*Str;inti,n,Num;
Str=（char*）malloc（MAXNUM）;
printf（"输入程序运行时访问的页面次序以及物理存的分页数:
\n"）;
scanf（"%s%d",Str,&Num）;
Phy_Page=（structPhy_Memory*）malloc（Num*sizeof（structPhy_Memory））;//初始化物理存结构体
OutPut=（char*）malloc（Num*strlen（Str））;
for（i=0;itime=0;
printf（"选择置换算法:
\n1.FIFO2.LRU3.OPT4.LFU5.NRU\n"）;
scanf（"%d",&n）;
switch（n）{
case1:
printf（"\n以下为FIFO算法图解:
\n"）;FIFO（Str,Num）;break;
case2:
printf（"\n以下为LRU算法图解:
\n"）;LRU（Str,Num）;break;
case3:
printf（"\n以下为OPT算法图解:
\n"）;OPT（Str,Num）;break;
case4:
printf（"\n以下为LFU算法图解:
\n各时期计数器如下:
\n"）;LFU（Str,Num）;break;
case5:
printf（"\n以下为NRU算法图解:
\n"）;NRU（Str,Num）;break;
}
free（Phy_Page）;free（OutPut）;
return0;
}
注：
这里只对分页数为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）算法.
升级会员 