页面置换算法实验.doc

《页面置换算法实验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、页面置换算法实验报告一、实验目的：设计和实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Clock置换算法；通过支持页面访问序列随机发生实现有关算法的测试及性能比较。二、实验容：l虚拟存页面总数为N，页号从0到N-1l物理存由M个物理块组成l页面访问序列串是一个整数序列，整数的取值围为0到N-1。页面访问序列串中的每个元素p表示对页面p的一次访问l页表用整数数组或结构数组来表示q符合局部访问特性的随机生成算法1.确定虚拟存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p+1），以及一个

2、围在0和1之间的值t；2.生成m个取值围在p和p+e间的随机数，并记录到页面访问序列串中；3.生成一个随机数r，0≤r≤1；4.如果r

3、改进的CLOCK置换具有循环队列的特性，故用循环队列模拟存实现；4、所有算法都是采用整数数组来模拟页面访问序列。二、数据结构设计：//页面访问序列数组：intref[ref_size];//存数组：intphy[phy_size];//队列数据结构定义：typedefstructQNode//定义队列数据结构{intdata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//头指针QueuePtrrear;//尾指针}LinkQueue;//定义链表数据结构typedefstructLNode//定义循环链表数据结

4、构{intdata;intflag;//访问位intmodify;//修改位structLNode*next;}LNode,*LinkList;二、主要函数说明：1、voidset_rand_num()//产生具有局部特性的随机数列；2、intExchange_LNode(LinkList&L,inte,inti)//将链表L中序号为i的结点替换为容为e的结点；3、boolSearch_LinkList(LinkList&L,inte,int&i)//找到链表L中容为e的结点，并用i返回其位置，i=1表示第一个非头结点，依次类推；4、voidSearch_LL_Flag(LinkList&L

5、,int&i)//用i返回第一个flag为0的结点的位置,i=1表示第一个非头结点，以此类推；5、voidSet_LL_Flag(LinkList&L,inti)//设置链表L中的序号为i的结点的flag标志为1；6、intSearch_LL_ModifyClock(LinkList&L,int&modify_num)//找到改进的CLOCK算法所需要淘汰的页，用modify_num返回其位置；此函数根据书上给的思路，第一遍扫描A=0且M=0的页面予以淘汰，若失败，则进行第二轮扫描A=0且M=1的页面，第二轮扫描时将所有访问过的页面的访问位A置0；若失败则重复上述两部；7、voidSet_L

6、L_modify(LinkList&L,inti)//设置链表L中的序号为i的结点的modify标志为1；8、boolSearchQueue(LinkQueue&Q,inte,int&i)//寻找队列Q中结点data域等于e的结点，并用i返回其在Q中的位置；9、intgetnum(inta,intb)//用b返回元素a在被引用数列中的下一个位置10、voidORA()//实现最佳置换算法，包括判断页面是否在存中、页面进存、输出存状态等容；11、voidRAND()//随机置换算法12、voidFIFO()//先进先出算法13、voidLRU()//最近最久未使用算法实现最近最久未使用算法的思

7、想是：判断待进入存的页面，如果与存中的第一个页面相同，则将它移到最后一个，即标志为最近使用的页；如果与存中的第二个页面相同，则将它删除，并在队列尾部添加相同元素，即标志为最近使用的页；14、voidCLOCK()//实现CLOCK算法15、voidModified_Clock()//实现改进的CLOCK算法16、intmain()//主函数，调用实现各算法的6个主要函数，并输出各算法的缺页率。二、实验问题回答