先進先出算法

先進先出算法

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

定義

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

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

實現機制

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

特點

優點

簡單,且容易實現。

缺點

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

相關詞條

熱門詞條

聯絡我們