採用fifo頁面置換演算法是

⑴ 頁面置換演算法有哪些

頁面置換演算法包括先進先出（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演算法在現實中無法完美實現。

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

頁面置換演算法在計算機內存管理中扮演重要角色，用於解決內存與處理器之間的數據交換問題。其中，不同演算法各有其特點與適用場景。

最佳置換演算法（OPT）旨在選擇未來永不訪問或最久不訪問的頁面淘汰，以此降低缺頁率，實現內存資源的高效利用。

先進先出置換演算法（FIFO）遵循「先入先出」原則，淘汰最早進入內存的頁面。該演算法簡單直觀，但可能因預測不準確而產生較多缺頁現象。

最近最久未使用（LRU）演算法基於頁面的訪問歷史，淘汰最近最久未訪問的頁面，以確保頻繁訪問的頁面得到優先訪問機會。

Clock置換演算法（LRU演算法的近似實現）通過為每幀關聯使用位，動態模擬LRU演算法的淘汰策略，實現對最近未使用的頁面的高效淘汰。

最少使用（LFU）置換演算法關注頁面的訪問頻率，淘汰訪問次數最少的頁面，旨在平衡頁面訪問頻率與內存使用效率。

工作集演算法考慮程序運行時的頁面使用情況，通過工作集的大小預測頁面需求，實現更合理的頁面置換。

工作集時鍾演算法結合Clock置換演算法與工作集概念，優化內存管理策略，提升演算法效能。

老化演算法（類似LRU的有效演算法）通過跟蹤頁面的訪問情況，對頁面進行「老化」處理，淘汰訪問頻率較低的頁面，以優化內存使用。

NRU（最近未使用）演算法追蹤頁面的使用情況，優先淘汰長時間未被訪問的頁面，減少缺頁現象。

第二次機會演算法在頁面置換策略中引入二次淘汰機會，對被淘汰頁面進行評估，若發現有較高訪問頻率，可將其重新加入內存，減少因錯誤預測帶來的缺頁成本。

在地址映射過程中，若在頁面中發現所要訪問的頁面不再內存中，則產生缺頁中斷。當發生缺頁中斷時操作系統必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換演算法

⑶ fifo演算法是什麼

FIFO（First Input First Output），即先進先出隊列。可以類比 我們在飯堂排隊打飯，先排到隊伍的最後，等待前面的人一個個打完飯再輪到下一個。這就是一種先進先出機制，先排隊的人先行打飯離開。

FIFO（先進先出頁面置換演算法）：看到先進先出，我們想到的數據結構就是隊列當分配的內存物理塊數量為3時。

6，7，5先進入內存，那麼出來的順序就是5，7，6 缺頁次數為3次。

2調入內存，6調出內存，那麼順序就是2，5，7 缺頁次數為4次。

6調入內存，7調出內存，那麼順序就是6，2，5 缺頁次數為5次。

7調入內存，5調出內存，那麼順序就是7，6，2 缺頁次數為6次。

3調入內存，2調出內存，那麼順序就是3，7，6 缺頁次數為7次。

6調入內存，已經存在，不需要調入。

7調入內存，已經存在，不需要調入。

5調入內存，6調出內存，那麼順序就是5，3，7 缺頁次數為8次。

2調入內存，7調出內存，那麼順序就是2，5，3 缺頁次數為9次。

3調入內存，已經存在，不需要調入。

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

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