時鍾置換演算法

⑴ 計算機操作系統中頁面置換的三種方式

常見的置換演算法有：
1．最佳置換演算法（OPT）（理想置換演算法）
2．先進先出置換演算法（FIFO）：
3．最近最久未使用（LRU）演算法
4．Clock置換演算法改御（LRU演算法的近似實現坦陪）核信岩
5．最少使用（LFU）置換演算法
6．工作集演算法
7 . 工作集時鍾演算法
8. 老化演算法（非常類似LRU的有效演算法）
9. NRU(最近未使用）演算法
10. 第二次機會演算法

⑵ 頁面置換演算法有哪些

頁面置換演算法有先進先出（FIFO）演算法、最近最久未使用（LRU）演算法、最不常用（LFU）演算法、時鍾（Clock）演算法、最佳（OPT）演算法。

1、先進先出（FIFO）演算法

這是最簡單的頁面置換演算法。它通過維護一個頁面隊列，將最早進入內存的頁面置換出去。當一個新的頁面需要進入內存時，會將最早進入內存的頁面置換出去。FIFO演算法的優點是實現簡單，但它沒有考慮頁面的訪問頻率和重要性，可能會導致性能低下。

⑶ 頁面置換演算法

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

  演算法思想：每次選擇 淘汰的頁面 將是 以後永不使用 ，或者 在最長時間內不再被訪問的頁面 ，這樣可以保證最低的缺頁率。
  舉例說明，假設系統為進程分配了三個內存塊，並考慮到有以下頁面號引用串（會依次訪問這些頁面）：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）、最近最久未使用（LRU）、最不常用（LFU）、時鍾（Clock）以及理想（OPT）演算法。
1. 先進先出（FIFO）演算法
該演算法的基本原則是先進入內存的頁面先被置換。當內存空間不足時，系統會選擇最早進入內存的頁面進行置換。FIFO演算法的優勢在於實現簡單，但其缺點在於未能考慮頁面的實際使用頻率和重要性，可能導致不必要的性能損耗。
2. 最近最久未使用（LRU）演算法
LRU演算法依據頁面的歷史訪問記錄來進行頁面置換。它傾向於將最長時間未被訪問的頁面置換出內存。為了有效地追蹤頁面訪問順序，LRU演算法通常需要使用特殊的數據結構，如鏈表或棧。盡管LRU演算法在理論上較為合理，但其實現復雜度較高，且需要額外的存儲空間來維護訪問順序。
3. 最不常用（LFU）演算法
LFU演算法是基於頁面訪問頻率的置換策略。它認為訪問頻率低的頁面在未來也較少會被訪問，因此將這些頁面置換出內存。LFU演算法需要跟蹤每個頁面的訪問頻率，並進行相應的排序。然而，LFU演算法可能會導致一些頻繁訪問的頁面被過早置換，影響系統性能。
4. 時鍾（Clock）演算法
Clock演算法是基於FIFO的一種改進。它使用一個時鍾指針來遍歷頁面隊列，並根據特定的標記位（如訪問位或修改位）來決定置換頁面。當新頁面需要載入時，時鍾指針繼續移動，直到找到一個標記位為0的頁面進行置換。Clock演算法的優勢在於其實現相對簡單且效率較高。
5. 理想（OPT）演算法
理想演算法是一個理論上的最優頁面置換演算法，它能夠准確預測未來的頁面訪問模式，並據此選擇最長時間內不會被訪問的頁面進行置換。然而，由於實際中無法准確預測訪問模式，OPT演算法在現實中無法完美實現。

⑸ 一文看懂頁面置換演算法

頁面置換演算法分為兩類：局部頁面置換演算法與全局頁面置換演算法。其主要功能是在內存已滿時，選擇應置換出內存的物理頁面，目標是減少頁面換進換出次數，通常基於過去數據預測未來行為。頁面鎖定用於關鍵部分或時間關鍵應用，不參與置換。頁面置換演算法通常僅考慮頁號，通過模擬行為記錄缺頁次數。下面介紹幾種常用的頁面置換演算法。

最優頁面置換演算法考慮每個邏輯頁面在下一次訪問前的等待時間，選擇等待時間最長的頁面置換。然而，該演算法無法實時運行，只能通過上帝視角模擬。

先進先出演算法(FIFO)選擇內存中最久未使用的頁面置換，實現簡單，但產生缺頁次數較多，且可能頻繁置換出經常訪問的頁面。

最近最久未使用演算法(LRU)選擇最久未被訪問的頁面置換，基於局部性原理預測未來訪問行為，效果較好但實現復雜。

時鍾頁面置換演算法結合了LRU與FIFO的優點，通過訪問位和環形鏈表實現更優化的頁面置換策略。

二次機會法通過區分讀寫操作，優先保留經常讀取的頁面，減少頻繁置換，降低回寫概率。

最不常用演算法(LFU)選擇訪問次數最少的頁面置換，雖然實現簡單，但增加計數器消耗資源，且容易產生不合理置換。

Belady現象指增加物理頁面導致缺頁率提高的反直覺現象，源於FIFO演算法與動態特徵不匹配。相比之下，LRU演算法與棧屬性相匹配，較少出現Belady現象。

局部頁面置換演算法適用於單程序情況，而全局頁面置換演算法更適合多程序環境，需考慮動態分配物理頁幀以適應進程需求變化。工作集模型描述了進程當前使用的邏輯頁面集合，常駐集則表示實際駐留在內存的頁面。工作集頁置換演算法根據工作集大小動態調整物理頁幀，缺頁率頁面置換演算法則基於缺頁率調整常駐集大小。

抖動問題發生在物理頁面分配不足時，頻繁置換導致進程運行效率降低。解決抖動的關鍵在於平衡並發進程數與物理頁面數量，確保系統穩定運行。通過優化演算法與資源分配，可有效減少抖動，提高系統整體性能。