操作系統(tǒng)淘汰算法
操作系統(tǒng)淘汰算法
操作系統(tǒng)中的內(nèi)存淘汰算法主要有三種。下面由學(xué)習(xí)啦小編為大家整理了操作系統(tǒng)淘汰算法的相關(guān)知識,希望對大家有幫助!
操作系統(tǒng)淘汰算法詳解
操作系統(tǒng)淘汰算法1,LRU(Least Recently Used,最少最近使用算法)
計時法:給頁表中的每一頁增加一個域,專門用來存放計時標(biāo)志,用來記錄該頁面自上次被訪問以來所經(jīng)歷的時間。頁面每被訪問一次,計時清0。要裝入新頁時,從內(nèi)存的頁面中選出時間最長的一頁,調(diào)出,同時把各頁的計時標(biāo)志全部清0,重新開始計時。 計時法可以稍作改變,成為計數(shù)法:頁面被訪問,計數(shù)標(biāo)志清0,其余所有內(nèi)存頁面計數(shù)器加1;要裝入新頁時,選出計數(shù)最大的一頁調(diào)出,同時所有計數(shù)器清0。
鏈表法:操作系統(tǒng)為每個進(jìn)程維護(hù)一條鏈表,鏈表的每個結(jié)點(diǎn)記錄一張頁面的地址。調(diào)用一次頁面,則把該頁面的結(jié)點(diǎn)從鏈中取出,放到鏈尾;要裝入新頁,則把鏈頭的頁面調(diào)出,同時生成調(diào)入頁面的結(jié)點(diǎn),放到鏈尾。鏈表法可看作簡單計時/計數(shù)法的改良,維護(hù)一個鏈表,自然要比維護(hù)所有頁面標(biāo)志要簡單和輕松。可是,這并沒有在數(shù)量級上改變算法的時間復(fù)雜度,每調(diào)用一個頁面,都要在鏈表中搜尋對應(yīng)結(jié)點(diǎn)并放至鏈尾的工作量并不算小。
操作系統(tǒng)淘汰算法2,F(xiàn)IFO(先進(jìn)先出算法)
顧名思義,最先被置換進(jìn)內(nèi)存的頁面最先出來,公正公平,大家都別搶,但是不一定合理,能者要多勞啊。
最先進(jìn)去的頁面,比如一些初始化性質(zhì)的頁面,通常在整個程序運(yùn)行期間都是需要,被置換出去非常不合理。
操作系統(tǒng)淘汰算法3,NRU(Not Recently Used,最近未使用算法,又稱CLK算法)
a. 給每一幀關(guān)聯(lián)一個附加位,稱為使用位
b. 當(dāng)某一頁首次裝入主存時,該幀的使用位設(shè)置為1
c. 當(dāng)該頁隨后再被訪問到時,它的使用位也被置為1
d. 對于頁替換算法,用于替換的候選幀集合看做一個循環(huán)緩沖區(qū),并且有一個指針與之相關(guān)聯(lián)
e. 當(dāng)某一頁被替換時,該指針被設(shè)置成指向緩沖區(qū)中的下一幀
f. 當(dāng)需要替換一頁時,操作系統(tǒng)掃描緩沖區(qū),以查找使用位被置為0的一幀。每當(dāng)遇到一個使用位為1的幀時,操作系統(tǒng)就將該位重新置為0
g. 如果在這個過程開始時,緩沖區(qū)中所有幀的使用位均為0,則選擇遇到的第一個幀替換
h. 如果所有幀的使用位均為1,則指針在緩沖區(qū)中完整地循環(huán)一周,把所有使用位都置為0,并且停留在最初的位置上,替換該幀中的頁