页面置换算法实验(内含完整代码).doc
《页面置换算法实验(内含完整代码).doc》由会员分享，可在线阅读，更多相关《页面置换算法实验(内含完整代码).doc（10页珍藏版）》请在冰点文库上搜索。
实验二存储管理
一、实验目的
通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特 点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程， 并比较它们的效率。
二、实验内容
基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。
1、最佳淘汰算法（OPT）
2、先进先出的算法（FIFO）
3、最近最久未使用算法（LRU）
4、简单时钟（钟表）算法（CLOCK）
命中率＝１－页面失效次数／页地址流（序列）长度
三、实验原理简述
UNIX中，为了提高内存利用率，提供了内外存进程对换机制；内存空间的分配和回收均以页为单位进行；一个进程只需将其一部分（段或页）调入内存便可运行；还支持请求调页的存储管理方式。
当进程在运行中需要访问某部分程序和数据时，发现其所在页面不在内存，就立即提出请求（向CPU发出缺中断），由系统将其所需页面调入内存。
这种页面调入方式叫请求调页。
为实现请求调页，核心配置了四种数据结构：
页表、页帧（框）号、访问位、修改位、有效位、保护位等。
当CPU接收到缺页中断信号，中断处理程序先保存现场，分析中断原因，转入缺页中断处理程序。
该程序通过查找页表，得到该页所在外存的物理块号。
如果此时内存未满，能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。
如果内存已满，则须按某种置换算法从内存中选出一页准备换出，是否重新写盘由页表的修改位决定，然后将缺页调入，修改页表。
利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。
整个页面的调入过程对用户是透明的。
四、算法描述
本实验的程序设计基本上按照实验内容进行。
即使用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页。
五、算法实现与分析
1.常量及变量
#definetotal_instruction320//指令流长
#definetotal_vp32//虚页长
#defineclear_period50//清周期
pfc_typepfc[total_vp], //主存区页面控制结构数组
pfc_type*freepf_head, //主存区页面控制结构的空闲页面头指针
pfc_type*busypf_head, //主存区页面控制结构的忙页面头指针
pfc_type*busypf_tail; //主存区页面控制结构的忙页面尾指针
intdiseffect; //页错误计数器，初次把页面载入主存时也当做页错误
pl_typepl[total_vp];//页面结构数组
2.数据结构
typedefstruct//页面结构
{
intpn, //页面序号
pfn, //页面所在内存区的帧号
counter, //单位时间内访问次数
time; //上次访问的时间
}pl_type;
structpfc_struct{//页面控制结构，模拟内存中的页集
intpn, //页面号
pfn; //内存区页面的帧号
structpfc_struct*next; //页面指针，用于维护内存缓冲区的链式结构
};
3.函数定义
intinitialize（int）; //初始化页面结构数组和页面控制结构数组
intFIFO（int）; //先进先出算法
intLRU（int）; //最近最久未使用算法
intOPT（int）; //最佳置换算法
intCLOCK（int）; //简单时钟（钟表）算法
六、实验结果分析
实验数据结果：
------------随机产生指令流------------
2572583738
226227109110
184185164165
1661675960
310311135136
148149105106
240241121122
1241255051
315316308309
312313299300
315316284285
284285272273
318319216217
310311266267
318319127128
1291305253
53544849
1301316263
159160107108
206207130131
167168123124
2722732324
1231243233
303304163164
206207134135
269270123124
177178124125
2442455455
686956
165166144145
2702717576
88896566
69703132
56574041
1891907374
92935051
92937778
88896263
1251267172
255256125126
2892909798
235236163164
2402412930
1581598081
280281263264
3123135859
2262277879
121122108109
2022033233
42431819
1531546768
2922936364
2642655455
2692704041
296297295296
318319269270
278279214215
222223186187
2202213031
2682693334
226227117118
211212170171
3133147778
2482493435
2322332526
82835960
61622324
1681692425
259260239240
318319275276
2832847475
244245144145
2442458687
120121115116
238239209210
275276215216
284285214215
285286186187
208209162163
2382394142
--------------------------------------
--不同页面工作区各种替换策略的命中率表--
PageFIFOLRUOPTCLOCK
40.5500.5590.6690.550
50.5660.5720.7000.572
60.5780.5940.7220.578
70.5910.6030.7410.597
80.6310.6280.7560.637
90.6370.6560.7720.650
100.6410.6690.7870.653
110.6560.6780.8000.666
120.6880.6840.8130.672
130.7030.6970.8220.697
140.7130.7130.8310.719
150.7220.7280.8410.722
160.7310.7470.8500.741
170.7440.7720.8560.747
180.7690.7780.8630.769
190.7780.7870.8690.778
200.7810.7970.8750.794
210.7870.8000.8810.806
220.8160.8090.8870.809
230.8220.8220.8910.822
240.8380.8310.8940.838
250.8440.8470.8970.841
260.8470.8560.9000.856
270.8470.8690.9000.859
280.8560.8780.9000.872
290.8590.8840.9000.878
300.8810.8910.9000.891
310.8970.8970.9000.897
320.9000.9000.9000.900
请按任意键继续...
结果分析：
理论上，四种替换算法的命中率由高到底排列应该是OPT>LRU>CLOCK>FIFO。
实际上，从实验数据观测得到，存在这种由高到低的趋势，由page=4时可以观测到，但是效果不是很明显。
效果不明显的原因：
推测与指令流的产生方式有关系。
因为指令流的产生方式要能体现局部性原理，所以该指令流产生设计为：
50%的指令是顺序执的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分。
但是这样的指令流设计方式能否最佳地体现局部性原理，这还有待验证。
同时，估计和指令数量有关系。
因为320条指令太少了，通常一个稍大点的程序都几千行指令了。
而且由于随即数产生具有一定的波动性，该命中率的计算也有一定的波动性。
所以会有局部的实验数据与理论不符。
改进方法是多次实验取平均值，这样可以减小波动，让实验数据更加平滑。
唯一显著的是OPT算法的命中率与其他3个调度算法保持了比较大的差距。
例如在page=26时，OPT算法就能达到0.9的命中率了。
到后期，由于page越来越大，因此越来越容易命中，因此各替换算法的命中率差距变小了。
这由最后几行命中率相似可以看出。
七、实验总结
这次实验其实不一定要在linux操作系统下做，在windows操作系统一样可以实现，只要把头文件稍作修改即可。
为了保险起见，我在2个操作系统下都编译过，都没问题。
在windows操作系统，要屏蔽//#include这句话，在linux操作系统下则启用。
此次实验借助于老师提供的主函数main模板，只需要写FIFO，LRU，OPT,CLOCK等4个替换算法，所以阻力没那么大。
每个替换算法必须弄懂其中的细节，写起来才得心应手。
一开始做这个实验时，首先是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺点和相互之间衍生互补关系。
这四个算法中，难以实现的是LRU算法，因为它涉及到访问时间的计算，而且它的开销也比较大。
OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。
而FIFO和CLOCK实现起来比较容易，FIFO算法的实现和CLOCK算法的实现很相似，FIFO可视为CLOCK的退化版。
我先写了CLOCK算法，再删去一些约束条件就退化为FIFO算法。
这就是两者的相同之处。
理论上，CLOCK算法需要维持一个循环的主存缓冲区，需要一个循环队列去实现，并且，FIFO算法保持先进先出，因此需要一个先进先出队列。
但是，我实现这两个算法只用到了单向链表的数据结构，剩下的由其中的指针去把握了。
因此，必须对指针使用有敏锐的感觉。
八、程序源码（在两个系统上都通过）
#include
#include
#include//在window操作系统下要屏蔽此条指令
#include
#ifndef_UNISTD_H
#define_UNISTD_H
#include
#include
#endif
#defineTRUE1
#defineFALSE0
#defineINVALID-1
#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; //页错误计数器，初次把页面载入主存时也当做页错误
inta[total_instruction]; //随即指令流数组
intpage[total_instruction]; //指令对应的页面号
intoffset[total_instruction]; //指令所在页面中的偏移量
intinitialize（int）; //初始化页面结构数组和页面控制结构数组
intFIFO（int）; //先进先出算法
intLRU（int）; //最近最久未使用算法
intOPT（int）; //最佳置换算法
intCLOCK（int）; //简单时钟（钟表）算法
intmain（）
{
ints; //随机数
int i;
srand（10*getpid（））;/*每次运行时进程号不同，用来作为初始化随机数队列的"种子"*/
s=（int）（（float）（total_instruction-1）*（rand（）/（RAND_MAX+1.0）））;
printf（"\n------------随机产生指令流------------\n"）;
for（i=0;i{
a[i]=s;//任选一指令访问点m
a[i+1]=a[i]+1;//顺序执行一条指令
a[i+2]=（int）（（float）a[i]*（rand（）/（RAND_MAX+1.0）））;//执行前地址指令m'
a[i+3]=a[i+2]+1;//顺序执行一条指令
printf（"%6d%6d%6d%6d\n",a[i],a[i+1],a[i+2],a[i+3]）;
s=（int）（（float）（（total_instruction-1）-a[i+2]）*（rand（）/（RAND_MAX+1.0）））+a[i+2];
}
printf（"--------------------------------------\n"）;
for（i=0;i{
page[i]=a[i]/10;
offset[i]=a[i]%10;
}
printf（"\n--不同页面工作区各种替换策略的命中率表--\n"）;
printf（"Page\tFIFO\tLRU\tOPT\tCLOCK\n"）;
for（i=4;i<=32;i++）//用户内存工作区从个页面到个页面
{
printf（"%2d\t",i）;
FIFO（i）;
LRU（i）;
OPT（i）;
CLOCK（i）;
printf（"\n"）;
}
return0;
}
//初始化页面结构数组和页面控制结构数组
//total_pf;用户进程的内存页面数
intinitialize（inttotal_pf）
{
inti;
diseffect=0;
for（i=0;i {
pl[i].pn=i;
pl[i].pfn=INVALID;//置页面所在主存区的帧号为-1.表示该页不在主存中
pl[i].counter=0; //置页面结构中的访问次数为
pl[i].time=-1; //置页面结构中的上次访问的时间为-1
}
for（i=0;i {
pfc[i].next=&pfc[i+1]; //建立pfc[i-1]和pfc[i]之间的链接
pfc[i].pfn=i; //初始化主存区页面的帧号
}
pfc[total_pf-1].next=NULL;
pfc[total_pf-1].pfn=total_pf-1;
freepf_head=&pfc[0]; //主存区页面控制结构的空闲页面头指针指向pfc[0]
return0;
}
//最近最久未使用算法
//inttotal_pf;用户进程的内存页面数
intLRU（inttotal_pf）
{
intMinT; //最小的访问时间，即很久没被访问过
intMinPn; //拥有最小的访问时间的页的页号
inti,j;
intCurrentTime; //系统当前时间
initialize（total_
升级会员 