頁面置換算法

在虛擬記憶體管理中，當作業執行時，所存取的頁面可能不在主記憶體中。此時，需要將該頁面從外存（如磁碟）載入到主記憶體中。如果主記憶體已滿，系統需要選擇已在記憶體中的頁面將其調出，以為新頁面騰出空間。這個過程稱為「頁面置換」。選擇要被替換的頁面的演算法就是頁面置換演算法。

抖動現象

抖動（或稱為顛簸）指的是當頁面在主記憶體和外存之間頻繁地交換，導致系統大部分時間都花費在頁面調度上，而實際的計算工作非常少，系統效能急劇下降。這通常是因為頁面置換演算法不夠高效，或者分配的記憶體不合理。

一個好的頁面置換演算法應該盡量減少抖動現象，確保頁面調度次數較少，系統運作順暢。

頁面走向是指程式執行時所存取的頁面的順序。在分析頁面置換時，我們通常只關心頁面的存取順序，而不是特定的記憶體位址。透過簡化頁面的走向，可以幫助評估頁面置換演算法的效率。

範例：

假設一個程式的位址序列是：

0100, 0432, 0101, 0612, 0102, 0103, 0104,
0101, 0611, 0102, 0103, 0104, 0101, 0610,
0102, 0103, 0104, 0101, 0609, 0102, 0105

假設每頁大小為100字節，那麼頁面走向可以簡化為

1, 4, 1, 6, 1, 6, 1, 6, 1, 6, 1

**如何實現？ **

為了簡化頁面走向，首先需要根據給定的位址序列和頁面大小，將每個位址轉換為對應的頁號。假設每頁大小為100字節，位址序列給定的是以位元組為單位的位址值。接下來，將每個位址「除以100」（也就是取頁號），就可以得到對應的頁號。頁面走向就是這些頁面號碼的序列。

地址序列：

0100, 0432, 0101, 0612, 0102, 0103, 0104,
0101, 0611, 0102, 0103, 0104, 0101, 0610,
0102, 0103, 0104, 0101, 0609, 0102, 0105

步驟 1：計算每個位址的頁號

我們知道每頁大小是100位元組。因此，可以透過將每個位址除以100來確定其頁面號碼。每次造訪某個地址時，我們只關心其頁號，不關心特定的地址。

步驟 2：簡化頁面走向

將每個位址對應的頁號列出並簡化重複造訪的頁面。連續造訪同一個頁面時，我們只保留第一次造訪。

根據以上計算，原始頁號序列為：

1, 4, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1, 1, 1, 6, 1, 1

去掉重複的造訪後，簡化後的頁面走向序列為：

1, 4, 6, 1, 6, 1, 6, 1

這意味著在頁面訪問序列中，頁面 1 和 6 經常被訪問，而頁面 4 和 7 只在某些特定時刻出現。

最佳頁面置換演算法是理想化的演算法，它假設可以預知未來的頁面訪問情況。根據這個演算法，當需要替換頁面時，應選擇在未來最久未被造訪的頁面進行替換。

FIFO（First-In-First-Out）是最簡單的頁面置換演算法。它假設最先進入主存的頁面最不可能在未來被訪問，因此選擇最早進入記憶體的頁面進行替換。

LRU（Least Recently Used）頁面置換演算法選擇最近一段時間內最久未被訪問的頁面進行替換。

時脈頁面置換演算法是LRU的近似演算法。它使用一個環形佇列和一個指標（時鐘指標）來模擬最近最少使用的情況，避免了LRU演算法的複雜性。

實作：為每個頁面增加一個引用位，指標指向目前頁面。當頁面被存取時，引用位置為1；當發生缺頁中斷時，指標逐一檢查頁面，如果某頁的引用位元為0，則淘汰該頁面；如果引用位元為1，則將引用位元清除，並移動指標繼續檢查下一個頁面。
優點：實作較為簡單，效率高。
缺點：可能無法完美模擬LRU的行為。

LFU（Least Frequently Used）頁面置換演算法選擇在過去一段時間內訪問次數最少的頁面進行替換。

缺頁中斷率（Page Fault Rate）是衡量頁面置換演算法效率的重要指標。它表示在一定時間內，發生缺頁中斷的次數佔總造訪次數的比例。優化頁面置換演算法的目標之一就是減少缺頁中斷率。

影響缺頁中斷率的因素：

缺頁中斷率公式：

\[ f = \frac{F}{A} \]

其中：