存储管理常用页面置换算法模拟实验.docx
《存储管理常用页面置换算法模拟实验.docx》由会员分享，可在线阅读，更多相关《存储管理常用页面置换算法模拟实验.docx（25页珍藏版）》请在冰点文库上搜索。
存储管理常用页面置换算法模拟实验
实验目地
通过模拟实现请求页式存储管理地几种基本页面置换算法，了解虚拟存储技术地特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法地基本思想和实现过程，并比较它们地效率.文档收集自网络，仅用于个人学习
实验内容设计一个虚拟存储区和内存工作区，并使用下述算法计算访问命中率.
1、最佳淘汰算法（OPT）
2、先进先出地算法（FIFO）
3、最近最久未使用算法（LRU）
4、最不经常使用算法（LFU）
5、最近未使用算法（NUR）命中率＝１－页面失效次数／页地址流长度实验准备
本实验地程序设计基本上按照实验内容进行.即首先用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页.
实验指导
一、虚拟存储系统
UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间地分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页地存储管理方式.文档收集自网络，仅用于个人学习当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存.这种页面调入方式叫请求调页.文档收
集自网络，仅用于个人学习
为实现请求调页，核心配置了四种数据结构：
页表、页框号、访问位、修改位、有效位、保护位等.
二、页面置换算法
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序.该程序通过查找页表，得到该页所在外存地物理块号.如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表.如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表地修改位决定，然后将缺页调入，修改页表.利用修改后地页表，去形成所要访问数据地物理地址，再去访问内存数据.整个页面
地调入过程对用户是透明地.文档收集自网络，仅用于个人学习
常用地页面置换算法有
1、最佳置换算法（Optimal）
2、先进先出法（FisrtInFirstOut）
3、最近最久未使用（LeastRecentlyUsed）
4、最不经常使用法（LeastFrequentlyUsed）
5、最近未使用法（NoUsedRecently）
三、参考程序：
viewplaincopytoclipboardprint?
10·····20···30····40
50··60····70·····80···90·100
····110···120·130···140····150文档收集自网络，仅用于个人学习
#defineTRUE1
#defineFALSE0
#defineINVALID-1
/*指令流长*/
/*虚页长*/
/*清0周期*/
/*页面结构*/
/*页面结构数组*//*页面控制结构*/
#defineNULL0#definetotal_instruction320
#definetotal_vp32
#defineclear_period50
typedefstruct
{
intpn,pfn,counter,time;
}pl_type;
pl_typepl[total_vp];
structpfc_struct{
intpn,pfn;
structpfc_struct*next;
};
文档收集自网络，仅用于个人学习
typedefstructpfc_structpfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
intdiseffect,a[total_instruction];
intpage[total_instruction],offset[total_instruction];文档收集自网络，仅用于个人学习
intinitialize（int）;
intFIFO（int）;intLRU（int）;intLFU（int）;
intNUR（int）;
intOPT（int）;
intmain（）
{
ints,i,j;
srand（10*getpid（））;/*由于每次运行时进程号不同，故可用来作为初始化
随机数队列地“种子”*/文档收集自网络，仅用于个人学习
s=（float）319*rand（）/32767/32767/2+1;//for（i=0;iif（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],anumberwhichis:
%dands==%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个页面到32个页面*/
{
printf（"---%2dpageframes---\n",i）;
FIFO（i）;
LRU（i）;
LFU（i）;
NUR（i）;
OPT（i）;
}return0;
/*初始化相关数据结构*/文档收集自网络，仅用于个人学习
/*用户进程地内存页面数*/文档收集自网络，仅用于个
}
intinitialize（total_pf）
inttotal_pf;
人学习
for（i=0;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;/*按FIFO方式调新页面入内存页面*/freepf_head->next=NULL;
freepf_head->pn=page[i];
pl[page[i]].pfn=freepf_head->pfn;
if（busypf_tail==NULL）
/*free页面减少一个*/
busypf_head=busypf_tail=freepf_head;else{
busypf_tail->next=freepf_head;busypf_tail=freepf_head;
}
freepf_head=p;
}
}
printf（"FIFO:
%6.4f\n",1-（float）diseffect/320）;return0;
}
intLRU（total_pf）
inttotal_pf;
{
intmin,minj,i,j,present_time;initialize（total_pf）;
present_time=0;for（i=0;i{
if（pl[page[i]].pfn==INVALID）
{
diseffect++;
if（freepf_head==NULL）
{
/*最近最久未使用算法
*/
/*页面失效*/
/*无空闲页面*/
min=32767;
for（j=0;jif（min>pl[j].time&&pl[j].pfn!
=INV
{
/*找出time地最小值*/ALID）
min=pl[j].time;
minj=j;
}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=NULL;
//腾出一个单元
}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next;
//有空闲页面,改为有效
//减少一个free页面
}else
pl[page[i]].time=present_time;
收集自网络，仅用于个人学习
present_time++;
}
printf（"LRU:
%6.4f\n",1-（float）diseffect/320）;return0;
}
/*最近未使用算法*/
/*页面失效*/
/*无空闲页面*/
ALID）
intNUR（total_pf）
inttotal_pf;
{inti,j,dp,cont_flag,old_dp;
pfc_type*t;
initialize（total_pf）;
dp=0;
for（i=0;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!
=INV
cont_flag=FALSE;
else
{
dp++;
if（dp==total_vp）
dp=0;
if（dp==old_dp）
for（j=0;jpl[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;
}
elsepl[page[i]].counter=1;
if（i%clear_period==0）
for（j=0;jpl[j].counter=0;
}
printf（"NUR:
%6.4f\n",1-（float）diseffect/320）;return0;
}
intOPT（total_pf）/*最佳置换算法*/
inttotal_pf;
{inti,j,max,maxpage,d,dist[total_vp];
pfc_type*t;
initialize（total_pf）;
for（i=0;i1,i=%d\n",i）;
文档收集自网络，仅用于个人
{//printf（"InOPTfor//i=86;i=176;206;250;220,221;192,193,194;258;274,275,276,277,278;学习
if（pl[page[i]].pfn==INVALID）/*页面失效*/
{
diseffect++;
if（freepf_head==NULL）/*无空闲页面*/
{for（j=0;j文档收集自网络，仅用于个人学
if（pl[j].pfn!
=INVALID）dist[j]=32767;/*最大"距离"*/习
elsedist[j]=0;
d=1;
for（j=i+1;j{
if（pl[page[j]].pfn!
=INVALID）
dist[page[j]]=d;
d++;
}
max=-1;
for（j=0;jif（max{
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\n",1-（float）diseffect/320）;
return0;
}
intLFU（total_pf）/*最不经常使用置换法*/
inttotal_pf;
{
inti,j,min,minpage;
pfc_type*t;
initialize（total_pf）;for（i=0;i{if（pl[page[i]].pfn==INVALID）/*页面失效*/
{diseffect++;if（freepf_head==NULL）/*无空闲页面*/
{min=32767;for（j=0;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->next=NULL;
}
pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效
pl[page[i]].counter++;
freepf_head=freepf_head->next;//减少一个free页面
}
elsepl[page[i]].counter++;
}
printf（"LFU:
%6.4f\n",1-（float）diseffect/320）;
return0;
}
#defineTRUE1
#defineFALSE0#defineINVALID-1
/*指令流长*/
/*虚页长*//*清0周期*//*页面结构*/
/*页面结构数组*/
#defineNULL0#definetotal_instruction320
#definetotal_vp32
#defineclear_period50
typedefstruct
{
intpn,pfn,counter,time;
}pl_type;
pl_typepl[total_vp];
structpfc_struct{/*页面控制结构*/
intpn,pfn;
structpfc_struct*next;
};
typedefstructpfc_structpfc_type;
pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;文档收集自网络，仅用于个人学习intdiseffect,a[total_instruction];
intpage[total_instruction],offset[total_instruction];文档收集自网络，仅用于个人学习
intinitialize（int）;
intFIFO（int）;
intLRU（int）;
intLFU（int）;
intNUR（int）;
intOPT（int）;
intmain（）
{
ints,i,j;
srand（10*getpid（））;/*由于每次运行时进程号不同，故可用来作为初始化
随机数队列地“种子”*/文档收集自网络，仅用于个人学习
s=（float）319*rand（）/32767/32767/2+1;//for（i=0;i{
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],anumberwhichis:
%dands==%d\n",i,a[i+2],s）;文档收集自网络，仅
用于个人学习
}
for（i=0;ipage[i]=a[i]/10;offset[i]=a[i]%10;
for（i=4;i<=32;i++）/*用户内存工作区从4个页面到32个页面*/{
printf（"---%2dpageframes---\n",i）;
FIFO（i）;
LRU（i）;
LFU（i）;
NUR（i）;
OPT（i）;
}
return0;
intinitialize（total_pf）inttotal_pf;
/*初始化相关数据结构*/文档收集自网络，仅用于个人学习
/*用户进程地内存页面数*/文档收集自网络，仅用于个人学
}
习
{inti;
diseffect=0;
for（i=0;i{
pl[i].pn=i;
pl[i].pfn=INVALID;/*置页面控制结构中地页号，页面为空*/
pl[i].counter=0;
pl[i].time=-1;/*页面控制结构中地访问次数为0，时间为-1*/}for（i=0;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];
return0;
}
intFIFO（total_pf）
inttotal_pf;
{
inti,j;
pfc_type*p;initialize（total_pf）;
/*空页面队列地头指针为pfc[0]*/
/*先进先出算法*/
/*用户进程地内存页面数*/
/*初始化相关页面控制用数据结构*/
busypf_head=busypf_tail=NULL;/*忙页面队列头，队列尾链接*/for（i=0;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;/*按FIFO方式调新页面入内存页面*/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=fr
升级会员 