帶你梳理一下操作系統(tǒng)中都出現(xiàn)過(guò)哪些算法

此篇文章帶你梳理一下操作系統(tǒng)中都出現(xiàn)過(guò)哪些算法

進(jìn)程和線程管理中的算法

進(jìn)程和線程在調(diào)度時(shí)候出現(xiàn)過(guò)很多算法，這些算法的設(shè)計(jì)背景是當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)，會(huì)頻繁的有很多進(jìn)程或者線程來(lái)同時(shí)競(jìng)爭(zhēng) CPU 時(shí)間片。那么如何選擇合適的進(jìn)程/線程運(yùn)行是一項(xiàng)藝術(shù)。當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程/線程處于就緒狀態(tài)時(shí)，就會(huì)發(fā)生這種情況。如果只有一個(gè) CPU 可用，那么必須選擇接下來(lái)哪個(gè)進(jìn)程/線程可以運(yùn)行。操作系統(tǒng)中有一個(gè)叫做調(diào)度程序(scheduler)的角色存在，它就是做這件事兒的，調(diào)度程序使用的算法叫做調(diào)度算法(scheduling algorithm)。

調(diào)度算法分類

針對(duì)不同的操作系統(tǒng)環(huán)境，也有不同的算法分類，操作系統(tǒng)主要分為下面這幾種

批處理操作系統(tǒng)

交互式操作系統(tǒng)

實(shí)時(shí)操作系統(tǒng)

下面我們分別來(lái)看一下這些操作系統(tǒng)中的算法。

批處理操作系統(tǒng)中的算法

設(shè)計(jì)目標(biāo)

批處理系統(tǒng)廣泛應(yīng)用于商業(yè)領(lǐng)域，比如用來(lái)處理工資單、存貨清單、賬目收入、賬目支出、利息計(jì)算、索賠處理和其他周期性作業(yè)。在批處理系統(tǒng)中，一般會(huì)選擇使用非搶占式算法或者周期性比較長(zhǎng)的搶占式算法。這種方法可以減少線程切換因此能夠提升性能。

在交互式用戶環(huán)境中，因?yàn)闉榱擞脩趔w驗(yàn)，所以會(huì)避免長(zhǎng)時(shí)間占用進(jìn)程，所以需要搶占式算法。由于某個(gè)進(jìn)程出現(xiàn)錯(cuò)誤也有可能無(wú)限期的排斥其他所有進(jìn)程。為了避免這種情況，搶占式也是必須的。

在實(shí)時(shí)系統(tǒng)中，搶占式不是必須的，因?yàn)檫M(jìn)程知道自己可能運(yùn)行不了很長(zhǎng)時(shí)間，通常很快的做完自己的工作并掛起。

關(guān)鍵指標(biāo)

通常有三個(gè)指標(biāo)來(lái)衡量系統(tǒng)工作狀態(tài)：吞吐量、周轉(zhuǎn)時(shí)間和 CPU 利用率

吞吐量(throughout)是系統(tǒng)每小時(shí)完成的作業(yè)數(shù)量。綜合考慮，每小時(shí)完成 50 個(gè)工作要比每小時(shí)完成 40 個(gè)工作好。

周轉(zhuǎn)時(shí)間(Turnaround time)是一種平均時(shí)間，它指的是從一個(gè)批處理提交開(kāi)始直到作業(yè)完成時(shí)刻為止的平均時(shí)間。該數(shù)據(jù)度量了用戶要得到輸出所需的平均等待時(shí)間。周轉(zhuǎn)時(shí)間越小越好。

CPU 利用率(CPU utilization)通常作為批處理系統(tǒng)上的指標(biāo)。即使如此，CPU 利用率也不是一個(gè)好的度量指標(biāo)，真正有價(jià)值的衡量指標(biāo)是系統(tǒng)每小時(shí)可以完成多少作業(yè)（吞吐量），以及完成作業(yè)需要多長(zhǎng)時(shí)間（周轉(zhuǎn)時(shí)間）。

下面我們就來(lái)認(rèn)識(shí)一下批處理中的算法。

先來(lái)先服務(wù)

很像是先到先得。。。它是一種非搶占式的算法。此算法將按照請(qǐng)求順序?yàn)檫M(jìn)程分配 CPU。最基本的，會(huì)有一個(gè)就緒進(jìn)程的等待隊(duì)列。當(dāng)?shù)谝粋€(gè)任務(wù)從外部進(jìn)入系統(tǒng)時(shí)，將會(huì)立即啟動(dòng)并允許運(yùn)行任意長(zhǎng)的時(shí)間。它不會(huì)因?yàn)檫\(yùn)行時(shí)間太長(zhǎng)而中斷。當(dāng)其他作業(yè)進(jìn)入時(shí)，它們排到就緒隊(duì)列尾部。當(dāng)正在運(yùn)行的進(jìn)程阻塞，處于等待隊(duì)列的第一個(gè)進(jìn)程就開(kāi)始運(yùn)行。當(dāng)一個(gè)阻塞的進(jìn)程重新處于就緒態(tài)時(shí)，它會(huì)像一個(gè)新到達(dá)的任務(wù)，會(huì)排在隊(duì)列的末尾，即排在所有進(jìn)程最后。

這個(gè)算法的強(qiáng)大之處在于易于理解和編程，在這個(gè)算法中，一個(gè)單鏈表記錄了所有就緒進(jìn)程。要選取一個(gè)進(jìn)程運(yùn)行，只要從該隊(duì)列的頭部移走一個(gè)進(jìn)程即可；要添加一個(gè)新的作業(yè)或者阻塞一個(gè)進(jìn)程，只要把這個(gè)作業(yè)或進(jìn)程附加在隊(duì)列的末尾即可。這是很簡(jiǎn)單的一種實(shí)現(xiàn)。

不過(guò)，先來(lái)先服務(wù)也是有缺點(diǎn)的，那就是沒(méi)有優(yōu)先級(jí)的關(guān)系，試想一下，如果有 100 個(gè) I/O 進(jìn)程正在排隊(duì)，第 101 個(gè)是一個(gè) CPU 密集型進(jìn)程，那豈不是需要等 100 個(gè) I/O 進(jìn)程運(yùn)行完畢才會(huì)等到一個(gè) CPU 密集型進(jìn)程運(yùn)行，這在實(shí)際情況下根本不可能，所以需要優(yōu)先級(jí)或者搶占式進(jìn)程的出現(xiàn)來(lái)優(yōu)先選擇重要的進(jìn)程運(yùn)行。

最短作業(yè)優(yōu)先

批處理中的第二種調(diào)度算法是最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時(shí)間已知。例如，一家保險(xiǎn)公司，因?yàn)槊刻煲鲱愃频墓ぷ?，所以人們可以相?dāng)精確地預(yù)測(cè)處理 1000 個(gè)索賠的一批作業(yè)需要多長(zhǎng)時(shí)間。當(dāng)輸入隊(duì)列中有若干個(gè)同等重要的作業(yè)被啟動(dòng)時(shí)，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法

如上圖 a 所示，這里有 4 個(gè)作業(yè) A、B、C、D ，運(yùn)行時(shí)間分別為 8、4、4、4 分鐘。若按圖中的次序運(yùn)行，則 A 的周轉(zhuǎn)時(shí)間為 8 分鐘，B 為 12 分鐘，C 為 16 分鐘，D 為 20 分鐘，平均時(shí)間內(nèi)為 14 分鐘。

現(xiàn)在考慮使用最短作業(yè)優(yōu)先算法運(yùn)行 4 個(gè)作業(yè)，如上圖 b 所示，目前的周轉(zhuǎn)時(shí)間分別為 4、8、12、20，平均為 11 分鐘，可以證明最短作業(yè)優(yōu)先是最優(yōu)的?？紤]有 4 個(gè)作業(yè)的情況，其運(yùn)行時(shí)間分別為 a、b、c、d。第一個(gè)作業(yè)在時(shí)間 a 結(jié)束，第二個(gè)在時(shí)間 a + b 結(jié)束，以此類推。平均周轉(zhuǎn)時(shí)間為 (4a + 3b + 2c + d) / 4 。顯然 a 對(duì)平均值的影響最大，所以 a 應(yīng)該是最短優(yōu)先作業(yè)，其次是 b，然后是 c ，最后是 d 它就只能影響自己的周轉(zhuǎn)時(shí)間了。

需要注意的是，在所有的進(jìn)程都可以運(yùn)行的情況下，最短作業(yè)優(yōu)先的算法才是最優(yōu)的。

最短剩余時(shí)間優(yōu)先

最短作業(yè)優(yōu)先的搶占式版本被稱作為最短剩余時(shí)間優(yōu)先(Shortest Remaining Time Next)算法。使用這個(gè)算法，調(diào)度程序總是選擇剩余運(yùn)行時(shí)間最短的那個(gè)進(jìn)程運(yùn)行。當(dāng)一個(gè)新作業(yè)到達(dá)時(shí)，其整個(gè)時(shí)間同當(dāng)前進(jìn)程的剩余時(shí)間做比較。如果新的進(jìn)程比當(dāng)前運(yùn)行進(jìn)程需要更少的時(shí)間，當(dāng)前進(jìn)程就被掛起，而運(yùn)行新的進(jìn)程。這種方式能夠使短期作業(yè)獲得良好的服務(wù)。

交互式系統(tǒng)中的調(diào)度

交互式系統(tǒng)中在個(gè)人計(jì)算機(jī)、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來(lái)探討一下交互式調(diào)度

輪詢調(diào)度

一種最古老、最簡(jiǎn)單、最公平并且最廣泛使用的算法就是輪詢算法(round-robin)。每個(gè)進(jìn)程都會(huì)被分配一個(gè)時(shí)間段，稱為時(shí)間片(quantum)，在這個(gè)時(shí)間片內(nèi)允許進(jìn)程運(yùn)行。如果進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束，則 CPU 立即進(jìn)行切換。輪詢算法比較容易實(shí)現(xiàn)。調(diào)度程序所做的就是維護(hù)一個(gè)可運(yùn)行進(jìn)程的列表，就像下圖中的 a，當(dāng)一個(gè)進(jìn)程用完時(shí)間片后就被移到隊(duì)列的末尾，就像下圖的 b。

時(shí)間片輪詢調(diào)度中唯一有意思的一點(diǎn)就是時(shí)間片的長(zhǎng)度。從一個(gè)進(jìn)程切換到另一個(gè)進(jìn)程需要一定的時(shí)間進(jìn)行管理處理，包括保存寄存器的值和內(nèi)存映射、更新不同的表格和列表、清除和重新調(diào)入內(nèi)存高速緩存等。這種切換稱作進(jìn)程間切換(process switch)和上下文切換(context switch)。

優(yōu)先級(jí)調(diào)度

輪詢調(diào)度假設(shè)了所有的進(jìn)程是同等重要的。但事實(shí)情況可能不是這樣。例如，在一所大學(xué)中的等級(jí)制度，首先是院長(zhǎng)，然后是教授、秘書(shū)、后勤人員，最后是學(xué)生。這種將外部情況考慮在內(nèi)就實(shí)現(xiàn)了優(yōu)先級(jí)調(diào)度(priority scheduling)

它的基本思想很明確，每個(gè)進(jìn)程都被賦予一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)高的進(jìn)程優(yōu)先運(yùn)行。

但是也不意味著高優(yōu)先級(jí)的進(jìn)程能夠永遠(yuǎn)一直運(yùn)行下去，調(diào)度程序會(huì)在每個(gè)時(shí)鐘中斷期間降低當(dāng)前運(yùn)行進(jìn)程的優(yōu)先級(jí)。如果此操作導(dǎo)致其優(yōu)先級(jí)降低到下一個(gè)最高進(jìn)程的優(yōu)先級(jí)以下，則會(huì)發(fā)生進(jìn)程切換。或者，可以為每個(gè)進(jìn)程分配允許運(yùn)行的最大時(shí)間間隔。當(dāng)時(shí)間間隔用完后，下一個(gè)高優(yōu)先級(jí)的進(jìn)程會(huì)得到運(yùn)行的機(jī)會(huì)。

可以很方便的將一組進(jìn)程按優(yōu)先級(jí)分成若干類，并且在各個(gè)類之間采用優(yōu)先級(jí)調(diào)度，而在各類進(jìn)程的內(nèi)部采用輪轉(zhuǎn)調(diào)度。下面展示了一個(gè)四個(gè)優(yōu)先級(jí)類的系統(tǒng)

它的調(diào)度算法主要描述如下：上面存在優(yōu)先級(jí)為 4 類的可運(yùn)行進(jìn)程，首先會(huì)按照輪轉(zhuǎn)法為每個(gè)進(jìn)程運(yùn)行一個(gè)時(shí)間片，此時(shí)不理會(huì)較低優(yōu)先級(jí)的進(jìn)程。若第 4 類進(jìn)程為空，則按照輪詢的方式運(yùn)行第三類進(jìn)程。若第 4 類和第 3 類進(jìn)程都為空，則按照輪轉(zhuǎn)法運(yùn)行第 2 類進(jìn)程。如果不對(duì)優(yōu)先級(jí)進(jìn)行調(diào)整，則低優(yōu)先級(jí)的進(jìn)程很容易產(chǎn)生饑餓現(xiàn)象。

最短進(jìn)程優(yōu)先

對(duì)于批處理系統(tǒng)而言，由于最短作業(yè)優(yōu)先常常伴隨著最短響應(yīng)時(shí)間，所以如果能夠把它用于交互式進(jìn)程，那將是非常好的。交互式進(jìn)程通常遵循下列模式：等待命令、執(zhí)行命令、等待命令、執(zhí)行命令。。。如果我們把每個(gè)命令的執(zhí)行都看作一個(gè)分離的作業(yè)，那么我們可以通過(guò)首先運(yùn)行最短的作業(yè)來(lái)使響應(yīng)時(shí)間最短。這里唯一的問(wèn)題是如何從當(dāng)前可運(yùn)行進(jìn)程中找出最短的那一個(gè)進(jìn)程。

一種方式是根據(jù)進(jìn)程過(guò)去的行為進(jìn)行推測(cè)，并執(zhí)行估計(jì)運(yùn)行時(shí)間最短的那一個(gè)。假設(shè)每個(gè)終端上每條命令的預(yù)估運(yùn)行時(shí)間為T0，現(xiàn)在假設(shè)測(cè)量到其下一次運(yùn)行時(shí)間為T1，可以用兩個(gè)值的加權(quán)來(lái)改進(jìn)估計(jì)時(shí)間，即aT0+ (1- 1)T1。通過(guò)選擇 a 的值，可以決定是盡快忘掉老的運(yùn)行時(shí)間，還是在一段長(zhǎng)時(shí)間內(nèi)始終記住它們。當(dāng) a = 1/2 時(shí)，可以得到下面這個(gè)序列

可以看到，在三輪過(guò)后，T0 在新的估計(jì)值中所占比重下降至 1/8。

有時(shí)把這種通過(guò)當(dāng)前測(cè)量值和先前估計(jì)值進(jìn)行加權(quán)平均從而得到下一個(gè)估計(jì)值的技術(shù)稱作老化(aging)。這種方法會(huì)使用很多預(yù)測(cè)值基于當(dāng)前值的情況。

保證調(diào)度

一種完全不同的調(diào)度方法是對(duì)用戶做出明確的性能保證。一種實(shí)際而且容易實(shí)現(xiàn)的保證是：若用戶工作時(shí)有 n 個(gè)用戶登錄，則每個(gè)用戶將獲得 CPU 處理能力的 1/n。類似地，在一個(gè)有 n 個(gè)進(jìn)程運(yùn)行的單用戶系統(tǒng)中，若所有的進(jìn)程都等價(jià)，則每個(gè)進(jìn)程將獲得 1/n 的 CPU 時(shí)間。

彩票調(diào)度

對(duì)用戶進(jìn)行承諾并在隨后兌現(xiàn)承諾是一件好事，不過(guò)很難實(shí)現(xiàn)。但是有一種既可以給出預(yù)測(cè)結(jié)果而又有一種比較簡(jiǎn)單的實(shí)現(xiàn)方式的算法，就是彩票調(diào)度(lottery scheduling)算法。

其基本思想是為進(jìn)程提供各種系統(tǒng)資源（例如 CPU 時(shí)間）的彩票。當(dāng)做出一個(gè)調(diào)度決策的時(shí)候，就隨機(jī)抽出一張彩票，擁有彩票的進(jìn)程將獲得該資源。在應(yīng)用到 CPU 調(diào)度時(shí)，系統(tǒng)可以每秒持有 50 次抽獎(jiǎng)，每個(gè)中獎(jiǎng)?wù)邔@得比如 20 毫秒的 CPU 時(shí)間作為獎(jiǎng)勵(lì)。

如果希望進(jìn)程之間協(xié)作的話可以交換它們之間的票據(jù)。例如，客戶端進(jìn)程給服務(wù)器進(jìn)程發(fā)送了一條消息后阻塞，客戶端進(jìn)程可能會(huì)把自己所有的票據(jù)都交給服務(wù)器，來(lái)增加下一次服務(wù)器運(yùn)行的機(jī)會(huì)。當(dāng)服務(wù)完成后，它會(huì)把彩票還給客戶端讓其有機(jī)會(huì)再次運(yùn)行。事實(shí)上，如果沒(méi)有客戶機(jī)，服務(wù)器也根本不需要彩票。

可以把彩票理解為 buff，這個(gè) buff 有 15% 的幾率能讓你產(chǎn)生速度之靴的效果。

公平分享調(diào)度

到目前為止，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身，而不用考慮該進(jìn)程的擁有者是誰(shuí)。結(jié)果是，如果用戶 1 啟動(dòng)了 9 個(gè)進(jìn)程，而用戶 2 啟動(dòng)了一個(gè)進(jìn)程，使用輪轉(zhuǎn)或相同優(yōu)先級(jí)調(diào)度算法，那么用戶 1 將得到 90 % 的 CPU 時(shí)間，而用戶 2 將之得到 10 % 的 CPU 時(shí)間。

為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會(huì)把進(jìn)程的擁有者考慮在內(nèi)。在這種模型下，每個(gè)用戶都會(huì)分配一些CPU 時(shí)間，而調(diào)度程序會(huì)選擇進(jìn)程并強(qiáng)制執(zhí)行。因此如果兩個(gè)用戶每個(gè)都會(huì)有 50% 的 CPU 時(shí)間片保證，那么無(wú)論一個(gè)用戶有多少個(gè)進(jìn)程，都將獲得相同的 CPU 份額。

實(shí)時(shí)系統(tǒng)中的調(diào)度

實(shí)時(shí)系統(tǒng)(real-time)對(duì)于時(shí)間有要求的系統(tǒng)。實(shí)時(shí)系統(tǒng)可以分為兩類，硬實(shí)時(shí)(hard real time)和軟實(shí)時(shí)(soft real time)系統(tǒng)，前者意味著必須要滿足絕對(duì)的截止時(shí)間；后者的含義是雖然不希望偶爾錯(cuò)失截止時(shí)間，但是可以容忍。在這兩種情形中，實(shí)時(shí)都是通過(guò)把程序劃分為一組進(jìn)程而實(shí)現(xiàn)的，其中每個(gè)進(jìn)程的行為是可預(yù)測(cè)和提前可知的。這些進(jìn)程一般壽命較短，并且極快的運(yùn)行完成。在檢測(cè)到一個(gè)外部信號(hào)時(shí)，調(diào)度程序的任務(wù)就是按照滿足所有截止時(shí)間的要求調(diào)度進(jìn)程。

實(shí)時(shí)系統(tǒng)中的事件可以按照響應(yīng)方式進(jìn)一步分類為周期性(以規(guī)則的時(shí)間間隔發(fā)生)事件或非周期性(發(fā)生時(shí)間不可預(yù)知)事件。一個(gè)系統(tǒng)可能要響應(yīng)多個(gè)周期性事件流，根據(jù)每個(gè)事件處理所需的時(shí)間，可能甚至無(wú)法處理所有事件。例如，如果有 m 個(gè)周期事件，事件 i 以周期 Pi 發(fā)生，并需要 Ci 秒 CPU 時(shí)間處理一個(gè)事件，那么可以處理負(fù)載的條件是

只有滿足這個(gè)條件的實(shí)時(shí)系統(tǒng)稱為可調(diào)度的，這意味著它實(shí)際上能夠被實(shí)現(xiàn)。一個(gè)不滿足此檢驗(yàn)標(biāo)準(zhǔn)的進(jìn)程不能被調(diào)度，因?yàn)檫@些進(jìn)程共同需要的 CPU 時(shí)間總和大于 CPU 能提供的時(shí)間。

實(shí)時(shí)系統(tǒng)的調(diào)度算法可以是靜態(tài)的或動(dòng)態(tài)的。前者在系統(tǒng)開(kāi)始運(yùn)行之前做出調(diào)度決策；后者在運(yùn)行過(guò)程中進(jìn)行調(diào)度決策。只有在可以提前掌握所完成的工作以及必須滿足的截止時(shí)間等信息時(shí)，靜態(tài)調(diào)度才能工作，而動(dòng)態(tài)調(diào)度不需要這些限制。

調(diào)度策略和機(jī)制

到目前為止，我們隱含的假設(shè)系統(tǒng)中所有進(jìn)程屬于不同的分組用戶并且進(jìn)程間存在相互競(jìng)爭(zhēng) CPU 的情況。通常情況下確實(shí)如此，但有時(shí)也會(huì)發(fā)生一個(gè)進(jìn)程會(huì)有很多子進(jìn)程并在其控制下運(yùn)行的情況。例如，一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)進(jìn)程會(huì)有很多子進(jìn)程。每一個(gè)子進(jìn)程可能處理不同的請(qǐng)求，或者每個(gè)子進(jìn)程實(shí)現(xiàn)不同的功能（如請(qǐng)求分析、磁盤(pán)訪問(wèn)等）。主進(jìn)程完全可能掌握哪一個(gè)子進(jìn)程最重要（或最緊迫），而哪一個(gè)最不重要。但是，以上討論的調(diào)度算法中沒(méi)有一個(gè)算法從用戶進(jìn)程接收有關(guān)的調(diào)度決策信息，這就導(dǎo)致了調(diào)度程序很少能夠做出最優(yōu)的選擇。

解決問(wèn)題的辦法是將調(diào)度機(jī)制(scheduling mechanism)和調(diào)度策略(scheduling policy)分開(kāi)，這是長(zhǎng)期一貫的原則。這也就意味著調(diào)度算法在某種方式下被參數(shù)化了，但是參數(shù)可以被用戶進(jìn)程填寫(xiě)。讓我們首先考慮數(shù)據(jù)庫(kù)的例子。假設(shè)內(nèi)核使用優(yōu)先級(jí)調(diào)度算法，并提供了一條可供進(jìn)程設(shè)置優(yōu)先級(jí)的系統(tǒng)調(diào)用。這樣，盡管父進(jìn)程本身并不參與調(diào)度，但它可以控制如何調(diào)度子進(jìn)程的細(xì)節(jié)。調(diào)度機(jī)制位于內(nèi)核，而調(diào)度策略由用戶進(jìn)程決定，調(diào)度策略和機(jī)制分離是一種關(guān)鍵性思路。

內(nèi)存管理中的算法

操作系統(tǒng)在內(nèi)存管理上也出現(xiàn)過(guò)許多算法，這些算法的目標(biāo)的最終目的都是為了合理分配內(nèi)存。

操作系統(tǒng)有兩種內(nèi)存管理方式，一種是位圖，一種是鏈表。

在使用鏈表管理內(nèi)存時(shí)，有幾種方法的變體

當(dāng)按照地址順序在鏈表中存放進(jìn)程和空閑區(qū)時(shí)，有幾種算法可以為創(chuàng)建的進(jìn)程（或者從磁盤(pán)中換入的進(jìn)程）分配內(nèi)存。我們先假設(shè)內(nèi)存管理器知道應(yīng)該分配多少內(nèi)存，最簡(jiǎn)單的算法是使用首次適配(first fit)。內(nèi)存管理器會(huì)沿著段列表進(jìn)行掃描，直到找個(gè)一個(gè)足夠大的空閑區(qū)為止。除非空閑區(qū)大小和要分配的空間大小一樣，否則將空閑區(qū)分為兩部分，一部分供進(jìn)程使用；一部分生成新的空閑區(qū)。首次適配算法是一種速度很快的算法，因?yàn)樗鼤?huì)盡可能的搜索鏈表。

首次適配的一個(gè)小的變體是下次適配(next fit)。它和首次匹配的工作方式相同，只有一個(gè)不同之處那就是下次適配在每次找到合適的空閑區(qū)時(shí)就會(huì)記錄當(dāng)時(shí)的位置，以便下次尋找空閑區(qū)時(shí)從上次結(jié)束的地方開(kāi)始搜索，而不是像首次匹配算法那樣每次都會(huì)從頭開(kāi)始搜索。Bays(1997)證明了下次適配算法的性能略低于首次匹配算法。

另外一個(gè)著名的并且廣泛使用的算法是最佳適配(best fit)。最佳適配會(huì)從頭到尾尋找整個(gè)鏈表，找出能夠容納進(jìn)程的最小空閑區(qū)。最佳適配算法會(huì)試圖找出最接近實(shí)際需要的空閑區(qū)，以最好的匹配請(qǐng)求和可用空閑區(qū)，而不是先一次拆分一個(gè)以后可能會(huì)用到的大的空閑區(qū)。比如現(xiàn)在我們需要一個(gè)大小為 2 的塊，那么首次匹配算法會(huì)把這個(gè)塊分配在位置 5 的空閑區(qū)，而最佳適配算法會(huì)把該塊分配在位置為 18 的空閑區(qū)，如下

那么最佳適配算法的性能如何呢？最佳適配會(huì)遍歷整個(gè)鏈表，所以最佳適配算法的性能要比首次匹配算法差。但是令人想不到的是，最佳適配算法要比首次匹配和下次匹配算法浪費(fèi)更多的內(nèi)存，因?yàn)樗鼤?huì)產(chǎn)生大量無(wú)用的小緩沖區(qū)，首次匹配算法生成的空閑區(qū)會(huì)更大一些。

最佳適配的空閑區(qū)會(huì)分裂出很多非常小的緩沖區(qū)，為了避免這一問(wèn)題，可以考慮使用最差適配(worst fit)算法。即總是分配最大的內(nèi)存區(qū)域（所以你現(xiàn)在明白為什么最佳適配算法會(huì)分裂出很多小緩沖區(qū)了吧），使新分配的空閑區(qū)比較大從而可以繼續(xù)使用。仿真程序表明最差適配算法也不是一個(gè)好主意。

如果為進(jìn)程和空閑區(qū)維護(hù)各自獨(dú)立的鏈表，那么這四個(gè)算法的速度都能得到提高。這樣，這四種算法的目標(biāo)都是為了檢查空閑區(qū)而不是進(jìn)程。但這種分配速度的提高的一個(gè)不可避免的代價(jià)是增加復(fù)雜度和減慢內(nèi)存釋放速度，因?yàn)楸仨殞⒁粋€(gè)回收的段從進(jìn)程鏈表中刪除并插入空閑鏈表區(qū)。

如果進(jìn)程和空閑區(qū)使用不同的鏈表，那么可以按照大小對(duì)空閑區(qū)鏈表排序，以便提高最佳適配算法的速度。在使用最佳適配算法搜索由小到大排列的空閑區(qū)鏈表時(shí)，只要找到一個(gè)合適的空閑區(qū)，則這個(gè)空閑區(qū)就是能容納這個(gè)作業(yè)的最小空閑區(qū)，因此是最佳匹配。因?yàn)榭臻e區(qū)鏈表以單鏈表形式組織，所以不需要進(jìn)一步搜索?？臻e區(qū)鏈表按大小排序時(shí)，首次適配算法與最佳適配算法一樣快，而下次適配算法在這里毫無(wú)意義。

另一種分配算法是快速適配(quick fit)算法，它為那些常用大小的空閑區(qū)維護(hù)單獨(dú)的鏈表。例如，有一個(gè) n 項(xiàng)的表，該表的第一項(xiàng)是指向大小為 4 KB 的空閑區(qū)鏈表表頭指針，第二項(xiàng)是指向大小為 8 KB 的空閑區(qū)鏈表表頭指針，第三項(xiàng)是指向大小為 12 KB 的空閑區(qū)鏈表表頭指針，以此類推。比如 21 KB 這樣的空閑區(qū)既可以放在 20 KB 的鏈表中，也可以放在一個(gè)專門存放大小比較特別的空閑區(qū)鏈表中。

快速匹配算法尋找一個(gè)指定代銷的空閑區(qū)也是十分快速的，但它和所有將空閑區(qū)按大小排序的方案一樣，都有一個(gè)共同的缺點(diǎn)，即在一個(gè)進(jìn)程終止或被換出時(shí)，尋找它的相鄰塊并查看是否可以合并的過(guò)程都是非常耗時(shí)的。如果不進(jìn)行合并，內(nèi)存將會(huì)很快分裂出大量進(jìn)程無(wú)法利用的小空閑區(qū)。

頁(yè)面置換算法

頁(yè)面置換有非常多的算法，下面一起來(lái)認(rèn)識(shí)一下

當(dāng)發(fā)生缺頁(yè)異常時(shí)，操作系統(tǒng)會(huì)選擇一個(gè)頁(yè)面進(jìn)行換出從而為新進(jìn)來(lái)的頁(yè)面騰出空間。如果要換出的頁(yè)面在內(nèi)存中已經(jīng)被修改，那么必須將其寫(xiě)到磁盤(pán)中以使磁盤(pán)副本保持最新狀態(tài)。如果頁(yè)面沒(méi)有被修改過(guò)，并且磁盤(pán)中的副本也已經(jīng)是最新的，那么就不需要進(jìn)行重寫(xiě)。那么就直接使用調(diào)入的頁(yè)面覆蓋需要移除的頁(yè)面就可以了。

當(dāng)發(fā)生缺頁(yè)中斷時(shí)，雖然可以隨機(jī)的選擇一個(gè)頁(yè)面進(jìn)行置換，但是如果每次都選擇一個(gè)不常用的頁(yè)面會(huì)提升系統(tǒng)的性能。如果一個(gè)經(jīng)常使用的頁(yè)面被換出，那么這個(gè)頁(yè)面在短時(shí)間內(nèi)又可能被重復(fù)使用，那么就可能會(huì)造成額外的性能開(kāi)銷。在關(guān)于頁(yè)面的主題上有很多頁(yè)面置換算法(page replacement algorithms)，這些已經(jīng)從理論上和實(shí)踐上得到了證明。

下面我們就來(lái)探討一下有哪些頁(yè)面置換算法。

最優(yōu)頁(yè)面置換算法

最優(yōu)的頁(yè)面置換算法很容易描述，但在實(shí)際情況下很難實(shí)現(xiàn)。它的工作流程如下：在缺頁(yè)中斷發(fā)生時(shí)，這些頁(yè)面之一將在下一條指令（包含該指令的頁(yè)面）上被引用。其他頁(yè)面則可能要到 10、100 或者 1000 條指令后才會(huì)被訪問(wèn)。每個(gè)頁(yè)面都可以用在該頁(yè)首次被訪問(wèn)前所要執(zhí)行的指令數(shù)作為標(biāo)記。

最優(yōu)化的頁(yè)面算法表明應(yīng)該標(biāo)記最大的頁(yè)面。如果一個(gè)頁(yè)面在 800 萬(wàn)條指令內(nèi)不會(huì)被使用，另外一個(gè)頁(yè)面在 600 萬(wàn)條指令內(nèi)不會(huì)被使用，則置換前一個(gè)頁(yè)面，從而把需要調(diào)入這個(gè)頁(yè)面而發(fā)生的缺頁(yè)中斷推遲。計(jì)算機(jī)也像人類一樣，會(huì)把不愿意做的事情盡可能的往后拖。

這個(gè)算法最大的問(wèn)題是無(wú)法實(shí)現(xiàn)。當(dāng)缺頁(yè)中斷發(fā)生時(shí)，操作系統(tǒng)無(wú)法知道各個(gè)頁(yè)面的下一次將在什么時(shí)候被訪問(wèn)。這種算法在實(shí)際過(guò)程中根本不會(huì)使用。

最近未使用頁(yè)面置換算法

為了能夠讓操作系統(tǒng)收集頁(yè)面使用信息，大部分使用虛擬地址的計(jì)算機(jī)都有兩個(gè)狀態(tài)位，R 和 M，來(lái)和每個(gè)頁(yè)面進(jìn)行關(guān)聯(lián)。每當(dāng)引用頁(yè)面（讀入或?qū)懭耄r(shí)都設(shè)置 R，寫(xiě)入（即修改）頁(yè)面時(shí)設(shè)置 M，這些位包含在每個(gè)頁(yè)表項(xiàng)中，就像下面所示

因?yàn)槊看卧L問(wèn)時(shí)都會(huì)更新這些位，因此由硬件來(lái)設(shè)置它們非常重要。一旦某個(gè)位被設(shè)置為 1，就會(huì)一直保持 1 直到操作系統(tǒng)下次來(lái)修改此位。

如果硬件沒(méi)有這些位，那么可以使用操作系統(tǒng)的缺頁(yè)中斷和時(shí)鐘中斷機(jī)制來(lái)進(jìn)行模擬。當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，將其所有的頁(yè)面都標(biāo)記為不在內(nèi)存；一旦訪問(wèn)任何一個(gè)頁(yè)面就會(huì)引發(fā)一次缺頁(yè)中斷，此時(shí)操作系統(tǒng)就可以設(shè)置R 位(在它的內(nèi)部表中)，修改頁(yè)表項(xiàng)使其指向正確的頁(yè)面，并設(shè)置為READ ONLY模式，然后重新啟動(dòng)引起缺頁(yè)中斷的指令。如果頁(yè)面隨后被修改，就會(huì)發(fā)生另一個(gè)缺頁(yè)異常。從而允許操作系統(tǒng)設(shè)置 M 位并把頁(yè)面的模式設(shè)置為READ/WRITE。

可以用 R 位和 M 位來(lái)構(gòu)造一個(gè)簡(jiǎn)單的頁(yè)面置換算法：當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)，操作系統(tǒng)將其所有頁(yè)面的兩個(gè)位都設(shè)置為 0。R 位定期的被清零（在每個(gè)時(shí)鐘中斷）。用來(lái)將最近未引用的頁(yè)面和已引用的頁(yè)面分開(kāi)。

當(dāng)出現(xiàn)缺頁(yè)中斷后，操作系統(tǒng)會(huì)檢查所有的頁(yè)面，并根據(jù)它們的 R 位和 M 位將當(dāng)前值分為四類：

第 0 類：沒(méi)有引用 R，沒(méi)有修改 M

第 1 類：沒(méi)有引用 R，已修改 M

第 2 類：引用 R ，沒(méi)有修改 M

第 3 類：已被訪問(wèn) R，已被修改 M

盡管看起來(lái)好像無(wú)法實(shí)現(xiàn)第一類頁(yè)面，但是當(dāng)?shù)谌愴?yè)面的 R 位被時(shí)鐘中斷清除時(shí)，它們就會(huì)發(fā)生。時(shí)鐘中斷不會(huì)清除 M 位，因?yàn)樾枰@個(gè)信息才能知道是否寫(xiě)回磁盤(pán)中。清除 R 但不清除 M 會(huì)導(dǎo)致出現(xiàn)一類頁(yè)面。

NRU(Not Recently Used)算法從編號(hào)最小的非空類中隨機(jī)刪除一個(gè)頁(yè)面。此算法隱含的思想是，在一個(gè)時(shí)鐘內(nèi)（約 20 ms）淘汰一個(gè)已修改但是沒(méi)有被訪問(wèn)的頁(yè)面要比一個(gè)大量引用的未修改頁(yè)面好，NRU 的主要優(yōu)點(diǎn)是易于理解并且能夠有效的實(shí)現(xiàn)。

先進(jìn)先出頁(yè)面置換算法

另一種開(kāi)銷較小的方式是使用FIFO(First-In,First-Out)算法，這種類型的數(shù)據(jù)結(jié)構(gòu)也適用在頁(yè)面置換算法中。由操作系統(tǒng)維護(hù)一個(gè)所有在當(dāng)前內(nèi)存中的頁(yè)面的鏈表，最早進(jìn)入的放在表頭，最新進(jìn)入的頁(yè)面放在表尾。在發(fā)生缺頁(yè)異常時(shí)，會(huì)把頭部的頁(yè)移除并且把新的頁(yè)添加到表尾。

先進(jìn)先出頁(yè)面可能是最簡(jiǎn)單的頁(yè)面替換算法了。在這種算法中，操作系統(tǒng)會(huì)跟蹤鏈表中內(nèi)存中的所有頁(yè)。下面我們舉個(gè)例子看一下（這個(gè)算法我剛開(kāi)始看的時(shí)候有點(diǎn)懵逼，后來(lái)才看懂，我還是很菜）

初始化的時(shí)候，沒(méi)有任何頁(yè)面，所以第一次的時(shí)候會(huì)檢查頁(yè)面 1 是否位于鏈表中，沒(méi)有在鏈表中，那么就是MISS，頁(yè)面1 進(jìn)入鏈表，鏈表的先進(jìn)先出的方向如圖所示。

類似的，第二次會(huì)先檢查頁(yè)面 2 是否位于鏈表中，沒(méi)有在鏈表中，那么頁(yè)面 2 進(jìn)入鏈表，狀態(tài)為MISS，依此類推。

我們來(lái)看第四次，此時(shí)的鏈表為1 2 3，第四次會(huì)檢查頁(yè)面2是否位于鏈表中，經(jīng)過(guò)檢索后，發(fā)現(xiàn) 2 在鏈表中，那么狀態(tài)就是HIT，并不會(huì)再進(jìn)行入隊(duì)和出隊(duì)操作，第五次也是一樣的。

下面來(lái)看第六次，此時(shí)的鏈表還是1 2 3，因?yàn)橹皼](méi)有執(zhí)行進(jìn)入鏈表操作，頁(yè)面5會(huì)首先進(jìn)行檢查，發(fā)現(xiàn)鏈表中沒(méi)有頁(yè)面 5 ，則執(zhí)行頁(yè)面 5 的進(jìn)入鏈表操作，頁(yè)面 2 執(zhí)行出鏈表的操作，執(zhí)行完成后的鏈表順序?yàn)? 3 5。

第二次機(jī)會(huì)頁(yè)面置換算法

我們上面學(xué)到的 FIFO 鏈表頁(yè)面有個(gè)缺陷，那就是出鏈和入鏈并不會(huì)進(jìn)行 check檢查，這樣就會(huì)容易把經(jīng)常使用的頁(yè)面置換出去，為了避免這一問(wèn)題，我們對(duì)該算法做一個(gè)簡(jiǎn)單的修改：我們檢查最老頁(yè)面的R 位，如果是 0 ，那么這個(gè)頁(yè)面就是最老的而且沒(méi)有被使用，那么這個(gè)頁(yè)面就會(huì)被立刻換出。如果 R 位是 1，那么就清除此位，此頁(yè)面會(huì)被放在鏈表的尾部，修改它的裝入時(shí)間就像剛放進(jìn)來(lái)的一樣。然后繼續(xù)搜索。

這種算法叫做第二次機(jī)會(huì)(second chance)算法，就像下面這樣，我們看到頁(yè)面 A 到 H 保留在鏈表中，并按到達(dá)內(nèi)存的時(shí)間排序。

a）按照先進(jìn)先出的方法排列的頁(yè)面；b）在時(shí)刻 20 處發(fā)生缺頁(yè)異常中斷并且 A 的 R 位已經(jīng)設(shè)置時(shí)的頁(yè)面鏈表。

假設(shè)缺頁(yè)異常發(fā)生在時(shí)刻 20 處，這時(shí)最老的頁(yè)面是 A ，它是在 0 時(shí)刻到達(dá)的。如果 A 的 R 位是 0，那么它將被淘汰出內(nèi)存，或者把它寫(xiě)回磁盤(pán)（如果它已經(jīng)被修改過(guò)），或者只是簡(jiǎn)單的放棄（如果它是未被修改過(guò)）。另一方面，如果它的 R 位已經(jīng)設(shè)置了，則將 A 放到鏈表的尾部并且重新設(shè)置裝入時(shí)間為當(dāng)前時(shí)刻（20 處），然后清除 R 位。然后從 B 頁(yè)面開(kāi)始繼續(xù)搜索合適的頁(yè)面。

尋找第二次機(jī)會(huì)的是在最近的時(shí)鐘間隔中未被訪問(wèn)過(guò)的頁(yè)面。如果所有的頁(yè)面都被訪問(wèn)過(guò)，該算法就會(huì)被簡(jiǎn)化為單純的FIFO 算法。具體來(lái)說(shuō)，假設(shè)圖 a 中所有頁(yè)面都設(shè)置了 R 位。操作系統(tǒng)將頁(yè)面依次移到鏈表末尾，每次都在添加到末尾時(shí)清除 R 位。最后，算法又會(huì)回到頁(yè)面 A，此時(shí)的 R 位已經(jīng)被清除，那么頁(yè)面 A 就會(huì)被執(zhí)行出鏈處理，因此算法能夠正常結(jié)束。

時(shí)鐘頁(yè)面置換算法

即使上面提到的第二次頁(yè)面置換算法也是一種比較合理的算法，但它經(jīng)常要在鏈表中移動(dòng)頁(yè)面，既降低了效率，而且這種算法也不是必須的。一種比較好的方式是把所有的頁(yè)面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，一個(gè)表針指向最老的頁(yè)面。如下圖所示

當(dāng)缺頁(yè)錯(cuò)誤出現(xiàn)時(shí)，算法首先檢查表針指向的頁(yè)面，如果它的 R 位是 0 就淘汰該頁(yè)面，并把新的頁(yè)面插入到這個(gè)位置，然后把表針向前移動(dòng)一位；如果 R 位是 1 就清除 R 位并把表針前移一個(gè)位置。重復(fù)這個(gè)過(guò)程直到找到了一個(gè) R 位為 0 的頁(yè)面位置。了解這個(gè)算法的工作方式，就明白為什么它被稱為時(shí)鐘(clokc)算法了。

最近最少使用頁(yè)面置換算法

最近最少使用頁(yè)面置換算法的一個(gè)解釋會(huì)是下面這樣：在前面幾條指令中頻繁使用的頁(yè)面和可能在后面的幾條指令中被使用。反過(guò)來(lái)說(shuō)，已經(jīng)很久沒(méi)有使用的頁(yè)面有可能在未來(lái)一段時(shí)間內(nèi)仍不會(huì)被使用。這個(gè)思想揭示了一個(gè)可以實(shí)現(xiàn)的算法：在缺頁(yè)中斷時(shí)，置換未使用時(shí)間最長(zhǎng)的頁(yè)面。這個(gè)策略稱為L(zhǎng)RU(Least Recently Used)，最近最少使用頁(yè)面置換算法。

雖然 LRU 在理論上是可以實(shí)現(xiàn)的，但是從長(zhǎng)遠(yuǎn)看來(lái)代價(jià)比較高。為了完全實(shí)現(xiàn) LRU，會(huì)在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表，最頻繁使用的頁(yè)位于表頭，最近最少使用的頁(yè)位于表尾。困難的是在每次內(nèi)存引用時(shí)更新整個(gè)鏈表。在鏈表中找到一個(gè)頁(yè)面，刪除它，然后把它移動(dòng)到表頭是一個(gè)非常耗時(shí)的操作，即使使用硬件來(lái)實(shí)現(xiàn)也是一樣的費(fèi)時(shí)。

然而，還有其他方法可以通過(guò)硬件實(shí)現(xiàn) LRU。讓我們首先考慮最簡(jiǎn)單的方式。這個(gè)方法要求硬件有一個(gè) 64 位的計(jì)數(shù)器，它在每條指令執(zhí)行完成后自動(dòng)加 1，每個(gè)頁(yè)表必須有一個(gè)足夠容納這個(gè)計(jì)數(shù)器值的域。在每次訪問(wèn)內(nèi)存后，將當(dāng)前的值保存到被訪問(wèn)頁(yè)面的頁(yè)表項(xiàng)中。一旦發(fā)生缺頁(yè)異常，操作系統(tǒng)就檢查所有頁(yè)表項(xiàng)中計(jì)數(shù)器的值，找到值最小的一個(gè)頁(yè)面，這個(gè)頁(yè)面就是最少使用的頁(yè)面。

用軟件模擬 LRU

盡管上面的 LRU 算法在原則上是可以實(shí)現(xiàn)的，但是很少有機(jī)器能夠擁有那些特殊的硬件。上面是硬件的實(shí)現(xiàn)方式，那么現(xiàn)在考慮要用軟件來(lái)實(shí)現(xiàn) LRU 。一種可以實(shí)現(xiàn)的方案是NFU(Not Frequently Used，最不常用)算法。它需要一個(gè)軟件計(jì)數(shù)器來(lái)和每個(gè)頁(yè)面關(guān)聯(lián)，初始化的時(shí)候是 0 。在每個(gè)時(shí)鐘中斷時(shí)，操作系統(tǒng)會(huì)瀏覽內(nèi)存中的所有頁(yè)，會(huì)將每個(gè)頁(yè)面的 R 位（0 或 1）加到它的計(jì)數(shù)器上。這個(gè)計(jì)數(shù)器大體上跟蹤了各個(gè)頁(yè)面訪問(wèn)的頻繁程度。當(dāng)缺頁(yè)異常出現(xiàn)時(shí)，則置換計(jì)數(shù)器值最小的頁(yè)面。

NFU 最主要的問(wèn)題是它不會(huì)忘記任何東西，想一下是不是這樣？例如，在一個(gè)多次（掃描）的編譯器中，在第一遍掃描中頻繁使用的頁(yè)面會(huì)在后續(xù)的掃描中也有較高的計(jì)數(shù)。事實(shí)上，如果第一次掃描的執(zhí)行時(shí)間恰好是各次掃描中最長(zhǎng)的，那么后續(xù)遍歷的頁(yè)面的統(tǒng)計(jì)次數(shù)總會(huì)比第一次頁(yè)面的統(tǒng)計(jì)次數(shù)小。結(jié)果是操作系統(tǒng)將置換有用的頁(yè)面而不是不再使用的頁(yè)面。

幸運(yùn)的是只需要對(duì) NFU 做一個(gè)簡(jiǎn)單的修改就可以讓它模擬 LRU，這個(gè)修改有兩個(gè)步驟

首先，在 R 位被添加進(jìn)來(lái)之前先把計(jì)數(shù)器右移一位；

第二步，R 位被添加到最左邊的位而不是最右邊的位。

修改以后的算法稱為老化(aging)算法，下圖解釋了老化算法是如何工作的。

我們假設(shè)在第一個(gè)時(shí)鐘周期內(nèi)頁(yè)面 0 - 5 的 R 位依次是 1，0，1，0，1，1，（也就是頁(yè)面 0 是 1，頁(yè)面 1 是 0，頁(yè)面 2 是 1 這樣類推）。也就是說(shuō)，在 0 個(gè)時(shí)鐘周期到 1 個(gè)時(shí)鐘周期之間，0，2，4，5 都被引用了，從而把它們的 R 位設(shè)置為 1，剩下的設(shè)置為 0 。在相關(guān)的六個(gè)計(jì)數(shù)器被右移之后 R 位被添加到左側(cè)，就像上圖中的 a。剩下的四列顯示了接下來(lái)的四個(gè)時(shí)鐘周期內(nèi)的六個(gè)計(jì)數(shù)器變化。

當(dāng)缺頁(yè)異常出現(xiàn)時(shí)，將置換（就是移除）計(jì)數(shù)器值最小的頁(yè)面。如果一個(gè)頁(yè)面在前面 4 個(gè)時(shí)鐘周期內(nèi)都沒(méi)有被訪問(wèn)過(guò)，那么它的計(jì)數(shù)器應(yīng)該會(huì)有四個(gè)連續(xù)的 0 ，因此它的值肯定要比前面 3 個(gè)時(shí)鐘周期內(nèi)都沒(méi)有被訪問(wèn)過(guò)的頁(yè)面的計(jì)數(shù)器小。

這個(gè)算法與 LRU 算法有兩個(gè)重要的區(qū)別：看一下上圖中的e，第三列和第五列

它們?cè)趦蓚€(gè)時(shí)鐘周期內(nèi)都沒(méi)有被訪問(wèn)過(guò)，在此之前的時(shí)鐘周期內(nèi)都引用了兩個(gè)頁(yè)面。根據(jù) LRU 算法，如果需要置換的話，那么應(yīng)該在這兩個(gè)頁(yè)面中選擇一個(gè)。那么問(wèn)題來(lái)了，我萌應(yīng)該選擇哪個(gè)？現(xiàn)在的問(wèn)題是我們不知道時(shí)鐘周期 1 到時(shí)鐘周期 2 內(nèi)它們中哪個(gè)頁(yè)面是后被訪問(wèn)到的。因?yàn)樵诿總€(gè)時(shí)鐘周期內(nèi)只記錄了一位，所以無(wú)法區(qū)分在一個(gè)時(shí)鐘周期內(nèi)哪個(gè)頁(yè)面最早被引用，哪個(gè)頁(yè)面是最后被引用的。因此，我們能做的就是置換頁(yè)面3，因?yàn)轫?yè)面 3 在周期 0 - 1 內(nèi)都沒(méi)有被訪問(wèn)過(guò)，而頁(yè)面 5 卻被引用過(guò)。

LRU 與老化之前的第 2 個(gè)區(qū)別是，在老化期間，計(jì)數(shù)器具有有限數(shù)量的位（這個(gè)例子中是 8 位），這就限制了以往的訪問(wèn)記錄。如果兩個(gè)頁(yè)面的計(jì)數(shù)器都是 0 ，那么我們可以隨便選擇一個(gè)進(jìn)行置換。實(shí)際上，有可能其中一個(gè)頁(yè)面的訪問(wèn)次數(shù)是在 9 個(gè)時(shí)鐘周期以前，而另外一個(gè)頁(yè)面是在 1000 個(gè)時(shí)鐘周期之前，但是我們卻無(wú)法看到這些。在實(shí)際過(guò)程中，如果時(shí)鐘周期是 20 ms，8 位一般是夠用的。所以我們經(jīng)常拿 20 ms 來(lái)舉例。

工作集頁(yè)面置換算法

在最單純的分頁(yè)系統(tǒng)中，剛啟動(dòng)進(jìn)程時(shí)，在內(nèi)存中并沒(méi)有頁(yè)面。此時(shí)如果 CPU 嘗試匹配第一條指令，就會(huì)得到一個(gè)缺頁(yè)異常，使操作系統(tǒng)裝入含有第一條指令的頁(yè)面。其他的錯(cuò)誤比如全局變量和堆棧引起的缺頁(yè)異常通常會(huì)緊接著發(fā)生。一段時(shí)間以后，進(jìn)程需要的大部分頁(yè)面都在內(nèi)存中了，此時(shí)進(jìn)程開(kāi)始在較少的缺頁(yè)異常環(huán)境中運(yùn)行。這個(gè)策略稱為請(qǐng)求調(diào)頁(yè)(demand paging)，因?yàn)轫?yè)面是根據(jù)需要被調(diào)入的，而不是預(yù)先調(diào)入的。

在一個(gè)大的地址空間中系統(tǒng)的讀所有的頁(yè)面，將會(huì)造成很多缺頁(yè)異常，因此會(huì)導(dǎo)致沒(méi)有足夠的內(nèi)存來(lái)容納這些頁(yè)面。不過(guò)幸運(yùn)的是，大部分進(jìn)程不是這樣工作的，它們都會(huì)以局部性方式(locality of reference)來(lái)訪問(wèn)，這意味著在執(zhí)行的任何階段，程序只引用其中的一小部分。

一個(gè)進(jìn)程當(dāng)前正在使用的頁(yè)面的集合稱為它的工作集(working set)，如果整個(gè)工作集都在內(nèi)存中，那么進(jìn)程在運(yùn)行到下一運(yùn)行階段（例如，編譯器的下一遍掃面）之前，不會(huì)產(chǎn)生很多缺頁(yè)中斷。如果內(nèi)存太小從而無(wú)法容納整個(gè)工作集，那么進(jìn)程的運(yùn)行過(guò)程中會(huì)產(chǎn)生大量的缺頁(yè)中斷，會(huì)導(dǎo)致運(yùn)行速度也會(huì)變得緩慢。因?yàn)橥ǔＶ恍枰獛准{秒就能執(zhí)行一條指令，而通常需要十毫秒才能從磁盤(pán)上讀入一個(gè)頁(yè)面。如果一個(gè)程序每 10 ms 只能執(zhí)行一到兩條指令，那么它將需要很長(zhǎng)時(shí)間才能運(yùn)行完。如果只是執(zhí)行幾條指令就會(huì)產(chǎn)生中斷，那么就稱作這個(gè)程序產(chǎn)生了顛簸(thrashing)。

在多道程序的系統(tǒng)中，通常會(huì)把進(jìn)程移到磁盤(pán)上（即從內(nèi)存中移走所有的頁(yè)面），這樣可以讓其他進(jìn)程有機(jī)會(huì)占用 CPU 。有一個(gè)問(wèn)題是，當(dāng)進(jìn)程想要再次把之前調(diào)回磁盤(pán)的頁(yè)面調(diào)回內(nèi)存怎么辦？從技術(shù)的角度上來(lái)講，并不需要做什么，此進(jìn)程會(huì)一直產(chǎn)生缺頁(yè)中斷直到它的工作集被調(diào)回內(nèi)存。然后，每次裝入一個(gè)進(jìn)程需要 20、100 甚至 1000 次缺頁(yè)中斷，速度顯然太慢了，并且由于 CPU 需要幾毫秒時(shí)間處理一個(gè)缺頁(yè)中斷，因此由相當(dāng)多的 CPU 時(shí)間也被浪費(fèi)了。

因此，不少分頁(yè)系統(tǒng)中都會(huì)設(shè)法跟蹤進(jìn)程的工作集，確保這些工作集在進(jìn)程運(yùn)行時(shí)被調(diào)入內(nèi)存。這個(gè)方法叫做工作集模式(working set model)。它被設(shè)計(jì)用來(lái)減少缺頁(yè)中斷的次數(shù)的。在進(jìn)程運(yùn)行前首先裝入工作集頁(yè)面的這一個(gè)過(guò)程被稱為預(yù)先調(diào)頁(yè)(prepaging)，工作集是隨著時(shí)間來(lái)變化的。

根據(jù)研究表明，大多數(shù)程序并不是均勻的訪問(wèn)地址空間的，而訪問(wèn)往往是集中于一小部分頁(yè)面。一次內(nèi)存訪問(wèn)可能會(huì)取出一條指令，也可能會(huì)取出數(shù)據(jù)，或者是存儲(chǔ)數(shù)據(jù)。在任一時(shí)刻 t，都存在一個(gè)集合，它包含所有最近 k 次內(nèi)存訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面。這個(gè)集合w(k,t)就是工作集。因?yàn)樽罱?k = 1次訪問(wèn)肯定會(huì)訪問(wèn)最近 k > 1 次訪問(wèn)所訪問(wèn)過(guò)的頁(yè)面，所以w(k,t)是 k 的單調(diào)遞減函數(shù)。隨著 k 的增大，w(k,t)是不會(huì)無(wú)限變大的，因?yàn)槌绦虿豢赡茉L問(wèn)比所能容納頁(yè)面數(shù)量上限還多的頁(yè)面。

事實(shí)上大多數(shù)應(yīng)用程序只會(huì)任意訪問(wèn)一小部分頁(yè)面集合，但是這個(gè)集合會(huì)隨著時(shí)間而緩慢變化，所以為什么一開(kāi)始曲線會(huì)快速上升而 k 較大時(shí)上升緩慢。為了實(shí)現(xiàn)工作集模型，操作系統(tǒng)必須跟蹤哪些頁(yè)面在工作集中。一個(gè)進(jìn)程從它開(kāi)始執(zhí)行到當(dāng)前所實(shí)際使用的 CPU 時(shí)間總數(shù)通常稱作當(dāng)前實(shí)際運(yùn)行時(shí)間。進(jìn)程的工作集可以被稱為在過(guò)去的 t 秒實(shí)際運(yùn)行時(shí)間中它所訪問(wèn)過(guò)的頁(yè)面集合。

下面來(lái)簡(jiǎn)單描述一下工作集的頁(yè)面置換算法，基本思路就是找出一個(gè)不在工作集中的頁(yè)面并淘汰它。下面是一部分機(jī)器頁(yè)表

因?yàn)橹挥心切┰趦?nèi)存中的頁(yè)面才可以作為候選者被淘汰，所以該算法忽略了那些不在內(nèi)存中的頁(yè)面。每個(gè)表項(xiàng)至少包含兩條信息：上次使用該頁(yè)面的近似時(shí)間和 R（訪問(wèn)）位?？瞻椎木匦伪硎驹撍惴ú恍枰渌侄危珥?yè)框數(shù)量、保護(hù)位、修改位。

算法的工作流程如下，假設(shè)硬件要設(shè)置 R 和 M 位。同樣的，在每個(gè)時(shí)鐘周期內(nèi)，一個(gè)周期性的時(shí)鐘中斷會(huì)使軟件清除Referenced(引用)位。在每個(gè)缺頁(yè)異常，頁(yè)表會(huì)被掃描以找出一個(gè)合適的頁(yè)面把它置換。

隨著每個(gè)頁(yè)表項(xiàng)的處理，都需要檢查 R 位。如果 R 位是 1，那么就會(huì)將當(dāng)前時(shí)間寫(xiě)入頁(yè)表項(xiàng)的上次使用時(shí)間域，表示的意思就是缺頁(yè)異常發(fā)生時(shí)頁(yè)面正在被使用。因?yàn)轫?yè)面在當(dāng)前時(shí)鐘周期內(nèi)被訪問(wèn)過(guò)，那么它應(yīng)該出現(xiàn)在工作集中而不是被刪除（假設(shè) t 是橫跨了多個(gè)時(shí)鐘周期）。

如果 R 位是 0 ，那么在當(dāng)前的時(shí)鐘周期內(nèi)這個(gè)頁(yè)面沒(méi)有被訪問(wèn)過(guò)，應(yīng)該作為被刪除的對(duì)象。為了查看是否應(yīng)該將其刪除，會(huì)計(jì)算其使用期限（當(dāng)前虛擬時(shí)間 - 上次使用時(shí)間），來(lái)用這個(gè)時(shí)間和 t 進(jìn)行對(duì)比。如果使用期限大于 t，那么這個(gè)頁(yè)面就不再工作集中，而使用新的頁(yè)面來(lái)替換它。然后繼續(xù)掃描更新剩下的表項(xiàng)。

然而，如果 R 位是 0 但是使用期限小于等于 t，那么此頁(yè)應(yīng)該在工作集中。此時(shí)就會(huì)把頁(yè)面臨時(shí)保存起來(lái)，但是會(huì)記生存時(shí)間最長(zhǎng)（即上次使用時(shí)間的最小值）的頁(yè)面。如果掃描完整個(gè)頁(yè)表卻沒(méi)有找到適合被置換的頁(yè)面，也就意味著所有的頁(yè)面都在工作集中。在這種情況下，如果找到了一個(gè)或者多個(gè) R = 0 的頁(yè)面，就淘汰生存時(shí)間最長(zhǎng)的頁(yè)面。最壞的情況下是，在當(dāng)前時(shí)鐘周期內(nèi)，所有的頁(yè)面都被訪問(wèn)過(guò)了（也就是都有 R = 1），因此就隨機(jī)選擇一個(gè)頁(yè)面淘汰，如果有的話最好選一個(gè)未被訪問(wèn)的頁(yè)面，也就是干凈的頁(yè)面。

工作集時(shí)鐘頁(yè)面置換算法

當(dāng)缺頁(yè)異常發(fā)生后，需要掃描整個(gè)頁(yè)表才能確定被淘汰的頁(yè)面，因此基本工作集算法還是比較浪費(fèi)時(shí)間的。一個(gè)對(duì)基本工作集算法的提升是基于時(shí)鐘算法但是卻使用工作集的信息，這種算法稱為WSClock(工作集時(shí)鐘)。由于它的實(shí)現(xiàn)簡(jiǎn)單并且具有高性能，因此在實(shí)踐中被廣泛應(yīng)用。

與時(shí)鐘算法一樣，所需的數(shù)據(jù)結(jié)構(gòu)是一個(gè)以頁(yè)框?yàn)樵氐难h(huán)列表，就像下面這樣

工作集時(shí)鐘頁(yè)面置換算法的操作：a) 和 b) 給出 R = 1 時(shí)所發(fā)生的情形；c) 和 d) 給出 R = 0 的例子

最初的時(shí)候，該表是空的。當(dāng)裝入第一個(gè)頁(yè)面后，把它加載到該表中。隨著更多的頁(yè)面的加入，它們形成一個(gè)環(huán)形結(jié)構(gòu)。每個(gè)表項(xiàng)包含來(lái)自基本工作集算法的上次使用時(shí)間，以及 R 位（已標(biāo)明）和 M 位（未標(biāo)明）。

與時(shí)鐘算法一樣，在每個(gè)缺頁(yè)異常時(shí)，首先檢查指針指向的頁(yè)面。如果 R 位被是設(shè)置為 1，該頁(yè)面在當(dāng)前時(shí)鐘周期內(nèi)就被使用過(guò)，那么該頁(yè)面就不適合被淘汰。然后把該頁(yè)面的 R 位置為 0，指針指向下一個(gè)頁(yè)面，并重復(fù)該算法。該事件序列化后的狀態(tài)參見(jiàn)圖 b。

現(xiàn)在考慮指針指向的頁(yè)面 R = 0 時(shí)會(huì)發(fā)生什么，參見(jiàn)圖 c，如果頁(yè)面的使用期限大于 t 并且頁(yè)面為被訪問(wèn)過(guò)，那么這個(gè)頁(yè)面就不會(huì)在工作集中，并且在磁盤(pán)上會(huì)有一個(gè)此頁(yè)面的副本。申請(qǐng)重新調(diào)入一個(gè)新的頁(yè)面，并把新的頁(yè)面放在其中，如圖 d 所示。另一方面，如果頁(yè)面被修改過(guò)，就不能重新申請(qǐng)頁(yè)面，因?yàn)檫@個(gè)頁(yè)面在磁盤(pán)上沒(méi)有有效的副本。為了避免由于調(diào)度寫(xiě)磁盤(pán)操作引起的進(jìn)程切換，指針繼續(xù)向前走，算法繼續(xù)對(duì)下一個(gè)頁(yè)面進(jìn)行操作。畢竟，有可能存在一個(gè)老的，沒(méi)有被修改過(guò)的頁(yè)面可以立即使用。

原則上來(lái)說(shuō)，所有的頁(yè)面都有可能因?yàn)榇疟P(pán)I/O在某個(gè)時(shí)鐘周期內(nèi)被調(diào)度。為了降低磁盤(pán)阻塞，需要設(shè)置一個(gè)限制，即最大只允許寫(xiě)回 n 個(gè)頁(yè)面。一旦達(dá)到該限制，就不允許調(diào)度新的寫(xiě)操作。

那么就有個(gè)問(wèn)題，指針會(huì)繞一圈回到原點(diǎn)的，如果回到原點(diǎn)，它的起始點(diǎn)會(huì)發(fā)生什么？這里有兩種情況：

至少調(diào)度了一次寫(xiě)操作

沒(méi)有調(diào)度過(guò)寫(xiě)操作

在第一種情況中，指針僅僅是不停的移動(dòng)，尋找一個(gè)未被修改過(guò)的頁(yè)面。由于已經(jīng)調(diào)度了一個(gè)或者多個(gè)寫(xiě)操作，最終會(huì)有某個(gè)寫(xiě)操作完成，它的頁(yè)面會(huì)被標(biāo)記為未修改。置換遇到的第一個(gè)未被修改過(guò)的頁(yè)面，這個(gè)頁(yè)面不一定是第一個(gè)被調(diào)度寫(xiě)操作的頁(yè)面，因?yàn)橛脖P(pán)驅(qū)動(dòng)程序?yàn)榱藘?yōu)化性能可能會(huì)把寫(xiě)操作重排序。

對(duì)于第二種情況，所有的頁(yè)面都在工作集中，否則將至少調(diào)度了一個(gè)寫(xiě)操作。由于缺乏額外的信息，最簡(jiǎn)單的方法就是置換一個(gè)未被修改的頁(yè)面來(lái)使用，掃描中需要記錄未被修改的頁(yè)面的位置，如果不存在未被修改的頁(yè)面，就選定當(dāng)前頁(yè)面并把它寫(xiě)回磁盤(pán)。

頁(yè)面置換算法小結(jié)

我們到現(xiàn)在已經(jīng)研究了各種頁(yè)面置換算法，現(xiàn)在我們來(lái)一個(gè)簡(jiǎn)單的總結(jié)，算法的總結(jié)歸納如下

最優(yōu)算法在當(dāng)前頁(yè)面中置換最后要訪問(wèn)的頁(yè)面。不幸的是，沒(méi)有辦法來(lái)判定哪個(gè)頁(yè)面是最后一個(gè)要訪問(wèn)的，因此實(shí)際上該算法不能使用。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)。

NRU算法根據(jù) R 位和 M 位的狀態(tài)將頁(yè)面氛圍四類。從編號(hào)最小的類別中隨機(jī)選擇一個(gè)頁(yè)面。NRU 算法易于實(shí)現(xiàn)，但是性能不是很好。存在更好的算法。

FIFO會(huì)跟蹤頁(yè)面加載進(jìn)入內(nèi)存中的順序，并把頁(yè)面放入一個(gè)鏈表中。有可能刪除存在時(shí)間最長(zhǎng)但是還在使用的頁(yè)面，因此這個(gè)算法也不是一個(gè)很好的選擇。

第二次機(jī)會(huì)算法是對(duì) FIFO 的一個(gè)修改，它會(huì)在刪除頁(yè)面之前檢查這個(gè)頁(yè)面是否仍在使用。如果頁(yè)面正在使用，就會(huì)進(jìn)行保留。這個(gè)改進(jìn)大大提高了性能。

時(shí)鐘算法是第二次機(jī)會(huì)算法的另外一種實(shí)現(xiàn)形式，時(shí)鐘算法和第二次算法的性能差不多，但是會(huì)花費(fèi)更少的時(shí)間來(lái)執(zhí)行算法。

LRU算法是一個(gè)非常優(yōu)秀的算法，但是沒(méi)有特殊的硬件(TLB)很難實(shí)現(xiàn)。如果沒(méi)有硬件，就不能使用 LRU 算法。

NFU算法是一種近似于 LRU 的算法，它的性能不是非常好。

老化算法是一種更接近 LRU 算法的實(shí)現(xiàn)，并且可以更好的實(shí)現(xiàn)，因此是一個(gè)很好的選擇

最后兩種算法都使用了工作集算法。工作集算法提供了合理的性能開(kāi)銷，但是它的實(shí)現(xiàn)比較復(fù)雜。WSClock是另外一種變體，它不僅能夠提供良好的性能，而且可以高效地實(shí)現(xiàn)。

總之，最好的算法是老化算法和WSClock算法。他們分別是基于 LRU 和工作集算法。他們都具有良好的性能并且能夠被有效的實(shí)現(xiàn)。還存在其他一些好的算法，但實(shí)際上這兩個(gè)可能是最重要的。

文件系統(tǒng)中的算法

文件系統(tǒng)在備份的過(guò)程中會(huì)使用到算法，文件備份分為邏輯轉(zhuǎn)儲(chǔ)和物理轉(zhuǎn)儲(chǔ)

物理轉(zhuǎn)儲(chǔ)和邏輯轉(zhuǎn)儲(chǔ)

物理轉(zhuǎn)儲(chǔ)的主要優(yōu)點(diǎn)是簡(jiǎn)單、極為快速（基本上是以磁盤(pán)的速度運(yùn)行），缺點(diǎn)是全量備份，不能跳過(guò)指定目錄，也不能增量轉(zhuǎn)儲(chǔ)，也不能恢復(fù)個(gè)人文件的請(qǐng)求。因此絕大多數(shù)情況下不會(huì)使用物理轉(zhuǎn)儲(chǔ)，而使用邏輯轉(zhuǎn)儲(chǔ)。

邏輯轉(zhuǎn)儲(chǔ)(logical dump)從一個(gè)或幾個(gè)指定的目錄開(kāi)始，遞歸轉(zhuǎn)儲(chǔ)自指定日期開(kāi)始后更改的文件和目錄。因此，在邏輯轉(zhuǎn)儲(chǔ)中，轉(zhuǎn)儲(chǔ)磁盤(pán)上有一系列經(jīng)過(guò)仔細(xì)識(shí)別的目錄和文件，這使得根據(jù)請(qǐng)求輕松還原特定文件或目錄。

既然邏輯轉(zhuǎn)儲(chǔ)是最常用的方式，那么下面就讓我們研究一下邏輯轉(zhuǎn)儲(chǔ)的通用算法。此算法在 UNIX 系統(tǒng)上廣為使用，如下圖所示

待轉(zhuǎn)儲(chǔ)的文件系統(tǒng)，其中方框代表目錄，圓圈代表文件。黃色的項(xiàng)目表是自上次轉(zhuǎn)儲(chǔ)以來(lái)修改過(guò)。每個(gè)目錄和文件都被標(biāo)上其 inode 號(hào)。

此算法會(huì)轉(zhuǎn)儲(chǔ)位于修改文件或目錄路徑上的所有目錄（也包括未修改的目錄），原因有兩個(gè)。第一是能夠在不同電腦的文件系統(tǒng)中恢復(fù)轉(zhuǎn)儲(chǔ)的文件。通過(guò)這種方式，轉(zhuǎn)儲(chǔ)和重新存儲(chǔ)的程序能夠用來(lái)在兩個(gè)電腦之間傳輸整個(gè)文件系統(tǒng)。第二個(gè)原因是能夠?qū)蝹€(gè)文件進(jìn)行增量恢復(fù)。

邏輯轉(zhuǎn)儲(chǔ)算法需要維持一個(gè) inode 為索引的位圖(bitmap)，每個(gè) inode 包含了幾位。隨著算法的進(jìn)行，位圖中的這些位會(huì)被設(shè)置或清除。算法的執(zhí)行分成四個(gè)階段。第一階段從起始目錄（本例為根目錄）開(kāi)始檢查其中所有的目錄項(xiàng)。對(duì)每一個(gè)修改過(guò)的文件，該算法將在位圖中標(biāo)記其 inode。算法還會(huì)標(biāo)記并遞歸檢查每一個(gè)目錄（不管是否修改過(guò)）。

在第一階段結(jié)束時(shí)，所有修改過(guò)的文件和全部目錄都在位圖中標(biāo)記了，如下圖所示

理論上來(lái)說(shuō)，第二階段再次遞歸遍歷目錄樹(shù)，并去掉目錄樹(shù)中任何不包含被修改過(guò)的文件或目錄的標(biāo)記。本階段執(zhí)行的結(jié)果如下

注意，inode 編號(hào)為 10、11、14、27、29 和 30 的目錄已經(jīng)被去掉了標(biāo)記，因?yàn)樗鼈兯膬?nèi)容沒(méi)有修改。它們也不會(huì)轉(zhuǎn)儲(chǔ)。相反，inode 編號(hào)為 5 和 6 的目錄本身盡管沒(méi)有被修改過(guò)也要被轉(zhuǎn)儲(chǔ)，因?yàn)樵谛碌臋C(jī)器上恢復(fù)當(dāng)日的修改時(shí)需要這些信息。為了提高算法效率，可以將這兩階段的目錄樹(shù)遍歷合二為一。

現(xiàn)在已經(jīng)知道了哪些目錄和文件必須被轉(zhuǎn)儲(chǔ)了，這就是上圖 b 中標(biāo)記的內(nèi)容，第三階段算法將以節(jié)點(diǎn)號(hào)為序，掃描這些 inode 并轉(zhuǎn)儲(chǔ)所有標(biāo)記為需轉(zhuǎn)儲(chǔ)的目錄，如下圖所示

為了進(jìn)行恢復(fù)，每個(gè)被轉(zhuǎn)儲(chǔ)的目錄都用目錄的屬性（所有者、時(shí)間）作為前綴。

最后，在第四階段，上圖中被標(biāo)記的文件也被轉(zhuǎn)儲(chǔ)，同樣，由其文件屬性作為前綴。至此，轉(zhuǎn)儲(chǔ)結(jié)束。

從轉(zhuǎn)儲(chǔ)磁盤(pán)上還原文件系統(tǒng)非常簡(jiǎn)單。一開(kāi)始，需要在磁盤(pán)上創(chuàng)建空文件系統(tǒng)。然后恢復(fù)最近一次的完整轉(zhuǎn)儲(chǔ)。由于磁帶上最先出現(xiàn)目錄，所以首先恢復(fù)目錄，給出文件系統(tǒng)的框架(skeleton)，然后恢復(fù)文件系統(tǒng)本身。在完整存儲(chǔ)之后是第一次增量存儲(chǔ)，然后是第二次重復(fù)這一過(guò)程，以此類推。

盡管邏輯存儲(chǔ)十分簡(jiǎn)單，但是也會(huì)有一些棘手的問(wèn)題。首先，既然空閑塊列表并不是一個(gè)文件，那么在所有被轉(zhuǎn)儲(chǔ)的文件恢復(fù)完畢之后，就需要從零開(kāi)始重新構(gòu)造。

另外一個(gè)問(wèn)題是關(guān)于鏈接。如果文件鏈接了兩個(gè)或者多個(gè)目錄，而文件只能還原一次，那么并且所有指向該文件的目錄都必須還原。

還有一個(gè)問(wèn)題是，UNIX 文件實(shí)際上包含了許多空洞(holes)。打開(kāi)文件，寫(xiě)幾個(gè)字節(jié)，然后找到文件中偏移了一定距離的地址，又寫(xiě)入更多的字節(jié)，這么做是合法的。但兩者之間的這些塊并不屬于文件本身，從而也不應(yīng)該在其上進(jìn)行文件轉(zhuǎn)儲(chǔ)和恢復(fù)。

最后，無(wú)論屬于哪一個(gè)目錄，特殊文件，命名管道以及類似的文件都不應(yīng)該被轉(zhuǎn)儲(chǔ)。

I/O 中的算法

在 I/O 的磁盤(pán)調(diào)度中也出現(xiàn)過(guò)很多算法，關(guān)于尋址和磁盤(pán)臂的轉(zhuǎn)動(dòng)都會(huì)對(duì)算法產(chǎn)生影響，下面我們就來(lái)一起看下

一般情況下，影響磁盤(pán)快讀寫(xiě)的時(shí)間由下面幾個(gè)因素決定

尋道時(shí)間 - 尋道時(shí)間指的就是將磁盤(pán)臂移動(dòng)到需要讀取磁盤(pán)塊上的時(shí)間

旋轉(zhuǎn)延遲 - 等待合適的扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間

實(shí)際數(shù)據(jù)的讀取或者寫(xiě)入時(shí)間

這三種時(shí)間參數(shù)也是磁盤(pán)尋道的過(guò)程。一般情況下，尋道時(shí)間對(duì)總時(shí)間的影響最大，所以，有效的降低尋道時(shí)間能夠提高磁盤(pán)的讀取速度。

如果磁盤(pán)驅(qū)動(dòng)程序每次接收一個(gè)請(qǐng)求并按照接收順序完成請(qǐng)求，這種處理方式也就是先來(lái)先服務(wù)(First-Come, First-served, FCFS)，這種方式很難優(yōu)化尋道時(shí)間。因?yàn)槊看味紩?huì)按照順序處理，不管順序如何，有可能這次讀完后需要等待一個(gè)磁盤(pán)旋轉(zhuǎn)一周才能繼續(xù)讀取，而其他柱面能夠馬上進(jìn)行讀取，這種情況下每次請(qǐng)求也會(huì)排隊(duì)。

通常情況下，磁盤(pán)在進(jìn)行尋道時(shí)，其他進(jìn)程會(huì)產(chǎn)生其他的磁盤(pán)請(qǐng)求。磁盤(pán)驅(qū)動(dòng)程序會(huì)維護(hù)一張表，表中會(huì)記錄著柱面號(hào)當(dāng)作索引，每個(gè)柱面未完成的請(qǐng)求會(huì)形成鏈表，鏈表頭存放在表的相應(yīng)表項(xiàng)中。

一種對(duì)先來(lái)先服務(wù)的算法改良的方案是使用最短路徑優(yōu)先(SSF)算法，下面描述了這個(gè)算法。

假如我們?cè)趯?duì)磁道 6 號(hào)進(jìn)行尋址時(shí)，同時(shí)發(fā)生了對(duì) 11 , 2 , 4, 14, 8, 15, 3 的請(qǐng)求，如果采用先來(lái)先服務(wù)的原則，如下圖所示

我們可以計(jì)算一下磁盤(pán)臂所跨越的磁盤(pán)數(shù)量為 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51，相當(dāng)于是跨越了 51 次盤(pán)面，如果使用最短路徑優(yōu)先，我們來(lái)計(jì)算一下跨越的盤(pán)面

跨越的磁盤(pán)數(shù)量為 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ，相比 51 足足省了兩倍的時(shí)間。

但是，最短路徑優(yōu)先的算法也不是完美無(wú)缺的，這種算法照樣存在問(wèn)題，那就是優(yōu)先級(jí)問(wèn)題，

這里有一個(gè)原型可以參考就是我們?nèi)粘Ｉ钪械碾娞?，電梯使用一種電梯算法(elevator algorithm)來(lái)進(jìn)行調(diào)度，從而滿足協(xié)調(diào)效率和公平性這兩個(gè)相互沖突的目標(biāo)。電梯一般會(huì)保持向一個(gè)方向移動(dòng)，直到在那個(gè)方向上沒(méi)有請(qǐng)求為止，然后改變方向。

電梯算法需要維護(hù)一個(gè)二進(jìn)制位，也就是當(dāng)前的方向位：UP(向上)或者是DOWN(向下)。當(dāng)一個(gè)請(qǐng)求處理完成后，磁盤(pán)或電梯的驅(qū)動(dòng)程序會(huì)檢查該位，如果此位是 UP 位，磁盤(pán)臂或者電梯倉(cāng)移到下一個(gè)更高跌未完成的請(qǐng)求。如果高位沒(méi)有未完成的請(qǐng)求，則取相反方向。當(dāng)方向位是DOWN時(shí)，同時(shí)存在一個(gè)低位的請(qǐng)求，磁盤(pán)臂會(huì)轉(zhuǎn)向該點(diǎn)。如果不存在的話，那么它只是停止并等待。

我們舉個(gè)例子來(lái)描述一下電梯算法，比如各個(gè)柱面得到服務(wù)的順序是 4，7，10，14，9，6，3，1 ，那么它的流程圖如下

所以電梯算法需要跨越的盤(pán)面數(shù)量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22

電梯算法通常情況下不如 SSF 算法。

一些磁盤(pán)控制器為軟件提供了一種檢查磁頭下方當(dāng)前扇區(qū)號(hào)的方法，使用這樣的控制器，能夠進(jìn)行另一種優(yōu)化。如果對(duì)一個(gè)相同的柱面有兩個(gè)或者多個(gè)請(qǐng)求正等待處理，驅(qū)動(dòng)程序可以發(fā)出請(qǐng)求讀寫(xiě)下一次要通過(guò)磁頭的扇區(qū)。

這里需要注意一點(diǎn)，當(dāng)一個(gè)柱面有多條磁道時(shí)，相繼的請(qǐng)求可能針對(duì)不同的磁道，這種選擇沒(méi)有代價(jià)，因?yàn)檫x擇磁頭不需要移動(dòng)磁盤(pán)臂也沒(méi)有旋轉(zhuǎn)延遲。

對(duì)于磁盤(pán)來(lái)說(shuō)，最影響性能的就是尋道時(shí)間和旋轉(zhuǎn)延遲，所以一次只讀取一個(gè)或兩個(gè)扇區(qū)的效率是非常低的。出于這個(gè)原因，許多磁盤(pán)控制器總是讀出多個(gè)扇區(qū)并進(jìn)行高速緩存，即使只請(qǐng)求一個(gè)扇區(qū)時(shí)也是這樣。一般情況下讀取一個(gè)扇區(qū)的同時(shí)會(huì)讀取該扇區(qū)所在的磁道或者是所有剩余的扇區(qū)被讀出，讀出扇區(qū)的數(shù)量取決于控制器的高速緩存中有多少可用的空間。

磁盤(pán)控制器的高速緩存和操作系統(tǒng)的高速緩存有一些不同，磁盤(pán)控制器的高速緩存用于緩存沒(méi)有實(shí)際被請(qǐng)求的塊，而操作系統(tǒng)維護(hù)的高速緩存由顯示地讀出的塊組成，并且操作系統(tǒng)會(huì)認(rèn)為這些塊在近期仍然會(huì)頻繁使用。

當(dāng)同一個(gè)控制器上有多個(gè)驅(qū)動(dòng)器時(shí)，操作系統(tǒng)應(yīng)該為每個(gè)驅(qū)動(dòng)器都單獨(dú)的維護(hù)一個(gè)未完成的請(qǐng)求表。一旦有某個(gè)驅(qū)動(dòng)器閑置時(shí)，就應(yīng)該發(fā)出一個(gè)尋道請(qǐng)求來(lái)將磁盤(pán)臂移到下一個(gè)被請(qǐng)求的柱面。如果下一個(gè)尋道請(qǐng)求到來(lái)時(shí)恰好沒(méi)有磁盤(pán)臂處于正確的位置，那么驅(qū)動(dòng)程序會(huì)在剛剛完成傳輸?shù)尿?qū)動(dòng)器上發(fā)出一個(gè)新的尋道命令并等待，等待下一次中斷到來(lái)時(shí)檢查哪個(gè)驅(qū)動(dòng)器處于閑置狀態(tài)。

死鎖中的算法

在死鎖的處理策略中，其中一點(diǎn)是忽略死鎖帶來(lái)的影響（驚呆了），出現(xiàn)過(guò)一個(gè)叫做鴕鳥(niǎo)算法的

最簡(jiǎn)單的解決辦法就是使用鴕鳥(niǎo)算法(ostrich algorithm)，把頭埋在沙子里，假裝問(wèn)題根本沒(méi)有發(fā)生。每個(gè)人看待這個(gè)問(wèn)題的反應(yīng)都不同。數(shù)學(xué)家認(rèn)為死鎖是不可接受的，必須通過(guò)有效的策略來(lái)防止死鎖的產(chǎn)生。工程師想要知道問(wèn)題發(fā)生的頻次，系統(tǒng)因?yàn)槠渌虮罎⒌拇螖?shù)和死鎖帶來(lái)的嚴(yán)重后果。如果死鎖發(fā)生的頻次很低，而經(jīng)常會(huì)由于硬件故障、編譯器錯(cuò)誤等其他操作系統(tǒng)問(wèn)題導(dǎo)致系統(tǒng)崩潰，那么大多數(shù)工程師不會(huì)修復(fù)死鎖。

在死鎖的檢測(cè)中出現(xiàn)過(guò)一些算法

每種類型多個(gè)資源的死鎖檢測(cè)方式

如果有多種相同的資源存在，就需要采用另一種方法來(lái)檢測(cè)死鎖?？梢酝ㄟ^(guò)構(gòu)造一個(gè)矩陣來(lái)檢測(cè)從 P1 -> Pn 這 n 個(gè)進(jìn)程中的死鎖。

現(xiàn)在我們提供一種基于矩陣的算法來(lái)檢測(cè)從 P1 到 Pn 這 n 個(gè)進(jìn)程中的死鎖。假設(shè)資源類型為 m，E1 代表資源類型1，E2 表示資源類型 2 ，Ei 代表資源類型 i (1 <= i <= m)。E 表示的是?現(xiàn)有資源向量(existing resource vector)，代表每種已存在的資源總數(shù)。

現(xiàn)在我們就需要構(gòu)造兩個(gè)數(shù)組：C 表示的是當(dāng)前分配矩陣(current allocation matrix)，R 表示的是請(qǐng)求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數(shù)。所以，Cij 表示 Pi 持有資源 j 的數(shù)量。Rij 表示 Pi 所需要獲得的資源 j 的數(shù)量

一般來(lái)說(shuō)，已分配資源 j 的數(shù)量加起來(lái)再和所有可供使用的資源數(shù)相加 = 該類資源的總數(shù)。

死鎖的檢測(cè)就是基于向量的比較。每個(gè)進(jìn)程起初都是沒(méi)有被標(biāo)記過(guò)的，算法會(huì)開(kāi)始對(duì)進(jìn)程做標(biāo)記，進(jìn)程被標(biāo)記后說(shuō)明進(jìn)程被執(zhí)行了，不會(huì)進(jìn)入死鎖，當(dāng)算法結(jié)束時(shí)，任何沒(méi)有被標(biāo)記過(guò)的進(jìn)程都會(huì)被判定為死鎖進(jìn)程。

上面我們探討了兩種檢測(cè)死鎖的方式，那么現(xiàn)在你知道怎么檢測(cè)后，你何時(shí)去做死鎖檢測(cè)呢？一般來(lái)說(shuō)，有兩個(gè)考量標(biāo)準(zhǔn)：

每當(dāng)有資源請(qǐng)求時(shí)就去檢測(cè)，這種方式會(huì)占用昂貴的 CPU 時(shí)間。

每隔 k 分鐘檢測(cè)一次，或者當(dāng) CPU 使用率降低到某個(gè)標(biāo)準(zhǔn)下去檢測(cè)。考慮到 CPU 效率的原因，如果死鎖進(jìn)程達(dá)到一定數(shù)量，就沒(méi)有多少進(jìn)程可以運(yùn)行，所以 CPU 會(huì)經(jīng)常空閑。

還有死鎖避免的算法

銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調(diào)度算法，它本身是一種死鎖的調(diào)度算法。它的模型是基于一個(gè)城鎮(zhèn)中的銀行家，銀行家向城鎮(zhèn)中的客戶承諾了一定數(shù)量的貸款額度。算法要做的就是判斷請(qǐng)求是否會(huì)進(jìn)入一種不安全的狀態(tài)。如果是，就拒絕請(qǐng)求，如果請(qǐng)求后系統(tǒng)是安全的，就接受該請(qǐng)求。

比如下面的例子，銀行家一共為所有城鎮(zhèn)居民提供了 15 單位個(gè)貸款額度，一個(gè)單位表示 1k 美元，如下所示

城鎮(zhèn)居民都喜歡做生意，所以就會(huì)涉及到貸款，每個(gè)人能貸款的最大額度不一樣，在某一時(shí)刻，A/B/C/D 的貸款金額如下

上面每個(gè)人的貸款總額加起來(lái)是 13，馬上接近 15，銀行家只能給 A 和 C 進(jìn)行放貸，可以拖著 B 和 D、所以，可以讓 A 和 C 首先完成，釋放貸款額度，以此來(lái)滿足其他居民的貸款。這是一種安全的狀態(tài)。

如果每個(gè)人的請(qǐng)求導(dǎo)致總額會(huì)超過(guò)甚至接近 15 ，就會(huì)處于一種不安全的狀態(tài)，如下所示

這樣，每個(gè)人還能貸款至少 2 個(gè)單位的額度，如果其中有一個(gè)人發(fā)起最大額度的貸款請(qǐng)求，就會(huì)使系統(tǒng)處于一種死鎖狀態(tài)。

這里注意一點(diǎn)：不安全狀態(tài)并不一定引起死鎖，由于客戶不一定需要其最大的貸款額度，但是銀行家不敢抱著這種僥幸心理。

銀行家算法就是對(duì)每個(gè)請(qǐng)求進(jìn)行檢查，檢查是否請(qǐng)求會(huì)引起不安全狀態(tài)，如果不會(huì)引起，那么就接受該請(qǐng)求；如果會(huì)引起，那么就推遲該請(qǐng)求。

類似的，還有多個(gè)資源的銀行家算法，讀者可以自行了解。