存储管理常用页面置换算法模拟
实验项目名称 实验七:存储管理常用页面置换算法模拟
实验目的 通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
实验要求 1、理解页式存储管理页面置换算法。
2、比较个算法的特性。
实验原理 1)通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成:
A:50%的指令是顺序执行的
B:25%的指令是均匀分布在前地址部分
C: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)将指令序列变换为页地址流
设:页面大小为1K;
用户内存容量4页到32页;
用户虚存容量为32K。
。
实验步骤 一、虚拟存储系统
二、页面置换算法
常用的页面置换算法有
1、最佳置换算法(Optimal)
2、先进先出法(Fisrt In First Out)
3、最近最久未使用(Least Recently Used)
4、最不经常使用法(Least Frequently Used)
5、最近未使用法(No Used Recently)
实验内容 /***************************************************************************/
#define TRUE 1
#define FALSE 0
#define INVALID -1
#define NULL 0
#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清0周期*/
typedef struct /*页面结构*/
{
int pn,pfn,counter,time;
}pl_type;
pl_type pl[total_vp]; /*页面结构数组*/
struct pfc_struct{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
int initialize(int);
int FIFO(int);
int LRU(int);
int LFU(int);
int NUR(int);
int OPT(int);
int main( )
{
int s,i,j;
srand(10*getpid()); /*由于每次运行时进程号不同,故可用来作为初始化随机数队列的“种子”*/
s=(float)319*rand( )/32767/32767/2+1; //
for(i=0;i<total_instruction;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+1]=a[i]+1; /*顺序执行一条指令*/
a[i+2]=(float)a[i]*rand( )/32767/32767/2; /*执行前地址指令m' */
a[i+3]=a[i+2]+1; /*顺序执行一条指令*/
s=(float)(318-a[i+2])*rand( )/32767/32767/2+a[i+2]+2;
if((a[i+2]>318)||(s>319))
printf("a[%d+2],a number which is :%d and s==%d\n",i,a[i+2],s);
}
for (i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/
{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/
{
printf("---%2d page frames---\n",i);
FIFO(i);
LRU(i);
LFU(i);
NUR(i);
OPT(i);
}
return 0;
}
int initialize(total_pf) /*初始化相关数据结构*/
int total_pf; /*用户进程的内存页面数*/
{int i;
diseffect=0;
751com.cn
pl[i].time=-1; /*页面控制结构中的访问次数为0,时间为-1*/
}
for(i=0;i<total_pf-1;i++)
{
pfc[i].next=&pfc[i+1];
pfc[i].pfn=i;
} /*建立pfc[i-1]和pfc[i]之间的链接*/
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; /*空页面队列的头指针为pfc[0]*/
return 0;
}
/***************************先进先出算法*******************************/
int FIFO(total_pf)
int total_pf; /*用户进程的内存页面数*/
{
int i,j;178