一、操作系統(tǒng)幾種主要的頁面置換算法

算法通常只是描述解決問題的一個(gè)步驟，具體用什么數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)則是視情況而定。LRU“實(shí)現(xiàn)起來比較困難，且開銷大是因?yàn)長(zhǎng)RU算法希望淘汰最后未使用的頁面，而CLOCK算法則放低的要求，較久未使用即可，不一定是最久的。CLOCK算法恰好可以充分使用現(xiàn)有的為“請(qǐng)求分頁存儲(chǔ)管理“設(shè)計(jì)的硬件機(jī)構(gòu)，所以也會(huì)更加高效，而LRU則難以使用現(xiàn)成的硬件機(jī)構(gòu)來加速算法執(zhí)行。

LRU又稱最近最少使用，意為每次都淘汰最久未使用的頁面。按照LRU的思想，一種實(shí)現(xiàn)思路如下三點(diǎn)：

下面來逐一分析這三點(diǎn)：

名列前茅點(diǎn)：這塊內(nèi)存空間不能太小，否則極易導(dǎo)致數(shù)據(jù)溢出，尤其是對(duì)于運(yùn)行在server上OS來說，可能一開機(jī)就很久不關(guān)機(jī)，溢出的可能性更大。這段內(nèi)存空間也不能太大，不然會(huì)造成空間浪費(fèi)；

第二點(diǎn)：每執(zhí)行一條指令必定帶來至少一次訪存，甚至更多，每次訪存都要去維護(hù)這個(gè)時(shí)間開銷無疑是很大的（CLOCK算法也要去維護(hù)一個(gè)bit，但是開銷卻小得多，原因后面再討論），因?yàn)槭褂脭?shù)組記錄則需要線性的時(shí)間來維護(hù)，使用heap記錄則需要對(duì)數(shù)時(shí)間來維護(hù)，而訪存則是十分頻繁的，這個(gè)代價(jià)是不能接受的；值得一提的是雖然看起來heap開銷小一些，但是數(shù)據(jù)量很大的話heap相對(duì)無序array來說對(duì)緩存不友好，這也是一個(gè)問題，不過我不知道是否可以忽略；

第三點(diǎn)：選擇出最久未使用的頁面的開銷也很大，使用無序array記錄則需要線性的時(shí)間來查找，使用heap記錄則需要對(duì)數(shù)時(shí)間來查找；

綜合上述三點(diǎn)可知LRU具體實(shí)現(xiàn)起來確實(shí)很困難開銷也很大。那么CLOCK算法和LRU相比優(yōu)勢(shì)在哪里？

未改進(jìn)CLOCK算法需要維護(hù)一個(gè)bit，用來標(biāo)志該頁面是否被使用過；很自然地想到同樣需要三點(diǎn)，即存儲(chǔ)，維護(hù)和查找，但是前兩點(diǎn)（存儲(chǔ)和維護(hù)）的實(shí)現(xiàn)和開銷相對(duì)LRU則簡(jiǎn)單很多。

延伸閱讀：

二、全局頁面置換算法

功能：

當(dāng)缺頁中斷發(fā)生，需要調(diào)入新的頁面而內(nèi)存已滿時(shí)，選擇內(nèi)存當(dāng)中哪個(gè)物理頁面被置換。

目標(biāo)：

盡可能地減少頁面的換進(jìn)換出次數(shù)（既缺頁中斷的次數(shù)）。具體來說，把未來不再使用的或短期內(nèi)較少使用的頁面換出，通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計(jì)數(shù)據(jù)來進(jìn)行預(yù)測(cè)。

頁面鎖定（frame locking）：

用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時(shí)間關(guān)鍵（time-critical）的應(yīng)用程序。實(shí)現(xiàn)的方法是L在頁表中添加鎖定標(biāo)志位（lock bit）。使其不在頁面置換算法范圍之內(nèi)，也就說不會(huì)被換入換出。

通常只需要考慮頁號(hào)，因?yàn)槠铺?hào)一般不起作用。只保留頁號(hào)。基于這個(gè)list來設(shè)計(jì)各種的頁面替換算法。
通過模擬一個(gè)頁面置換的行為并且記錄產(chǎn)生頁缺失數(shù)的數(shù)量。一般情況下，產(chǎn)生的缺頁次數(shù)越少，性能就越高。