1 引言
在程序執行過程中，若其訪問的頁面不在記憶體而需將其調入，但記憶體已無空閒空間時，需從記憶體中調出一頁程式或資料，送入磁碟的對換區。但應將哪個頁面調出，需根據一定的演算法來確定。把選擇換出頁面的演算法稱為頁面置換演算法，其好壞直接影響系統的效能。
剛被淘汰出記憶體的頁面，過後不久又要訪問它，需要再次將其調入，而該頁調入記憶體後不入又再次被淘汰出記憶體，然後又要訪問它，如此反覆，這種現象稱為抖動（又稱顛簸）。
乙個好的置換演算法應具有較低的頁面更換頻率。從理論上講，應將那些以後不會再訪問的頁面換出，或者把那些在較長時間內不會再訪問的頁面換出。
2 常用的頁面置換演算法
2.1 最佳置換演算法（the best optimal）
最佳置換演算法是由belady於2023年提出的一種理論上的演算法。其所選擇的被淘汰頁面，將是以後永不使用的， 或許是在最長(未來)時間內不再被訪問的頁面。採用最佳置換演算法，通常可保證獲得最低的缺頁率。
由於人們無法預知乙個程序在記憶體的若干個頁面中，哪乙個頁面是將來最長時間內不再被訪問的頁面，因此該演算法無法實現。但該演算法可以用來評價其他演算法。
例：就是課本上的例子
假定系統為某程序分配了三個物理塊， 並考慮有以下的頁面號引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
2.2 先進先出頁面置換演算法(fifo)
該演算法淘汰最先進入記憶體的頁面，即選擇在記憶體中駐留時間最久的頁面淘汰。
belady現象：使用fifo演算法時，在未給程序或作業分配足它所要求的頁面數時，有時會出現分配的頁面增多，缺頁次數反而增加的奇怪現象，就是belady現象。
例：和上例一樣
例子：1，2，3，4，1，2，5，1，2，3，4，5
記憶體3個物理頁面：缺頁9次
記憶體4個物理頁面：缺頁10次異常！ belady現象
2.3 最近最久未使用置換演算法(least recently used,lru)
2.3.1 演算法描述
演算法思想：利用「最近的過去」作為「最近的將來」。選擇最近最久未使用的頁面淘汰。
該演算法對每個頁面設定乙個訪問字段，用於記錄乙個頁面自上次被訪問以來所經歷的時間t,每次淘汰t值最大的頁面，也就是最近最久未使用的頁面。
例：缺頁12次，總訪問次數20次，缺頁率12/20＝60％
2.3.2 硬體支援
兩類硬體支援：暫存器、棧。
為每個在記憶體中的頁面配置乙個移位暫存器，用來記錄某程序在記憶體中各頁的使用情況。移位暫存器表示為
r=當程序訪問某物理塊時，要將相應暫存器的位置成1。此時，定時訊號將每隔一定時間將暫存器右移一位。如果把n位暫存器的數看作乙個整數，那麼具有最小數值的暫存器所對應的頁面，就是最近最久未使用的頁面。
例：某程序在記憶體中具有8個頁面，為每個頁面配置乙個8位暫存器。如下圖：
2.3.3 棧
利用乙個特殊的棧來儲存當前使用的各個頁面的頁面號。每當程序訪問某頁面時，便將該頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號，而棧底則是最近最久未使用頁面的頁面號。
如下圖：
2.4 clock置換演算法
是一種最近最久未使用演算法的近似演算法。
2.4.1 簡單的clock置換演算法
演算法描述：
每頁設定一位訪問位，某頁被訪問時，其訪問位被置1。記憶體中的所有頁鏈結成乙個迴圈佇列；
迴圈檢查各頁面的使用情況，訪問位為「0」，選擇該頁淘汰；訪問位為「1」，復位訪問位為「0」，查詢指標前進一步。
因為該演算法只有一位訪問位，只能用它表示該頁是否使用過，置換時只能將未使用過的頁面置換出去，因此稱為「最近未使用」置換演算法（nru）
例子：2.4.2 改進型的clock置換演算法
1 由訪問位a和修改位m可以組合成下面四種型別的頁面：
1類(a=0, m=0): 表示該頁最近既未被訪問，又未被修改， 是最佳淘汰頁。
2類(a=0, m=1)： 表示該頁最近未被訪問，但已被修改， 並不是很好的淘汰頁。
3類(a=1, m=0)： 最近已被訪問， 但未被修改，該頁有可能再被訪問。
4類(a=1, m=1): 最近已被訪問且被修改，該頁可能再被訪問。
2 執行過程
訪問位a，修改位m共同表示乙個頁面的狀態：四種狀態：00 01 10 11。
三輪掃瞄：
第一輪：查詢00頁面，若找到，則淘汰所找到的第一頁，結束；若未找到，下一步；
第二輪：查詢01頁面，若找到，則淘汰所找到的第一頁，結束；，若未找到，下一步；（第二輪中，所有掃瞄過的頁面，a位復位為「0」）
第三輪：所有頁面a位復位為「0」，重複第一步。
(1) 從指標所指示的當前位置開始， 掃瞄迴圈佇列， 尋找a=0且m=0的第一類頁面， 將所遇到的第乙個頁面作為所選中的淘汰頁。 在第一次掃瞄期間不改變訪問位a；
(2) 如果第一步失敗，即查詢一周後未遇到第一類頁面， 則開始第二輪掃瞄，尋找a=0且m=1的第二類頁面，將所遇到的第乙個這類頁面作為淘汰頁。在第二輪掃瞄期間，將所有掃瞄過的頁面的訪問位都置0；
(3) 如果第二步也失敗，亦即未找到第二類頁面，則將指標返回到開始的位置，並將所有的訪問位復0。 然後重複第一步，如果仍失敗，必要時再重複第二步，此時就一定能找到被淘汰的頁。
2.5 其他置換演算法
2.5.1 最少使用(lfu： least frequently used)置換演算法
選擇到當前時間為止被訪問次數最少的頁面被置換；
每頁設定訪問計數器，每當頁面被訪問時，該頁面的訪問計數器加1；
發生缺頁中斷時，淘汰計數值最小的頁面，並將所有計數清零；
2.5.2頁面緩衝演算法(pba： page buffering algorithm)
它是對fifo演算法的發展，通過被置換頁面的緩衝，有機會找回剛被置換的頁面.
◆ 被置換頁面的選擇和處理：用fifo演算法選擇被置換頁，把被置換的頁面放入兩個鍊錶之一。
如果頁面未被修改，就將其歸入到空閒頁面鍊錶的末尾
否則將其歸入到已修改頁面鍊錶。
◆ 需要調入新的物理頁面時，將新頁面內容讀入到空閒頁面鍊錶的第一項所指的頁面，然後將第一項刪除（從空閒鍊錶摘下）。
◆ 空閒頁面和已修改頁面，仍停留在記憶體中一段時間，如果這些頁面被再次訪問，只需較小開銷，而被訪問的頁面可以返還作為程序的記憶體頁。
◆ 當已修改頁面達到一定數目後，再將它們一起調出到外存，然後將它們歸入空閒頁面鍊錶，這樣能大大減少i/o操作的次數。
第15講儲存器管理之虛擬儲存器
系統須設定相應的硬體支援和軟體 1 硬體支援 請求分頁的頁表機制 缺頁中斷機構和位址變換機構。2 軟體 請求調頁功能和頁置換功能的軟體。2.2 分段請求系統 在分段系統的基礎上，增加了請求調段功能及分段置換功能，所形成的段式虛擬儲存器系統。它允許只裝入若干段的使用者程式和資料，便可啟動執行，以後再硬...
第4章儲存器管理
一 判斷題 正確的在括號中記 錯誤的記 1.為了減少內部碎片,頁應偏小為好 2.為了減少缺頁中斷率,頁應該小一些 8.lru頁面排程演算法總是選擇在主存駐留時間最長的頁面被淘汰 二 單項選擇題，在每小題的四個備選答案中選出乙個正確答案，並將其 寫在題幹後面的括號內。不選 錯選或多選者該題無分。1.在...
作業系統之儲存器管理
p116 4.0.1 儲存器管理的目的和功能 儲存器管理的主要目的和功能如下 1.主儲存器的分配和管理 按使用者要求把適當的儲存空間分配給相應的作業。乙個有效的儲存分配機制，應在使用者請求時能作出快速的響應，分配相應的儲存空間 在使用者不再使用它時，應立即 以供其他使用者使用。為此，這個儲存分配機制...