[仿真实验]操作系统的内存管理
EmilMatthew(EmilMatthew@126.com)
摘要:
本文利用模拟实验，实现了操作系统内存管理中的FIFO策略及LRU策略。
关键词: 内存管理，FIFO，LRU
[Simulation Trial]Management Strategies of OS
EmilMatthew(EmilMatthew@126.com)
Abstract:
In this article , I implemented the simulation of OS management strategies , including FIFO strategies and LRU strategies.
Key Words: Memory Management , FIFO , LRU
1前言:
虚拟内存技术为操作系统在有限的内存空间内运行较大内存需求的程序实现了可能。而随之产生了相应的内存换页策略，如FIFO，LRU。这里，采用离散事件模拟的方式，实现了操作系统换页策略中的FIFO及LRU策略。
2模拟框架:
这个虚拟内存换页摸拟的离散系统可以看成事件驱动型。
while(已测页面数<要求测试页面数)
{
1）产生新页面。
2）根据策略，选择是否有页面要淘汰，如有淘汰，则更新更新。
}
计算策略效率值=1-换出页面数/请求页面数
测试的页面采用完全的随机走向，这一点上来说，可能与实际的程序运行有所差距。不
过，从摸拟管理策略的角度来说，是可以满足要求的。
3实验代码:
//LRU策略的实现较为冗杂。
//--main test for mem management stimulate program.--
#include <windows.h>
#include <stdio.h>
#include <time.h>
#include "Ulti.h"
#include "EQueue.h"
#include "MyAssert.h"
//---const variables---
#define TEST_PAGE_NUM 320
#define PAGE_POOL_SIZE 4
//--strategy Num--
#define FIFO 1
#define LRU 2
#define LFR 3
#define NUR 4
//--global variables--
int gRequestedPageNum;
int gPageStream[TEST_PAGE_NUM];
int gTestedNum;
int gStrategy;
int gMemUsedNum;
typedef struct
{
int times;
int pageNum;
}metaMem;
metaMem gPagePool[PAGE_POOL_SIZE];
PSingleRearSeqQueue gQueue;//for fifo strategy.
//--core functions in simulation--
int sFIFO();
int sLRU();
int sNUR();
int strStrtegyToInt(char* inS);
int preJudge();
//--ulti tested files--
FILE* inputFile;
FILE* outputFile;
char *inFileName="inputData.txt";
char *outFileName="outputData.txt";
int main()
{
int i;
int tmpRequireAddress;
char strStrategy[5];
int swapTimes;
int swapOutMemBlockID;
assertF((inputFile=fopen(inFileName,"rb"))!=NULL,"open inputfile error\n");
assertF((outputFile=fopen(outFileName,"wb"))!=NULL,"open outputfile error\n");
printf("oepn files success \n");
fscanf(inputFile,"strategy=%s\r\n",strStrategy);
//read in argument data.
printf("\nstrategy:%s.\n",strStrategy);
strStrategy[strlen(strStrategy)]='\0';
//change str strategy to int strategy.
gStrategy=strStrtegyToInt(strStrategy);
assertF(gStrategy>0&&gStrategy<5,"error gStrategy num");
//--init request address stream (at once change to page num)--
srand((unsigned int)time (NULL));
i=0;
while(i<TEST_PAGE_NUM)
{
tmpRequireAddress=(int)eRandom(320); //[0,319]
gPageStream[i]=tmpRequireAddress%16;
i++;
}
outputListArrInt(gPageStream,0,TEST_PAGE_NUM,outputFile);
//init loop variable
//the inidex for the request page num in simulation
gTestedNum=0;
//init the queue used in fifo.
gQueue=createNullSingleRearSeqQueue();
//note the swap times
swapTimes=0;
//indicate the mem used num
gMemUsedNum=0;
//init mem pool
for(i=0;i<PAGE_POOL_SIZE;i++)
{
gPagePool[i].times=0;
gPagePool[i].pageNum=-1;
i++;
}
//--main part of simulation--
while(gTestedNum<TEST_PAGE_NUM)
{
//get new page num
gRequestedPageNum=gPageStream[gTestedNum];
swapOutMemBlockID=-1;
switch(gStrategy)
{
case FIFO: swapOutMemBlockID=sFIFO();
break;
case LRU: swapOutMemBlockID=sLRU();
break;
case NUR: swapOutMemBlockID=sNUR();
break;
default:
printf("error index passin StragetyFun.\n");
return -1;
break;
}
if(swapOutMemBlockID!=-1)
{
//show swap info.
fprintf(stdout,"swap out->page num:%d use times:%d\r\n",gPagePool[swapOutMemBlockID].pageNum,gPagePool[swapOutMemBlockID].times);
fprintf(outputFile,"swap out->page num:%d use times:%d\r\n",gPagePool[swapOutMemBlockID].pageNum,gPagePool[swapOutMemBlockID].times);
fprintf(stdout,"swap in->page num:%d \r\n",gRequestedPageNum);
fprintf(outputFile,"swap in->page num:%d \r\n\r\n",gRequestedPageNum);
//updating
gPagePool[swapOutMemBlockID].pageNum=gRequestedPageNum;
gPagePool[swapOutMemBlockID].times=1;
swapTimes++;
}
gTestedNum++;
}
fprintf(stdout,"stragety:%s effciency:%f",strStrategy,1-(float)swapTimes/TEST_PAGE_NUM);
fprintf(outputFile,"stragety:%s effciency:%f",strStrategy,1-(float)swapTimes/TEST_PAGE_NUM);
return 0;
}
int strStrtegyToInt(char* inS)
{
if(strcmp(inS,"FIFO")==0)
return FIFO;
else if(strcmp(inS,"LRU")==0)
return LRU;
else if(strcmp(inS,"LFR")==0)
return LFR;
else if(strcmp(inS,"NUR")==0)
return NUR;
else
{
printf("in foundStrategy,pass in Strategy is illegal!\n");
return -1;
}
}
int sFIFO()
{
int reBlockID=-1;
int i;
if(gMemUsedNum<PAGE_POOL_SIZE)
{
for(i=0;i<gMemUsedNum;i++)
if(gPagePool[i].pageNum==gRequestedPageNum)
break;
if(i==gMemUsedNum)
{
enQueue(gQueue,gMemUsedNum);
gPagePool[gMemUsedNum].pageNum=gRequestedPageNum;
gPagePool[gMemUsedNum].times=1;
fprintf(stdout,"swap in->page num:%d \r\n",gRequestedPageNum);
fprintf(outputFile,"swap in->page num:%d \r\n\r\n",gRequestedPageNum);
gMemUsedNum++;
}
}
else if(preJudge()==-1)//detect whether page has been used in the mem area.
{
//get swap out mem block id
reBlockID=deQueue(gQueue);
//insert to the end of the queue.
enQueue(gQueue,reBlockID);
}
return reBlockID;
}
int sLRU()
{
int reBlockID=-1;
int i,maxIndex;
if(gMemUsedNum<PAGE_POOL_SIZE)
{
for(i=0;i<gMemUsedNum;i++)
if(gPagePool[i].pageNum==gRequestedPageNum)
break;
if(i<gMemUsedNum)
{
gPagePool[i].times=1;
reBlockID=i;
for(i=0;i<gMemUsedNum;i++)
if(i!=reBlockID)
gPagePool[i].times++;
reBlockID=-1;
}
else
{
for(i=0;i<gMemUsedNum;i++)
gPagePool[i].times++;
gPagePool[gMemUsedNum].pageNum=gRequestedPageNum;
gPagePool[gMemUsedNum].times=1;
fprintf(stdout,"swap in->page num:%d \r\n",gRequestedPageNum);
fprintf(outputFile,"swap in->page num:%d \r\n\r\n",gRequestedPageNum);
gMemUsedNum++; //next mem sloo
}
}
else if((reBlockID=preJudge())!=-1)//detect whether page has been used in the mem area.
{
gPagePool[reBlockID].times=1;
for(i=0;i<PAGE_POOL_SIZE;i++)
{
if(i!=reBlockID)
gPagePool[i].times++;
}
reBlockID=-1;
}
else
{
//select the min times of the pages in the mems.
maxIndex=0;
for(i=1;i<PAGE_POOL_SIZE;i++)
if(gPagePool[i].times>gPagePool[maxIndex].times)
maxIndex=i;
reBlockID=maxIndex;
//use time add 1
for(i=0;i<PAGE_POOL_SIZE;i++)
{
if(i!=maxIndex)
gPagePool[i].times++;
}
}
return reBlockID;
}
int preJudge()
{
int i;
for(i=0;i<PAGE_POOL_SIZE;i++)
if(gPagePool[i].pageNum==gRequestedPageNum)
break;
if(i<PAGE_POOL_SIZE)
return i; //block id
else
return -1;
}
4实验结果:
在请求页面有320页，最大页号为20时：
4.1内存区域大小为4页时的测试结果:
实验次数
1
2
3
AVG
FIFO 效率
0.2375
0.3031
0.2875
0.276033
LRU 效率
0.3094
0.2344
0.2781
0.273967
4.2内存区域大小为8页时的测试结果:
内存区域大小为8页，请求页面有320页的测试结果:
实验次数
1
2
3
AVG
FIFO 效率
0.5438
0.5156
0.4906
0.516667
LRU 效率
0.5531
0.5063
0.5094
0.522933
可以看到，内存区域增大时，LRU的效率偏高。
参考文献:
[1] 何炎祥,李飞,李宁,计算机操作系统,清华大学出版社,2002. 程序完成日:06/04/30
文章完成日:06/05/01
附录:
1测试程序下载:
http://emilmatthew.51.net/EmilPapers/06_16OSMemMag/code.rar
若直接点击无法下载(或浏览)，请将下载(或浏览)的超链接粘接至浏览器地址栏后按回车.若不出意外，此时应能下载。
若下载中出现了问题，请参考:
http://blog.csdn.net/emilmatthew/archive/2006/04/08/655612.aspx
