先進先出算法

先進先出算法是最簡單的分頁替換算法，是指每次有新的分頁需要調入時，會選擇調入記憶體時間最久的分頁換出。它簡單，容易實現，但這種絕對的公平方式容易導致效率的降低。

定義

先進先出（First In First Out，FIFO）算法的核心是更換最早進入記憶體的頁面。先進先出是任何人都能直觀想到的辦法，因為它是人類的天性。

最簡單的分頁替換算法就是先進先出算法，當每次有新的分頁需要調入時，會選擇調入記憶體時間最久的分頁換出。有兩種實現的方法：第一種是記錄每個分頁被調入到頁框的時間，當每次需要換出分頁時，會找到調入時間最早的一頁，也就是在主存儲器中存在最久的分頁。另外一種方式就是利用FIFO佇列來實現，當要進行分頁替換時，就把佇列最前端的分頁換出，再把要調入的分頁放到佇列的末端。

實現機制

使用鍊表將所有在記憶體的頁面按照進入時間的早晚連結起來，然後每次置換鍊表頭上的頁面就行了。新加進來的頁面則掛在鍊表的末端。

特點

優點

簡單，且容易實現。

缺點

這種絕對的公平方式容易導致效率的降低。例如，如果最先載入進來的頁面是經常被訪問的頁面，這樣做很可能造成常被訪問的頁面替換到磁碟上，導致很快就需要再次發生缺頁中斷，從而降低效率。