一、操作系統(tǒng)幾種主要的頁(yè)面置換算法
算法通常只是描述解決問(wèn)題的一個(gè)步驟,具體用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)則是視情況而定。LRU“實(shí)現(xiàn)起來(lái)比較困難,且開(kāi)銷大是因?yàn)長(zhǎng)RU算法希望淘汰最后未使用的頁(yè)面,而CLOCK算法則放低的要求,較久未使用即可,不一定是最久的。CLOCK算法恰好可以充分使用現(xiàn)有的為“請(qǐng)求分頁(yè)存儲(chǔ)管理“設(shè)計(jì)的硬件機(jī)構(gòu),所以也會(huì)更加高效,而LRU則難以使用現(xiàn)成的硬件機(jī)構(gòu)來(lái)加速算法執(zhí)行。
LRU又稱最近最少使用,意為每次都淘汰最久未使用的頁(yè)面。按照LRU的思想,一種實(shí)現(xiàn)思路如下三點(diǎn):
開(kāi)辟一塊內(nèi)存空間用來(lái)記錄每個(gè)頁(yè)面最后一次使用的時(shí)間(這里假如使用heap或者無(wú)序array來(lái)記錄);每次訪存都要去維護(hù)這個(gè)時(shí)間;要淘汰頁(yè)面的時(shí)候選擇出最久未使用的頁(yè)面予以淘汰;下面來(lái)逐一分析這三點(diǎn):
名列前茅點(diǎn):這塊內(nèi)存空間不能太小,否則極易導(dǎo)致數(shù)據(jù)溢出,尤其是對(duì)于運(yùn)行在server上OS來(lái)說(shuō),可能一開(kāi)機(jī)就很久不關(guān)機(jī),溢出的可能性更大。這段內(nèi)存空間也不能太大,不然會(huì)造成空間浪費(fèi);
第二點(diǎn):每執(zhí)行一條指令必定帶來(lái)至少一次訪存,甚至更多,每次訪存都要去維護(hù)這個(gè)時(shí)間開(kāi)銷無(wú)疑是很大的(CLOCK算法也要去維護(hù)一個(gè)bit,但是開(kāi)銷卻小得多,原因后面再討論),因?yàn)槭褂脭?shù)組記錄則需要線性的時(shí)間來(lái)維護(hù),使用heap記錄則需要對(duì)數(shù)時(shí)間來(lái)維護(hù),而訪存則是十分頻繁的,這個(gè)代價(jià)是不能接受的;值得一提的是雖然看起來(lái)heap開(kāi)銷小一些,但是數(shù)據(jù)量很大的話heap相對(duì)無(wú)序array來(lái)說(shuō)對(duì)緩存不友好,這也是一個(gè)問(wèn)題,不過(guò)我不知道是否可以忽略;
第三點(diǎn):選擇出最久未使用的頁(yè)面的開(kāi)銷也很大,使用無(wú)序array記錄則需要線性的時(shí)間來(lái)查找,使用heap記錄則需要對(duì)數(shù)時(shí)間來(lái)查找;
綜合上述三點(diǎn)可知LRU具體實(shí)現(xiàn)起來(lái)確實(shí)很困難開(kāi)銷也很大。那么CLOCK算法和LRU相比優(yōu)勢(shì)在哪里?
未改進(jìn)CLOCK算法需要維護(hù)一個(gè)bit,用來(lái)標(biāo)志該頁(yè)面是否被使用過(guò);很自然地想到同樣需要三點(diǎn),即存儲(chǔ),維護(hù)和查找,但是前兩點(diǎn)(存儲(chǔ)和維護(hù))的實(shí)現(xiàn)和開(kāi)銷相對(duì)LRU則簡(jiǎn)單很多。
延伸閱讀:
二、全局頁(yè)面置換算法
工作集模型工作集頁(yè)置換算法缺頁(yè)率置換算法功能:
當(dāng)缺頁(yè)中斷發(fā)生,需要調(diào)入新的頁(yè)面而內(nèi)存已滿時(shí),選擇內(nèi)存當(dāng)中哪個(gè)物理頁(yè)面被置換。
目標(biāo):
盡可能地減少頁(yè)面的換進(jìn)換出次數(shù)(既缺頁(yè)中斷的次數(shù))。具體來(lái)說(shuō),把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面換出,通常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)來(lái)進(jìn)行預(yù)測(cè)。
頁(yè)面鎖定(frame locking):
用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵(time-critical)的應(yīng)用程序。實(shí)現(xiàn)的方法是L在頁(yè)表中添加鎖定標(biāo)志位(lock bit)。使其不在頁(yè)面置換算法范圍之內(nèi),也就說(shuō)不會(huì)被換入換出。
通常只需要考慮頁(yè)號(hào),因?yàn)槠铺?hào)一般不起作用。只保留頁(yè)號(hào)。基于這個(gè)list來(lái)設(shè)計(jì)各種的頁(yè)面替換算法。
通過(guò)模擬一個(gè)頁(yè)面置換的行為并且記錄產(chǎn)生頁(yè)缺失數(shù)的數(shù)量。一般情況下,產(chǎn)生的缺頁(yè)次數(shù)越少,性能就越高。