cache排程演算法

在虛擬儲存器中，當發生頁面失效時，需要從磁碟儲存器中調入一頁（或一段）到主儲存器中。在段式和段頁式虛擬儲存器中，由於多使用者虛頁數比主儲存器的實頁數要多得多。在段式虛擬儲存器中，虛存空間中能容納的程式段數要比主存空間中能存放的相同長度的程式段數多得多。

因此，必然會出現當主存中所有頁面都已經被占用，或者所有主存空間都已經被占用，而又要從磁碟儲存器中調入新頁的情況。這時，必須從主儲存器中淘汰掉乙個不常用的頁面，以便騰出主存空間來存放新調入的頁面。那麼，按照什麼樣的規則替換主儲存器中的頁面呢？

這就是頁面替換演算法要解決的問題。

以下，為了敘述方便，主要介紹頁式和段頁式虛擬儲存器中的頁面替換演算法及其實現方法，在這兩種虛擬儲存器中都是以頁面為單位進行排程的。而段式虛擬儲存器是以程式段為單位進行排程的，但是它所採用的替換演算法及演算法的實現方法都是相同的。

評價乙個頁面替換演算法好壞的標準主要有兩個，一是命中率要高，二是演算法要容易實現。要提高乙個頁面替換演算法的命中率，首先要使這種演算法能正確反映程式的區域性性，其次是這種演算法要能夠充分利用主存中頁面排程情況的歷史資訊，或者能夠**主存中將要發生的頁面排程情況。

頁面替換演算法主要用於如下幾個地方：

(1) 虛擬儲存器中，主存頁面（或程式段）的替換。

(2) cache中的塊替換。

(3) 虛擬儲存器的快慢表中，快表的替換。

(4) 虛擬儲存器中，使用者基位址暫存器的替換。

在虛擬儲存器中常用的頁面替換演算法有如下幾種：

(1)隨機演算法，即rand演算法（random algorithm）。利用軟體或硬體的隨機數發生器來確定主儲存器中被替換的頁面。這種演算法最簡單，而且容易實現。

但是，這種演算法完全沒有利用主儲存器中頁面排程情況的歷史資訊，也沒有反映程式的區域性性，所以命中率比較低。

(2)先進先出演算法，即fifo演算法（first-in first-out algorithm）。這種演算法選擇最先調入主儲存器的頁面作為被替換的頁面。它的優點是比較容易實現，能夠利用主儲存器中頁面排程情況的歷史資訊，但是，沒有反映程式的區域性性。

因為最先調入主存的頁面，很可能也是經常要使用的頁面。

(3)近期最少使用演算法，即lfu演算法（least frequently used algorithm）。這種演算法選擇近期最少訪問的頁面作為被替換的頁面。顯然，這是一種非常合理的演算法，因為到目前為止最少使用的頁面，很可能也是將來最少訪問的頁面。

該演算法既充分利用了主存中頁面排程情況的歷史資訊，又正確反映了程式的區域性性。但是，這種演算法實現起來非常困難，它要為每個頁面設定乙個很長的計數器，並且要選擇乙個固定的時鐘為每個計數器定時計數。在選擇被替換頁面時，要從所有計數器中找出乙個計數值最大的計數器。

因此，通常採用如下一種相對比較簡單的方法。

(4)最久沒有使用演算法，即lru演算法（least recently used algorithm）。這種演算法把近期最久沒有被訪問過的頁面作為被替換的頁面。它把lfu演算法中要記錄數量上的"多"與"少"簡化成判斷"有"與"無"，因此，實現起來比較容易。

(5)最優替換演算法，即opt演算法（optimal replacement algorithm）。上面介紹的幾種頁面替換演算法主要是以主儲存器中頁面排程情況的歷史資訊為依據的，它假設將來主儲存器中的頁面排程情況與過去一段時間內主儲存器中的頁面排程情況是相同的。顯然，這種假設不總是正確的。

最好的演算法應該是選擇將來最久不被訪問的頁面作為被替換的頁面，這種替換演算法的命中率一定是最高的，它就是最優替換演算法。

要實現opt演算法，唯一的辦法是讓程式先執行一遍，記錄下實際的頁位址流情況。根據這個頁位址流才能找出當前要被替換的頁面。顯然，這樣做是不現實的。

因此，opt演算法只是一種理想化的演算法，然而，它也是一種很有用的演算法。實際上，經常把這種演算法用來作為評價其它頁面替換演算法好壞的標準。在其它條件相同的情況下，哪一種頁面替換演算法的命中率與opt演算法最接近，那麼，它就是一種比較好的頁面替換演算法。