頁面置換演算法比較

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

最簡單的頁面置換演算法是先入先出（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演算法了。

❷ 操作系統題：頁面置換演算法 OPT FIFO LRU

fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。

❸ 操作系統課程設計，用C#實現內存頁面的置換。實現演算法間比較

頁面置換演算法

一．題目要求：

通過實現頁面置換演算法的FIFO和LRU兩種演算法，理解進程運行時系統是怎樣選擇換出頁面的，對於兩種不同的演算法各自的優缺點是哪些。

要求設計主界面以靈活選擇某演算法，且以下演算法都要實現 1) 最佳置換演算法(OPT)：將以後永不使用的或許是在最長(未來)時間內不再被訪問的頁面換出。

2) 先進先出演算法(FIFO)：淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。

3) 最近最久未使用演算法(LRU)：淘汰最近最久未被使用的頁面。 4) 最不經常使用演算法(LFU) 二．實驗目的：

1、用C語言編寫OPT、FIFO、LRU，LFU四種置換演算法。 2、熟悉內存分頁管理策略。 3、了解頁面置換的演算法。 4、掌握一般常用的調度演算法。 5、根據方案使演算法得以模擬實現。 6、鍛煉知識的運用能力和實踐能力。 三、設計要求

1、編寫演算法，實現頁面置換演算法FIFO、LRU；

2、針對內存地址引用串，運行頁面置換演算法進行頁面置換； 3、演算法所需的各種參數由輸入產生（手工輸入或者隨機數產生）； 4、輸出內存駐留的頁面集合，頁錯誤次數以及頁錯誤率；

四．相關知識：

1．虛擬存儲器的引入：

局部性原理：程序在執行時在一較短時間內僅限於某個部分；相應的，它所訪問的存儲空間也局限於某個區域，它主要表現在以下兩個方面：時間局限性和空間局限性。

2．虛擬存儲器的定義：

虛擬存儲器是只具有請求調入功能和置換功能，能從邏輯上對內存容量進行擴充的一種存儲器系統。

3．虛擬存儲器的實現方式：

分頁請求系統，它是在分頁系統的基礎上，增加了請求調頁功能、頁面置換功能所形成的頁面形式虛擬存儲系統。

請求分段系統，它是在分段系統的基礎上，增加了請求調段及分段置換功能後，所形成的段式虛擬存儲系統。

4．頁面分配：

平均分配演算法，是將系統中所有可供分配的物理塊，平均分配給各個進程。 按比例分配演算法，根據進程的大小按比例分配物理塊。

考慮優先的分配演算法，把內存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據個進程的優先權，適當的增加其相應份額後，分配給各進程。

5．頁面置換演算法：

常用的頁面置換演算法有OPT、FIFO、LRU、Clock、LFU、PBA等。 五、設計說明

1、採用數組頁面的頁號

2、FIFO演算法，選擇在內存中駐留時間最久的頁面予以淘汰；

分配n個物理塊給進程，運行時先把前n個不同頁面一起裝入內存，然後再從後面逐一比較，輸出頁面及頁錯誤數和頁錯誤率。

3、LRU演算法，根據頁面調入內存後的使用情況進行決策；

同樣分配n個物理塊給進程，前n個不同頁面一起裝入內存，後面步驟與前一演算法類似。

選擇置換演算法，先輸入所有頁面號，為系統分配物理塊，依次進行置換： 六．設計思想：

OPT基本思想：

是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組next[mSIZE]記錄物理塊中對應頁面的最後訪問時間。每當發生缺頁時，就從物理塊中找出最後訪問時間最大的頁面，調出該頁，換入所缺的頁面。

FIFO基本思想：

是用隊列存儲內存中的頁面，隊列的特點是先進先出，與該演算法是一致的，所以每當發生缺頁時，就從隊頭刪除一頁，而從隊尾加入缺頁。或者藉助輔助數組time[mSIZE]記錄物理塊中對應頁面的進入時間，每次需要置換時換出進入時間最小的頁面。

LRU基本思想：

是用一維數組page[pSIZE]存儲頁面號序列，memery[mSIZE]是存儲裝入物理塊中的頁面。數組flag[10]標記頁面的訪問時間。每當使用頁面時，刷新訪問時間。發生缺頁時，就從物理塊中頁面標記最小的一頁，調出該頁，換入所缺的頁面。 七．流程圖：

如下頁所示

六．運行結果： 1. 按任意鍵進行初始化：

2. 載入數據：

3. 進入置換演算法選擇界面：

4.運算中延遲操作：

5.三種演算法演示結果：

❹ 頁面置換演算法

在瞎啟虛程序的執行過程中，當所訪問的信息不在內存時，會由操作系統負責將所需信息從外存調入內存，然後再繼續執行程序，如果在調入內存時，發現內存空間不夠，會由操作系統負責將內存中暫時用不到的信息換出到外存,由於頻繁的進行IO操作會影響計算機性能，所以我們需要使用合適的演算法來進行頁面的置換。這里介紹幾種常見的頁面置換演算法：

每次選擇淘汰的頁面將是以後永不使用，或者在最長時間不再被訪問的頁面，這樣可以保證最低的缺頁率。但是實際上進程執行的過程才能知道接下來會訪問到的是哪個頁面，操作系統無法預知，因此最佳置換演算法是一種 理想化 演算法，無法實現。

每次旁純選擇淘汰的頁面是最早進入內存的頁面，這種演算法雖然實現簡單，但是該演算法與進程實際運行時的規律不適應，因為先進入的頁面也有可能最經常被訪問，因此該演算法性能磨燃很差。

每次淘汰的頁面是最近最久未被使用的頁面，需要有額外的內存空間來記錄該頁面自上次被訪問以來所經過的時間，但是性能很好。

該演算法是一種性能和開銷較均衡的演算法，又稱最近未使用演算法（NRU）。每個頁面需要額外添加兩個標志位：訪問位（0代表最近沒有被訪問，1代表最近被訪問）、修改位（0代表最近沒有被修改，1代表最近被修改過）。如果淘汰的頁面最近是被修改過，那麼淘汰該頁面前會進行寫入外存的IO操作，使性能變差，所以在其他條件都相同的情況下，應優先淘汰沒有修改過的頁面。

演算法規則：將所有可能被置換的頁面排成一個循環隊列 （訪問位， 修改位）

第一輪：從當前位置開始掃描到第一個（0，0）的頁用於替換。

第二輪：若第一輪掃描失敗，則重新掃描，查找第一個（0，1）的頁面用於替換，同時將掃描過的頁面的訪問位設為0。例如（1，0）變成（0，0）

第三輪：若第二輪掃描失敗，則重新掃描，查找第一個（0，0）的頁面用於替換。

第四輪：若第三輪掃描識別，則重新掃描，查找第一個（0，1）的頁面用於替換。本次掃描必定會有一個頁面被選中。

❺ 計算機操作系統頁面置換演算法的問題

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

❻ 頁面置換演算法

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

  演算法思想：每次選擇 淘汰的頁面 將是 以後永不使用 ，或者 在最長時間內不再被訪問的頁面 ，這樣可以保證最低的缺頁率。
  舉例說明，假設系統為進程分配了三個內存塊，並考慮到有以下頁面號引用串（會依次訪問這些頁面）：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) 第四優先順序淘汰的是 最近訪問且修改 的頁面。