存储管理模拟实现.docx

存储管理模拟实现.docx

《存储管理模拟实现.docx》由会员分享，可在线阅读，更多相关《存储管理模拟实现.docx（27页珍藏版）》请在冰点文库上搜索。

存储管理模拟实现

存储管理模拟实现

一、实验目的

存储管理的主要功能之一是合理地分配空间。

请求页式管理是一种常用的虚拟存储管理技术。

本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

二、实验内容

编程实现页面置换算法，要求输出页面的置换过程，具体可以编程实现OPT、FIFO和LRU算法。

1．过随机数产生一个指令序列，共320条指令。

其地址按下述原则生成：

①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分；

③25%的指令是均匀分布在后地址部分；

#具体的实施方法是：

A.在[0，319]的指令地址之间随机选区一起点M;

B.顺序执行一条指令，即执行地址为M+1的指令；

C.在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;

D.顺序执行一条指令，其地址为M’+1；

E.在后地址[M’+2，319]中随机选取一条指令并执行；

F.重复A—E，直到执行320次指令。

2．指令序列变换成页地址流

设：

（1）页面大小为1K；

（2）用户内存容量为4页到32页；

（3）用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第0条—第9条指令为第0页（对应虚存地址为[0，9]）；

第10条—第19条指令为第1页（对应虚存地址为[10，19]）；

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

。

第310条—第319条指令为第31页（对应虚存地址为[310，319]）；

按以上方式，用户指令可组成32页。

3.计算并输出下述各种算法在不同内存容量下的命中率。

A.FIFO先进先出的算法

B.LRU最近最少使用算法

C．LFU最少访问页面算法

三、实验要求

1、需写出设计说明；

2、设计实现代码及说明

3、运行结果；

四、主要实验步骤

1、分析算法结构；

画出算法的流程图，即设计说明；

根据画出的流程图使用C语言编写相应的代码（代码过长，放到最后）；

程序主要由main函数和以下几个函数组成：

voidinitialization（）;初始化内存数据

voidFIFO（）;FIFO先进先出算法；

voidLRU（）;LRU最久未使用算法；

voidLFU（）;LFU最近最久未使用算法：

流程图如下：

页面置换算法整体结构

FIFO页面置换算法

LRU页面置换算法

LFU页面置换算法

2、设计说明及源代码

FIFO算法设计说明：

按照所要求的产生随机指令序列，存放在order[320]这个数组中。

通过循环产生这些随机指令，每产生一条都要进行下列判断：

是否和内存中即mem

_volume[4]中存放的页面相同，如果相同则不做任何操作，如果不相同，则产生缺页，相应的缺页次数加一，按照fcfs将最先进入内存的页数淘汰，并将该页写到内存中去。

重复上面的操作直到完成这320条指令。

源代码：

//储存管理.cpp:

定义控制台应用程序的入口点。

//

#include"stdafx.h"

int_tmain（intargc,_TCHAR*argv[]）

{

return0;

}

#include

#include

#include

#defineN5//总共运行的次数

voidmain（）

{

intorder[320],mem_volume[4]={100,100,100,100};

//使得mem_volume[]的值大于100>32，这样我们便可使其在开始就产生缺页

//定义add为缺页次数sign作为标识符判断所调页数是否在内存中

intl=0,i=0,j,num=0,cx,sign=0,add=0;

floatvalue=0,sum=0;//定义sum为缺页率

srand（time（NULL））;

for（cx=0;cx

{

while（i<320）

{

order[i]=rand（）%320;//产生随机数放order中

for（j=0;j<4;j++）

if（（order[i]+1）/10==mem_volume[j]）

sign=1;//通过sign标识判断所调页数是否在内存块中

if（sign）

sign=0;

else

{

l++;

if（mem_volume[3]==100）

mem_volume[3]=（order[i]+1）/10;//保证第一次调入的页面都产生缺页

else

{

mem_volume[num]=（order[i]+1）/10;//将所缺页调入到内存块中

num=（num+1）%4;

//num值为下次所要置换出去的内存块中对应的页数

}

}

i++;

order[i]=rand（）%（order[i-1]+2）;

for（j=0;j<4;j++）

if（order[i]/10==mem_volume[j]）

sign=1;

if（sign）

sign=0;

else

{

l++;

if（mem_volume[2]==100）

mem_volume[2]=order[i]/10;

else

{

mem_volume[num]=order[i]/10;

num=（num+1）%4;

}

}

i++;

order[i]=order[i-1]+1;

for（j=0;j<4;j++）

if（order[i]/10==mem_volume[j]）

sign=1;

if（sign）

sign=0;

else

{

l++;

if（mem_volume[1]==100）

mem_volume[1]=order[i]/10;

else

{

mem_volume[num]=order[i]/10;

num=（num+1）%4;

}

}

i++;

order[i]=rand（）%（319-order[i-1]-2）+（order[i-1]+2）;

for（j=0;j<4;j++）

if（order[i]/10==mem_volume[0]）

sign=1;

if（sign）

sign=0;

else

{

l++;

if（mem_volume[0]==100）

mem_volume[0]=（order[i]+1）/10;

else

{

mem_volume[num]=order[i]/10;

num=（num+1）%4;

}

}

i++;

}

value=l/320.0*100;

add=add+l;

sum=sum+value;

}

printf（"*******************FIFO页面置换算法*******************\n"）;

printf（"*******************最后一次指令序列*******************"）;

for（i=0;i<320;i++）

{

if（i%10==0）

printf（"\n"）;

printf（"%5d",order[i]）;

}

printf（"\n"）;

printf（"************************************************************\n"）;

printf（"\t\t%d次的平均缺页数为%d\n\t\t%d次的平均缺页率为%.3f%%\n",N,add/N,N,sum/N）;

printf（"\n"）;

}

LRU页面置换算法设计说明：

这个算法同FCFS算法的不同之处在于，每产生一条随机指令，如果和4个内存块中的某一个页数相同的话，就要对这4个内存块中的页数重新排序，将每次要置换出去的页数放在mem_volume[3]中，这样，在每次产生缺页的时候，都先将所缺页数写入到该内存块，然后再排序，将其放到mem_volume[0]中去。

源代码：

//储存管理.cpp:

定义控制台应用程序的入口点。

//

#include"stdafx.h"

int_tmain（intargc,_TCHAR*argv[]）

{

return0;

}

#include

#include

#include

#defineN5

intmain（void）

{

intorder[320],mem_volume[4]={100,100,100,100};

intl=0,i=0,j,cx;

intnum,temp=0,ex_chan=0,add=0;

floatvalue=0,sum=0;

srand（time（NULL））;

for（cx=0;cx

while（i<320）{

order[i]=rand（）%320;

if（（order[i]+1）/10==mem_volume[0]）

;//如果所调页数同第一个内存块中页数相同，则执行空操作

elseif（（order[i]+1）/10==mem_volume[1]）{

temp=mem_volume[1];

mem_volume[1]=mem_volume[0];

mem_volume[0]=temp;//如果所调页数同第二个内存块相同，则排序只需交换一次

}

elseif（（order[i]+1）/10==mem_volume[2]）{

for（j=2;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

elseif（（order[i]+1）/10==mem_volume[3]）{

for（j=3;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}//如果所调页数同第3、4个内存块中页数相同，则通过循环进行排序

else{

l++;

if（mem_volume[3]==100）

mem_volume[3]=（order[i]+1）/10;//保证刚开始调入内存块中就产生缺页

else{

mem_volume[3]=（order[i]+1）/10;

for（num=3;num>0;num--）{

ex_chan=mem_volume[num];

mem_volume[num]=mem_volume[num-1];

mem_volume[num-1]=ex_chan;//写人后重新排序

}

}

}

i++;

order[i]=rand（）%（order[i-1]+2）;

if（order[i]/10==mem_volume[0]）

;

elseif（order[i]/10==mem_volume[1]）{

temp=mem_volume[1];

mem_volume[1]=mem_volume[0];

mem_volume[0]=temp;

}

elseif（order[i]/10==mem_volume[2]）{

for（j=2;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

elseif（order[i]/10==mem_volume[3]）{

for（j=3;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

else{

l++;

if（mem_volume[2]==100）

mem_volume[2]=order[i]/10;

else{

mem_volume[3]=order[i]/10;

for（num=3;num>0;num--）{

ex_chan=mem_volume[num];

mem_volume[num]=mem_volume[num-1];

mem_volume[num-1]=ex_chan;

}

}

}

i++;

order[i]=order[i-1]+1;

if（order[i]/10==mem_volume[0]）

;

elseif（order[i]/10==mem_volume[1]）{

temp=mem_volume[1];

mem_volume[1]=mem_volume[0];

mem_volume[0]=temp;

}

elseif（order[i]/10==mem_volume[2]）{

for（j=2;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

elseif（order[i]/10==mem_volume[3]）{

for（j=3;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

else{

l++;

if（mem_volume[1]==100）

mem_volume[1]=order[i]/10;

else{

mem_volume[3]=order[i]/10;

for（num=3;num>0;num--）{

ex_chan=mem_volume[num];

mem_volume[num]=mem_volume[num-1];

mem_volume[num-1]=ex_chan;

}

}

}

i++;

order[i]=rand（）%（319-order[i-1]-2）+（order[i-1]+2）;

if（order[i]/10==mem_volume[0]）

;

elseif（order[i]/10==mem_volume[1]）{

temp=mem_volume[1];

mem_volume[1]=mem_volume[0];

mem_volume[0]=temp;

}

elseif（order[i]/10==mem_volume[2]）{

for（j=2;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

elseif（order[i]/10==mem_volume[3]）{

for（j=3;j>0;j--）{

temp=mem_volume[j];

mem_volume[j]=mem_volume[j-1];

mem_volume[j-1]=temp;

}

}

else{

l++;

if（mem_volume[0]==100）

mem_volume[0]=order[i]/10;

else{

mem_volume[3]=order[i]/10;

for（num=3;num>0;num--）{

ex_chan=mem_volume[num];

mem_volume[num]=mem_volume[num-1];

mem_volume[num-1]=ex_chan;

}

}

}

i++;

}

value=l/320.0*100;

sum=sum+value;

add=add+l;

}

printf（"*******************LRU页面置换算法******************\n"）;

printf（"*******************指令序列******************"）;

for（i=0;i<320;i++）{

if（i%10==0）

printf（"\n"）;

printf（"%5d",order[i]）;

}

printf（"\n"）;

printf（"**********************************************************\n"）;

printf（"\t\t%d次的平均缺页数为%d\n\t\t%d次的平均缺页率为%.3f%%\n",N,add/N,N,sum/N）;

printf（"\n"）;

}

LFU页面置换算法设计说明：

该算法主要是将最近时期页面使用最少的页面作为淘汰页。

这里通过设立count[32]这个计数数组记录32页的调用次数，通过比较来确定要调出的页面。

但如果没产生缺页就只需对所调页数对应的count值加1即可。

源代码：

//储存管理.cpp:

定义控制台应用程序的入口点。

//

#include"stdafx.h"

int_tmain（intargc,_TCHAR*argv[]）

{

return0;

}

#include

#include

#include

#defineN5//定义运行次数

voidmain（）

{

intorder[320],count[32]={0},compare[4]={0},mem_volume[4]={100,100,100,100};

//compare数组中存放了每次要比较的四个内存块中页数的调用次数

intl=0,i=0,j,k=0,cx=0;

intmin,num=0,n,sign=0,add=0;

floatvalue=0,sum=0;

srand（time（NULL））;

for（cx=0;cx

while（i<320）{

order[i]=rand（）%320;

for（j=0;j<4;j++）

if（（order[i]+1）/10==mem_volume[j]）{

n=（order[i]+1）/10;

count[n]+=1;

sign=1;//相同执行加1操作

}

if（sign）

sign=0;

else{

l++;

if（mem_volume[3]==100）{

mem_volume[3]=（order[i]+1）/10;

n=（order[i]+1）/10;

count[n]+=1;

}

else{min=1000;

for（num=0;num<4;num++）{

k=mem_volume[num];

compare[num]=count[k];

if（compare[num]

min=compare[num];

j=num;//通过比较确定最少使用的页数，

}

}

mem_volume[j]=（order[i]+1）/10;

}

}

i++;

order[i]=rand（）%（order[i-1]+2）;

for（j=0;j<4;j++）

if（order[i]/10==mem_volume[j]）{

n=order[i]/10;

count[n]+=1;

sign=1;

}

if（sign）

sign=0;

else{

l++;

if（mem_volume[2]==100）{

mem_volume[2]=（order[i]+1）/10;

n=（order[i]+1）/10;

count[n]+=1;

}

else{min=1000;

for（num=0;num<4;num++）{

k=mem_volume[num];

compare[num]=count[k];

if（compare[num]

min=compare[num];

j=num;

}

}

mem_volume[j]=（order[i]+1）/10;

}

}

i++;

order[i]=order[i-1]+1;

for（j=0;j<4;j++）

if（order[i]/10==mem_volume[j]）{

n=order[i]/10;

count[n]+=1;

sign=1;

}

if（sign）

sign=0;

else{

l++;

if（mem_volume[1]==100）{

mem_volume[1]=（order[i]+1）/10;

n=（order[i]+1）/10;

count[n]+=1;

}

else{min=1000;

for（num=0;num<4;num++）{