頁面置換算法實(shí)驗(yàn)報(bào)告

1、頁面置換算法實(shí)驗(yàn)報(bào)告一、 實(shí)驗(yàn)?zāi)康?:設(shè)計(jì)與實(shí)現(xiàn)最佳置換算法、 隨機(jī)置換算法、 先進(jìn)先出置換算法、 最近最久未使用置換算法、簡單 clock 置換算法及改進(jìn)型 c ock 置換算法 ; 通過支持頁面訪問序列隨機(jī)發(fā)生實(shí)現(xiàn)有關(guān)算法得測試及性能比較、二、實(shí)驗(yàn)內(nèi)容 :虛擬內(nèi)存頁面總數(shù)為n,頁號從 0 到 n 1物理內(nèi)存由 m 個(gè)物理塊組成頁面訪問序列串就是一個(gè)整數(shù)序列 ,整數(shù)得取值范圍為 0 到 n - 、頁面訪問序列串中得每個(gè)元素 p 表示對頁面 p 得一次訪問頁表用整數(shù)數(shù)組或結(jié)構(gòu)數(shù)組來表示符合局部訪問特性得隨機(jī)生成算法1. 確定虛擬內(nèi)存得尺寸 ,工作集得起始位置 p,工作集中包含得頁數(shù)e,工作集移

2、動率 (每處理 m 個(gè)頁面訪問則將起始位置 p 1),以及一個(gè)范圍在 0 與之間得值 t;2. 生成個(gè)取值范圍在 p 與 + e 間得隨機(jī)數(shù) ,并記錄到頁面訪問序列串中 ;3. 生成一個(gè)隨機(jī)數(shù) r,0 r 1;4.如果 r t,則為 p 生成一個(gè)新值 ,否則 p = (p ) mod n;5. 如果想繼續(xù)加大頁面訪問序列串得長度 ,請返回第 2 步 ,否則結(jié)束。三、實(shí)驗(yàn)環(huán)境 :操作系統(tǒng) :wi ows7軟件 : +6.0四、實(shí)驗(yàn)設(shè)計(jì) :本實(shí)驗(yàn)包含六種算法 ,基本內(nèi)容相差不太 ,在實(shí)現(xiàn)方面并沒有用統(tǒng)一得數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn) ,而就是根據(jù)不同算法得特點(diǎn)用不同得數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn) : 1、最佳置換與隨機(jī)置換所需

3、操作不多 ,用整數(shù)數(shù)組模擬內(nèi)存實(shí)現(xiàn) ;2、先進(jìn)先出置換與最近最久未使用置換具有隊(duì)列得特性,故用隊(duì)列模擬內(nèi)存來實(shí)現(xiàn) ;3、clock 置換與改進(jìn)得c o置換具有循環(huán)隊(duì)列得特性,故用循環(huán)隊(duì)列模擬內(nèi)存實(shí)現(xiàn) ;4、所有算法都就是采用整數(shù)數(shù)組來模擬頁面訪問序列。五、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì): /頁面訪問序列數(shù)組 : n e ref_sze; /內(nèi)存數(shù)組 :it pyphy_size;/隊(duì)列數(shù)據(jù)結(jié)構(gòu)定義 :tpe ef sr t qoe?/定義隊(duì)列數(shù)據(jù)結(jié)構(gòu)?int daa;structqnde * ext;qnod ,* ueueptr; yped strctqu u ptr rnt;?/頭指針?quuptr rea

4、 ;?/尾指針 linkqu u;/定義鏈表數(shù)據(jù)結(jié)構(gòu)typede struct lno /定義循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)i t data;i t flag;?int modfy; ?/訪問位?/修改位?stuctlnod ext;ln de,lin l st;六、主要函數(shù)說明:1、 vo d se _r _num()?/ 產(chǎn)生具有局部特性得隨機(jī)數(shù)列;2、 intexchange_ no (l nklis &l,in e,i ti)/ 將鏈表中序號為i 得結(jié)點(diǎn)替換為內(nèi)容為e 得結(jié)點(diǎn) ;3、 ool s rch_ i klis (lin st l, nt e, n &i) 找到鏈表中內(nèi)容為得結(jié)點(diǎn),并用 i

5、返回其位置 ,i=1 表示第一個(gè)非頭結(jié)點(diǎn),依次類推 ;4、 void e rch_ _fl g(li klis ,i t i)/ 用 i 返回第一個(gè)flag 為 0 得結(jié)點(diǎn)得位置 ,i 1 表示第一個(gè)非頭結(jié)點(diǎn),以此類推 ;5、 vo d e_ll lag(linkl結(jié)點(diǎn)得 la標(biāo)志為1;s&l,int i)/ 設(shè)置鏈表中得序號為得6、 i t arch_ l modifyclock(linkl st l, nt &mo y_ m) / 找到改進(jìn)得 clo 算法所需要淘汰得頁 ,用 od f _n m 返回其位置 ;此函數(shù)根據(jù)書上給得思路,第一遍掃描=且 m= 得頁面予以淘汰,若失敗 ,則進(jìn)行第

6、二輪掃描a= 且 m= 得頁面 ,第二輪掃描時(shí)將所有訪問過得頁面得訪問位置 0;若失敗則重復(fù)上述兩部;7、 vo d s ll_mo fy( l st l,inti) / 設(shè)置鏈表l 中得序號為i得結(jié)點(diǎn)得 odi y 標(biāo)志為 1;8、 boo sear hqu e(l n qu e q,i e,int )?/尋找隊(duì)列中結(jié)點(diǎn)data 域等于得結(jié)點(diǎn),并用 i 返回其在 q 中得位置 ;9、 nt getnum(i ta,int )?/ 用返回元素在被引用數(shù)列中得下一個(gè)位置10、 vo dora()/ 實(shí)現(xiàn)最佳置換算法,包括判斷頁面就是否在內(nèi)存中、頁面進(jìn)內(nèi)存、輸出內(nèi)存狀態(tài)等內(nèi)容;11、 oid r

7、d()? /隨機(jī)置換算法12、 void f o() ?/先進(jìn)先出算法1、 voi lr ()?/ 最近最久未使用算法實(shí)現(xiàn)最近最久未使用算法得思想就是:判斷待進(jìn)入內(nèi)存得頁面,如果與內(nèi)存中得第一個(gè)頁面相同 ,則將它移到最后一個(gè) ,即標(biāo)志為最近使用得頁 ;如果與內(nèi)存中得第二個(gè)頁面相同 ,則將它刪除 ,并在隊(duì)列尾部添加相同元素 ,即標(biāo)志為最近使用得頁 ;?、 v id c o k() ?實(shí)現(xiàn)clo k 算法1、 oid difi _ lock() /實(shí)現(xiàn)改進(jìn)得clock 算法16、 in ain() /主函數(shù) ,調(diào)用實(shí)現(xiàn)各算法得個(gè)主要函數(shù),并輸出各算法得缺頁率。七、實(shí)驗(yàn)問題回答:1、 fifo 算法

8、就是否比隨機(jī)置換算法優(yōu)越？答:f o 算法比隨機(jī)置換算法優(yōu)越,但優(yōu)勢并不明顯、2、 lru 算法比 fi 算法優(yōu)越多少？答 :l u 算法 ifo 算法得效率要高 5 10%,有理論知識可知 ,頁面訪問序列具有局部性 ,而 fo 算法并不符合實(shí)際情況。3、 ru 算法與 optimal 算法有何差距？答 :lru 算法就是所有算法中效率最接近 opimal 算法得算法 ,由理論知識可知 ,o t al 算法就是理想得算法 ,現(xiàn)實(shí)中幾乎不可能實(shí)現(xiàn) ,只能作為一種測評標(biāo)準(zhǔn) ,lru 算法就是效率較高得可實(shí)現(xiàn)置換算法 ,但其硬件要求較高 ,如果規(guī)模較小 ,則略顯麻煩。4、 clock 算法與 lr

9、算法有何差距？答 : lck 算法與 l u 算法從結(jié)果瞧來差距不大 ,l c算法就是使用軟件得方式實(shí)現(xiàn) lru 算法中硬件得功能 ,從而在執(zhí)行效率上會稍遜色些。八、實(shí)驗(yàn)過程結(jié)果截圖:實(shí)驗(yàn)結(jié)果截圖測評一 :測評二 :測評三 :實(shí)驗(yàn)過程截圖(注:只截取第三次測評 ,藍(lán)色字體表示產(chǎn)生缺頁中斷)九、實(shí)驗(yàn)結(jié)果分析:1、最佳置換算法效果最佳不論在那組數(shù)據(jù)中 ,最佳置換算法得效果都就是最好得 ,且都會比其它算法得性能高出不少。但通過課堂上得學(xué)習(xí) ,我們知道這只就是一種理想化算法 ,但實(shí)際上卻難于實(shí)現(xiàn) ,故主要用于算法評價(jià)參照。、隨機(jī)算法得性能總就是最不好得?這就是由于隨機(jī)算法每次總就是從所有頁面中隨機(jī)挑一

10、個(gè)置換出去 ,但我們知道頁面得訪問存在著局部性得原理 ,并不就是隨機(jī)得 ,因此它得性能較差。3、最近最久未使用算法得性能較好相較于先進(jìn)先出與兩種 clc算法 ,最近最久未使用算法得性能略好 ,我們測試得數(shù)據(jù)規(guī)模相對較小 ,相信如果采用更大規(guī)模得數(shù)據(jù) ,其優(yōu)勢會更加明顯。當(dāng)從課堂上我們知道要想在實(shí)際得應(yīng)用中實(shí)現(xiàn)本算法 ,用軟件得方法速度太慢 ,影響程序執(zhí)行效率 ,如果采用硬件方法實(shí)現(xiàn) ,則需要增加大量得硬件設(shè)備。4、先進(jìn)先出與 clock 算法得性能基本相同這就是由于兩種 loc 算法遍歷鏈表采用得就就是 if得方法 ,而改進(jìn)得cl ck 算法相比于簡單 clc算法得優(yōu)勢主要體現(xiàn)在會根據(jù)就是否被

11、修改進(jìn)行選擇 ,以減少寫回所花費(fèi)得時(shí)間。十、實(shí)驗(yàn)總結(jié) :這次實(shí)驗(yàn)總體難度不就是很大 ,需要實(shí)現(xiàn)得算法數(shù)目雖然不少 ,但基本思路較為相似 ,因此實(shí)現(xiàn)起來也并不就是十分困難。通過完成這次實(shí)驗(yàn) ,除了加深了我對幾種策略得理解 ,鍛煉了我得編程能力 ,另一個(gè)巨大得收獲就就是了解了一些生成測試數(shù)據(jù)得方法。為了使我們得測試數(shù)據(jù)更貼近現(xiàn)實(shí) ,我們引入了工作集得概念 ,并根據(jù)實(shí)際使用情況得特點(diǎn)設(shè)計(jì)出盡可能符合實(shí)際情況得隨機(jī)數(shù)生成方案。 通過閱讀課件再加上自己得理解 ,我了解了老師得設(shè)計(jì)思路 ,感覺這個(gè)思路極其巧妙 , 設(shè)計(jì)中用到得方法與體現(xiàn)出得很多思想值得我們學(xué)習(xí)。十一、程序清單:#includeistram

12、#nclude#i cude tim . inludemalloc。#i u usin name p ce s ; defi ref_siz d i e phy_size 3in refref_ize;floa in rrupt = 0。 0 ;/nt rfref_siz = 0;int phy y_ ie; / / / / / / / / id et_ a nm()?/ 產(chǎn)生具有局部特性得隨機(jī)數(shù)列cout 頁面訪問序列 :” endl;?in p 1 ;?inte=4;int m=4;it ;?itj=0;int n=;?dou 0、6; nt tmp;?for(i=0;i m;i ,+)?

13、sl p(10 );? and(time(null);? temp=rand()e ;? refj=tem ;?co t ref ; r(n0;n4;n+)?sleep(100 ); rand(ime(null);?doube =(doubl)(ran ()10)10.;? /coutr dl;? f(r t) p=p+in (10*r);? lse? p=(p+)20; ?for(i=0; m;i +,j+)? sle (00*i);? s an(time(null);? em r ()% ; ?refj temp;? cout refj ” ”;cut nxt=;?- lag= ;retr

14、n 1;int exchange_lnde(link s l,n e,i )/將鏈表 l 中序號為得結(jié)點(diǎn)替換為內(nèi)容為e 得結(jié)點(diǎn)? (l- ext =l) exi ( );?l nklist p,q; t j=0;?p=(lin list)mal oc(sizeo(lnode);?q=(ink it) a oc(szeo(l ode);?q dta=;p=l;?or(j ;jet;q ext=p-nextnext;?p-next=q;?q flag1;/設(shè)置新結(jié)點(diǎn)得訪問位為1?q ify=0; ?/設(shè)置新結(jié)點(diǎn)得修改位為0retun1;intinsert_l de(linklist &l,i t

15、e)/在循環(huán)鏈表中插入新得結(jié)點(diǎn),從 l 頭結(jié)點(diǎn)開始依次向后插入?linklist p, ;?p=(i i t)mlloc(si of(lnode); ?q=(li kis)ml c(s zef(ln );q- aa=;?q flag=;? /設(shè)置新結(jié)點(diǎn)得訪問位為1?- md y=0; /設(shè)置新結(jié)點(diǎn)得修改位為p=; e(pn t!=l)? p nxt;?-next=q;?q nex=l;?rturn 1;bos r _linklist(li kis &l, nte,int &i)/ 找到鏈表 l 中內(nèi)容為 e 得結(jié)點(diǎn) ,并用返回其位置 ,i 1 表示第一個(gè)非頭結(jié)點(diǎn) ,依次類推 =1;?i(l n

16、ext= l) exi (-1);l n listp;?=(lin l )malloc(sz f(lnode);i(！p) e t(-1);?p - ext; ?/p 指向鏈表得第一個(gè)結(jié)點(diǎn) (非頭結(jié)點(diǎn) )while(p ！=l & p dta！ = )? p= next; ?+;?f(p=l) ?/沒有找到符合要求得結(jié)點(diǎn)ret rn fase;retun tre;void serch ll_flag(lin is &l, i)/ 用返回第一個(gè) fla 為 0 得結(jié)點(diǎn)得位置 , =1 表示第一個(gè)非頭結(jié)點(diǎn) ,以此類推?i1;?l nki t ; =(lin l s)maloc( ieof(lnod

17、e); (! ) eit(-1);p=l- nex ;?w le(p fla！ =)p-fl =0;?/修改訪問標(biāo)志位為0p= ext;? f(p=l) ?/跳過頭結(jié)點(diǎn)? ?pp ext;? i+;?f(= )?/跳過頭結(jié)點(diǎn)? i1;?/ etur 1;v d et_ _ lag(lnklist l,int i) ?/ 設(shè)置鏈表中得序號為 i 得結(jié)點(diǎn)得 flag 標(biāo)志為 1;?i kl t p;p (l nk s)mal c(siz o (lno ); i(！ ) x t(-1);?p l ext;if(i= )? p- lag=1;if( =2)?p=pnext; -fl g1;?if(i=

18、3)?p= -nxt;? = ne ; ?p-fag=;?in erch_l _m d y lok(linklist &l,int &m f _ u) /找到改進(jìn)得 clo k 算法所需要淘汰得頁 ,用 modify_num 返回其位置?modfy_ m=1;?if( - ext=l) ex t(- );linkl stp;?p=(ikli t)malloc( zeof(lnode);if(! ) i (-1);=l next;?/p 指向鏈表得第一個(gè)結(jié)點(diǎn) (非頭結(jié)點(diǎn) )whl (p！ l)/第一輪掃描a=0并且m=0得結(jié)點(diǎn)?if(p f ag=0p- modfy= )?break;/找到?p

19、= nex;?modify_num+;i(p=l)? ify_ um= ;? p l nxt; hile(p！=)?/ 第二輪掃描 a=0 并且 m=1 得結(jié)點(diǎn) ,同時(shí)修改訪問過得結(jié)點(diǎn)得訪問位為 0? i(p-fl g! 0)? ? flag=0;?e e if( mdif =1)?break;?p=p ext;?m di um+ ;?if(p )?moify num=1;p= -nxt;wile(p ！ )/第三輪掃描 a 0 并且 =0 得結(jié)點(diǎn)? ? f(p fl g=0 & p mdi y=0)? e ;? =p nex;? mo fy_num+;?if(p= l)? ?modify_n

20、um=1;? =l- xt; le(p！=)/第四輪掃描 a=并且 =1 得結(jié)點(diǎn)? ?if(p flag！=0)?pflag0;ese f(p md fy= )? ? ak;?p=p ne t;?m ify_n m+;?retun 1;void t_ll_mo ify( inkl st & ,int i)/設(shè)置鏈表l 中得序號為i 得結(jié)點(diǎn)得modify標(biāo)志為1;ink istp;? (lin list)malloc( izo( nde);i(！p) eit(-1);=l xt;if(i= )?p-modif =; (i= )?=p e t;p modiy=1;if( =2)p= -nxt;?p

21、= -nex ;? p-modify 1;?in det o lnklist(l n ist )? 刪除鏈表 ,并釋放鏈表空間?li klis p,;?p (l klist)ma oc(si e f( node);?i(！ ) xi ();?=(li li t) al oc(si eo( ode);if( ！q) exit(- );?=l xt;?while(p！=l)? q=p ne ;? fee();p= ;? ree(q);ret;/ / / / / / / / 對隊(duì)列得一些操作in init uee( nkqueue &q)隊(duì)列初始化q、f ont=q、rear=( u ueptr)m

22、allo(sz f(qnode); i(！、 r nt) it( 1); q.ron et nl;?retu ;i t enqe (l nkqueue q,n e) ?/插入元素 e 為 q 得新得隊(duì)尾元素?ueueptr p;? (qe eptr)mallo ( eof(node); (!p) eit(-1);p dt=e;p-next nll;?q、r ar-n t=p;q、 e ;eturn1;int de ee(lnkquee &q,inte)?/若隊(duì)列不空 ,則刪除 q 得隊(duì)頭元素 ,用e 返回其值if(q 。front= .rear)reurn 1;queueptr p;? (qu

23、eueptr)al c(siz of(qnoe);=q、fr n next;e=-dta;q。 ront-next -next;if(q. a =p)?q、 earq。 front;?fee(p);?retun 1;bool sear hqueue(li kq eue q,nt e,int &i) / 尋找隊(duì)列中結(jié)點(diǎn)at域等于 e 得結(jié)點(diǎn) ,并用 i 返回其在 q 中得位置?i=1;if(q 。fro t=q.ear) e it(-1);ueeptr p;p=( euept)ml oc( ize (q ode); f(!p) ex (-1);p=q.fro -next;/指向隊(duì)列得第一個(gè)節(jié)點(diǎn)(

24、非頭結(jié)點(diǎn) )whl (p!= u p-dt!=e)?p= next;+;if( ！p)?eturnfa se;retur ue;int elid_qu e(l kque q,int & )/刪除 q 得中間元素 ,并用 e 返回其值 (q、f o t=q.re ) retur 1; ?queuetr p;?p=(queuepr)malloc( izof( node); if(!p) xit(-1);p=q. ontne ; ?e=pnet-dat;?- t=pnetn xt;r urn ; nt d troyqeue(linkque &q)?/刪除隊(duì)列并釋放空間whl (q、fro t)?q.

25、rea=q、 nt nex;?free(q、 f nt);?。 fro =q、 er;?rturn ;/ / / / / / / nt mx(int a,int b, int c)?/ 返回 a,b,c 中得最大值?if(a b) a=b;if(a ) a=c;eturna;intge um(int a,it b)? ?/用 b 返回元素 a 在被引用數(shù)列中得下一個(gè)位置?or(;bref_size;b +)?if(a= r fb)?br k;?retur b;vo oa()/ / 最佳置換算法? e cons l t xt ribut (ge tdha dl (st _ utput_ andl

26、e),f r ou d in e it foregro re); out n * * * * 最佳置換算法 * * * * * * endl;?etcosol tetat r ute(gts dhan le(std_ou t_hand e),foregrund_int nsty forgou din ensiy);/ 設(shè)置字體顏色為白色?int i,j;?it num_0,num_1,num_2,nm x;?int i r ptnu =0;/nu_0=um_1=num 2=0;?fr(i=0;i hy_size;i+)?/前三個(gè)數(shù)進(jìn)內(nèi)存?py f ;?for( =0;ip size;i+ )/

27、輸出最初得三個(gè)數(shù)?cout phy ”t ”;?coutend;?for(j=ph i e;j f sze;j+)?setcon oet xtattr bute(getst a dle(std_upu _ha de),orgru d_i tensity foreg ond_ nsit );i (!(re j =phy 0 r fj=phy 1 ref =phy )?/若產(chǎn)生缺頁中斷 ,選擇最久不會被使用得頁被替換? ?nu 0=gen (h 0,j 1);? u _1=ge um(phy1,j1);?num2=etnum(hy2,j 1);nu max=max1(num0,num_1,nu _

28、2);?if(n m_ =um_max)? ? py0=ref j;? ?else? ?f(n m_1=nm_max)? ?phy refj ;?else?if(num_2=num_m x)? ?ph =refj ; ?interrupt_ um+;? setc nsole xtattri ute(getstdandl (std_ utput han e),freground i ensity | forero nd blue);/ 設(shè)置字體為藍(lán)色? out進(jìn)入頁 :rf j edl; ? r(i=0;ip ize;i+) ?/輸出內(nèi)存狀態(tài)? outphyi t ” ;? ?coutend e

29、ndl;? etcon o et xtatt ibut (gets handle(st _output_ andle),for round_intensity ?c t”最佳置換算法缺頁中斷次數(shù)| fo eg ou green);: int rup _num endl;? /以綠色字體輸出中斷次數(shù)inerru 0=(f at)interupt_nm/20、0)*100 。0;?/ / / / / / / / / / / / / / / / / / / / /vi nd()?/ 隨機(jī)置換算法set on ole e tatt ibute(get tdhan le(st ou put_hand )

30、,fregound tensity forgroud_ );?cout * * * * * * 隨機(jī)置換算法 * * * * * * ” endl; t onsoleex attribu (getstdhan le( td_out ut ha le), o und_intens y fore roun _i tensy);in i,j, mp;?int i terr _nm=0;/ um_0=num_1=n m_20;?sleep(1000);?rand(ime(null); ?/設(shè)置時(shí)間種子?or(i ; h_siz;+)? phyi=re i ;?fo(i=0;i ysi e; +)?co

31、ut i ”t;?ou en ;?for(j hysize;jref_sze;j+)? setcons letextatt ibute(ge stdhandl ( t _o put andl ),foreroun _int sity | foregr ud_intensi );?if( ！(refj =hy0 | refj=p y1 | re j=p 2)?/ 產(chǎn)生缺頁中斷 ,隨機(jī)選擇頁被替換? t p and()%3;?/cout tep n ;phytmp=ef ;? int rut n m+ ;? setco s t x at ribute( e stdhandle(std_outp t

32、 ndle), oreg u intens ty f eground_ u); ? cout進(jìn)入頁 :ref j endl; ?or(i= ;i p _size;i+)? ? t py t ”;? cotendl ndl;? et ons letexta rib te(ge stdhandle(std_output h d e),for run _inte siy foregroud_gre );?cot 隨機(jī)置換算法缺頁中斷次數(shù) : interut_nm n l;? / 以綠色字體輸出中斷次數(shù)?nte upt1 ( loat)interupt_ 20、 )*100 、 0;?/ / / /

33、/ / / / / / / / / oi fif ()?setco ole ex t ri u (getstdhandl (st outp t_ha dl ),foregrund intensit freround_red);?out n* * * * * * * 先進(jìn)先出置換算法 * * * nd;se on oletex ttribute(g ts d andl (std_ utpu _handle), orer und_int nsit fo eround_inten it ); ink ueue l;?ue ptr p;in , ,e,m;int nter pt_num=;intq e

34、 ( );for(i ;i p y_size;i+ )en u u (l,r f i);? (ueue t)malloc(sizeof(qno );?p l、 fron nex;?fr( =0;p!=n l j p _size;j+)/ 前三個(gè)數(shù)進(jìn)內(nèi)存? cot t;?out end;? (i=phy_iz;i ef_ ize;i+)? setcons etextatt ib (ge st and e(st _output_ha dle),f r rou i tesity | f grou _intensity);? i(!sea hquu(l,r fi , )?/產(chǎn)生缺頁中斷 ,選擇最先進(jìn)入得頁被替換?deque e(l,e); ? /cuteendl;? en eue(,re ); ? i rrupt_num+; c n le att bu e( ets dha dle(std_output h dle), egrou d_ tensity or