实验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，请给出采用下列各页面置换算法时页面的换进换出情况，并计算各调度算法的命中率(命中率=非缺页次数/总访问次数)，初始物理内存为空,物理内存可在4～20页中选择.
(1）FIFO：最先进入的页被淘汰;
（2)LRU：最近最少使用的页被淘汰；
（3)OPT:最不常用的页被淘汰；（选做）
(4）LFU:访问次数最少的页被淘汰（LFU）。（选做）
源代码：
#include <stdio。h〉
#include <string。h〉
#include 〈limits。h〉
＃include 〈malloc.h>
#define MAXNUM 100
struct 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;i〈strlen（PageStr）;i++）printf("％c ”,＊(PageStr+i));printf（”\n"）；
for（i=0；i〈strlen（PageStr）；i++）printf(”-—”）;printf(”\n”）；
for(i=0；i<Phy_PageNum;i++){
for（j=0;j<strlen（PageStr)；j++）｛
printf(”%c ”，*(OutPut+i＊strlen(PageStr）+j)）；
｝
printf（”\n"）;
}
printf(”缺页数为：％d\n”，absence）；
printf（”总访问次数为:%d\n",strlen(PageStr）)；
printf（”缺页率为％。2f\n”，(double)absence/strlen(PageStr）);
｝
int IsExist（char ＊Temp，int Phy_PageNum）{ //判断某页面是否存在于物理内存中
int i;
for(i=0;i<Phy_PageNum＆＆(Phy_Page+i)—〉Page！=*Temp；i++)；
if(i<Phy_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（Flag〈Phy_PageNum）{ //若物理内存未满
if（！IsExist(Temp，Flag)）{ //若此页面未被访问
(Phy_Page+Flag）—〉Page=＊Temp;
Flag++；absence++;
｝
}
else｛ //若物理内存已满
if（!IsExist（Temp，Phy_PageNum)）｛ //若此页面未被访问
for（i=0;i〈Flag;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；i〈Flag；i++)｛ //将当前物理内存数组列放入二维数组中
（Phy_Page+i)—>time++；
＊（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; //定义一个标记变量，标记插入位置
while（＊Temp！=’\0'）{ //页面未访问完
num=0；
if（Flag〈Phy_PageNum){ //若物理内存未满
if（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；i〈Flag；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；i<Flag；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）！=’\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(Flag〈Phy_PageNum）｛ //若物理内存未满
if(!IsExist（Temp,Flag））｛ //若此页面未被访问
(Phy_Page+Flag）—〉Page=＊Temp；
Flag++；absence++;
｝
｝
else{ //若物理内存已满
if（！IsExist（Temp,Phy_PageNum)）｛ //若此页面未被访问
for（i=0；i<Flag;i++）{ //淘汰在访问串中将来再也不会出现的或离当前最远的位置上出现的页
Size=Distance（PageStr,Temp,（Phy_Page+i）—>Page）； //调用distance函数返回值为与当前位置物理页面相同页号的距离
if(num〈Size）｛
location=i；num=Size；
｝
｝
（Phy_Page+location）—〉Page=*Temp；absence++；
｝
｝
for（i=0；i〈Flag;i++) //将当前物理内存数组列放入二维数组中
＊(OutPut+i＊strlen（PageStr）+（Temp—PageStr))=(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;i<length；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=0；i〈length;i++）｛ //将不重复的访问页置于计数器中
if（＊（NowPage+i）！=’\0')｛
*（Count+Size—1）=＊（NowPage+i）；
Size—-；
}
｝
Size=length—Num;
for（i=Size；i〈2＊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,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;i〈2＊Size;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（Flag<Phy_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；i<Flag；i++)｛ //找到被访问次数最少的一页
time=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〈Flag;i++） //将当前物理内存数组列放入二维数组中
*（OutPut+i＊strlen(PageStr）+（Temp—PageStr))=（Phy_Page+i)—>Page;
Temp++;
int j; //打印每次访问后的计数器值
for（i=0；i〈2；i++）｛
for（j=0;j〈Size；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（Flag〈Phy_PageNum）｛ //若物理内存未满
if（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〈Flag;i++）{ //将当前物理内存数组列放入二维数组中
*（OutPut+i*strlen（PageStr)+(Temp—PageStr））=(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（Num＊strlen（Str）)；
for（i=0；i〈Num;i++)(Phy_Page+i )—〉time=0;
printf（"选择置换算法：\n1。FIFO 2.LRU 3。OPT 4.LFU 5。NRU\n”);
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）算法。