操作系統(tǒng)淘汰算法

　　操作系統(tǒng)中的內(nèi)存淘汰算法主要有三種。下面由學(xué)習(xí)啦小編為大家整理了操作系統(tǒng)淘汰算法的相關(guān)知識(shí)，希望對(duì)大家有幫助!

　　操作系統(tǒng)淘汰算法詳解

　　操作系統(tǒng)淘汰算法1，LRU(Least Recently Used，最少最近使用算法)

　　計(jì)時(shí)法:給頁(yè)表中的每一頁(yè)增加一個(gè)域，專(zhuān)門(mén)用來(lái)存放計(jì)時(shí)標(biāo)志，用來(lái)記錄該頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間。頁(yè)面每被訪問(wèn)一次，計(jì)時(shí)清0。要裝入新頁(yè)時(shí)，從內(nèi)存的頁(yè)面中選出時(shí)間最長(zhǎng)的一頁(yè)，調(diào)出，同時(shí)把各頁(yè)的計(jì)時(shí)標(biāo)志全部清0，重新開(kāi)始計(jì)時(shí)。 計(jì)時(shí)法可以稍作改變，成為計(jì)數(shù)法：頁(yè)面被訪問(wèn)，計(jì)數(shù)標(biāo)志清0，其余所有內(nèi)存頁(yè)面計(jì)數(shù)器加1;要裝入新頁(yè)時(shí)，選出計(jì)數(shù)最大的一頁(yè)調(diào)出，同時(shí)所有計(jì)數(shù)器清0。

　　鏈表法:操作系統(tǒng)為每個(gè)進(jìn)程維護(hù)一條鏈表，鏈表的每個(gè)結(jié)點(diǎn)記錄一張頁(yè)面的地址。調(diào)用一次頁(yè)面，則把該頁(yè)面的結(jié)點(diǎn)從鏈中取出，放到鏈尾;要裝入新頁(yè)，則把鏈頭的頁(yè)面調(diào)出，同時(shí)生成調(diào)入頁(yè)面的結(jié)點(diǎn)，放到鏈尾。鏈表法可看作簡(jiǎn)單計(jì)時(shí)/計(jì)數(shù)法的改良，維護(hù)一個(gè)鏈表，自然要比維護(hù)所有頁(yè)面標(biāo)志要簡(jiǎn)單和輕松?？墒?，這并沒(méi)有在數(shù)量級(jí)上改變算法的時(shí)間復(fù)雜度，每調(diào)用一個(gè)頁(yè)面，都要在鏈表中搜尋對(duì)應(yīng)結(jié)點(diǎn)并放至鏈尾的工作量并不算小。

　　操作系統(tǒng)淘汰算法2，F(xiàn)IFO(先進(jìn)先出算法)

　　顧名思義，最先被置換進(jìn)內(nèi)存的頁(yè)面最先出來(lái)，公正公平，大家都別搶?zhuān)遣灰欢ê侠?，能者要多勞啊?/p>

　　最先進(jìn)去的頁(yè)面，比如一些初始化性質(zhì)的頁(yè)面，通常在整個(gè)程序運(yùn)行期間都是需要，被置換出去非常不合理。

　　操作系統(tǒng)淘汰算法3，NRU(Not Recently Used，最近未使用算法，又稱CLK算法)

　　a. 給每一幀關(guān)聯(lián)一個(gè)附加位，稱為使用位

　　b. 當(dāng)某一頁(yè)首次裝入主存時(shí)，該幀的使用位設(shè)置為1

　　c. 當(dāng)該頁(yè)隨后再被訪問(wèn)到時(shí)，它的使用位也被置為1

　　d. 對(duì)于頁(yè)替換算法，用于替換的候選幀集合看做一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之相關(guān)聯(lián)

　　e. 當(dāng)某一頁(yè)被替換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一幀

　　f. 當(dāng)需要替換一頁(yè)時(shí)，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀。每當(dāng)遇到一個(gè)使用位為1的幀時(shí)，操作系統(tǒng)就將該位重新置為0

　　g. 如果在這個(gè)過(guò)程開(kāi)始時(shí)，緩沖區(qū)中所有幀的使用位均為0，則選擇遇到的第一個(gè)幀替換

　　h. 如果所有幀的使用位均為1,則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁(yè)