[实验目的]
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。
[实验学时]
4学时
[实验类型]
设计性
[实验内容]
设计一个虚拟分页系统，并使用下述算法计算访问命中率（选择2种算法即可）。
1、最佳淘汰算法（OPT）
2、先进先出的算法（FIFO）
3、最近最久未使用算法（LRU）
命中率＝１－页面失效次数／页地址流长度
本实验的程序设计基本上按照实验内容进行。视能力可以在完整算法模拟和基本简要算法模拟其中二选一
1.完整算法要求
：即首先用srand( )和rand( )函数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。
（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。
在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第 0 条-第 9 条指令为第0页（对应虚存地址为[0，9]）
第10条-第19条指令为第1页（对应虚存地址为[10，19]）
………………………………
第310条-第319条指令为第31页（对应虚存地址为[310，319]）
按以上方式，用户指令可组成32页。
2.基本简要算法要求：忽略指令的地址映射过程，首先直接生成合法的页面访问序列号，并设置关键的数据结构-扩充页表，再针对不同的算法计算出相应的命中率。
[实验步骤]
一、虚拟存储系统
UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：页表、页框号、访问位、修改位、有效位、保护位等。
二、页面置换算法
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。该程序通过查找页表，得到该页所在外存的物理块号。如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。
常用的页面置换算法有
1、最佳置换算法（Optimal）
2、先进先出法（Fisrt In First Out）
3、最近最久未使用（Least Recently Used）
程序源代码：
#define TRUE1
#defineFALSE 0
#defineINVALID -1
#define NULL0
#define total_instruction 320 /*指令流长*/
#definetotal_vp 32 /*虚页长*/
#defineclear_period 50 /*清0周期*/
typedef struct /*页面结构*/
{
intpn,pfn,counter,time;
}
pl_type;
pl_typepl[total_vp]; /*页面结构数组*/
structpfc_struct
{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedefstruct pfc_struct pfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect, a[total_instruction];
intpage[total_instruction], offset[total_instruction];
int initialize(int);
intNUR(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("Wheni==%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 ands==%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("---%2dpage frames---\n",i);
NUR(i);
}
return 0;
}
int initialize(total_pf) /*初始化相关数据结构*/
inttotal_pf; /*用户进程的内存页面数*/
{int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;
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;
}
intNUR(total_pf) /*最近未使用算法*/
inttotal_pf;
{inti,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\n",1-(float)diseffect/320);
return 0;
}
#define TRUE1
#defineFALSE 0
#defineINVALID -1
#define NULL0
#define total_instruction 320 /*指令流长*/
#definetotal_vp 32 /*虚页长*/
#defineclear_period 50 /*清0周期*/
typedef struct /*页面结构*/
{
intpn,pfn,counter,time;
}
pl_type;
pl_typepl[total_vp]; /*页面结构数组*/
structpfc_struct
{ /*页面控制结构*/
int pn,pfn;
struct pfc_struct *next;
};
typedefstruct pfc_struct pfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect, a[total_instruction];
intpage[total_instruction], offset[total_instruction];
int initialize(int);
intNUR(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("Wheni==%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 ands==%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("---%2dpage frames---\n",i);
NUR(i);
}
return 0;
}
int initialize(total_pf) /*初始化相关数据结构*/
inttotal_pf; /*用户进程的内存页面数*/
{int i;
diseffect=0;
for(i=0;i<total_vp;i++)
{
pl[i].pn=i;
pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/
pl[i].counter=0;
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;
}
intNUR(total_pf) /*最近未使用算法*/
inttotal_pf;
{inti,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\n",1-(float)diseffect/320);
return 0;
}
运行后截图：
程序代码所表示的流程图：
一、 心得体会。
是用队列存储内存中的页面，队列的特点是先进先出，与该算法是一致的，所以每当发生缺页时，就从队头删除一页，而从队尾加入缺页。或者借助辅助数组time[mSIZE]记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面。所以fifo需要进行页面置换，即把内存中装入最早的那个页面淘汰，换入当前的页面。总的来说使用FIFO算法，总是淘汰最先进入内存的页面，即即选择在内存中驻留时间最久的页面予以淘汰。通过这个实验我体会到了编程的思路流程，结构流程图的作用。一个程序如果一开始计划的好，结构设计完善，才可能顺利进行。