頁面置換算法(什么是頁面置換算法)

頁面置換算法:本質是為了讓有限內存能滿足無線進程。

先說明一下處理缺頁錯誤的過程:

分頁硬件在通過頁表轉換地址時會注意到無效位被設置,從而陷入操作系統,這種陷阱是因為操作系統未能將所需要的頁面調入內存引起的。

處理缺頁錯誤:

1、檢查這個進程的內部表,確定該引用是否為有效的內存訪問(可以理解為這個內存能被當前進程使用),如果無效那么直接終止進程;如果有效但是尚未調入頁面,就將該頁面調入內存。

2、然后從空閑幀鏈表上找到一個空閑幀。

3、調度磁盤將進程所需要的內存讀入頁幀中,

4、磁盤讀取完成,修改頁表,使空閑幀對應到該頁號上。并且修改頁表有效-無效位 為有效。

注意頁表中的一些標志位:

修改位:如果有效為位1,表明被修改,那么替換頁面時需要將內存寫入磁盤中;如果為0,表明未被修改,那么使用頁面替換算法直接釋放

保護位:可以標記為只讀,寫。

有效-無效位:i:表示邏輯頁號不對應物理頁幀,為V表示有對應的物理頁幀

頁面替換算法:

FIFO:算法

操作系統總時替換出在內存中停留時間最久的頁面,可以用一個指針來指向這個位置(開銷很小,可以使用一個隊列來實現,每次缺頁時移出末尾的頁面,再隊列頭添加新的頁面,未發生缺頁錯誤就不需要對隊列進行操作)

LRU算法:操作系統總時替換在內存中最久沒有使用的頁面:我么可以使用鏈表來實現這個算法,表頭表示的是最近被使用的頁面,表尾表示最久沒被使用的頁面,每一次不管是否發生缺頁,都需要對這個鏈表進行從新增刪改查,來保證每一次的鏈表都是我們需要的(開銷太大)

近似LRU算法:我們在頁表中添加一個引用位clock,當clock為1時,不能移出,當clock為0時,表明可以移除

procedure t: {  指針p:指向當前的頁面  p = 0;//指向初始位置  boolean :標志位clock  進程包含的所有頁面組成的循環鏈表:linklist//當進程在運行時,鏈表存在,進程結束時,鏈表也消失  while(進程運行){        if(p.clock == 1){      p.clock = 0;      p++;//指針指向下一個    }    if(p.clock == 0){      刪除p指向的頁面并且在p處添加新的頁面;      p.clock = 1;      p++;    }  }}

近似LRU增強算法:將修改位和引用位合起來作為是否替換條件:當(修改位,引用位) = (0,0)時表明可以替換

procedure t: {  指針p:指向當前的頁面  p = 0;//指向初始位置  boolean :標志位clock  boolean : 修改位m  進程包含的所有頁面組成的循環鏈表:linklist//當進程在運行時,鏈表存在,進程結束時,鏈表也消失  while(進程運行){          if(p.(clock,m) == (0,0)){            刪除p指向的頁面并且在p處添加新的頁面;      p.(clock,m) = (1,0);      p++;    }    if(p.(clock,m) == (0,1)){                  p.(clock,m) = (0,0);      p++;    }    if(p.(clock,m) == (1,0)){                  p.(clock,m) = (0,0);      p++;    }    if(p.(clock,m) == (1,1)){            p.(clock,m) = (0,1);      p++;    }    if(修改頁面){      p.(clock,m) = (1,1);      p++    }    if(讀頁面){      p.(clock,m) = (1,0);      p++;    }  }}

頁面緩沖算法:操作做系統保留一個空閑幀池。

當發生缺頁錯誤時,所需要的頁面就讀取空閑幀,并且將替換的犧牲幀放入緩沖池,在調頁空閑時期將緩沖池中的犧牲幀中的內容寫入(如果頁表上的修改位為1)磁盤中(減少了操作系統的調頁時直接訪問磁盤的過程,提高了調頁效率).

第二種方法:將犧牲幀中的內容寫入磁盤,但是不釋放幀中的內容,因為進程有可能調用之前的頁,這樣就將緩沖池中的幀直接寫入內存,減少了(從磁盤讀取數據的操作)。

以上均為局部頁面置換算法,都是在單個進程內部進行的頁面替換操作,但是操作系統在運行過程中不同的進程可以并行并發執行,這樣對頁面的替換就不會僅僅局限于單個進程中

下面我們學習全局置換算法:我們規定一個工作集和一個常駐集。工作集表明當前程序需要訪問的Δ個頁面,常駐集表明操作系統正在使用的頁面。

工作集:WS(Δ,t) = {}　　工作集不斷移動,操作系統替換出不在工作集中的頁面

動態工作集頁面替換算法:如下圖,我們規定一個閾值windows size = 2,我們使用兩次缺頁中斷的差值(表明兩次中斷之間有多少次沒有中斷)和閾值比較,如果比閾值大,那么將不再當前工作集的頁面換出,并且重置工作集的大小,如果比閾值小,那么將缺的頁換入工作集并且重置工作集的大小。

以上就是關于什么是頁面置換算法的內容,如果你們有學習到知識或者技能,可以把它分享出去讓更多的人看到。