《操作系统》实验五：页面置换算法模拟

实验五. 请求页式存储管理的模拟 [实验内容]:

熟悉虚拟存储管理的各种页面置换算法，并编写模拟程序实现请求页式存储管理的页面置换算法----最近最久未使用算法（LRU），要求在每次产生置换时显示页面分配状态和缺页率。 [实验要求]：

1、运行给出的实验程序，查看执行情况，进而分析算法的执行过程，在理解FIFO页面置换算法和最近最久未使用算法（LRU）置换算法后，给出最佳置换算法的模拟程序实现，并集成到参考程序中。

2、执行2个页面置换模拟程序，分析缺页率的情况。最好页框数和访问序列长度可调节，在使用同一组访问序列数据的情况下，改变页框数并执行2个页面置换模拟程序，查看缺页率的变化。

3、在每次产生置换时要求显示分配状态和缺页率。程序的地址访问序列通过随机数产生，要求具有足够的长度。最好页框数和访问序列长度可调节。

实验的执行结果如下图所示（左下图为FIFO执行结果，右下图为LRU执行结果）：

程序源代码：

#include #include \#include #include #include #include #include #include

void initialize(); //初始化相关数据结构 void createps(); //随机生成访问序列

void displayinfo(); //显示当前状态及缺页情况 void fifo(); //先进先出算法

int findpage(); //查找页面是否在内存 void lru(); //最近最久未使用算法

int invalidcount = 0; // 缺页次数 int vpoint; //页面访问指针 int pageframe[10]; // 分配的页框

int pagehistory[10]; //记录页框中数据的访问历史 int rpoint; //页面替换指针

int inpflag; //缺页标志，0为不缺页，1为缺页

struct PageInfo //页面信息结构 {

int serial[100]; // 模拟的最大访问页面数，实际控制在20以上 int flag; // 标志位，0表示无页面访问数据 int diseffect; // 缺页次数 int total_pf; // 分配的页框数 int total_pn; // 访问页面序列长度 } pf_info;

//////////////////////////////////////////////////////////////////////// //初始化相关数据结构

void initialize() {

int i,pf;

inpflag=0; //缺页标志，0为不缺页，1为缺页 pf_info.diseffect =0; // 缺页次数

pf_info.flag =0; // 标志位，0表示无页面访问数据

printf(\请输入要分配的页框数：\自定义分配的页框数 scanf(\

pf_info.total_pf =pf;

for(i=0;i<100;i++) // 清空页面序列 {

pf_info.serial[i]=-1; }

}

/////////////////////////////////////////////////////////////////// // 随机生成访问序列 void createps(void ) {

int s,i,pn;

initialize(); //初始化相关数据结构

printf(\请输入要随机生成访问序列的长度：\自定义随机生成访问序列的长度 scanf(\

srand(rand()); //初始化随机数队列的\种子\

s=((float) rand() / 32767) * 50 + pn; // 随机产生页面序列长度 pf_info.total_pn = s;

for(i=0;i

pf_info.serial[i]=((float) rand() / 32767) * 16 ; //随机数的大小在0-15之间 } }

//////////////////////////////////////////////////////////////////////// // 显示当前状态及缺页情况 void displayinfo(void) {

int i,n;

if(vpoint==0) {

printf(\页面访问序列=============\\n\ for(i=0; i

printf(\

if ((i+1) % 10 ==0) printf(\每行显示10个 }

printf(\ }

printf(\访问= : 内存<\ for(n=0;n

if (pageframe[n] >=0)

printf(\ else

printf(\ }

printf(\

if(inpflag==1) //缺页标志，0为不缺页，1为缺页 {

printf(\缺页 \

printf(\缺页率%3.1f\ }

printf(\}

//////////////////////////////////////////////////////////////////////// // 查找页面是否在内存，1为在内存，0为不在即缺页 int findpage(int page) {

int n;

for(n=0;n

pagehistory[n] ++; // 访问历史加1 }

for(n=0;n

if (pageframe[n]==page ) {

inpflag=0 ; //inpflag缺页标志，0为不缺页，1为缺页 pagehistory[n]=0; //置访问历史为0 return 1; } }

inpflag=1; //页面不存在，缺页 return 0; }

//////////////////////////////////////////////////////////////////////// // FIFO页面置换算法 void fifo(void) {

int n,count,pstate;

rpoint=0; // 页面替换指针初始化为0 invalidcount = 0; // 缺页数初始化为0 createps(); // 随机生成访问序列 count=0; // 是否装满是所有的页框

for(n=0;n

pageframe[n]=-1; }

inpflag=0; //缺页标志，0为不缺页，1为缺页

for(vpoint=0;vpoint

pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存 if(count

if(pstate==0) // 页不存在则装入页面 {

pageframe[rpoint]=pf_info.serial[vpoint]; rpoint=(rpoint+1) % pf_info.total_pf; count++; } }

else // 正常缺页置换

{

if(pstate==0) // 页不存在则置换页面 {

pageframe[rpoint]=pf_info.serial[vpoint]; rpoint=(rpoint+1) % pf_info.total_pf; pf_info.diseffect++; // 缺页次数加1 } }

Sleep(10);

displayinfo(); // 显示当前状态 } // 置换算法循环结束 getch(); return; }

/////////////////////////////////////////////////////////////////// // LRU页面置换算法

void lru(void) {

int n,count,pstate,max;

rpoint=0; // 页面替换指针

invalidcount = 0; // 缺页次数初始化为0 createps(); // 随机生成访问序列 count=0; // 是否装满所有的页框 for(n=0;n

pageframe[n]=-1; // 清除页框信息 pagehistory[n]=0; // 清除页框历史 }

inpflag=0; //缺页标志，0为不缺页，1为缺页

for(vpoint=0;vpoint

pstate=findpage(pf_info.serial[vpoint]); //查找页面是否在内存 if(count

if(pstate==0) // 页不存在则装入页面 {

pageframe[rpoint]=pf_info.serial[vpoint]; //把要调入的页面放入一个空的页框里 rpoint=(rpoint+1) % pf_info.total_pf; count++; } }

else // 正常缺页置换 {

if(pstate==0)// 页不存在则置换页面 {

max=0;

for(n=1;n

if(pagehistory[n]>pagehistory[max])

本文来源：https://www.bwwdw.com/article/0g9f.html