页面置换算法模拟实验报告

实验编号4 名称页面置换算法模拟

实验目的

通过请求页式存储管理中页面置换算法模拟设计，以便:

1、 了解虚拟存储技术的特点

2、 掌握请求页式存储管理中页面置换算法

实验内容与步骤

设计一个虚拟存储区和内存工作区，并使用

FIFO 和LRU 算法计算访问命中率。

＜程序设计＞

先用srand()函数和rand()函数定义和产生指令序列， 然后将指令序列变换成相应的页

地址流，并针对不同的算法计算相应的命中率。

＜程序1＞

#in clude //Windows 版，随机函数需要， GetCurre ntProcessld() 需^< 〃#include

//L in ux

版，随机函数srand 和rand 需要

#in clude

//pri ntf()

需^<

#defi ne TRUE 1 #defi ne FALSE 0

#define INVALID -1 #defi ne NULL 0 #defi ne total i nstruction 320

//共320条指令

#defi ne total_vp 32 //虚存页共32页 #defi ne clear_period 50 //访问次数清零周期

typedef struct{〃 定义页表结构类型(页面映射表 PMT

int pn, pfn, counter, time;// 页号、页框号(块号)、一个周期内访问该页面的次数、

访问时间

}PMT; PMT pmt[32];

typedef struct pfc_struct｛〃页面控制结构

int pn, pfn;

struct

pfc_struct

*n ext;

}pfc type;

pfc_type pfc[32];

pfc_type *freepf_head,*busypf_head,*busypf_tail;〃空闲页头指针，忙页头指针，忙页

尾指针

int NoPageCou nt; // 缺页次数

指令流数组

int a[total i nstructio n];//

int page[total_ in structi on], offset[total_ in

structi on ];//

每条指令的页和页内偏移

void in itialize( int );

void

FIFO( int );//

先进先出

void LRU( int );// 最近最久未使用

void NRU( int );// 最近最不经常使用

/****************************************************************************

main ()

*****************************************************************************

void mai n(){

int i,s;

//sran d(1O*getpid());〃用进程号作为初始化随机数队列的种子〃Li nux 版sran d(10*GetCurre ntProcessld());〃用进程号作为初始化随机数的种子//Win dows

s=rand()%320;〃在[0，319]的指令地址之间随机选取一起点m

for(i=0;i

n;i+=4){//

产生指令队列

if(s<0||s>319){

printf("when i==%d,error,s==%d\n",i,s);

exit(0);

}

a[i]=s;// 任意选一指令访问点m (将随机数作为指令地址

a[i+2]=rand()%(s+2);〃在[0，m+1]的前地址之间随机选取一地址，记为m'

a[i+3]=a[i+2]+1;〃顺序执行一条指令

取一起点

s = a[i+2] + (in t)ra nd()%(320-a[i+2]);〃在[m'，319]的指令地址之间随机选

if((a[i+2]>318)||(s>319)) prin tf("a[%d+2,a number which is:%d and s=%d\n",i,a[i+2],s);

}

for(i=0;i

page[i]=a[i]/10;

offset[i]=a[i]%10;

}

for(i=4;i<=32;i++){// 内存块分别为4块、5块、..H 块时的命中率

prin tf("%2d page frames"」)；

FIFO(i);// 计算用FIFO置换时，有i个内存块时的命中率

LRU(i);// 最近最久未使用

NRU(i);//最近最不经常使用

prin tf("\n ”);

} }]

/***************************************************************************

in itialize()

形参：内存块数

功能：初始化

*****************************************************************************/

void initialize(int total_pf)// 初始化相关数据结构，形参total_pf 是用户进程的内存页面数

{

int i;

NoPageCount=O;〃缺页次数，初始化为0

for(i=0;i

pmt[i].p n=i;〃填逻辑页号

pmt[i].pfn=INVALID;〃物理页面号为-1

pmt[i].cou nter=0;〃置页面控制结构中的访问次数为0

pm t[i] .time=-1; // 置页面控制结构中的时间为-1 }

for(i=0;i

pfc[i]. next=&pfc[i+1];

pfc[i].pfn=i;

二}

pfc[total_pf-1]. next=NULL;

pfc[total_pf-1].pfn=total_pf-1;

freepf_head=&pfc[0];〃页面队列的头指针为pfc[0]

/*****************************************************************************

FIFO 算法

形参：内存块数输出：命中率

*****************************************************************************/