頁面置換演算法實驗報告

Ⅰ 頁面置換演算法

  上文說到，請求分頁管理方式中，當需要調入頁面到內存中，但此時內存已滿，就需要從內存中按照一定的置換演算法決定將哪個頁面取出將內存給調入的頁面。本文將介紹幾種頁面置換算方法。
   本文內容

  演算法思想：每次選擇 淘汰的頁面 將是 以後永不使用 ，或者 在最長時間內不再被訪問的頁面 ，這樣可以保證最低的缺頁率。
  舉例說明，假設系統為進程分配了三個內存塊，並考慮到有以下頁面號引用串（會依次訪問這些頁面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

  ....按照此演算法依次執行，最後的結果如下

  結果圖

  註：缺頁時未必發生頁面置換，若還有可用的空閑內存空間就不用進行頁面置換。
  最佳置換演算法可以保證最低的缺頁率，但是實際上，只有進程執行的過程中才能知道接下來會訪問到的是哪個頁面。操作系統無法提前預判頁面的訪問序列。因此， 最佳置換演算法是無法實現的 。

  演算法思想：每次選擇 淘汰的頁面是最早進入內存的頁面。
  該演算法很簡單，每次淘汰最在內存中待時間最久的各個，下面分別給出系統為進程分為配三個內存塊和四個內存塊的執行情況圖。訪問序列為3,2,1,0,3,2,4,3,2,1,0,4
  分配三個內存塊的情況：

  分配四個內存塊的情況：

  當為進程分配的物理塊數增大時，缺頁次數不減反增的異常現象稱為 貝萊迪（Belay）異常 。
   只有FIFO演算法會產生Belay異常。 另外，FIFO演算法雖然實現簡單，但是該演算法與進程實際運行時的規律不適應。因為先進入的頁面也有可能最經常被訪問。因此， 演算法性能差。

  演算法思想： 每次淘汰的頁面是最近最久未使用的頁面。
  實現方法：賦予每個頁面對應的頁表項中，用 訪問欄位記錄該頁面純虧自上次被訪問以來所經歷的時間t。 當需要淘汰一個頁面時，選擇現有頁面中t最大的頁面，即最近最久未使用。

  舉例說明，加入某系統為某進程分配了四個內存塊，並考慮到有以下頁面號引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
  這里先直接給出答案

  結果圖

  最佳置換演算法那性能最好，但無法實現。先進先出置換演算法實現簡單，但是演算法性能差。最近最久未使用置換演算法性能好，是最接近OPT演算法性能的，但是實現起來需要專門的硬體支持，演算法開銷大。 時鍾置換演算法 是一種 性能和開銷均春褲配平衡 的演算法。又稱 CLOCK演算法 ，或 最近未用演算法 （ NRU ，Not Recently Used）
   簡單CLOCK演算法 演算法思想：為每個頁面設置一個 訪問位 ，再將內存中的頁面都通過 鏈接指針鏈接成一個循環隊列 。當某個頁被訪問時，其訪問位置1.當需要淘汰一個頁面時，只需檢查頁的訪問位。如果是0，就選擇該頁換出；如果是1，暫不換出，將訪問位改為0，繼續檢查下一個頁面，若第一輪掃描中所有的頁面都是1，則將這些頁面的訪問位一次置為0後，再進行第二輪掃描（第二輪掃描中一定會有訪問位為0的頁面，因此簡單的CLOCK演算法選擇一個扒指淘汰頁面最多會經過 兩輪掃描 ）。

  這個演算法指針在掃描的過程就像時鍾一樣轉圈，才被稱為時鍾置換演算法。

  簡單的時鍾置換演算法僅考慮到了一個頁面最近是否被訪問過。事實上，如果淘汰的頁面沒有被修改過，就不需要執行I/O操作寫回外存。 只有淘汰的頁面被修改過時，才需要寫回外存。
  因此，除了考慮一個頁面最近有沒有被訪問過之外，操作系統還需要考慮頁面有沒有被修改過。
  改進型時鍾置換演算法的 演算法思想 ： 在其他在條件相同時，應該優先淘汰沒有被修改過的頁面， 從而來避免I/O操作。
  為了方便討論，用（訪問位，修改位）的形式表示各頁面的狀態。如（1,1）表示一個頁面近期被訪問過，且被修改過。
   演算法規則 ：將所有可能被置換的頁面排成一個循環隊列

  由於第二輪已將所有的頁的訪問位都設為0，因此第三輪、第四輪掃描一定會選中一個頁，因此 改進型CLOCK置換演算法最多會進行四輪掃描。

  假設系統為進程分配了5個內存塊，某時刻，各個頁的狀態如下圖

  如果此時有新的頁要進入內存，開始第一輪掃描就找到了要替換的頁，即最下面的狀態為（0,0）的頁。

  某一時刻頁面狀態如下

  如果此時有新的頁要進入內存，開始第一輪掃描就發現沒有狀態為（0，0）的頁，第一輪掃描後不修改任何標志位。所以各個頁狀態和上圖一樣。
  然後開始第二輪掃描，嘗試找到狀態為（0,1）的頁，並將掃描過後的頁的訪問位設為0，第二輪掃描找到了要替換的頁。

  某一時刻頁面狀態如下

  第一輪掃描沒有找到狀態為（0,0）的頁，且第一輪掃描不修改任何標志位，所以第一輪掃描後狀態和上圖一致。
  然後開始第二輪掃描，嘗試找狀態為（0,1）的頁，也沒有找到，第二輪掃描需要將訪問位設為1，第二輪掃描後，狀態為下圖

  某一時刻頁面狀態如下

  具體的掃描過程和上面相同，這里只給出最後的結果，如下圖

  所以，改進型的CLOCK置換演算法最多需要四輪掃描確定要置換的頁。從上面的分析可以看出，改進型的CLOCK置換演算法
  (1) 第一優先順序淘汰的是 最近沒有訪問且沒有修改 的頁面。
  (2) 第二優先順序淘汰的是 最近沒有訪問但修改 的頁面。
  (3) 第三優先順序淘汰的是 最近訪問但沒有修改 的頁面。
  (4) 第四優先順序淘汰的是 最近訪問且修改 的頁面。

Ⅱ 頁面置換演算法的常見的置換演算法

最簡單的頁面置換演算法是先入先出（FIFO）法。這種演算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內存的頁，先退出內存。理由是：最早調入內存的頁，其不再被使用的可能性比剛調入內存的可能性大。建立一個FIFO隊列，收容所有在內存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內存時，就把它插在隊尾上。
這種演算法只是在按線性順序訪問地址空間 時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變「老」而不得不被置換出去。
FIFO的另一個缺點是，它有一種異常現象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。
FIFO演算法和OPT演算法之間的主要差別是，FIFO演算法利用頁面進入內存後的時間長短作為置換依據，而OPT演算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似，那麼就可以把過去最長一段時間里不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在之前一段時間里最久沒有使用過的頁面予以置換。這種演算法就稱為最久未使用演算法（Least Recently Used，LRU）。
LRU演算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時，LRU演算法選擇過去一段時間里最久未被使用的頁面。
LRU演算法是經常採用的頁面置換演算法，並被認為是相當好的，但是存在如何實現它的問題。LRU演算法需要實際硬體的支持。其問題是怎麼確定最後使用時間的順序，對此有兩種可行的辦法：
1.計數器。最簡單的情況是使每個頁表項對應一個使用時間欄位，並給CPU增加一個邏輯時鍾或計數器。每次存儲訪問，該時鍾都加1。每當訪問一個頁面時，時鍾寄存器的內容就被復制到相應頁表項的使用時間欄位中。這樣我們就可以始終保留著每個頁面最後訪問的「時間」。在置換頁面時，選擇該時間值最小的頁面。這樣做， 不僅要查頁表，而且當頁表改變時（因CPU調度）要 維護這個頁表中的時間，還要考慮到時鍾值溢出的問題。
2.棧。用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁並把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其中有被置換頁。
因實現LRU演算法必須有大量硬體支持，還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的LRU近似演算法。
一種LRU近似演算法是最近未使用演算法（Not Recently Used，NUR）。它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。
4）Clock置換演算法（LRU演算法的近似實現）
5）最少使用（LFU）置換演算法
在採用最少使用置換演算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換演算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內可能對某頁面連續訪 問成千上萬次，因此，通常不能直接利用計數器來記錄某頁被訪問的次數，而是採用移位寄存器方式。每次訪問某頁時，便將該移位寄存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。
LFU置換演算法的頁面訪問圖與LRU置換演算法的訪問圖完全相同；或者說，利用這樣一套硬體既可實現LRU演算法，又可實現LFU演算法。應該指出，LFU演算法並不能真正反映出頁面的使用情況，因為在每一時間間隔內，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。
6）工作集演算法
7）工作集時鍾演算法
8）老化演算法（非常類似LRU的有效演算法）
9）NRU(最近未使用）演算法
10）第二次機會演算法
第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，檢查它的訪問位。如果是 0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。
第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個 存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

Ⅲ 濡傛灉浣犳槸璁＄畻鏈虹戝︿笌鎶鏈涓撲笟鐨勫ぇ瀛︾敓錛岃瘯鍒嗘瀽濡備笅涓や釜妗堜緥錛1銆侀〉闈㈢疆鎹㈢畻娉曚腑錛屼負浠涔堢疆鎹㈢畻娉曚細琚

妗堜緥涓錛
鍦―MA鏂瑰紡涓嬶紝姣忕掕繘琛孌MA鎿嶄綔涓猴細 5MB/5000B=5脳10 6 /5000=1脳10 3 嬈 鍥犱負DMA棰勫勭悊鍜屽悗澶勭悊鐨勬誨紑閿涓500涓鏃墮挓鍛ㄦ湡錛屾墍浠1縐掍箣鍐呯敤浜嶥MA鎿嶄綔鐨勬椂閽熷懆鏈熸暟涓猴細 500脳1脳10 3 =5脳10 5
妗堜緥鍒嗘瀽浜岋細
錛1錛夐〉闈㈠ぇ灝忎負4KB=212 錛屽垯寰楀埌欏靛唴浣嶇Щ鍗犺櫄鍦板潃鐨勪綆12浣嶏紝欏靛彿鍗犲墿浣欓珮浣嶃
31A2H錛氶〉鍙稰=3錛屾湁鏁堜綅涓1錛屽瓨鍦ㄥ唴瀛樹腑銆傚厛璁塊棶蹇琛2ns錛屽洜鍒濆嬩負絀猴紝涓嶅湪蹇琛ㄤ腑錛屽洜姝わ紝闇瑕佽塊棶欏佃〃200ns寰楀埌欏墊嗗彿錛屽悎鎴愮墿鐞嗗湴鍧鍚庤塊棶涓誨瓨200ns錛屽叡璁2ns+200ns+200ns=402ns銆

24C2H錛氶〉鍙稰=2錛屾湁鏁堜綅涓0錛屼笉瀛樺湪鍐呭瓨涓銆傚厛璁塊棶蹇琛2ns錛岃惤絀猴紝璁塊棶欏佃〃200ns钀界┖錛岃繘琛岀己欏典腑鏂澶勭悊107ns錛屽悎鎴愮墿鐞嗗湴鍧鍚庤塊棶涓誨瓨200ns錛屽叡璁2ns+200ns+107ns+200ns鈮107ns銆
36B4H錛氶〉鍙稰=3錛屾湁鏁堜綅涓1錛屽瓨鍦ㄥ唴瀛樹腑銆傝塊棶蹇琛錛屽洜絎涓嬈¤塊棶宸插皢璇ラ〉鍙鋒斁鍏ュ揩琛錛屽洜姝よ姳璐2ns渚垮彲鍚堟垚鐗╃悊鍦板潃錛岃塊棶涓誨瓨200ns錛屽叡璁2ns+200ns=202ns銆

錛2錛夊熀浜庝笂榪拌塊棶搴忓垪錛屽綋璁塊棶鉶氬湴鍧24C2H鏃朵駭鐢熺己欏典腑鏂錛屽悎娉曢┗鐣欓泦涓2錛屽繀欏諱粠琛ㄤ腑娣樻卑涓涓欏甸潰錛屾牴鎹棰樼洰鐨勭疆鎹㈢畻娉曪紝搴旀窐奼1鍙烽〉闈錛屽洜姝24C2H鐨勫瑰簲欏墊嗗彿涓906H銆傜敱姝ゅ彲寰24C2H鐨勭墿鐞嗗湴鍧涓9064C2H銆

Ⅳ 最佳頁面置換演算法的演算法描述

當產生缺頁中斷時，利用相應的淘汰頁面的演算法選擇需要淘汰的頁面。
頁面置換演算法在淘汰頁面時的演算法：
輸入：頁面號引用串P1,P2...Pn；
輸出：淘汰頁面Pt
實現：
1、如果頁框中的某個頁面P以後永不使用，則該頁面為淘汰頁面Pt。
2、如果每個P都會再次被訪問，那麼其中最長未來時間內不再被訪問的頁面為淘汰頁面Pt。