实验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 #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

for(j=0;j

printf(\ } .

.

printf(\ }

printf(\缺页数为:%d\\n\

printf(\总访问次数为:%d\\n\

printf(\缺页率为%.2f\\n\}

int IsExist(char *Temp,int Phy_PageNum){ //判断某页面是否存在于物理内存中 int i;

for(i=0;iPage!=*Temp;i++);

if(i

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(FlagPage=*Temp; Flag++;absence++; } }

else{ //若物理内存已满

if(!IsExist(Temp,Phy_PageNum)){ //若此页面未被访问 for(i=0;itime){

location=i;num=(Phy_Page+i)->time; } }

(Phy_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); } .

.

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

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;itime){

location=i;num=(Phy_Page+i)->time; } }

(Phy_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(*(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; Flag++;absence++; } }

else{ //若物理内存已满

if(!IsExist(Temp,Phy_PageNum)){ //若此页面未被访问

for(i=0;i

Size=Distance(PageStr,Temp,(Phy_Page+i)->Page); //调用distance函数返回值为与当前位置物理页面相同页号的距离 if(num

location=i;num=Size; } }

(Phy_Page+location)->Page=*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 *)malloc(length);

for(i=0;i

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

*(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

if(location=IsExist(Temp,Phy_PageNum)){ //若此页面已被访问 .