存储管理模拟实现

一、实验目的

存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。本实验的目的是通过请求页式存储管理中页面置换算法模拟设计，了解虚拟存储技术的特点，掌握请求页式管理的页面置换算法。

二、实验内容

编程实现页面置换算法，要求输出页面的置换过程，具体可以编程实现OPT、FIFO和LRU算法。 1．过随机数产生一个指令序列，共320条指令。其地址按下述原则生成： ①50%的指令是顺序执行的；

②25%的指令是均匀分布在前地址部分； ③25%的指令是均匀分布在后地址部分； #具体的实施方法是：

A. B. C. D. E. F.

在[0，319]的指令地址之间随机选区一起点M; 顺序执行一条指令，即执行地址为M+1的指令；

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

在后地址[M’+2，319]中随机选取一条指令并执行； 重复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函数和以下几个函数组成： void initialization();初始化内存数据 void FIFO();FIFO先进先出算法； void LRU();LRU最久未使用算法； void LFU();LFU最近最久未使用算法：

流程图如下：

开始按要求产生320个随机数将随机数转换成页面用户内存容量i=4FIFO页面置换算法LRU页面置换算法LFU页面置换算法i=i+1Ni>32?Y结束

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

页面置换算法整体结构

开始内存数据初始化，物理块0320?Y结束

FIFO页面置换算法

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

开始内存数据初始化，物理块0320?Y结束 LRU页面置换算法

资料收集于网络，如有侵权 请联系网站删除

开始内存数据初始化，物理块050?Y比较物理块中页面在之前的50次调用中出现的次数，将页面p[n]调入使用最少的页面占用的物理块N按照LRU页面置换算法调入页面n++Nn>320?Y结束

LFU页面置换算法

2、设计说明及源代码

FIFO算法设计说明：按照所要求的产生随机指令序列，存放在order[320]这个数组中。 通过循环产生这些随机指令，每产生一条都要进行下列判断：是否和内存中即mem

_volume[4]中存放的页面相同，如果相同则不做任何操作，如果不相同，则产生缺页，相应的只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

缺页次数加一，按照fcfs将最先进入内存的页数淘汰，并将该页写到内存中去。

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

// 储存管理.cpp : 定义控制台应用程序的入口点。 //

#include \"stdafx.h\"

int _tmain(int argc, _TCHAR* argv[]) {

return 0; }

#include #include #include

#define N 5 //总共运行的次数 void main() {

int order[320],mem_volume[4]={100,100,100,100};

//使得mem_volume[]的值大于100>32，这样我们便可使其在开始就产生缺页 //定义add为缺页次数 sign作为标识符判断所调页数是否在内存中 int l=0,i=0,j,num=0,cx,sign=0,add=0;

float value=0,sum=0; //定义sum为缺页率 srand(time(NULL));

for(cx=0;cxwhile(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\ }

printf(\"\\n\");

printf(\"************************************************************\\n\"); printf(\"\\%d次的平均缺页数为%d\\n\\%d次的平均缺页率为%.3f%%\\n\

printf(\"\\n\"); }

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

源代码：

// 储存管理.cpp : 定义控制台应用程序的入口点。 //

#include \"stdafx.h\"

int _tmain(int argc, _TCHAR* argv[]) {

return 0; } 只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

#include #include #include #define N 5 int main(void) {

int order[320],mem_volume[4]={100,100,100,100}; int l=0,i=0,j,cx;

int num,temp=0,ex_chan=0,add=0; float value=0,sum=0; srand(time(NULL)); for(cx=0;cxorder[i]=rand()%320;

if((order[i]+1)/10==mem_volume[0])

; //如果所调页数同第一个内存块中页数相同，则执行空操作 else if((order[i]+1)/10==mem_volume[1]){ temp=mem_volume[1];

mem_volume[1]=mem_volume[0];

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

else if((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; } }

else if((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]) ;

else if(order[i]/10==mem_volume[1]){ temp=mem_volume[1];

mem_volume[1]=mem_volume[0]; mem_volume[0]=temp; }

else if(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; } }

else if(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])

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

;

else if(order[i]/10 == mem_volume[1]){ temp=mem_volume[1];

mem_volume[1]=mem_volume[0]; mem_volume[0]=temp; }

else if(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; } }

else if(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]) ;

else if(order[i]/10==mem_volume[1]){ temp=mem_volume[1];

mem_volume[1]=mem_volume[0]; mem_volume[0]=temp; }

else if(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; } }

else if(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\ }

printf(\"\\n\");

printf(\"**********************************************************\\n\");

printf(\"\\%d次的平均缺页数为%d\\n\\%d次的平均缺页率为%.3f%%\\n\

printf(\"\\n\"); } 只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

LFU页面置换算法设计说明：该算法主要是将最近时期页面使用最少的页面作为淘汰页。这里通过设立count[32]这个计数数组记录32页的调用次数，通过比较来确定要调出的页面。但如果没产生缺页就只需对所调页数对应的count值加1即可。

源代码：

// 储存管理.cpp : 定义控制台应用程序的入口点。 //

#include \"stdafx.h\"

int _tmain(int argc, _TCHAR* argv[]) {

return 0; }

#include #include #include

#define N 5 //定义运行次数 void main() {

int order[320],count[32]={0},compare[4]={0},mem_volume[4]={100,100,100,100}; //compare数组中存放了每次要比较的四个内存块中页数的调用次数 int l=0,i=0,j,k=0,cx=0;

int min,num=0,n,sign=0,add=0; float value=0,sum=0; srand(time(NULL)); for(cx=0;cxorder[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]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]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++){ k=mem_volume[num]; compare[num]=count[k]; if(compare[num]mem_volume[j]=(order[i]+1)/10; } } 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]){ n=order[i]/10; count[n]+=1; sign=1; } if(sign) sign=0; else { l++;

if(mem_volume[0]==100){

mem_volume[0]=(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]mem_volume[j]=(order[i]+1)/10; } } i++; }

value=l/320.0*100; add=add+l; sum=sum+value; }

printf(\"******************* LFU页面置换算法 *********************\\n\"); printf(\"******************* 最后一次指令序列 *********************\"); for(i=0;i<320;i++){ if(i%10==0)

printf(\"\\n\");

printf(\"%5d\ }

printf(\"\\n\");

printf(\"***************************************************************\\n\"); printf(\"\%d次的平均缺页数为%d\\n\%d次的平均缺页率为%.3f%%\

printf(\"\\n\"); }

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

五、实验数据及处理结果

FIFO页面置换算法运行结果：

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

LRU页面置换算法运行结果：

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

只供学习与交流

资料收集于网络，如有侵权 请联系网站删除

LFU页面置换算法运行结果：

只供学习与交流