您好,登錄后才能下訂單哦!
這篇文章主要為大家展示了什么是頁面置換算法,內(nèi)容簡而易懂,希望大家可以學習一下,學習完之后肯定會有收獲的,下面讓小編帶大家一起來看看吧。
頁面置換算法:本質(zhì)是為了讓有限內(nèi)存能滿足無線進程。
先說明一下處理缺頁錯誤的過程:
分頁硬件在通過頁表轉(zhuǎn)換地址時會注意到無效位被設置,從而陷入操作系統(tǒng),這種陷阱是因為操作系統(tǒng)未能將所需要的頁面調(diào)入內(nèi)存引起的。
處理缺頁錯誤:
1、檢查這個進程的內(nèi)部表,確定該引用是否為有效的內(nèi)存訪問(可以理解為這個內(nèi)存能被當前進程使用),如果無效那么直接終止進程;如果有效但是尚未調(diào)入頁面,就將該頁面調(diào)入內(nèi)存。
2、然后從空閑幀鏈表上找到一個空閑幀。
3、調(diào)度磁盤將進程所需要的內(nèi)存讀入頁幀中,
4、磁盤讀取完成,修改頁表,使空閑幀對應到該頁號上。并且修改頁表有效-無效位 為有效。
注意頁表中的一些標志位:
修改位:如果有效為位1,表明被修改,那么替換頁面時需要將內(nèi)存寫入磁盤中;如果為0,表明未被修改,那么使用頁面替換算法直接釋放
保護位:可以標記為只讀,寫。
有效-無效位:i:表示邏輯頁號不對應物理頁幀,為V表示有對應的物理頁幀
頁面替換算法:
FIFO:算法
操作系統(tǒng)總時替換出在內(nèi)存中停留時間最久的頁面,可以用一個指針來指向這個位置(開銷很小,可以使用一個隊列來實現(xiàn),每次缺頁時移出末尾的頁面,再隊列頭添加新的頁面,未發(fā)生缺頁錯誤就不需要對隊列進行操作)
LRU算法:操作系統(tǒng)總時替換在內(nèi)存中最久沒有使用的頁面:我么可以使用鏈表來實現(xiàn)這個算法,表頭表示的是最近被使用的頁面,表尾表示最久沒被使用的頁面,每一次不管是否發(fā)生缺頁,都需要對這個鏈表進行從新增刪改查,來保證每一次的鏈表都是我們需要的(開銷太大)
近似LRU算法:我們在頁表中添加一個引用位clock,當clock為1時,不能移出,當clock為0時,表明可以移除
procedure t: { 指針p:指向當前的頁面 p = 0;//指向初始位置 boolean :標志位clock 進程包含的所有頁面組成的循環(huán)鏈表: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 進程包含的所有頁面組成的循環(huán)鏈表: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++; } } }
頁面緩沖算法:操作做系統(tǒng)保留一個空閑幀池。
當發(fā)生缺頁錯誤時,所需要的頁面就讀取空閑幀,并且將替換的犧牲幀放入緩沖池,在調(diào)頁空閑時期將緩沖池中的犧牲幀中的內(nèi)容寫入(如果頁表上的修改位為1)磁盤中(減少了操作系統(tǒng)的調(diào)頁時直接訪問磁盤的過程,提高了調(diào)頁效率).
第二種方法:將犧牲幀中的內(nèi)容寫入磁盤,但是不釋放幀中的內(nèi)容,因為進程有可能調(diào)用之前的頁,這樣就將緩沖池中的幀直接寫入內(nèi)存,減少了(從磁盤讀取數(shù)據(jù)的操作)。
以上均為局部頁面置換算法,都是在單個進程內(nèi)部進行的頁面替換操作,但是操作系統(tǒng)在運行過程中不同的進程可以并行并發(fā)執(zhí)行,這樣對頁面的替換就不會僅僅局限于單個進程中
下面我們學習全局置換算法:我們規(guī)定一個工作集和一個常駐集。工作集表明當前程序需要訪問的Δ個頁面,常駐集表明操作系統(tǒng)正在使用的頁面。
工作集:WS(Δ,t) = {} 工作集不斷移動,操作系統(tǒng)替換出不在工作集中的頁面
動態(tài)工作集頁面替換算法:如下圖,我們規(guī)定一個閾值windows size = 2,我們使用兩次缺頁中斷的差值(表明兩次中斷之間有多少次沒有中斷)和閾值比較,如果比閾值大,那么將不再當前工作集的頁面換出,并且重置工作集的大小,如果比閾值小,那么將缺的頁換入工作集并且重置工作集的大小。
以上就是關于什么是頁面置換算法的內(nèi)容,如果你們有學習到知識或者技能,可以把它分享出去讓更多的人看到。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。