C語言中文網
首頁 > 編程筆記 > 操作系統筆記 閱讀:1,972

頁面置換算法及其優缺點詳解

本節,討論幾種頁面置換算法。為此,假設有 3 個幀并且引用串為:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

FIFO頁面置換

FIFO 算法是最簡單的頁面置換算法。FIFO 頁面置換算法為每個頁面記錄了調到內存的時間,當必須置換頁面時會選擇最舊的頁面。

注意,并不需要記錄調入頁面的確切時間,可以創建一個 FIFO 隊列,來管理所有的內存頁面。置換的是隊列的首個頁面。當需要調入頁面到內存時,就將它加到隊列的尾部。

對于樣例引用串,3 個幀開始為空。首次的 3 個引用(7,0,1)會引起缺頁錯誤,并被調到這些空幀。之后將調入這些空閑幀。

下一個引用(2)置換 7,這是因為頁面 7 最先調入。由于 0 是下一個引用并且已在內存中,所以這個引用不會有缺頁錯誤。

對 3 的首次引用導致頁面 0 被替代,因為它現在是隊列的第一個。因為這個置換,下一個對 0 的引用將有缺頁錯誤,然后頁面1被頁面0置換。該進程按圖 1 所示方式繼續進行。每當有缺頁錯誤時,圖 1 顯示了哪些頁面在這三個幀中。總共有 15 次缺頁錯誤。

FIFO頁面置換算法
圖 1 FIFO頁面置換算法

FIFO 頁面置換算法易于理解和編程。然而,它的性能并不總是十分理想。一方面,所置換的頁面可以是很久以前使用過但現已不再使用的初始化模塊。另一方面,所置換的頁面可以包含一個被大量使用的變量,它早就初始化了,但仍在不斷使用。

注意,即使選擇正在使用的一個頁面來置換,一切仍然正常工作。在活動頁面被置換為新頁面后,幾乎立即發生缺頁錯誤,以取回活動頁面。某個其他頁面必須被置換,以便將活動頁面調回到內存。因此,選擇不當的置換增加缺頁錯誤率,并且減慢處理執行。然而,它不會造成執行不正確。

為了說明使用 FIFO 頁面置換算法可能出現的問題,假設如下引用串:

1,2,3,4,1,2,5,1,2,3,4,5

圖 2 為這個引用串的缺頁錯誤數量與可用幀數量的曲線。4 幀的缺頁錯誤數(10)比 3 幀的缺頁錯誤數(9)還要大!這個最意想不到的結果被稱為 Belady 異常,即對于有些頁面置換算法,隨著分配幀數量的增加,缺頁錯誤率可能會增加,雖然我們原本期望為一個進程提供更多的內存可以改善其性能。

一個引用串的FIFO置換的缺頁錯誤曲線
圖 2 一個引用串的FIFO置換的缺頁錯誤曲線

最優頁面置換

發現 Belady 異常的一個結果是尋找最優頁面置換算法,這個算法具有所有算法的最低的缺頁錯誤率,并且不會遭受 Belady 異常。這種算法確實存在,它被稱為 OPT MIN。該算法的思想是:置換最長時間不會使用的頁面。

這種頁面置換算法確保對于給定數量的幀會產生最低的可能的缺頁錯誤率。

例如,針對示例引用串,最優置換算法會產生 9 個缺頁錯誤,如圖 3 所示。

最優置換算法
圖 3 最優置換算法

頭 3 個引用會產生缺頁錯誤,以填滿 3 個空閑幀。對頁面 2 的引用會置換頁面 7,因為頁面 7 直到第 18 次引用時才使用,頁面 0 在第 5 次引用時使用,頁面 1 在第 14 次引用時使用。對頁面 3 的引用會置換頁面 1,因為頁面 1 是位于內存的 3 個頁面中最后被再次引用的頁面。

有 9 個缺頁錯誤的最優頁面置換算法要好于有 15 個缺頁錯誤的 FIFO 置換算法(如果我們忽略前 3 個,這是所有算法都會遭遇的,那么最優置換要比 FIFO 置換好一倍)。事實上,沒有置換算法能夠只用 3 個偵并且少于 9 個缺頁錯誤,就能處理樣例引用串。

然而,最優置換算法難以實現,因為需要引用串的未來知識。因此,最優算法主要用于比較研究。例如,如果知道一個算法不是最優,但是與最優相比最壞不差于 12.3%,平均不差于 4.7%,那么也是很有用的。

LRU頁面置換

如果最優算法不可行,那么最優算法的近似或許成為可能。FIFO 和 OPT 算法的關鍵區別在于,除了在時間上向后或向前看之外,FIFO 算法使用的是頁面調入內存的時間,OPT 算法使用的是頁面將來使用的時間。

如果我們使用最近的過去作為不遠將來的近似,那么可以置換最長時間沒有使用的頁。這種方法稱為最近最少使用算法

LRU 置換將每個頁面與它的上次使用的時間關聯起來。當需要置換頁面時,LRU選擇最長時間沒有使用的頁面。這種策略可當作在時間上向后看而不是向前看的最優頁面置換算法。

奇怪的是,如果 SR 表示引用串 S 的倒轉,那么針對 S 的 OPT 算法的缺頁錯誤率與針對 SR 的 OPT 算法的缺頁錯誤率是相同的。類似地,針對 S 的 LRU 算法的缺頁錯誤率與針對 SR 的 LRU 算法的缺頁錯誤率相同。

LRU頁面置換算法
圖 4 LRU頁面置換算法

將 LRU 置換應用于樣例引用串的結果,如圖 4 所示。LRU 算法產生 12 次缺頁錯誤。 注意,頭 5 個缺頁錯誤與最優置換一樣。然而,當頁面 4 的引用出現時,由于在內存的 3 個幀中,頁面 2 最近最少使用,因此,LRU 算法置換頁面 2,而并不知道頁面 2 即將要用。

接著,當頁面 2 出錯時,LRU 算法置換頁面 3,因為位于內存的 3 個頁中,頁面 3 最近最少使用。盡管會有這些問題,有 12 個缺頁錯誤的 LRU 置換仍然要好于有 15 個缺頁錯誤的 FIFO 置換。

LRU 策略通常用作頁面置換算法,并被認為是不錯的策略。它的主要問題是如何實現 LRU 置換。LRU 頁面置換算法可能需要重要的硬件輔助。它的問題是,確定由上次使用時間定義的幀的順序。兩個實現是可行的。

第一種方法是使用計數器:在最簡單的情況下,為每個頁表條目關聯一個使用時間域,并為 CPU 添加一個邏輯時鐘或計數器。每次內存引用都會遞增時鐘。每當進行頁面引用時,時鐘寄存器的內容會復制到相應頁面的頁表條目的使用時間域。

這樣,我們總是有每個頁面的最后引用的“時間”,我們置換具有最小時間的頁面。這種方案需要搜索頁表以查找 LRU 頁面,而且每次內存訪問都要寫到內存(到頁表的使用時間域)。當頁表更改時(由于 CPU 調度),還必須保留時間。時鐘溢出也要考慮。

實現 LRU 置換的另一種方法是采用頁碼堆棧。每當頁面被引用時,它就從堆棧中移除并放在頂部。這樣,最近使用的頁面總是在堆棧的頂部,最近最少使用的頁面總是在底部(圖 5)。因為必須從堆棧的中間刪除條目,所以最好通過使用具有首指針和尾指針的雙向鏈表來實現這種方法。

采用堆棧記錄最近頁面引用
圖 5 采用堆棧記錄最近頁面引用

這樣,刪除一個頁面并放在堆棧頂部,在最壞情況下需要改變 6 個指針。雖說每次更新有點費時,但是置換不需要搜索;指針指向堆棧的底部,這是 LRU 頁面。這種方法特別適用于 LRU 置換的軟件或微代碼實現。

像最優置換一樣,LRU 置換沒有 Belady 異常。這兩個都屬于同一類算法,稱為堆棧算法,都絕不可能有 Belady 異常。

堆找算法可以證明,幀數為 w 的內存頁面集合是幀數為 n+1 的內存頁面集合的子集。對于 LRU 置換,內存中的頁面集合為最近引用的個頁面。如果幀數增加,那么這 n 個頁面仍然是最近被引用的,因此仍然在內存中。

注意,除了標準的 TLB 寄存器沒有其他輔助硬件,這兩種 LRU 實現都是不可能的。每次內存引用,都應更新時鐘域或堆棧。如果每次引用都釆用中斷以便允許軟件更新這些數據結構,那么它會使內存引用至少慢 10 倍,進而使用戶進程運行慢 10 倍。很少有系統可以容忍這種級別的內存管理開銷。

近似LRU頁面置換

很少有計算機系統能提供足夠的硬件來支持真正的 LRU 頁面置換算法。事實上,有些系統不提供硬件支持,并且必須使用其他頁面置換算法(例如 FIFO 算法)。

然而,許多系統都通過引用位的形式提供一定的支持。每當引用一個頁面時(無論是對頁面的字節進行讀或寫),它的頁面引用位就被硬件置位。頁表內的每個條目都關聯著一個引用位。

最初,所有引用位由操作系統清零(至 0)。當用戶進程執行時,每個引用到的頁面引用位由硬件設置(至 1)。一段時間后,我們可以通過檢查引用位來確定哪些頁面已被使用,哪些頁面尚未使用,雖說我們不知道使用的順序。這種信息是許多近似 LRU 頁面置換算法的基礎。

額外引用位算法

通過定期記錄引用位,我們可以獲得額外的排序信息。可以為內存中的頁表的每個頁面保留一個 8 位的字節。定時器中斷定期地(如每 100ms)將控制傳到操作系統。操作系統將每個頁面引用位移到其 8 位字節的高位,將其他位右移 1 位,并丟棄最低位。這些 8 位移位寄存器包含著最近 8 個時間周期內的頁面使用情況。

例如,如果移位寄存器包含 00000000,那么該頁面在 8 個時間周期內沒有使用。每個周期內使用至少一次的頁面具有 11111111 的移位寄存器值。具有 11000100 的歷史寄存器值的頁面比具有值為 01110111 的頁面更為“最近使用的”。

如果將這些 8 位字節解釋為無符號整數,那么具有最小編號的頁面是 LRU 頁面,可以被替換。請注意,不能保證數字是唯一的。可以置換所有具有最小值的頁面,或者在這些頁面之間采用 FIFO 來選擇置換。

當然,移位寄存器的歷史位數可以改變,并可以選擇以便使更新盡可能快(取決于可用的硬件)。在極端情況下,位數可降為 0,即只有引用位本身。這種算法稱為第二次機會頁面置換算法

第二次機會算法

第二次機會置換的基本算法是一種 FIFO 置換算法。然而,當選擇了一個頁面時,需要檢查其引用位。如果值為 0,那么就直接置換此頁面;如果引用位設置為 1,那么就給此頁面第二次機會,并繼續選擇下一個 FIFO 頁面。

當一個頁面獲得第二次機會時,其引用位被清除,并且到達時間被設為當前時間。因此,獲得第二次機會的頁面,在所有其他頁面被置換(或獲得第二次機會)之前,不會被置換。此外,如果一個頁面經常使用以致于其引用位總是得到設置,那么它就不會被置換。

實現第二次機會算法(有時稱為時鐘算法)的一種方式是采用循環隊列。指針(即時鐘指針)指示接下來要置換哪個頁面。當需要一個幀時,指針向前移動直到找到一個引用位為 0 的頁面。在向前移動時,它會清除引用位(圖 6)。一旦找到犧牲頁面,就置換該頁面,并且在循環隊列的這個位置上插入新頁面。

第二次機會(時鐘)頁面置換算法
圖 6 第二次機會(時鐘)頁面置換算法

注意,在最壞的情況下,當所有位都已設置,指針會循環遍歷整個隊列,給每個頁面第二次機會。在選擇下一個頁面進行置換之前,它將清除所有引用位。如果所有位都為 1,第二次機會置換退化為 FIFO 替換。

增強型第二次機會算法

通過將引用位和修改位作為有序對,可以改進二次機會算法。有了這兩個位,就有下面四種可能的類型:

每個頁面都屬于這四種類型之一。當需要頁面置換時,可使用與時鐘算法一樣的方案;但不是檢查所指頁面的引用位是否設置,而是檢查所查頁面屬于哪個類型。我們替換非空的最低類型中的第一個頁面。請注意,可能需要多次掃描循環隊列,才會找到要置換的頁面。

這種算法與更為簡單的時鐘算法的主要區別在于:這里為那些已修改頁面賦予更高級別,從而降低了所需 I/O 數量。

基于計數的頁面置換

頁面置換還有許多其他算法。例如,可以為每個頁面的引用次數保存一個計數器,并且開發以下兩個方案。
  1. 最不經常使用(LFU)頁面置換算法要求置換具有最小計數的頁面。這種選擇的原因是,積極使用的頁面應當具有大的引用計數。然而,當一個頁面在進程的初始階段大量使用但是隨后不再使用時,會出現問題。由于被大量使用,它有一個大的計數,即使不再需要卻仍保留在內存中。一種解決方案是,定期地將計數右移 1 位,以形成指數衰減的平均使用計數。
  2. 最經常使用(MFU)頁面置換算法是基于如下論點:具有最小計數的頁面可能剛剛被引入并且尚未使用。

正如你可以想象的,MFU 和 LFU 置換都不常用。這些算法的實現是昂貴的,并且它們不能很好地近似 OPT 置換。

頁面緩沖算法

除了特定頁面置換算法之外,還經常采用其他措施。例如,系統通常保留一個空閑幀緩沖池。當出現缺頁錯誤時,會像以前一樣選擇一個犧牲幀。然而,在寫出犧牲幀之前,所需頁面就讀到來自緩沖池的空閑幀。這種措施允許進程盡快重新啟動,而無需等待寫出犧牲幀。當犧牲幀以后被寫出后,它被添加到空閑幀池。

這種方法的擴展之一是維護一個修改頁面的列表。每當調頁設備空閑時,就選擇一個修改頁面以寫到磁盤上,然后重置它的修改位。這種方案增加了在需要選擇置換時干凈的且無需寫出的頁面的概率。

另一種修改是保留一個空閑幀池,并且記住哪些頁面在哪些幀內。因為在幀被寫到磁盤后幀內容并未被修改,所以當該幀被重用之前,如果再次需要,那么舊的頁面可以從空閑幀池中直接取出并被使用。這種情況不需要 I/O。當發生缺頁錯誤時,首先檢查所需頁面是否在空閑幀池中。如果不在,我們應選擇一個自由偵并讀入頁面。

這種技術與 FIFO 置換算法一起用于 VAX/VMS 系統中。當 FIFO 置換算法錯誤地置換了一個常用頁面時,該頁面可從空閑幀池中很快取出,而且不需要 I/O。這種空閑幀緩沖彌補了相對差但卻簡單的 FIFO 置換算法。這種方法是必要的,因為早期版本的 VAX 沒有正確實現引用位。

有些版本的 UNIX 系統將此方法與第二次機會算法一起使用。這種方法可用來改進任何頁面置換算法,以降低因錯誤選擇犧牲頁面而引起的開銷。

應用程序與頁面置換

在某些情況下,通過操作系統的虛擬內存訪問數據的應用程序比操作系統根本沒有提供緩沖區更差。一個典型的例子是數據庫,它提供自己的內存管理和 I/O 緩沖。類似這樣的程序比提供通用目的算法的操作系統,更能理解自己的內存使用與磁盤使用。如果操作系統提供 I/O 緩沖而應用程序也提供 I/O 緩沖,那么用于這些 I/O 的內存自然就成倍了。

另一個例子是數據倉庫,它頻繁地執行大量的、順序的磁盤讀取,隨后計算并寫入。LRU 算法會刪除舊的頁面并保留新的頁面,而應用程序將更可能讀取較舊的頁面而不是較新的頁面(因為它再次開始順序讀取)。這里,MFU 可能比 LRU 更為高效。

由于這些問題,有的操作系統允許特殊程序能夠將磁盤分區作為邏輯塊的大的數組來使用,而不需要通過文件系統的數據結構。這種數組有時稱為原始磁盤,而這種數組的 I/O 稱為原始 I/O

原始 I/O 繞過所有文件系統服務,例如文件 I/O 的請求調頁、文件鎖定、預取、空間分配、文件名和目錄等。請注意,盡管有些應用程序在原始分區上實現自己的專用存儲服務更加高效,但是大多數應用程序采用通用文件系統服務更好。

所有教程

優秀文章

精美而實用的網站,提供C語言C++STLLinuxShellJavaGo語言等教程,以及socketGCCviSwing設計模式JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo