先進先出頁面置換算法

在操作系統中，若發現所要訪問的頁面不再內存中，則產生缺頁中斷。當發生缺頁中斷時操作系統必須在內存選擇一個頁面將其移出內存，以便為即將調入的頁面讓出空間。將哪些頁面調入調出，就需要根據算法來確定，這些算法稱為頁面置換算法（Page Replacement Algorithms）。 ^[1] 

FIFO頁面置換算法, 也就是先進先出的意思。這和我們現實生活中的排隊方式很相似, 先進隊伍的人會先買到票, 然後先從隊伍中離開。如果使用FIFO算法作為頁面置換算法, 緩存空間大小是三個頁面時, 一次進入Page1, Page2, Page3。當Page4要進入緩存時, 操作系統將會把Page1清除出緩存, 將Page4加入至緩存中。如果再有Page5要進入緩存時, 操作系統會將Page2清除出緩存空間, 以此類推。 ^[2] 

比如有下述頁面走向:1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6。當內存塊數量分別為3時, 我們算一算使有此方法時產生的缺頁次情況。 (注意, 所有內存塊最初都是空的, 凡第一次用到的頁面都產生一次缺頁。) ^[3] 

當內存塊數量分別為3時, FIFO算法的執行過程如下圖所示。 ^[3] 

打叉的表示發生了缺頁, 共缺頁16次。 ^[3] 

　　

先進先出頁面置換算法的優點是其實現起來比較簡單，可以不需要硬件的支持， 因而不需要增加系統的成本。 ^[1] 

先進先出頁面置換算法沒有考慮到緩存頁面被使用的情況。如果一個頁面被頻繁訪問, 我們應該將它保留在緩存中, 這樣就能夠提高程序的性能。但是使用FIFO算法, 很可能將一個被頻繁訪問的頁面清除出緩存, 所以FIFO算法在實際的應用中是很少被使用到的, 但是這種思想是計算機系統中常常被採用的。 ^[2] 

在大數情況下，先進先出頁面置換算法缺頁率比較低或會產生Belady異常現象。 ^[1]