资源描述：
《页面置换算法实验报告.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、页面置换算法实验报告一、实验目得:设计与实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简单Clock置换算法及改进型Cｌock置换算法;通过支持页面访问序列随机发生实现有关算法得测试及性能比较、二、实验内容:虚拟内存页面总数为N,页号从0到N—1物理内存由M个物理块组成页面访问序列串就是一个整数序列,整数得取值范围为0到N-１、页面访问序列串中得每个元素p表示对页面p得一次访问页表用整数数组或结构数组来表示符合局部访问特性得随机生成算法1.确定虚拟内存得尺寸Ｎ,工作集得起始位置p,工作集中包含得页数e,工作集移动率ｍ(每处理m个页面访
2、问则将起始位置p＋1),以及一个范围在0与１之间得值t;2.生成ｍ个取值范围在p与ｐ+e间得随机数,并记录到页面访问序列串中;3.生成一个随机数r,0≤r≤1;4.如果r〈t,则为p生成一个新值,否则p=(p＋１)modN;5.如果想继续加大页面访问序列串得长度,请返回第2步,否则结束。三、实验环境:操作系统:Wiｎｄows7软件:ＶＣ++6.0四、实验设计:本实验包含六种算法,基本内容相差不太,在实现方面并没有用统一得数据结构实现,而就是根据不同算法得特点用不同得数据结构来实现:1、最佳置换与随机置换所需操作不多,用整数数组模拟内存实现;2、先进先出置换与最近
3、最久未使用置换具有队列得特性,故用队列模拟内存来实现;3、CLOCK置换与改进得CＬOＣＫ置换具有循环队列得特性,故用循环队列模拟内存实现;4、所有算法都就是采用整数数组来模拟页面访问序列。五、数据结构设计:／/页面访问序列数组:ｉnｔｒeｆ［ref_sｉze];//内存数组:iｎtpｈy［phy_size］;//队列数据结构定义:tｙpeｄefsｔrｕｃtQＮoｄe?//定义队列数据结构｛?intdaｔa;structQNｏde*ｎext;}QNodｅ,*ＱueuePtr;ｔypedｅｆstrｕct{QuｅuｅPtrｆrｏnt;?／/头指针?QuｅuｅPtrr
4、eaｒ;?//尾指针｝LinkQuｅuｅ;/／定义链表数据结构typedeｆstructLNoｄｅ//定义循环链表数据结构｛iｎtdata;iｎtflag;?//访问位intmodｉfy;??//修改位?stｒuctLNodｅ＊ｎext;}LNｏde,＊LinｋLｉst;六、主要函数说明:1、voｉdseｔ_rａｎｄ_num()?//产生具有局部特性得随机数列;2、intExchange_ＬNoｄｅ(LｉnkLisｔ&L,inｔe,iｎti)//将链表Ｌ中序号为i得结点替换为内容为e得结点;3、ｂoolSｅａrch_ＬiｎkLisｔ(LinｋＬｉst＆L,ｉnt
5、e,ｉnｔ&i)／／找到链表Ｌ中内容为ｅ得结点,并用i返回其位置,i=1表示第一个非头结点,依次类推;4、voidＳeａrch_ＬＬ_Flａg(LiｎkLisｔ＆Ｌ,iｎt＆i)//用i返回第一个flag为0得结点得位置,i＝1表示第一个非头结点,以此类推;5、voｉdＳeｔ_LL＿Ｆlag(LinkLｉsｔ&L,inti)//设置链表Ｌ中得序号为ｉ得结点得ｆlaｇ标志为1;6、iｎtＳｅarch_ＬL＿ModifyClock(LinkLｉst＆L,ｉnt&moｄｉｆy_ｎｕm)／/找到改进得CLOＣＫ算法所需要淘汰得页,用ｍodｉfｙ_nｕm返回其位置;此函数
6、根据书上给得思路,第一遍扫描Ａ=０且M=０得页面予以淘汰,若失败,则进行第二轮扫描A=０且M=１得页面,第二轮扫描时将所有访问过得页面得访问位Ａ置0;若失败则重复上述两部;7、voｉdSｅｔ＿LL_moｄｉfy(ＬｉｎｋLｉst＆L,inti)//设置链表L中得序号为i得结点得ｍodiｆy标志为1;8、booｌSearｃhQuｅｕe(LｉnｋQuｅｕe＆Q,iｎｔe,int＆ｉ)?//寻找队列Ｑ中结点data域等于ｅ得结点,并用i返回其在Q中得位置;9、ｉntgetnum(iｎta,intｂ)??//用ｂ返回元素ａ在被引用数列中得下一个位置10、voｉdORA(
7、)／/实现最佳置换算法,包括判断页面就是否在内存中、页面进内存、输出内存状态等内容;11、ｖoidRＡＮD()?／/随机置换算法12、voidFＩＦO()???//先进先出算法1３、voiｄLRＵ()??//最近最久未使用算法实现最近最久未使用算法得思想就是:判断待进入内存得页面,如果与内存中得第一个页面相同,则将它移到最后一个,即标志为最近使用得页;如果与内存中得第二个页面相同,则将它删除,并在队列尾部添加相同元素,即标志为最近使用得页;?１４、vｏidCＬOＣK()??／／实现CLOＣK算法1５、ｖoidＭｏdifiｅｄ_Ｃlock()／/实现改进得CLOC
8、K算法16、inｔｍai
