一、实验目的
1、了解虚拟存储技术的特点，掌握请求页式存储管理的主要页面置换算法原理。
2、掌握请求页式存储管理中页面置换算法的模拟设计方法。
二、实验内容
设计一个虚拟存储区和内存工作区，并使用下述方法计算访问命中率。
①先进先出的算法（FIFO）：最先进来的页先出去了啊。该算法是基于最早进入主存器的页未被使用的可能性要大。但如果一页要经常的被访问，它在一定的时间内又会被重新的调入。这会增加磁盘启动的次数。
②最近最少少使用算法(LRU)：是基于程序使用的局部性原理。我们规定，队首元素为最近最久未使用的页。所以当发生缺页中断时，将该队首的页调出去。
③最佳淘汰算法(OPT):选淘汰最不常用的页地址。
④最少访问页面算法(LFR)：在过去一段时间里被访问次数多的页可能是进常需要用的页，所以应调出被访问次数少的页。
⑤最近最不经常使用算法(NUR)： 又称为
简单的CLCOK
算法，每页设置一个访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列；当某个页面被访问时，其访问位置1。淘汰时，检查其访问位，如果是0，就换出；若为1，则重新将它置0；再按FIFO算法检查下一个页面，到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首再去检查第一个页面。
命中率= 1 – 页面失效次数 / 页地址流长度
三、实验指导
1、通过随机数产生一个指令序列，共320条指令。指令的地址按下述原则生成：
①50％的指令是顺序执行的；
②25％的指令是均匀分布在前地址部分；
③25％的指令是均匀分布在后地址部分。
具体的实施方法是：
①在[1，319]指令地址之间随机选取一起点m；
②顺序执行一条指令，即执行地址为m十1的指令；
③在前地址［0，m十1］中随机选取一条指令并执行，该指令的地址为 m’；
④顺序执行一条指令，其地址为m‘＋1；
⑤在后地址[m’＋2，319]中随机选取一条指令并执行；
③重复上述步骤①～⑤，直到执行320次指令。
2、将指令序列变换成为页地址流
设：①页面大小为IK；
②用户内存容量为4页到32页；
③用户虚存容量为32K。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方
式为：
第0条～第9条指令为第0页（对应虚存地址为［0，9］）；
第10条～第19条指令为第1页（对应虚存地址为[10，19]）；
第 310条～第 319条指令为第 31页（对应虚存地址为[310，319]）。
按以上方式，用户指令可组成32页。
3、按实验要求计算并输出各种算法在不同内存容量下的命中率。
在本实验中,页地址流长度为320,页面失效次数为每次访问相应指令时,该指令所对应的页不在内存的次数。
先进先出的算法（FIFO）
//void FIFO(total_pf) /*FIFO（First In First Out) ALOGRITHM*/
//int total_pf; /*用户进程的内存页面数*/
void FIFO(int total_pf)
//int total_pf;
{
int i;
pfc_type *p;
initialize(total_pf);
busypf_head=busypf_tail=NULL;
for (i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID)
{diseffect+=1;
if (freepf_head==NULL)
{
p=busypf_head->next;
pl[busypf_head->pn].pfn=INVALID;
freepf_head=busypf_head;
freepf_head->next=NULL;
busypf_head=p;
}
p=freepf_head->next;
freepf_head->next=NULL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if (busypf_tail==NULL)
busypf_head=busypf_tail=freepf_head;
else
{
busypf_tail->next=freepf_head;
busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf(" FIFO:%6.4f",1-(float)diseffect/320);
}
最近最少少使用算法(LRU)
void LRU(int total_pf)
//int total_pf;
{
int min,minj,i,j,present_time;
initialize(total_pf);
present_time=0;
for(i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn=INVALID)
{
diseffect++;
if (freepf_head==NULL)
{
min=32767;
for(j=0;j<total_vp;j++)
if (min>pl[j].time && pl[j].pfn!=INVALID)
{
min=pl[j].time;
minj=j;
}
freepf_head=&pfc[pl[minj].pfn];
pl[min].pfn=INVALID;
pl[min].time=-1;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
pl[page[i]].time=present_time;
freepf_head=freepf_head->next;
}
else
pl[page[i]].time=present_time;
present_time++;
}
printf(" LRU:%6.4f",1-(float)diseffect/320);
}
最佳淘汰算法(OPT):选淘汰最不常用的页地址
void OPT(int total_pf) /*OPT（Optional Replacement) ALOGRITHM*/
//int total_pf;
{
int i,j,max,maxpage,d,dist[total_vp];
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID)
{
diseffect++;
if (freepf_head==NULL)
{
for(j=0;j<total_vp;j++)
if (pl[j].pfn!=INVALID)
dist[j]=32767;
else
dist[j]=0;
d=1;
for(j=i+1;j<total_instruction;j++)
{
if (pl[page[j]].pfn!=INVALID)
dist[page[j]]=d;
d++;
}
max=-1;
for(j=0;j<total_vp;j++)
if (max<dist[j])
{
max=dist[j];
maxpage=j;
}
freepf_head=&pfc[pl[maxpage].pfn];
freepf_head->next=NULL;
pl[maxpage].pfn=INVALID;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
}
printf(" OPT:%6.4f",1-(float)diseffect/320);
}
最少访问页面算法(LFU)
void LFU(int total_pf) /*LFU（leat Frequently Used) ALOGRITHM*/
//int total_pf;
{
int i,j,min,minpage;
pfc_type *t;
initialize(total_pf);
for(i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID)
{
diseffect++;
if (freepf_head==NULL)
{
min=32767;
for(j=0;j<total_vp;j++)
{
if (min>pl[j].counter&&pl[j].pfn!=INVALID)
{
min=pl[j].counter;
minpage=j;
}
pl[j].counter=0;
}
freepf_head=&pfc[pl[minpage].pfn];
pl[minpage].pfn=INVALID;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter++;
}
}
printf(" LFU:%6.4f",1-(float)diseffect/320);
}
最近最不经常使用算法(NUR)
void NUR(int total_pf)
//int total_pf;
{
int i,j,dp,cont_flag,old_dp;
// pfc_type *t;
initialize(total_pf);
dp=0;
for(i=0;i<total_instruction;i++)
{
if (pl[page[i]].pfn==INVALID) /*页面失效*/
{
diseffect++;
if (freepf_head==NULL) /*无空闲页面*/
{
cont_flag=TRUE;
old_dp=dp;
while(cont_flag)
if (pl[dp].counter==0&&pl[dp].pfn!=INVALID)
cont_flag=FALSE;
else
{
dp++;
if (dp==total_vp)
dp=0;
if (dp==old_dp)
for (j=0;j<total_vp;j++)
pl[j].counter=0;
}
freepf_head=&pfc[pl[dp].pfn];
pl[dp].pfn=INVALID;
freepf_head->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;
freepf_head=freepf_head->next;
}
else
pl[page[i]].counter=1;
if (i%clear_period==0)
for(j=0;j<total_vp;j++)
pl[j].counter=0;
}
printf(" NUR:%6.4f",1-(float)diseffect/320);
}
结果：
