页面置换算法实验报告.doc
22页
页面置换算法实验报告页面置换算法实验报告一、 实验目的：设计和实现最正确置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改良型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比拟二、 实验内容：l 虚拟内存页面总数为N，页号从0到N-1l 物理内存由M个物理块组成l 页面访问序列串是一个整数序列，整数的取值范围为0到N - 1页面访问序列串中的每个元素p表示对页面p的一次访问l 页表用整数数组或结构数组来表示q 符合局部访问特性的随机生成算法1. 确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m〔每处理m个页面访问那么将起始位置p +1〕，以及一个范围在0和1之间的值t；2. 生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中；3. 生成一个随机数r，0 ≤ r ≤ 1；4. 如果r < t，那么为p生成一个新值，否那么p = (p + 1) mod N；5. 如果想继续加大页面访问序列串的长度，请返回第2步，否那么结束三、 实验环境：操作系统：Windows 7软件： VC++6.0四、 实验设计：本实验包含六种算法，根本内容相差不太，在实现方面并没有用统一的数据结构实现，而是根据不同算法的特点用不同的数据结构来实现：1、 最正确置换和随机置换所需操作不多，用整数数组模拟内存实现；2、 先进先出置换和最近最久未使用置换具有队列的特性，故用队列模拟内存来实现；3、 CLOCK置换和改良的CLOCK置换具有循环队列的特性，故用循环队列模拟内存实现；4、 所有算法都是采用整数数组来模拟页面访问序列。
五、 数据结构设计：//页面访问序列数组：int ref[ref_size];//内存数组：int phy[phy_size];//队列数据结构定义：typedef struct QNode //定义队列数据结构{ int data; struct QNode *next;}QNode,*QueuePtr;typedef struct{ QueuePtr front; //头指针 QueuePtr rear; //尾指针}LinkQueue;//定义链表数据结构typedef struct LNode //定义循环链表数据结构{ int data; int flag; //访问位 int modify; //修改位 struct LNode *next;}LNode,*LinkList;六、 主要函数说明：1、 void set_rand_num() //产生具有局部特性的随机数列；2、 int Exchange_LNode(LinkList &L,int e,int i)//将链表L中序号为i的结点替换为内容为e的结点；3、 bool Search_LinkList(LinkList &L,int e,int &i)//找到链表L中内容为e的结点，并用i返回其位置，i=1表示第一个非头结点，依次类推；4、 void Search_LL_Flag(LinkList &L,int &i)//用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推；5、 void Set_LL_Flag(LinkList &L,int i) //设置链表L中的序号为i的结点的flag标志为1；6、 int Search_LL_ModifyClock(LinkList &L,int &modify_num)//找到改良的CLOCK算法所需要淘汰的页，用modify_num返回其位置；此函数根据书上给的思路，第一遍扫描A=0且M=0的页面予以淘汰，假设失败，那么进行第二轮扫描A=0且M=1的页面，第二轮扫描时将所有访问过的页面的访问位A置0；假设失败那么重复上述两部；7、void Set_LL_modify(LinkList &L,int i) //设置链表L中的序号为i的结点的modify标志为1；8、bool SearchQueue(LinkQueue &Q,int e,int &i) //寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置；9、int getnum(int a,int b) //用b返回元素a在被引用数列中的下一个位置10、void ORA() //实现最正确置换算法，包括判断页面是否在内存中、页面进内存、输出内存状态等内容；11、void RAND() //随机置换算法12、void FIFO() //先进先出算法13、void LRU() //最近最久未使用算法实现最近最久未使用算法的思想是：判断待进入内存的页面，如果与内存中的第一个页面相同，那么将它移到最后一个，即标志为最近使用的页；如果与内存中的第二个页面相同，那么将它删除，并在队列尾部添加相同元素，即标志为最近使用的页； 14、void CLOCK() //实现CLOCK算法 15、void Modified_Clock() //实现改良的CLOCK算法16、int main() //主函数，调用实现各算法的6个主要函数，并输出各算法的缺页率。
七、 实验问题答复：1、FIFO算法是否比随机置换算法优越？答：FIFO算法比随机置换算法优越，但优势并不明显2、LRU算法比FIFO 算法优越多少？答：LRU算法FIFO算法的效率要高5%-10%，有理论知识可知，页面访问序列具有局部性，而FIFO 算法并不符合实际情况3、LRU算法和Optimal算法有何差距？答：LRU算法是所有算法中效率最接近Optimal算法的算法，由理论知识可知，Optimal算法是理想的算法，现实中几乎不可能实现，只能作为一种测评标准，LRU算法是效率较高的可实现置换算法，但其硬件要求较高，如果规模较小，那么略显麻烦4、Clock算法和LRU算法有何差距？答：Clock算法和LRU算法从结果看来差距不大，Clock算法是使用软件的方式实现LRU算法中硬件的功能，从而在执行效率上会稍逊色些八、 实验过程结果截图：实验结果截图测评一：测评二：测评三：实验过程截图〔注：只截取第三次测评，蓝色字体表示产生缺页中断〕九、 实验结果分析：1、最正确置换算法效果最正确不管在那组数据中，最正确置换算法的效果都是最好的，且都会比其它算法的性能高出不少但通过课堂上的学习，我们知道这只是一种理想化算法，但实际上却难于实现，故主要用于算法评价参照。
2、随机算法的性能总是最不好的 这是由于随机算法每次总是从所有页面中随机挑一个置换出去，但我们知道页面的访问存在着局部性的原理，并不是随机的，因此它的性能较差3、最近最久未使用算法的性能较好 相较于先进先出和两种clock算法，最近最久未使用算法的性能略好，我们测试的数据规模相对较小，相信如果采用更大规模的数据，其优势会更加明显 当从课堂上我们知道要想在实际的应用中实现本算法，用软件的方法速度太慢，影响程序执行效率，如果采用硬件方法实现，那么需要增加大量的硬件设备4、先进先出与clock算法的性能根本相同 这是由于两种clock算法遍历链表采用的就是FIFO的方法，而改良的clock算法相比于简单clock算法的优势主要表达在会根据是否被修改良行选择，以减少写回所花费的时间十、 实验总结：这次实验总体难度不是很大，需要实现的算法数目虽然不少，但根本思路较为相似，因此实现起来也并不是十分困难通过完成这次实验，除了加深了我对几种策略的理解，锻炼了我的编程能力，另一个巨大的收获就是了解了一些生成测试数据的方法为了使我们的测试数据更贴近现实，我们引入了工作集的概念，并根据实际使用情况的特点设计出尽可能符合实际情况的随机数生成方案。
通过阅读课件再加上自己的理解，我了解了老师的设计思路，感觉这个思路极其巧妙，设计中用到的方法和表达出的很多思想值得我们学习十一、 程序清单：#include
