页面置换算法实验报告

1、本文格式为word版，下载可任意编辑页面置换算法实验报告 页面置换算法 试验报告 一、 试验目得: 设计与实现最佳置换算法、随机置换算法、先进先出置换算法、最近最久未使用置换算法、简洁 clock 置换算法及改进型 cock 置换算法;通过支持页面访问序列随机发生实现有关算法得测试及性能比较、 二、 试验内容: l 虚拟内存页面总数为 n,页号从 0 到 n1 l 物理内存由 m 个物理块组成 l 页面访问序列串就是一个整数序列,整数得取值范围为 0 到 n - 、页面访问序列串中得每个元素 p 表示对页面 p 得一次访问 l 页表用整数数组或结构数组来表示 q 符合局部访问特性得随机生成算法

2、 1. 确定虚拟内存得尺寸,工作集得起始位置 p,工作集中包含得页数e,工作集移动率(每处理 m 个页面访问则将起始位置 p 1),以及一个范围在 0 与之间得值 t; 2. 生成个取值范围在 p与 + e 间得随机数,并记录到页面访问序列串中; 3. 生成一个随机数 r,0 r 1; 4. 假如 r t,则为 p 生成一个新值,否则 p = (p ) mod n; 5. 假如想连续加大页面访问序列串得长度,请返回第 2 步,否则结束。 三、 试验环境: 操作系统:wiows 7 软件: +6.0 四、 试验设计: 本试验包含六种算法,基本内容相差不太,在实现方面并没有用统一得数据结构实现,而

3、就是依据不同算法得特点用不同得数据结构来实现: 1、最佳置换与随机置换所需操作不多,用整数数组模拟内存实现; 2、先进先出置换与最近最久未使用置换具有队列得特性,故用队列模拟内存来实现; 3、clock 置换与改进得 co置换具有循环队列得特性,故用循环队列模拟内存实现; 4、全部算法都就是采纳整数数组来模拟页面访问序列。 五、 数据结构设计: /页面访问序列数组: n eref_sze; /内存数组: it pyphy_size; /队列数据结构定义: tpeef srt qoe/ 构结据数列队义定 ;aad tni struct qnde *ext; qnod,*ueueptr; yped

4、 strct quuptr rnt; /头指针 ;aer rtpuuq /尾指针 linkquu; /定义链表数据结构 typede struct lno /定义循环链表数据结构 it data; it flag; /访问位 int modfy; / 位改修 ;txe donl tcutslnde,linlst; 六、 主要函数说明: 1、 vod se_r_num()/ ;列数机随得性特部局有具生产2、 int exchange_no(lnklis l,in e,it i)/将链表中序号为 i 得结点替换为内容为 e 得结点; 3、 ool srch_iklis(linst l,nt e,n

5、 i)找到链表中内容为得结点,并用 i 返回其位置,i=1 表示第一个非头结点,依次类推; 4、 void erch_flg(liklis ,it i)/用 i 返回第一个 flag 为 0 得结点得位置,i1 表示第一个非头结点,以此类推; 5、 vod e_lllag(linkls l,int i) /设置链表中得序号为得结点得la标志为 1; 6、 it arch_lmodifyclock(linklst l,nt moy_m)/找到改进得 clo算法所需要淘汰得页,用odf_nm 返回其位置; 此函数依据书上给得思路,第一遍扫描=且 m=得页面予以淘汰,若失败,则进行其次轮扫描 a=且

6、 m=得页面,其次轮扫描时将全部访问过得页面得访问位置 0;若失败则重复上述两部; 7、vod sll_mofy(lst l,int i) /设置链表 l 中得序号为 i得结点得odiy 标志为 1; 8、boo searhque(lnque q,i e,int )/点结中列队找寻data 域等于得结点,并用 i 返回其在 q 中得位置; 9、nt getnum(it a,int ) /用返回元素在被引用数列中得下一个位置 10、vod ora() /实现最佳置换算法,包括推断页面就是否在内存中、页面进内存、输出内存状态等内容; 11、oid rd() /随机置换算法 12、void fo()

7、 /法算出先进先1、voi lr() /最近最久未使用算法 实现最近最久未使用算法得思想就是:推断待进入内存得页面,假如与内存中得第一个页面相同,则将它移到最终一个,即标志为最近使用得页;假如与内存中得其次个页面相同,则将它删除,并在队列尾部添加相同元素,即标志为最近使用得页; 、)(koc div 法算 kolc 现实 1、oid difi_lock() /实现改进得 clock 算法 16、in ain() /主函数,调用实现各算法得个主要函数,并输出各算法得缺页率。 七、 试验问题回答: 1、fifo 算法就是否比随机置换算法优越？ 答:fo 算法比随机置换算法优越,但优势并不明显、 2

8、、lru 算法比 fi 算法优越多少？ 答:lu 算法ifo 算法得效率要高 510%,有理论学问可知,页面访问序列具有局部性,而fo 算法并不符合实际状况。 3、ru 算法与 optimal 算法有何差距？ 答:lru 算法就是全部算法中效率最接近 opimal 算法得算法,由理论学问可知,otal 算法就是抱负得算法,现实中几乎不行能实现,只能作为一种测评标准,lru 算法就是效率较高得可实现置换算法,但其硬件要求较高,假如规模较小,则略显麻烦。 4、clock 算法与 lr算法有何差距？ 答:lck 算法与 lu 算法从结果瞧来差距不大,lc算法就是使用软件得方式实现 lru 算法中硬件

9、得功能,从而在执行效率上会稍逊色些。 八、 试验过程结果截图: 试验结果截图 测评一: 测评二: 测评三: 试验过程截图 (注:只截取第三次测评,蓝色字体表示产生缺页中断) 九、 试验结果分析: 1 、最佳置换算法效果最佳 不论在那组数据中,最佳置换算法得效果都就是最好得,且都会比其它算法得性能高出不少。但通过课堂上得学习,我们知道这只就是一种抱负化算法,但实际上却难于实现,故主要用于算法评价参照。 、随机算法得性能总就是最不好得 道知们我但,去出换置个一挑机随中面页有所从是就总次每法算机随于由是就这页面得访问存在着局部性得原理,并不就是随机得,因此它得性能较差。 3 、最近最久未使用算法得性

10、能较好 相较于先进先出与两种clc算法,最近最久未使用算法得性能略好,我们测试得数据规模相对较小,信任假如采纳更大规模得数据,其优势会更加明显。 当从课堂上我们知道要想在实际得应用中实现本算法,用软件得方法速度太慢,影响程序执行效率,假如采纳硬件方法实现,则需要增加大量得硬件设备。 4 、先进先出与 clock 算法得性能基本相同 这就是由于两种loc算法遍历链表采纳得就就是if得方法,而改进得clck 算法相比于简洁 clc算法得优势主要体现在会依据就是否被修改进行选择,以削减写回所花费得时间。 十、 试验总结: 这次试验总体难度不就是很大,需要实现得算法数目虽然不少,但基本思路较为相像,因

11、此实现起来也并不就是非常困难。通过完成这次试验,除了加深了我对几种策略得理解,熬炼了我得编程力量,另一个巨大得收获就就是了解了一些生成测试数据得方法。为了使我们得测试数据更贴近现实,我们引入了工作集得概念,并依据实际使用状况得特点设计出尽可能符合实际状况得随机数生成方案。通过课件再加上自己得理解,我了解了老师得设计思路,感觉这个思路极其奇妙,设计中用到得方法与体现出得许多思想值得我们学习。 十一、 程序清单: #includeistram #ncludewinow.h #icudetim. inludemalloc。 #iucoio. usin namepce s; defi ref_siz

12、die phy_size 3 in refref_ize; floa inrrupt=0。0; /nt rfref_siz=0; int phyy_ie; / id et_anm()/ 列数机随得性特部局有具生产 cout页面访问序列:'endl; ;1p ni ;4=e tni int m=4; it ; ;0=j ti int n=; ;6、0 uod nt tmp; )+,i;mi;0=i(rof ;)01(pls ;)llun(emit(dna temp=rand()e; refj=tem; ; fertoc r(n0;n4;n+) ;)001(peels rand(ime(n

13、ull); ;.01)01)(nar()lbuod(= ebuod /coutrdl; f(rt) p=p+in(10*r); lse p=(p+)20; )+j,+i;m;0=i(rof sle(00*i); san(time(null); emr()%; ;pmetjfer coutrefj' ' cutedl; / tyede struct node/ 构结据数列队义定 it ta; strct qnde *next; qode,*queueptr; typede truct queue front; / 针指头 queuptr rar; /尾指针 line; /定义链表

14、结点 typef struc lode /定义循环链表数据结构 ;ad n in lag; / 位问访 ;yfidom tn /修改位 ;txen dnl tcrtslnoe,*iklist; /对循环链表得一些操作 nt cralist(inklist l)/创建循环带有头结点得链表 ;)edon(eis(cl)tsikil(l i(!l) exit(-1); ;=txn- ;=gal- retrn 1; int exchange_lnde(links l,n e,i )/将链表 l 中序号为得结点替换为内容为 e 得结点 ;)(ixe )l=txe-l( ;q,p tsilknl t j=

15、0; ;)edonl(oezis(colam)tsilnil(=p ;)edol(oezs(coa)tikni(=q ;=atdq p=l; 头非个一第除删,证保应故,点结个一前得点结换更待为 p 使/)+j;ij;j(ro结点时 i=0,以此类推 p=pet; qext=p-nextnext; ;q=txen-p ;1galfq /设置新结点得访问位为 1 ;0=yfiq/ 0 为位改修得点结新置设 retun 1; int insert_lde(linklist l,it e)/在循环链表中插入新得结点,从 l 头结点开头依次向后插入 ;,p tsilknil ;)edonl(fois(c

16、ollm)tii(=p ;)nl(fezs(clm)sikil(=q q-aa=; /;=galfq 1 为位问访得点结新置设 为位改修得点结新置设/ ;0=ydm- p=; e(pnt!=l) pnxt; ;q=txen- ;l=xenq ;1 nrutr bo sr_linklist(likis l,nt e,int i)/找到链表 l 中内 容为 e 得结点,并用返回其位置,i1 表示第一个非头结点,依次类推 =1; ;)1-(ixe )l=txenl(i lnlist p; ;)edonl(fzs(collam)lnil(= i(！p) et(-1); / ;txe-p/ )点结头非(

17、点结个一第得表链向指 p while(p！=l pdta！=) p=next; ;+ /)l=p(f 点结得求要合符到找有没 retrn fase; retun tre; void serchll_flag(linis l, i)/用返回第一个 fla为 0得结点得位置,=1 表示第一个非头结点,以此类推 ;1i ; tiknl =(linls)maloc(ieof(lnode); (!) eit(-1); p=l-nex; )=！alfp(elw p-fl=0; / 0 为位志标问访改修 p=ext; f(p=l) / 点结头过跳 ;txepp i+; /)=(f/ 点结头过跳 i1; /

18、;1 rute vd et_lag(lnklist l,int i)/得点结得i为号序得中表链置设flag 标志为 1; ;p tlki p(lnks)malc(sizo(lno); i(！) xt(-1); ;txelp if(i=) p-lag=1; if(=2) ;txenp=p -flg1; if(i=3) ;txn-=p =ne; ;=gaf-p in erch_l_mdylok(linklist l,int mf_u)/找到改进得 clok 算法所需要淘汰得页,用 modify_num 返回其位置 ;1=m_yfdom ;)-(txe )l=txe-(fi linklst p; ;

19、)edonl(foez(collam)tilki(=p if(!) i(-1); =lnext;/ )点结头非(点结个一第得表链向指 p whl(p！l) /第一轮扫描 a=0 并且 m=0 得结点 )=yfdom-p 0=gafp(fi break; /找到 p=nex; ;+mun_yfidom i(p=l) ify_um=; plnxt; hile(p！=)/结得过问访改修时同,点结得 1=m 且并 0=a 描扫轮二第点得访问位为 0 i(p-flg!0) ;0=galf )1=fidm(fi ee;kaerb ;txep=p;+muidm if(p) moifynum=1; p=-nx

20、t; wile(p！) /第三轮扫描 a0 并且=0 得结点 f(pflg=0 pmdiy=0) ;e;xenp= mofy_num+; )l=p(fi ;1=mun_yfidom ;tx-l= le(p！=) /第四轮扫描 a=并且=1 得结点 )0=！galfp(fi ;0galfp ese f(pmdfy=) ;ka ;tenp=p mify_nm+; retun 1; void t_ll_moify(inklst ,int i) /设置链表 l 中得序号为 i 得结点得 modify 标志为 1; inkist p; ;)edn(ozi(collam)tsilnil( i(！p) ei

21、t(-1); =lxt; if(i=) ;=fidom-p (i=) ;tep= pmodiy=1; if(=2) p=-nxt; ;xen-=p p-modify1; in detolnklist(lnist ) 删除链表,并释放链表空间 ;,p silkil ;)edon(feis(coam)tsilkl(p ;)(ix )！(i ;)edo(oeis(cola)tilil(= if(！q) exit(-); ;txl= )l=！p(elihw q=pne; fee(); p=; ree(q); ret ; /对队列得一些操作 in inituee(nkqueue q) 队列初始化 q、f

22、ont=q、rear=(uueptr)mallo(szf(qnode); i(！、rnt) it(1); q.ronetnl; ; uter it enqe(lnkqueue q,n e) /尾队得新得 q 为 e 素元入插元素 ;p rtpeueu ;)edon(foe(ollam)rtpeeq( (!p) eit(-1); pdt=e; p-nextnll; ;p=tn-rar、q q、e; eturn 1; int deee(lnkquee q,int e)/用,素元头队得 q 除删则,空不列队若 e 返回其值 if(q。front=.rear) reurn 1; queueptr p;

23、 ;)eonq(fozis(cla)rtpeueuq( =q、frnnext; e=-dta; q。ront-next-next; if(q.a=p) ;tnorf。qrae、q ;)p(eef ;1 nuter bool searhqueue(likqeue q,nt e,int i) /查找队列中结点at域等于 e 得结点,并用 i 返回其在 q 中得位置 ;1=i if(q。frot=q.ear) eit(-1); ueeptr p; p=(euept)mloc(ize(qode); f(!p) ex(-1); p=q.fro-next; /指向队列得第一个节点(非头结点) whl(p!

24、=u p-dt!=e) ;txen=p +; if(！p) ;esaf nrute retur ue; int elid_que(lkque q,int ) /删除 q 得中间元素,并用 e 返回其值 (q、fot=q.re) retur 1; ;p rteueuq ;)edon(fozi(collam)rpeueuq(=p if(!p) xit(-1); p=q.ontne; ;tad-tenp=e ;txntenp=t- rurn ; nt dtroyqeue(linkque q) /删除队列并释放空间 whl(q、frot) q.rea=q、ntnex; ;)tnf、q(eerf ;re

25、、q=orf。 rturn ; / nt mx(int a,int b, int c)/ 值大最得中 c,b,a 回返 ;b=a )ba(fi if(a) a=c; eturn a; int geum(int a,it b)/ 置位个一下得中列数用引被在 a 素元回返 b 用 )+b;ezis_ferb;(ro )bfr=a(fi ;krb ;b ruter vo oa() /最佳置换算法 _tuptu_ts(ldahdteg(tubirtxtlsnoceandle),froudineit foregrore); outn*最佳置换算法*endl; dnah_tuo_dts(elnahdstg

26、(eturtatetlosoctee),foregrund_intnsty forgoudinensiy);/设置字体颜色为白色 ;j,i tni ;xmn,2_mun,1_mun,0_mun ti ;0=untpri tni /nu_0=um_1=num2=0; /)+i;ezis_yh i;0=i(rf/ 存内进数个三前 ;fyp )+i;ezispi;0=(rof /输出最初得三个数 ;'t'yhptuoc ;dnetuoc )+j;ezsfj;eihp=j(rof dah_upu_dts(eldatsteg(etubrttatxteonoctese),orgrud_it

27、ensity foregond_nsit); i(!(rej=phy0 rfj=phy1 ref=phy)/ 换替被页得用使被会不久最择选,断中页缺生产若 ;)1j,0h(neg=0un;)1j,1yhp(mueg=1_u num2=etnum(hy2,j1); numax=max1(num0,num_1,nu_2); )xam_mu=_mn(fi py0=refj; esle )xam_mn=1_mn(f ;jferyhp esle)xm_mun=2_mun(fi ;jfer=hp ;+mu_tpurretni setcnsolextattriute(getstdandl(std_utput

28、hane),fregroundiensity | forerondblue);/设置字体为蓝色 out进入页:rfjedl; /)+i;ezipi;0=i(r/ 态状存内出输 outphyit' ;ldnednetuoc _tuptuo_ ts(eldnah steg( tubi ttatx te o nocte andle),forround_intensity | foegougreen); /;ldnemun_purtni:数次断中页缺法算换置佳最'tc 以绿色字体输出中断次数 inerru0=(fat)interupt_nm/20、0)*100。0; / vi nd()

29、 /随机置换算法 setonoleetattibute(gettdhanle(stouput_hand),fregoundtensity forgroud_); *法算换置机随* tuoc*'endl; tonsoleexattribu(getstdhanle(td_oututhale),ound_intensy foreroun_itens y); in i,j,mp; ;0=mn_rreti tni /um_0=num_1=nm_20; ;)0001(peels/;)llun(emi(dnar/ 子种间时置设 )+;zis_h ;i(ro phyi=rei; )+;eisyi;0=

30、i(of ;t'ituoc ;neuo )+j;ezs_ferj;ezisyhj(rof setconsletextattibute(gestdhandl(t_oputandl),foreroun_intsity | foregrud_intensi); /)2p=jer | 1yp=jfer | 0yh=jfer(！(fi/产生缺页中断,随机选择页被替换 tpand()%3; /;npettuoc phytmp=ef; intrutnm+; setcostxatribute(estdhandle(std_outptndle),oreguintensty feground_u); co

31、ut进入页:refjendl; )+i;ezis_pi;=i(ro ;'typt cotendlndl; etonsletextaribte(gestdhandle(std_outputhde),forrun_intesiy foregroud_gre); / ;lnmn_turetni:数次断中页缺法算换置机随toc 以绿色字体输出中断次数 ;0、001*)、02_tpuretni)taol(1tpuetn / oi fif() ldah_tptuots(ldnahdtsteg(uirtxeelooctes),foregrundintensit freround_red); *法算换

32、置出先进先*ntuo*nd; se on oletex ttribute(g ts d andl (std_ utpu _handle),orerund_intnsit foeround_intenit); inkueue l; ;p rtpeu in ,e,m; int nterpt_num=; intqe(); for(i;ipy_size;i+) enuu(l,rfi); ;)onq(foezis(collam)teueu( ;xennorf、lp 存内进数个三前/)+j;ezis_pj ln=!p;0=(rf cotpdatat; p=-t; ;dnetuo )+i;ezi_fei;z

33、i_yhp=i( setconsetextattib(gestande(st_output_hadle),frrouitesity | fgrou_intensity); i(!seahquu(l,rfi,)/被页得入进先最择选,断中页缺生产替换 ;)e,l(eeuqed /cuteendl; eneue(,re); irrupt_num+; c n le att bu e( ets dha dle(std_outputhdle),egroud_tensity orrud_blue); ;ldneifer':页入进't ;txentnof、lp for(j=0;！=nul ph

34、y_sze;j+) ;'t'atadptuc ;txen-p=p coutedendl; tonseextatti(gstdhnle(std_outut_handle), ore round_inten ty | oreg nd_green); cout先进先出置换算法缺页中断次数:iterrut_numendl;/ 以绿色字体输出中断次数 intrpt2=(ft)inrtu/0。)*100、0; ;)p(eerf ;)l(eueuqyortsed / vod lu() /最近最久未使用算法 f,)eldn_tu_s(eldnhdtte(euirtttxetelosnoctsr

35、egoud_nesit rgroudred); otn*最近最久未使用置换算法*endl; ;0=mun_eonq ti_tuuo_dts(elntte(ubrttatxeelonotendl),foregun_itensity | foreond_itnsity); ; eueuni ;p reuq int ,j,e; int iterrpt_nm=; iitueue(l); )+i;zis_yhpi;0=i(rf enquue(l,ei); p=(queuet)alloc(izef(qnode); ;xetorf、l= for(0;p！=nll jhy_siz;j+) coutdata;

36、p=pnxt; ;ldetuc for(i=p_siz;_sze;i+) erof,)ldnah_tuuo_dt(eldnahdtsteg(ubrttatxetelosnoctesrond_intty fregrnd_intesiy); if(！searchque(l,efi,qode_num) /产生缺页中断,选择最"老'得页面被替换 equeu(,e); /cteedl; enqeue(l,efi); ;+munpurret s(e dnahdts g( tub a x t losno tesd_output_handl ),fo eground_in e sity |

37、foregrou d_blue); els if(qneum=1)/将则,个一第得中存内是就来下接果如它移到最终一个,即标志为最近使用得页 enqueue(l,rei); dequee(l,e); /)2=mun_edonq(f esle,除删它将则,个二第得中存内是就来下接果如并在队列尾部添加相同元素,即标志为最近使用得页 delmid_eue(l,); ;)e,l(uuqne ;ldneifer:页入进'tuc ;xen-trf、l=p 况状存内出输/ )j;zisyhp llun!;=j(rof ;tt-ptuoc pp-nex; cutendlend; uo_d s(e dna

38、h t eg(e ubir tx elo nocte ut_handl),fregrud_intensi foregond_ren); mn_purr :数次断中页缺法算换置用使未久最近最tuocendl;/ 数次断中出输体字色绿以 irupt3=(float)ttnum/0。0)*1.; deteue(l); fre(); / void cloc() setconsoletxttute(gtsthndl(tdoutp_handle),foregron_itens foregrund_red); out'n*cloc置换算法*endl; ahtptuo_dt(ldahdsteg(tuittattelosotedle),foregroundintenity | foregroundntensty); inerpt_num=0; ; tni in lnode_it_u0;/位得面页得同相面页入进带与中存内带记标置 i lode_fg_num; /标记访问位为0得页面在内存中得位置 ;l siknil cratlis(); ;p tsilkni ;)donl(foezis(collam)tilknl(=p for(i=;iph_sie;i+) isr