FIFO、LRU、OPT頁面排程算法及樣例

網上非常多介紹3種頁面置換算法的樣例和過程是不對的， 本文依據《作業系統概念》第七版對三種算法做介紹，并給出正确的樣例以驗證算法。

一、FIFO先進先出頁面置換算法，建立一個FIFO隊列來管理記憶體中的全部頁。

在計算缺頁率的時候最好把每一次頁面排程的隊列寫出來，這樣不easy出錯。

以下舉例說明：

如果頁幀為3，引用串為：7，0，1，2，0。3，0，4，2

頁面走向：7。0。1，2。0，3。0，4，2。

               -----------------------------------------------

實體頁：   7，7。7，2，2，2，2，4。4，

                       0，0，0。0，3，3，3，2，

                             1。1，1。1，0，0，0。

FIFO隊列：7, 7。7，0。0，1，2，3。0，

                       0，0。1，1。2，3。0，4。

                             1。2，2，3，0，4，2，

首先7,0,1頁面依次進入頁幀，隊列變為7,0,1,下一個引用2要調入。則隊列頭部的7出隊。隊列變為0,1,2，實體頁内将7換成2。下一個引用0調入，已經存在頁幀中。隊列不變。下一個3調入，隊列頭的0出隊，3入隊列尾，隊列變為1,2,3。頁幀将0變為3。

後面同理依次進行。

二、LRU是Least Recently Used 最近最少使用算法 ( 待更新 )

三、OPT是最佳頁面替換算法（待更新）

以下舉一些樣例及答案，可依據上述算法驗證排程算法的正确性。

1、在一個請求分頁系統中,假如一個作業的頁面走向為：1，2，3。6，4，7。3。2，1，4，7，5，6，5，2，1。當配置設定給該作業的實體塊數為4時,分别採用最佳置換算法、LRU和FIFO頁面置換算法,計算訪問過程中所發生的缺頁次數和缺頁率。

答：最佳置換算法的情況例如以下表

頁面走向	1	2	3	6	4	7						5
實體頁0
實體頁1
實體頁2
實體頁3
缺頁否	Y						N

缺頁次數為9。缺頁率為9/16

LRU算法的情況例如以下表：

缺頁次數為14，缺頁率為14/16

FIFO算法的情況例如以下表：

缺頁次數為10，缺頁率為10/16

二、在一個請求分頁系統中,假如一個作業的頁面走向為：4,3,2,1,4,3,5,4,3,2,1,5。當配置設定給該作業的實體塊數M為4時,分别採用最佳置換算法、LRU和FIFO頁面置換算法,計算訪問過程中所發生的缺頁次數和缺頁率。

答：最佳置換算法的情況例如以下表：

缺頁次數為6，缺頁率為6/12

LRU置換算法的情況例如以下表：

缺頁次數為8，缺頁率為8/12

缺頁次數為10，缺頁率為10/12