先進先出頁面置換算法

先進先出頁面置換算法

地址映射過程中，若在頁面中發現所要訪問的頁面不再記憶體中，則產生缺頁中斷。當發生缺頁中斷時作業系統必須在記憶體選擇一個頁面將其移出記憶體，以便為即將調入的頁面讓出空間。而用來選擇淘汰哪一頁的規則叫做頁面置換算法。最簡單的頁面置換算法是先入先出（FIFO）法。

基本介紹

  • 中文名：先進先出頁面置換算法
  • 外文名：FIFO
  • 分類：計算機作業系統
簡介,實現過程,缺點,

簡介

優先淘汰最早進入記憶體的頁面，亦即在記憶體中駐留時間最久的頁面。該算法實現簡單，只需把調入記憶體的頁面根據先後次序連結成佇列，設定一個指針總指向最早的頁面。但該算法與進程實際運行時的規律不適應，因為在進程中，有的頁面經常被訪問。

實現過程

假定系統為某進程分配了三個物理塊，並考慮有以下頁面號引用串：7, 0, 1, 2, 0, 3, 0,4,2,3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1。釆用FIFO算法進行頁面置換，進程訪問頁面2時，把最早進入記憶體的頁面7換出。然後訪問頁面3時，再把2, 0, 1中最先進入記憶體的頁換出。由下圖可以看出，利用FIFO算法時進行了12次頁面置換。
訪問頁面
7
0
1
2
0
3
0
4
2
3
0
3
2
1
2
0
1
7
0
1
物理塊1
7
7
7
2
2
2
4
4
4
0
0
0
7
7
7
物理塊2
0
0
0
3
3
3
2
2
2
1
1
1
0
0
物理塊3
1
1
1
0
0
0
3
3
3
2
2
2
1
缺頁否
√
√
√
√
√
√
√
√
√
√
√
√
√
√
√

缺點

FIFO算法還會產生當所分配的物理塊數增大而頁故障數不減反增的異常現象，這是由Belady於1969年發現，故稱為Belady異常，如下圖所示。只有FIFO算法可能出現Belady異常，而LRU和OPT算法永遠不會出現Belady異常。
訪問頁面
1
2
3
4
1
2
5
1
2
3
4
5
物理塊1
1
1
1
4
4
4
5
,5'
5
物理塊2
2
2
2
1
1
1
3
3
物理塊3
3
3
3
2
2
2
4
缺頁否
√
√
√
√
√
√
√
√
√
1
1
1
5
5
5
5
4
4
物理塊2*
2
2
2
2
1
1
1
1
5
物理塊3*
3
3
3
3
2
2
2
2
物理塊4*
4
4
4
4
3
3
3
缺頁否
√
√
√
√
√
√
√
√
√

相關詞條

熱門詞條

聯絡我們