操作系統(tǒng)-頁面置換算法課件

第一章1操作系統(tǒng)引論5.3

頁面置換算法在進程運行過程中，若其所要訪問的頁面不在內(nèi)存，而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時，為了保證該進程能正常運行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或數(shù)據(jù)送到磁盤的對換區(qū)中。但應(yīng)將哪個頁面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁面的算法稱為頁面置換算法

(Replacement

Algorithms)。置換算法的好壞將直接影響到系統(tǒng)的性能。第一章 操作系統(tǒng)引論25.3.1

最佳置換算法和先進先出置換算法1. 最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面將是以后永不使用的，或許是

在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法

通?？杀ＷC獲得最低的缺頁率。但由于人們目前還無法預(yù)知，一個進程在內(nèi)存的若干個頁面中，哪一個頁面是未來最長時

間內(nèi)不再被訪問的，因而該算法是無法實現(xiàn)的，但可以利用

該算法去評價其它算法。第一章操作系統(tǒng)引論圖5-3利用最佳頁面置換算法時的置換圖3第一章 操作系統(tǒng)引論42. 先進先出(FIFO)頁面置換算法FIFO算法是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以

淘汰。該算法實現(xiàn)簡單，只需把一個進程已調(diào)入內(nèi)存的頁面

按先后次序鏈接成一個隊列，并設(shè)置一個指針，稱為替換指

針，使它總是指向最老的頁面。但該算法與進程實際運行的

規(guī)律不相適應(yīng)，因為在進程中，有些頁面經(jīng)常被訪問，比如，含有全局變量、常用函數(shù)、例程等的頁面，F(xiàn)IFO算法并不能保證這些頁面不被淘汰。第一章操作系統(tǒng)引論圖5-4

利用FIFO置換算法時的置換圖5第一章 操作系統(tǒng)引論65.3.2

最近最久未使用和最少使用置換算法1.

LRU(Least

Recently Used)置換算法的描述FIFO置換算法的性能之所以較差，是因為它所依據(jù)的條件是各個頁面調(diào)入內(nèi)存的時間，而頁面調(diào)入的先后并不能反映頁面的使用情況。最近最久未使用(LRU)的頁面置換算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況做出決策的。第一章操作系統(tǒng)引論圖5-5LRU頁面置換算法7第一章 操作系統(tǒng)引論82. LRU置換算法的硬件支持1)寄存器為了記錄某進程在內(nèi)存中各頁的使用情況，須為每個在內(nèi)存中的頁面配置一個移位寄存器，可表示為R

=

Rn-1Rn-2Rn-3

…

R2R1R0第一章 操作系統(tǒng)引論9當(dāng)進程訪問某物理塊時，要將相應(yīng)寄存器的Rn-1位置成

1。此時，定時信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么，具有最小數(shù)值的寄存器所對應(yīng)的頁面，就是最近最久未使用的頁面。第一章操作系統(tǒng)引論圖5-6

某進程具有8個頁面時的LRU訪問情況10第一章 操作系統(tǒng)引論112)?？衫靡粋€特殊的棧保存當(dāng)前使用的各個頁面的頁面號。每當(dāng)進程訪問某頁面時，便將該頁面的頁面號從棧中移出，

將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，

而棧底則是最近最久未使用頁面的頁面號。假定現(xiàn)有一進程，它分有五個物理塊，所訪問的頁面的頁面號序列為：4，7，0，7，1，0，1，2，1，2，6第一章操作系統(tǒng)引論圖5-7用棧保存當(dāng)前使用頁面時棧的變化情況12第一章 操作系統(tǒng)引論133. 最少使用(Least

Frequently Used，LFU)置換算法在采用LFU算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。第一章 操作系統(tǒng)引論145.3.3 Clock置換算法1. 簡單的Clock置換算法當(dāng)利用簡單Clock算法時，只需為每頁設(shè)置一位訪問位，再將內(nèi)存中的所有頁面都通過鏈接指針鏈接成一個循環(huán)隊列。第一章操作系統(tǒng)引論圖5-8簡單Clock置換算法的流程和示例15第一章 操作系統(tǒng)引論162. 改進型Clock置換算法在將一個頁面換出時，如果該頁已被修改過，便須將該頁重新寫回到磁盤上；但如果該頁未被修改過，則不必將它拷回磁盤。換而言之，對于修改過的頁面，在換出時所付出的開銷比未修改過的頁面大，或者說，置換代價大。在改進型Clock算法中，除須考慮頁面的使用情況外，還須再增加一個因素——置換代價。第一章 操作系統(tǒng)引論175.3.4 頁面緩沖算法(Page

Buffering

Algorithm，PBA)1.

影響頁面換進換出效率的若干因素頁面置換算法。寫回磁盤的頻率。讀入內(nèi)存的頻率。第一章 操作系統(tǒng)引論182. 頁面緩沖算法PBAPBA算法的主要特點是：①顯著地降低了頁面換進、換出的頻率，使磁盤I/O的操作次數(shù)大為減少，因而減少了頁面換進、換出的開銷；②正是由于換入換出的開銷大幅度減小，才能使其采用一種較簡單的置換策略，如先進先出(FIFO)算法，它不需要特殊硬件的支持，實現(xiàn)起來非常簡單?？臻e頁面