## 摘要
比較並評估四種分頁替換演算法(page replacement algorithm)，以三種不同的資料型態進行比較，演算法各為 FIFO、ARB、ESC、DESC，資料型態各為Random、Locality、Most Random (MR.)。整體的排名為 (優) DESC > FIFO > ESC > ARB (差)，本實驗提出了「先生生成」與 DESC 兩個概念，分別是特殊的資料生成方式和獨特的演算法，如上述 DESC 在表現上比現有的幾個演算法好，但仍有許多進步的空間。

## 簡介
分頁(paging) 是作業系統裡記憶體管理的一種技術，可以使電腦的主記憶體可以使用儲存在輔助記憶體中的資料。作業系統會將輔助記憶體中的資料分割成固定大小的區塊，稱為分頁（page），而分頁表 (page table) 為儲存了虛擬位址到實體位址間之對映的表。當軟體試圖訪問目前未被載入在實體記憶體中的一個分頁時，會由中央處理器的記憶體管理單元發出中斷，這個狀況稱之為分頁錯誤(page fault) ，此時就需要替這個分頁尋找一個頁框(frame) 來使用。這個在發生分頁錯誤後，尋找頁框並使用的動作就稱為分頁替換(page replacement) 。當實體記憶體還沒滿的時候，分頁會被寫回實體記憶體，並更新分頁表；反之，當實體記憶體已滿時，找出一個將被替代掉的犧牲者(victim) ，儲存犧牲者的資訊，並將新分頁替換上來，更新分頁表，分頁的調入調出之相關操作方法，即分頁替換演算法。
本次實驗會實作四種分頁替換演算法，分別為First-in-first-out algorithm (FIFO) 、Additional reference bits algorithm (ARB) 、Enhanced second-chance algorithm (ESC) 、Decent enhanced second-chance algorithm (DESC) 。DESC 是我設計的分頁替換演算法，主體以ESC 進行改編，並融入本人發想的獨特設計-—Store Bits。本次實驗的資料有三種型態，分別為Random、Locality、Most Random (MR.)，MR. 亦是本人親自發想設計的，中文命名為「先生生成」，主要概念為模擬長期使用之電腦的實際狀況。

## 分頁替換演算法 (page replacement algorithm)
### First-in-first-out algorithm (FIFO)
FIFO 的核心理念是先來者先出去，故犧牲者為先來者，也就是存在記憶體中最久的分頁。FIFO 可以使用佇列 (queue)來實現，是易實作且不差的演算法。FIFO 的特性使得佇列中的分頁得以經常被更新，而且所有分頁都有機會被替換。
### Additional reference bits algorithm (ARB)
ARB 顧名思義即額外使用參考位元去決定犧牲者，通常會使用 8 位元並間隔一段時間，更新在記憶體內所有分頁的 ARB。更新方式是用位元運算，每次更新位元會往右移 1 位元，而最近有被參考過的分頁，其最高位元會是 1；而最近沒有被參考的分頁，其最高位元會是 0，因此透過 ARB 的值可以粗略判斷分頁最近是否有被使用過。
### Enhanced second-chance algorithm (ESC)
ESC 為SC 的進化型，核心概念為讓最近被參考過的分頁獲得一次免成為犧牲者的機會。ESC 可用圓形佇列(circular queue) 來實現，該演算法與SC 不同的是，除了參考每一個分頁的存取位元(reference bit) 外，還參考修改位元(dirty bit) 之資訊， 並依照(0, 0)→(0, 1)→(1, 0)→(1, 1) 的順序來決定犧牲者。
### Decent enhanced second-chance algorithm (DESC)
DESC 為ESC 的進化型，核心概念即ESC。DESC 一樣可用圓形佇列(circular queue) 來實現，顧名思義這個演算法相當的 decent ，與ESC不同的是我將存在記憶體內的分頁的其中一半作為儲存格，並定期清理未被使用過的分頁(包含給過一次機會的分頁)，在通常情況DESC 就是個比ESC 好的演算法，但極端設定的時候他的表現比上面三者好。

## 資料型態
資料中每一行代表一筆資料，每行會有長度固定/不固定的資料。
### Random
隨機產生分頁索引頭與區間，再以索引頭為開頭，連續取樣區間內的所有分頁。例如：第一次索引頭為 86、區間為10，故第一組資料為 86~95；第二次索引頭為 600、區間為 20，故第二組資料為 600~619，以此類推，直到產生到指定的資料大小(這裡指200000)。
### Locality
隨機產生分頁索引頭與區間，不過不是採用連續取樣，而是在選到的區間中隨機抽樣，並會在各個選到的區間抽樣至固定的長度。例如：第一組長度為 1000、索引頭為 300、區間為 50，故第一組資料會從 300~349 中均勻抽樣 1000 筆資料；第二組長度為 500、索引頭為 701、區間為 33，故第二組資料會從 701~733中均勻抽樣 500 筆資料，直到產生到指定的資料大小為止(這裡指200000)。
### Most Random(MR.)
模擬使用者長期使用電腦的情況，設想使用者在使用電腦時，僅會進行數個的作業，不論是玩遊戲、看影片、做報告，通常只會固定開啟部分程式，而大多數的程式是不會用到的(或不常使用)，於是我將被選過的分頁再次被選到的機率會增加，每被選一次就加一次。我將其命名為「先生生成」，先被生成者越容易被生成，選取方式與 Random 相同，一開始所有分頁的權重相等(機率相等)，經過隨機取樣後，被選到的分頁權重會增加，直到產生到指定的資料大小為止(這裡指200000)。

## 實驗結果
本次實驗有四個演算法、三組資料、五種記憶體大小 (20, 40, 60, 80, 100)，且每次產生 200000 次 reference 。使用三個指標來進行比較，分別為分頁錯誤 (page fault)、中斷 (interrupt)、寫回 (write back)。
本實驗分頁錯誤定義為只要在記憶體中找不到欲存取的分頁，即會產生一次分頁錯誤；中斷定義為需寫回或需更新 ARB 、 DESC 時，才會產生一次中斷，故照此定義，有分頁錯誤不一定會產生中斷，但有寫回則一定產生中斷；寫回定義為，如果發生分頁錯誤且該分頁被修改過，則會產生一次寫回。因此本實驗預設的寫回方式不是立即寫回，而是當發生分頁錯誤，該分頁要被替換掉且被改過時，才會執行寫回；修改分頁定義為每次分頁被 Hit 時，有50%的機會會被修改，因此在此定義下分頁在被 Hit 過前，Dirty Bit 都不可能為一。

### Random

#### 分頁錯誤
圖一、Random 資料中各演算法分頁錯誤數與頁框大小關係圖

圖一顯示在 Random 資料的分頁錯誤數：在 Random 資料中的分頁錯誤數並無明顯差異，這是因為在隨機得夠均勻的情況下，所有演算法都有同樣無法預測的未來，自然而然不可能有太大的差異。

#### 中斷

圖二、Random 資料中各演算法中斷數與頁框大小關係圖

圖二顯示在 Random 資料的中斷數：雖然分頁錯誤數並無明顯差異，但在中斷數就可以看到差異。ARB 最高是因 ARB 的中斷還包含更新 ARB，而 DESC 最低，是因為 DESC 會定期清理記憶體，使得大多數的時候中斷會被大量減少，Store Bit 的部分也會因記憶體大小變大而大大增加。

#### 寫回

圖三、Random 資料中各演算法寫回數與頁框大小關係圖

圖三、顯示在 Random 資料的寫回數：因為本實驗中斷的定義與其他人相當不同，所以在 Hit 數越高的情況下，寫回數也隨之增加。

### Locality
#### 分頁錯誤

圖四、Locality 資料中各演算法分頁錯誤數與頁框大小關係圖

圖四顯示在 Locality 資料的分頁錯誤數：ARB、ESC 並沒有針對資料類型進行特化，所以在 Locality 中的表現與 Random 無太明顯的進步，DESC 在各個情況下進行了數個不同的改善，所以表現次佳，在記憶體更大的情況下與 FIFO 相近，代表他比 ESC 更保留了FIFO的特性。 FIFO 表現最佳，因為 FIFO 替換分頁機率較為公平，所以當區域轉移時，FIFO 能快速適應新區域的分頁。

#### 中斷

圖五、Locality 資料中各演算法中斷數與頁框大小關係圖

圖五顯示在 Locality 資料的中斷數：其原因與圖四分頁錯誤的說明差不多。記憶體中的分頁，替換機率越不公平，就越難適應新的區域，因此表現就會越差；替換機率越公平，就越易適應新的區域，因此表現就會越好。值得一提的是 DESC 在中斷中會快速清理大量記憶體，所以在記憶體更大時，表現是會超過 FIFO 的，由於本實驗記憶體只到 100 ，較看不出此特性。

#### 寫回

圖六、Locality 資料中各演算法寫回數與頁框大小關係圖

圖六顯示在 Locality 資料的寫回數：由於定義的差異， Hit 與分頁錯誤之關係會大大影響寫回數，在 Random 看不太出來，所以這裡做較詳細的說明，在 Locality 的情況下， Hit 數的增加會與分頁錯誤率成反比，所以在此資料下，有公平替換率的演算法會隨著記憶體變大表現變好。

### Most Random (MR.)
#### 分頁錯誤

圖七、MR. 資料中各演算法分頁錯誤數與頁框大小關係圖

圖七顯示在 MR. 資料的分頁錯誤數： MR. 資料有利 ESC 這類演算法的特性，本資料的特性在極端的設定下會有明顯的表現，但本次實驗以較平均的情況進行討論。 ARB 在此資料中沒有特別突出的優點，故表現最差，對於 FIFO 這種較公平的演算法會隨記憶體增大而變好，ESC 與 DESC 的特性相似，所以在平均情況不會有突出的表現，但也不會很差， DESC 在記憶體大會突然變好的現象也是因為 Store Bits 增加，使得常出現的分頁能足夠被存下來。

#### 中斷

圖八、 MR. 資料中各演算法中斷數與頁框大小關係圖

圖八顯示在 MR. 資料的中斷數：由於 ARB 分頁錯誤最多且有額外的更新要做，所以中斷較多， FIFO 和 ESC 會與分頁錯誤的圖形相似， DESC 對減少中斷次數有進行特化，表現自然也比較好。

#### 寫回

圖九、 MR. 資料中各演算法寫回數與頁框大小關係圖

圖九顯示在 MR. 資料的寫回數：由於定義的差異，不會隨著記憶體改變而有變化，其中 DESC 會有突然往上是因為分頁錯誤的急劇減少而 Hit 數未有相當比例的增加，使得寫回數大量增加。

## 結論
各演算法整體的排名：DESC > FIFO > ESC > ARB， DESC 為最佳。

ARB 在整體表現中是最差的，但在寫回數能有不錯的表現，僅僅是因為在分頁錯誤表現得夠差使得寫回數也不高，但若不再我的定義下他將一文不值； FIFO 在 Locality 的表現最好，甚至可以說是 Optimal ，因為 FIFO 替換記憶體中的分頁較為公平，基本上是一視同仁，很快就能適應新區域的轉變，所以在記憶體夠大的情況下，可以將整個區域的分頁載入記憶體中，表現自然是最好； ESC 在整體表現平平，因為它替換分頁的機制不公平，也未針對資料的可能做特化，單純的照著規則走，所以比有較差規則的 ARB 來的好。 DESC 是本人親自超刀改編的演算法，表現自然很好，我改善了許多 ESC 的缺點，所以一般情況來說 DESC 就是個比 ESC 好的演算法。由於 DESC 有融入 FIFO 的特點，所以在 Locality 資料中，當記憶體夠大時，表現得與 FIFO 差不多。此外， DESC 進行了中斷減少的特化，所以中斷是四個演算法中表現最好的。
在 MR. 資料中，這個「先生生成」雖然是想體現 ESC 的表現，但我不清楚在現實中的機率是多少，所以設定成 1% 當作基準(被選到的分頁，被選到的機率增加 1%)，本人測試設定超過 3% 時就能突出 ESC 的表現。不過，在假設的通常情況下，各演算法的表現無太大的差異。
在本實驗提出的 DESC 演算法本人還未對其進行最佳化，因此 DESC 還有很大的進步空間，希望未來能在對其進行修正。