Page replacement 2：實驗結果與結論

 參、實驗結果

ㄧ、參數設定

（一）資料

Uniform		Local		Normal
Data size	300,000	Data size	300,000	Data size	300,000
Ref. size	1,200	Ref. size	1,200	Ref. size	1,200
Dirty rate	0.5	Dirty rate	0.5	Dirty rate	0.5
Ref. range	1~20	Ref. range	1~100	Set size	30
		Sub rate1	1 / 300	Mean	Ref. size / 2
		Sub rate2	1 / 120	S.D.	Ref. size / Set size

（二）分頁替換演算法 (page replacement algorithm)

Optimal		FIFO		LIFO		ARB		NRA
Mem. size		30, 60, 90, 120, 150
						Interval	Set size	Mean	Mem. size
								S.D.	Mem. size / Set size

二、資料型態

資料中每一行代表一筆資料，一行中會有兩欄資料，分別為被使用到的分頁索引值 (1~ Ref. size)與修改值 (0/1)，1代表有被修改，0代表沒被修改過。在產生資料前，會自定義修改率 (dirty rate)，因此每產生一個索引，就會隨機產生0~1間的一個值，如果此值 ≤ 修改率，則為1；如果此值 > 修改率，則為0。

（一）均勻隨機 (uniform random)

均勻隨機使用均勻分佈的隨機抽樣產生被使用的分頁索引頭與區間，再以索引頭為開頭，連續取樣區間內的所有分頁。例如：第一次索引頭為130、區間為10，故第一組資料為130~139；第二次索引頭為500、區間為15，故第二組資料為500~514；以此類推，直到產生到指定的資料大小。

（二）區域隨機 (local random)

區域隨機也是採用均勻分佈的隨機抽樣產生被使用的分頁索引頭與區間，不過不是使用連續取樣，而是在這區間中繼續均勻隨機抽樣。為了製造區域性 (locality)，我們會界定每組區域的大小。例如：第一組區域的大小為1,100、索引頭為300、區間為50，故第一組資料會從300~349中均勻抽樣1,100筆資料；第二組區域的大小為1,500、索引頭為700、區間為40，故第一組資料會從700~339中均勻抽樣1,500筆資料；直到產生到指定的資料大小為止。

（三）常態隨機 (normal random)

常態隨機是使用是採用常態分佈的隨機抽樣直接產生分頁索引值，常態分佈的平均值為Ref. size / 2，標準差為Ref. size / Set size，例如：平均值為600、標準差為40，依照68-95-99.7原則，有68%的資料會落在600±40內；有95%的資料會落在600±80內；有99.7%的資料會落在600±120內。

三、實驗結果

本次實驗有五個演算法、三組資料、五種記憶體大小 (30, 60, 90, 120, 150)，且實驗重複30次。使用三個指標來代表效能，分別為分頁錯誤 (page fault)、中斷 (interrupt)、寫回 (write back)。

本實驗分頁錯誤定義為只要在記憶體中找不到欲存取的分頁，即會產生一次分頁錯誤。本實驗中斷定義為需寫回或需更新ARB時，才會產生一次中斷，故依照此定義，有分頁錯誤不一定會產生中斷，但有寫回則一定產生中斷。本實驗寫回定義為，如果發生分頁錯誤且該分頁被修改過，則會產生一次寫回。因此本實驗預設的寫回方式不是立即寫回，而是當發生分頁錯誤，該分頁要被替換掉且被改過時，才會執行寫回。

（一）均勻隨機

1. 分頁錯誤

（圖一）均勻隨機資料中各演算法分頁錯誤數與頁框大小關係圖

圖一顯示在均勻隨機資料的分頁錯誤數：ARB = FIFO = NRA = LIFO > Optimal，除了Optimal外的其餘四個演算法，在均勻隨機資料中的分頁錯誤數並無明顯差異，而且Optimal的斜率是比其他四個演算法更斜。

2. 中斷

（圖二）均勻隨機資料中各演算法中斷數與頁框大小關係圖

圖二顯示在均勻隨機資料的中斷數：ARB > FIFO > NRA > LIFO > Optimal，雖然前四個的分頁錯誤數並無明顯差異，但在中斷數就可以看到差異。ARB最高是因ARB的中斷還包含更新ARB，而NRA次低，LIFO最低，是因為LIFO中堆疊中非頂端部分，都不會被替換出去，所以為最低，而NRA非頂端部分仍有機會被替換出去，因此次低。

3. 寫回

（圖三）均勻隨機資料中各演算法寫回數與頁框大小關係圖

圖三顯示在均勻隨機資料的寫回數：ARB = FIFO > NRA > LIFO > Optimal，圖二和圖三的差異只在於ARB，其他四條線都相同，因為本實驗中斷的定義為寫回和更新ARB，所以其他四個演算法的中斷數=寫回數，而ARB則會不同。

（二）區域隨機

1. 分頁錯誤

（圖四）區域隨機資料中各演算法分頁錯誤數與頁框大小關係圖

圖四顯示在區域隨機資料的分頁錯誤數：LIFO > NRA > ARB > FIFO > Optimal，由於LIFO只會更新堆疊的頂端，所以在區域性資料中表現最差，NRA有機會更新到堆疊的非頂端，所以表現次差。ARB和FIFO在30頁框時相近，但當頁框增加時，FIFO的改善比ARB更優，甚至到90頁框後快逼近Optimal，因為FIFO替換分頁機率較為公平，而ARB替換分頁機率較不公平，所以當區域轉移時，FIFO能更快適應新區域的分頁。

2. 中斷

（圖五）區域隨機資料中各演算法中斷數與頁框大小關係圖

圖五顯示在區域隨機資料的中斷數：LIFO > NRA > ARB > FIFO > Optimal，其原因與圖四的說明相同。記憶體中的分頁，替換機率越不公平，就越難適應新的區域，因此表現就會越差；替換機率越公平，就越易適應新的區域，因此表現就會越好。

3. 寫回

（圖六）區域隨機資料中各演算法寫回數與頁框大小關係圖

圖六顯示在區域隨機資料的寫回數：LIFO > NRA > ARB > FIFO > Optimal，圖五和圖六的差異只在於ARB，其他四條線都相同。

（三）常態隨機

1. 分頁錯誤

（圖七）區域隨機資料中各演算法分頁錯誤數與頁框大小關係圖

圖七顯示在常態隨機資料的分頁錯誤數：FIFO ≥ ARB > NRA = LIFO > Optimal，30頁框時，前四種表現差不多；中間90頁框時，FIFO有比ARB好一點，但後來FIFO斜率趨緩；到150頁框時，就分成兩群。整體而言，Optimal的斜率趨緩，LIFO和ARB斜率比FIFO和ARB陡，因為LIFO和ARB本身就比較適合經常使用同樣分頁的資料，故表現會比較好。

2. 中斷

（圖八）區域隨機資料中各演算法中斷數與頁框大小關係圖

圖八顯示在常態隨機資料的中斷數：ARB ≥ FIFO > NRA ≥ LIFO > Optimal，和圖二說明一樣，由於ARB和FIFO更新頻繁，所以中斷較多；而NRA和LIFO更新較不頻繁，所以中斷較少。

3. 寫回

（圖九）區域隨機資料中各演算法寫回數與頁框大小關係圖

圖九顯示在常態隨機資料的寫回數：ARB ≥ FIFO > NRA ≥ LIFO > Optimal，圖八和圖九的差異只在於ARB，其他四條線都相同。

四、結論

（表一）各演算法在不同資料型態的排名

Performance rank		Optimal	FIFO	ARB	LIFO	NRA
Uniform	Page fault	1	2	2	2	2
	Interrupt	1	4	5	2	2
	Write back	1	4	4	2	2
Local	Page fault	1	2	3	5	4
	Interrupt	1	2	3	5	4
	Write back	1	2	3	5	4
Normal	Page fault	1	4	4	2	2
	Interrupt	1	4	5	2	2
	Write back	1	4	4	2	2
Sum		9	28	33	27	24

表一顯示整體的排名：（優）Optimal < NRA < LIFO < FIFO < ARB（差），Optimal為效能的天花板。

ARB在整體表現中是最差的，但在區域隨機資料仍有不錯的效能，而FIFO在區域隨機的表現最好，甚至逼近Optimal，因為ARB和FIFO替換記憶體中的分頁較為公平，尤其FIFO是一視同仁，很快就能適應新區域的轉變。反觀LIFO在區域隨機中是最差的，因為它替換分頁的機制很不公平，永遠都是先替換新來者，因此它無法去適應新區域。然而FIFO這樣的缺點，在NRA中得到改善，因此NRA在區域隨機中，明顯比FIFO有優勢。

在常態隨機資料中，可以看到LIFO和NRA平分秋色，因此NRA雖然改善了LIFO的缺點，但同時也沒有失去LIFO本身的優點。不過NRA受標準差的影響很大，標準差越小，NRA越像LIFO；標準差越大，RNA越像FIFO。故NRA如果再導入自適應參數 (self-adaptive parameter)的概念，讓標準差能隨時間與資料型態的改變，而有所改變，NRA在區域隨機的資料將會有更顯著的改善。

相關文章

1. Page replacement 1：演算法介紹
2. Page replacement 2：實驗結果與結論
3. Page replacement source code
4. 高等作業系統｜使用者的代理人｜王友群
5. 排程力 Schedule Z 1：軟體使用說明
6. 排程力 Schedule Z 2：演算法介紹｜VIG_VNS for TSPTW
7. 排程力 Schedule Z 3：結果、結論與心得
8. Schedule Z載點
9. Schedule Z程式原始碼

引用文獻

1. Magic Len。2015。分頁替換演算法(Page Replacement Algorithm)介紹與模擬。MagicLen [Accessed by Oct. 2021]