1、請求頁式管理中的頁請求頁式管理中的頁面置換算法性能分析面置換算法性能分析指導(dǎo)老師：指導(dǎo)老師：余余 宏宏 生生組組員：員：鄧祥鐳鄧祥鐳 201041210123殷殷嶸嶸 201041210124柯希杰柯希杰 201041210125石賢主石賢主 201041210126尚晨曦尚晨曦 201041210141請求頁式管理中的頁面置換算法性能分析請求頁式管理中的頁面置換算法性能分析（湖北理工學院，黃石 435000）摘要摘要：隨著虛擬存儲技術(shù)在操作系統(tǒng)中的應(yīng)用，大大提高了操作系統(tǒng)的性能，其中頁面置換算法是虛擬存儲管理的重要組成部分， 頁面置換算法的優(yōu)劣將直接影響系統(tǒng)的整體性能。隨著大量有著不同讀寫速

2、度的外存設(shè)備共存于系統(tǒng)中，單一置換算法同樣影響著系統(tǒng)的整體性能。關(guān)鍵詞：關(guān)鍵詞：操作系統(tǒng)；虛擬存儲；頁面置換；算法The request paging page replacement algorithm performanceanalysisAbstract：With virtual storage technology in the applicationof the operating system, greatly improve the performance of theoperating system, including page replacement algorithm i

3、s animportant part of virtual storage management page replacementalgorithm quality will directly affect the overall performance ofthe system. As the speed of read and write a lot of differentperipheral storage devices coexist in the system, a singlereplacement algorithm also affects the overall perf

4、ormance ofthe system.Keyword：Operating stystem；Virtual storage；Page replacement；Algorithm1、引言、引言虛擬存儲器的實現(xiàn)是建立在離散分配存儲管理方式的基礎(chǔ)上的，一般采用分頁請求系統(tǒng)或分段請求系統(tǒng)來實現(xiàn)。 分頁 （段） 請求系統(tǒng)是在分頁 （段）系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁（段）功能、頁面（分段）置換功能所形成的頁（段）式虛擬存儲器系統(tǒng)。它允許只裝入若干頁面（分段）的用戶程序和數(shù)據(jù)（而非全部程序和數(shù)據(jù)） ，便可以啟動運行。 以后， 再通過調(diào)頁 （段）功能及頁面（分段）置換功能，把所需要的頁面（分段）調(diào)入內(nèi)存，同

5、時把暫時不運行的頁面（分段）換出到外存上，置換時以頁面（分段）為單位。在請求分頁式系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存時，便要產(chǎn)生一缺頁中斷，請求操作系統(tǒng)將所缺之頁面調(diào)入內(nèi)存。若內(nèi)存已無空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一個頁面，但應(yīng)該將哪個頁面調(diào)出，則必須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法(Page_ReplacementAlgorithms)。一個好的頁面置換算法， 應(yīng)具有較低的頁面更換頻率。從理論上講，應(yīng)將那些以后不再會訪問的頁面換出，或?qū)⒛切┰谳^長時間內(nèi)不會再訪問的頁面調(diào)出。2、傳統(tǒng)的頁面置換算法傳統(tǒng)的頁面置換算法傳統(tǒng)的頁面置換算法主要有

6、 FIFO（First In First Out，先進先出） 、最佳置換算法（Optimal） 、LRU（LeastRecently Used，最近最久未使用）和LFU（Least Frequently Used，最近最少使用）等算法。2.1、先進先出、先進先出(FIFO)頁面置換算法頁面置換算法這是最早出現(xiàn)的置換算法。 該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進程已調(diào)入內(nèi)存的頁面，按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指針，使它總是指向最老的頁面。但它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的

7、使用情況，故此算法性能一般較差。2.2、最佳置換算法、最佳置換算法 OPT(Optimal)它是由 Belady 于 1966 年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的或者是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通常可保證獲得最低的缺頁率。但由于人目前還無法預(yù)知一個進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。2.3、最近最久未使用（、最近最久未使用（LRU）置換算）置換算法法最近最久未使用（LRU）置換算法，是根據(jù)頁面調(diào)入內(nèi)存后的使用情況進行決策的。由于無法預(yù)測各頁面將來的

8、使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU 置換算法是選擇最近最久未使用的頁面予以淘汰。但是頁面的過去和未來的走向之間并無必然的聯(lián)系。2.4、最近最少使用（、最近最少使用（LFU）置換算法）置換算法LFU 頁面置換算法假定在一段時間內(nèi)訪問頻率較高的頁面與那些訪問頻率較低的頁面相比，更有可能在不遠的將來被訪問，因而選擇在一段時間內(nèi)訪問頻率較低的頁面予以淘汰，即將最近時期使用最少的頁面作為淘汰頁。3、程序清單程序清單參考實驗步驟如下：#include stdio.hchar find(int j);int findo(int j);int l(int j);int qu

9、eye;double queyelu;char z=%;chara420=7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1;/char a;void fifo()/先進先出算法 int i=2,m,j;queye=1;a10=a00;for(j=1;j3)i=1;if (find(j)=F)/調(diào)用查找函數(shù)aij=a0j;for(m=1;m4;m+)if(m!=i)amj=amj-1; queye=queye+1;i=i+1;elsea1j=a1j-1;a2j=a2j-1;a3j=a3j-1;for(i=0;i4;i+)/輸出序列for(j=0;j=3 &

10、(a0j=a1j-1 |a0j=a2j-1 | a0j=a3j-1)return (T);elsereturn(F);void opt()/OPT 置換算法int i,j,m,t;a10=a00;/a11=a00;for(j=1;j3;j+)for(i=1;ij+2;i+) if(i-j)=1)aij=a0j;elseaij=aij-1;queye=3;for(j=3;j20;j+)if(find(j)=F)t=findo(j);/ printf(n%dn,t);for(m=1;m4;m+)if(m!=t)amj=amj-1; / aij=ai-1j;atj=a0j;queye=queye+1

11、;elsea1j=a1j-1;a2j=a2j-1;a3j=a3j-1;for(i=0;i4;i+)/輸出序列for(j=0;jj;m-)if (a1j-1=a0m)x=m;if (a2j-1=a0m)y=m;if (a3j-1=a0m)z=m;/max=x;t=1;if (yx & yz)t=2;if(zx & zy)t=3;return (t);void lru()/LRU 置換算法int u,j,i;int k;a10=a00;/a11=a00;for(j=1;j3;j+)for(i=1;ij+2;i+) if(i-j)=1)aij=a0j;elseaij=aij-1;qu

12、eye=3;for (j=3;j0;i-)if(i!=u)akj=aij-1;k=k-1;a3j=a0j;elsefor(i=1;i3;i+)aij=ai+1j-1;a3j=a0j;queye=queye+1;for(i=0;i4;i+)/輸出序列for(j=0;j20;j+)printf(%c ,aij);printf(n);queyelu=queye*100/20;printf(缺頁率：%4.1f%cn,queyelu,z);int l(int j)/查找要替換的位置if (a0j=a1j-1)return(1);if (a0j=a2j-1)return(2);if (a0j=a3j-1)return(3);void main()printf(先進先出算法:n);fifo();printf(最佳置換 OPT 算法:n);opt();printf(LRU 算法:n);lru();4 4對不同算法的性能進行評價。對不同算法的性能進行評價。FIFO 算法較易實現(xiàn)，對具有線性順序特征的程序比較適用，而對具有其他特征的程序則效率不高，此算法還可能出現(xiàn)抖動現(xiàn)象（Belady）異常。LRU 算法基于程序的局部性原理，所以適用用大多數(shù)程序，此算實現(xiàn)必須維護一個特殊的隊列頁面淘汰隊列。 OPT 算法雖然產(chǎn)生的缺頁數(shù)最少，