請(qǐng)求頁(yè)式管理中的頁(yè)面置換算法性能分析

1、請(qǐng)求頁(yè)式管理中的頁(yè) 面置換算法性能分析指導(dǎo)老師： 余宏生組 員：鄧祥鐳201041210123殷蝶 201041210124柯希杰 201041210125石賢主 201041210126尚晨曦 201041210141請(qǐng)求頁(yè)式管理中的頁(yè)面置換算法性能分析（湖北理工學(xué)院，黃石435000）摘要：隨著虛擬存儲(chǔ)技術(shù)在操作系統(tǒng)中的應(yīng)用，大大提高了操作系統(tǒng)的性能，其 中頁(yè)面置換算法是虛擬存儲(chǔ)管理的重要組成局部，頁(yè)面置換算法的優(yōu)劣將直接影 響系統(tǒng)的整體性能。隨著大量有著不同讀寫(xiě)速度的外存設(shè)備共存于系統(tǒng)中，單一 置換算法同樣影響著系統(tǒng)的整體性能。關(guān)鍵詞：操作系統(tǒng)；虛擬存儲(chǔ)；頁(yè)面置換；算法The reque

2、st paging page replacement algorithm performanceanalysisAbstract： With virtual storage technology in the application of the operating system, greatly improve the performance of the operating system, including page replacement algorithm is an important part of virtual storage management page replacem

3、ent algorithm quality will directly affect the overall performance of the system. As the speed of read and write a lot of different peripheral storage devices coexist in the system, a single replacement algorithm also affects the overall performance of the system.Keyword： Operating stystem； Virtual

4、storage； Page replacement； Algorithm1、引言虛擬存儲(chǔ)器的實(shí)現(xiàn)是建立在離散分 配存儲(chǔ)管理方式的基礎(chǔ)上的，一般采 用分頁(yè)請(qǐng)求系統(tǒng)或分段請(qǐng)求系統(tǒng)來(lái)實(shí) 現(xiàn)。分頁(yè)（段）請(qǐng)求系統(tǒng)是在分頁(yè)（段） 系統(tǒng)的基礎(chǔ)上，增加了請(qǐng)求調(diào)頁(yè)（段） 功能、頁(yè)面（分段）置換功能所形成 的頁(yè)（段）式虛擬存儲(chǔ)器系統(tǒng)。它允 許只裝入假設(shè)干頁(yè)面（分段）的用戶(hù)程 序和數(shù)據(jù)（而非全部程序和數(shù)據(jù)），便 可以啟動(dòng)運(yùn)行。以后，再通過(guò)調(diào)頁(yè)（段） 功能及頁(yè)面（分段）置換功能，把所 需要的頁(yè)面（分段）調(diào)入內(nèi)存，同時(shí) 把暫時(shí)不運(yùn)行的頁(yè)面（分段）換出到 外存上，置換時(shí)以頁(yè)面（分段）為單 位。在請(qǐng)求分頁(yè)式系統(tǒng)中，每當(dāng)所要

5、訪(fǎng) 問(wèn)的頁(yè)面不在內(nèi)存時(shí)，便要產(chǎn)生一缺 頁(yè)中斷，請(qǐng)求操作系統(tǒng)將所缺之頁(yè)面 調(diào)入內(nèi)存。假設(shè)內(nèi)存已無(wú)空間時(shí)，為了 保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從 內(nèi)存中調(diào)出一個(gè)頁(yè)面，但應(yīng)該將哪個(gè) 頁(yè)面調(diào)出，那么必須根據(jù)一定的算法來(lái) 確定。通常，把選擇換出頁(yè)面的算法 稱(chēng)為頁(yè)面置換算法（Page_Replacement Algorithms） o一個(gè)好的頁(yè)面置換算法，應(yīng)具有較 低的頁(yè)面更換頻率。從理論上講，應(yīng) 將那些以后不再會(huì)訪(fǎng)問(wèn)的頁(yè)面換出， 或?qū)⒛切┰谳^長(zhǎng)時(shí)間內(nèi)不會(huì)再訪(fǎng)問(wèn)的 頁(yè)面調(diào)出。2、傳統(tǒng)的頁(yè)面置換算法傳統(tǒng)的頁(yè)面置換算法主要有FIFO（First In First Out ，先進(jìn)先出）、最正確 置換算法（Opt

6、imal）、LRU （ Least Recently Used,最近最久未使用）和 LFU （Least Frequently Used,最近最少使用）等算法。先進(jìn)先出（FIFO）頁(yè)面置換算法這是最早出現(xiàn)的置換算法。該算法 總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選 擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以 淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn) 程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈 接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱(chēng) 為替換指針，使它總是指向最老的頁(yè) 面。但它所依據(jù)的條件是各個(gè)頁(yè)面調(diào) 入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并 不能反映頁(yè)面的使用情況，故此算法 性能一般較差。最正確置換算法OPT（Optimal）它是由Belady

7、于1966年提出的一 種理論上的算法。其所選擇的被淘汰 頁(yè)面，將是以后永不使用的或者是在 最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪(fǎng)問(wèn)的頁(yè)面。 采用最正確置換算法，通?？杀ＷC獲得 最低的缺頁(yè)率。但由于人目前還無(wú)法 預(yù)知一個(gè)進(jìn)程在內(nèi)存的假設(shè)干個(gè)頁(yè)面 中，哪一個(gè)頁(yè)面是未來(lái)最長(zhǎng)時(shí)間內(nèi)不 再被訪(fǎng)問(wèn)的，因而該算法是無(wú)法實(shí)現(xiàn) 的，便可以利用此算法來(lái)評(píng)價(jià)其它算 法。最近最久未使用（LRU）置換算 法最近最久未使用（LRU）置換算法， 是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn) 行決策的。由于無(wú)法預(yù)測(cè)各頁(yè)面將來(lái) 的使用情況，只能利用“最近的過(guò)去” 作為“最近的將來(lái)”的近似，因此， LRU置換算法是選擇最近最久未使用 的頁(yè)面予以淘汰。但

8、是頁(yè)面的過(guò)去和 未來(lái)的走向之間并無(wú)必然的聯(lián)系。最近最少使用（LFU）置換算法LFU頁(yè)面置換算法假定在一段時(shí) 間內(nèi)訪(fǎng)問(wèn)頻率較高的頁(yè)面與那些訪(fǎng)問(wèn) 頻率較低的頁(yè)面相比，更有可能在不 遠(yuǎn)的將來(lái)被訪(fǎng)問(wèn)，因而選擇在一段時(shí)間內(nèi)訪(fǎng)問(wèn)頻率較低的頁(yè)面予以淘汰， 即將最近時(shí)期使用最少的頁(yè)面作為淘 汰頁(yè)。3、程序清單參考實(shí)驗(yàn)步驟如下：include stdio.h” char find(int j); int findo(int j); int l(int j);intqueye;double queyelu;char z=%；chara420=7,0,T；270,3；0；4；2,3,0 ,32T；2”,T7OT;/

9、char a;void fifo()/先進(jìn)先出算法int i=2,mj;queye=1;a10=a00;for(j=1 ;j3)i=1;if(fjnd(j)=,F)/調(diào)用查找函數(shù)(aij=aOj;for(m=1 ;m4;m+)if(m!=i)amj=amU-1; queye=queye+1;i+1;) else (a1j=a1U-1;a2U=a2j-1;a3U=a30-1；)for(i=0;i4;i+) 輸出序列for0=O;j=3 & (a0j=a1j-1 | a0D=a2U-1 | aO0=a3D-1)return (T);elsereturnfF);)void opt()/OPT 置換算

10、法(inta10=a00;/a11=a00;for(j=1;j3;j+)(for(i=1 ;ij+2;i+)if(H)=1)aij=aOj;elseaij=aij-1;)queye=3;for(j=3;j20;j+)(if(find(j)=,F,)(t=findo(j);/ printf(nn%dnHJt);for(m=1 ;m4;m+) if(m!=t)amj=amj-1;/ aij=ai-1j;atU=aOj;queye=queye+1;else(a1j=a1j-1;a2U=a2j-1;a3U=a3U-1;)for(i=0;i4;i+) 輸出序列(for(j=0;jj;m-)(if (a1

11、j-1=a0m)x=m;if (a2j-1=a0m)y=m;if (a3D-1=a0m)z=m;)/max=x;t=1;if (yx & yz)t=2;if(zx & zy)t=3;return (t);void lru() /LRU 置換算法void lru() /LRU 置換算法queye=queye+1;int ujj;int k;a10=a00;/a11=a00;for(j=1 ;j3;j+)(for(i=1 ;ij+2;i+)if(H)=1)aij=aOj;elseaij=aij-1;)queye=3;for G=3;j0;i-)(if(i!=u) akj=aij-1;k=k-1;)

12、a3D=a0j;)elsefor(i=0;i4;i+) 輸出序列(for(j=0;j20;j+)(printf(%c -);)printf(HnH);)queyelu=queye*100/20;printf (缺頁(yè)率：%4.1 f%cnn3queyelu,z);intl(intj)查找要替換的位置(if (a0j=a1U-1)return(1);if (a0D=a2j-1)return(2);if (a0j=a3j-1)return(3);void main()(printf(先進(jìn)先出算法:n)卅。()；printf(最正確置換OPT算法佳) opt()；printf(nLRU 算法:n”)；

13、 lru();for(i=1 ;i3;i+)4.對(duì)不同算法的性能進(jìn)行評(píng)價(jià)。FIFO算法較易實(shí)現(xiàn)，對(duì)具有線(xiàn)性 順序特征的程序比擬適用，而對(duì)具有 其他特征的程序那么效率不高，此算法 還可能出現(xiàn)抖動(dòng)現(xiàn)象(Belady)異常。 LRU算法基于程序的局部性原理，所 以適用用大多數(shù)程序，此算實(shí)現(xiàn)必須 維護(hù)一個(gè)特殊的隊(duì)列一一頁(yè)面淘汰隊(duì) 列。OPT算法雖然產(chǎn)生的缺頁(yè)數(shù)最少， 然而，卻需要預(yù)測(cè)程序的頁(yè)面引用串， 這是無(wú)法預(yù)知的，不可能對(duì)程序的運(yùn) 行過(guò)程做出精確的斷言，不過(guò)此理論 算法可用做衡量各種具體算法的標(biāo) 準(zhǔn)。5、結(jié)論本文首先對(duì)虛擬存儲(chǔ)器存在的基 本原理進(jìn)行了分析，知道分頁(yè)系統(tǒng)存 在的可能性。然后對(duì)傳統(tǒng)的幾種頁(yè)面 置換算法進(jìn)行了介紹，利用編寫(xiě)的程 序分析各自的性能，比擬得出了每種 算法的優(yōu)點(diǎn)和缺點(diǎn)。參考文獻(xiàn)：11操作系統(tǒng)清華大學(xué)出版社6、附錄(程序運(yùn)行結(jié)果)0 17 0 10 17 0 10 0 7 7 71110 0先進(jìn)先出算法:7 0 1 2 0 3 07 7 7 2 2 2 2缺頁(yè)率：75.0Z隱佳亶換OPT算法:0 12