页面置换算法实验报告

一、实验目的通过模拟实现请求页式存储管理的几种基本页面置换算法，了解虚拟存储技术的特点，掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程，并比较它们的效率。二、实验内容基于一个虚拟存储区和内存工作区，设计下述算法并计算访问命中率。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]的指令地址之间随机选取一起点mB：顺序执行一条指令，即执行地址为m+1的指令C：在前地址[0,m+1]中随机选取一条指令并执行，该指令的地址为m’D：顺序执行一条指令，其地址为m’+1E：在后地址[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);//简单时钟(钟表)算法六、实验结果分析理论上，四种替换算法的命中率由高到底排列应该是OPTLRUCLOCKFIFO。实际上，从实验数据观测得到，存在这种由高到低的趋势，由page=4时可以观测到，但是效果不是很明显。效果不明显的原因：推测与指令流的产生方式有关系。因为指令流的产生方式要能体现局部性原理，所以该指令流产生设计为：50%的指令是顺序执的，25%的指令是均匀分布在前地址部分，25%的指令是均匀分布在后地址部分。但是这样的指令流设计方式能否最佳地体现局部性原理，这还有待验证。同时，估计和指令数量有关系。因为320条指令太少了，通常一个稍大点的程序都几千行指令了。而且由于随即数产生具有一定的波动性，该命中率的计算也有一定的波动性。所以会有局部的实验数据与理论不符。改进方法是多次实验取平均值，这样可以减小波动，让实验数据更加平滑。唯一显著的是OPT算法的命中率与其他3个调度算法保持了比较大的差距。例如在page=26时，OPT算法就能达到0.9的命中率了。到后期，由于page越来越大，因此越来越容易命中，因此各替换算法的命中率差距变小了。这由最后几行命中率相似可以看出。七、实验总结这次实验其实不一定要在linux操作系统下做，在windows操作系统一样可以实现，只要把头文件稍作修改即可。为了保险起见，我在2个操作系统下都编译过，都没问题。在windows操作系统，要屏蔽//#includeunistd.h这句话，在linux操作系统下则启用。此次实验借助于老师提供的主函数main模板，只需要写FIFO，LRU，OPT,CLOCK等4个替换算法，所以阻力没那么大。每个替换算法必须弄懂其中的细节，写起来才得心应手。一开始做这个实验时，首先是看书，先把书上的替换算法知识点弄明白，要明白各种算法的优缺点和相互之间衍生互补关系。这四个算法中，难以实现的是LRU算法，因为它涉及到访问时间的计算，而且它的开销也比较大。OPT算法次难，它需要计算最近访问时间，并替换最近访问时间最大的页。而FIFO和CLOCK实现起来比较容易，FIFO算法的实现和CLOCK算法的实现很相似，FIFO可视为CLOCK的退化版。我先写了CLOCK算法，再删去一些约束条件就退化为FIFO算法。这就是两者的相同之处。理论上，CLOCK算法需要维持一个循环的主存缓冲区，需要一个循环队列去实现，并且，FIFO算法保持先进先出，因此需要一个先进先出队列。但是，我实现这两个算法只用到了单向链表的数据结构，剩下的由其中的指针去把握了。因此，必须对指针使用有敏锐的感觉。天下无难事，只怕有心人！八、程序源码（在两个系统上都通过）#includestdio.h#includestdlib.h#includeunistd.h//在window操作系统下要屏蔽此条指令#includestring.h#ifndef_UNISTD_H#define_UNISTD_H#includeIO.H#includePROCESS.H#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;//随机数inti;srand(10*getpid());/*每次运行时进程号不同，用来作为初始化随机数队列的种子*/s=(int)((float)(total_instruction-1)*(rand()/(RAND_MAX+1.0)));printf(\n------------随机产生指令流------------\n);for(i=0;itotal_instruction;i+=4)//产生指令队列{a[i]=s;//任选一指令访问点ma[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;itotal_instruction;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;itotal_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID;//置页面所在主存区的帧号为-1.表示该页不在主存中pl[i].counter=0;//置页面结构中的访问次数为pl[i].time=-1;//置页面结构中的上次访问的时间为-1}for(i=0;itotal_pf-1;i++){pfc[i].next=&pfc[i+1];//建立pfc[i-1]和pfc[i]之间的链接pf