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

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

進(jìn)程和線程在調(diào)度時(shí)候出現(xiàn)過很多算法，這些算法的設(shè)計(jì)背景是 當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)斗埂，會(huì)頻繁的有很多進(jìn)程或者線程來同時(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 可用，那么必須選擇接下來哪個(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)

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

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

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

批處理系統(tǒng) 廣泛應(yīng)用于商業(yè)領(lǐng)域实夹，比如用來處理工資單、存貨清單粒梦、賬目收入亮航、賬目支出、利息計(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ò)誤也有可能無限期的排斥其他所有進(jìn)程。為了避免這種情況讹剔，搶占式也是必須的。

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

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

通常有 三個(gè)指標(biāo) 來衡量系統(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è)批處理提交開始直到作業(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í)間）固该。

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

先來先服務(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)程就開始運(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)翰萨。

不過脏答，先來先服務(wù)也是有缺點(diǎn)的，那就是沒有優(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)來優(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)中都是很常用的隆敢，所以有必要來探討一下交互式調(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)被去，然后是教授、秘書奖唯、后勤人員惨缆，最后是學(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è)蟆盹，那么我們可以通過首先運(yùn)行最短的作業(yè)來使響應(yīng)時(shí)間最短。這里唯一的問題是如何從當(dāng)前可運(yùn)行進(jìn)程中找出最短的那一個(gè)進(jìn)程闺金。

一種方式是根據(jù)進(jìn)程過去的行為進(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)來改進(jìn)估計(jì)時(shí)間，即 aT0+ (1- 1)T1 掀亩。通過選擇 a 的值舔哪，可以決定是盡快忘掉老的運(yùn)行時(shí)間，還是在一段長(zhǎng)時(shí)間內(nèi)始終記住它們槽棍。當(dāng) a = 1/2 時(shí)捉蚤，可以得到下面這個(gè)序列

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

有時(shí)把這種通過當(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)承諾是一件好事灌侣，不過很難實(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ù)器舌狗，來增加下一次服務(wù)器運(yùn)行的機(jī)會(huì)叽奥。當(dāng)服務(wù)完成后，它會(huì)把彩票還給客戶端讓其有機(jī)會(huì)再次運(yùn)行痛侍。事實(shí)上朝氓，如果沒有客戶機(jī)，服務(wù)器也根本不需要彩票主届。

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

公平分享調(diào)度

到目前為止君丁，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身枫夺，而不用考慮該進(jìn)程的擁有者是誰。結(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í)間片保證爪喘，那么無論一個(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í)都是通過把程序劃分為一組進(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í)間煤傍，可能甚至無法處理所有事件盖文。例如嘱蛋，如果有 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)開始運(yùn)行之前做出調(diào)度決策函荣；后者在運(yùn)行過程中進(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ù)庫管理系統(tǒng)進(jìn)程會(huì)有很多子進(jìn)程资铡。每一個(gè)子進(jìn)程可能處理不同的請(qǐng)求，或者每個(gè)子進(jìn)程實(shí)現(xiàn)不同的功能（如請(qǐng)求分析幢码、磁盤訪問等）笤休。主進(jìn)程完全可能掌握哪一個(gè)子進(jìn)程最重要（或最緊迫），而哪一個(gè)最不重要症副。但是宛官，以上討論的調(diào)度算法中沒有一個(gè)算法從用戶進(jìn)程接收有關(guān)的調(diào)度決策信息，這就導(dǎo)致了調(diào)度程序很少能夠做出最優(yōu)的選擇瓦糕。

解決問題的辦法是將 調(diào)度機(jī)制(scheduling mechanism) 和 調(diào)度策略(scheduling policy) 分開底洗，這是長(zhǎng)期一貫的原則。這也就意味著調(diào)度算法在某種方式下被參數(shù)化了咕娄，但是參數(shù)可以被用戶進(jìn)程填寫亥揖。讓我們首先考慮數(shù)據(jù)庫的例子。假設(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)過許多算法，這些算法的目標(biāo)的最終目的都是為了合理分配內(nèi)存用含。

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

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

當(dāng)按照地址順序在鏈表中存放進(jìn)程和空閑區(qū)時(shí)，有幾種算法可以為創(chuàng)建的進(jì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é)束的地方開始搜索虾标，而不是像首次匹配算法那樣每次都會(huì)從頭開始搜索。 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)生大量無用的小緩沖區(qū)琅催，首次匹配算法生成的空閑區(qū)會(huì)更大一些居凶。

最佳適配的空閑區(qū)會(huì)分裂出很多非常小的緩沖區(qū)，為了避免這一問題恢暖，可以考慮使用 最差適配(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)一步搜索榨呆。空閑區(qū)鏈表按大小排序時(shí)庸队，首次適配算法與最佳適配算法一樣快积蜻，而下次適配算法在這里毫無意義。

另一種分配算法是 快速適配(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í)灶似，尋找它的相鄰塊并查看是否可以合并的過程都是非常耗時(shí)的。如果不進(jìn)行合并瑞你，內(nèi)存將會(huì)很快分裂出大量進(jìn)程無法利用的小空閑區(qū)酪惭。

頁面置換算法

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

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

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

下面我們就來探討一下有哪些頁面置換算法集歇。

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

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

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

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

最近未使用頁面置換算法

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

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

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

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

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

• 第 0 類：沒有引用 R蜈首，沒有修改 M

• 第 1 類：沒有引用 R实抡，已修改 M

• 第 2 類：引用 R ，沒有修改 M

• 第 3 類：已被訪問 R欢策，已被修改 M

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

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

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

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

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

• 初始化的時(shí)候烟具，沒有任何頁面，所以第一次的時(shí)候會(huì)檢查頁面 1 是否位于鏈表中奠蹬，沒有在鏈表中朝聋，那么就是 MISS ，頁面1 進(jìn)入鏈表囤躁，鏈表的先進(jìn)先出的方向如圖所示冀痕。

• 類似的，第二次會(huì)先檢查頁面 2 是否位于鏈表中狸演，沒有在鏈表中言蛇，那么頁面 2 進(jìn)入鏈表，狀態(tài)為 MISS 严沥，依此類推猜极。

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

• 下面來看第六次勘高，此時(shí)的鏈表還是 1 2 3 ，因?yàn)橹皼]有執(zhí)行進(jìn)入鏈表操作坟桅，頁面 5 會(huì)首先進(jìn)行檢查华望，發(fā)現(xiàn)鏈表中沒有頁面 5 ，則執(zhí)行頁面 5 的進(jìn)入鏈表操作仅乓，頁面 2 執(zhí)行出鏈表的操作赖舟，執(zhí)行完成后的鏈表順序?yàn)? 2 3 5 。

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

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

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

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

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

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

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

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

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

最近最少使用頁面置換算法

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

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

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

用軟件模擬 LRU

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

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

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

• 首先镊叁，在 R 位被添加進(jìn)來之前先把計(jì)數(shù)器右移一位尘颓；

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

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

我們假設(shè)在第一個(gè)時(shí)鐘周期內(nèi)頁面 0 - 5 的 R 位依次是 1敛腌，0卧土，1惫皱，0，1尤莺，1逸吵，（也就是頁面 0 是 1，頁面 1 是 0缝裁，頁面 2 是 1 這樣類推）扫皱。也就是說， 在 0 個(gè)時(shí)鐘周期到 1 個(gè)時(shí)鐘周期之間捷绑，0韩脑，2，4粹污，5 都被引用了 段多，從而把它們的 R 位設(shè)置為 1，剩下的設(shè)置為 0 壮吩。在相關(guān)的六個(gè)計(jì)數(shù)器被右移之后 R 位被添加到 左側(cè) 进苍，就像上圖中的 a。剩下的四列顯示了接下來的四個(gè)時(shí)鐘周期內(nèi)的六個(gè)計(jì)數(shù)器變化鸭叙。

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

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

它們?cè)趦蓚€(gè)時(shí)鐘周期內(nèi)都沒有被訪問過嗡善，在此之前的時(shí)鐘周期內(nèi)都引用了兩個(gè)頁面。根據(jù) LRU 算法学歧，如果需要置換的話罩引，那么應(yīng)該在這兩個(gè)頁面中選擇一個(gè)。那么問題來了枝笨，我萌應(yīng)該選擇哪個(gè)袁铐？現(xiàn)在的問題是我們不知道時(shí)鐘周期 1 到時(shí)鐘周期 2 內(nèi)它們中哪個(gè)頁面是后被訪問到的。因?yàn)樵诿總€(gè)時(shí)鐘周期內(nèi)只記錄了一位伺帘，所以無法區(qū)分在一個(gè)時(shí)鐘周期內(nèi)哪個(gè)頁面最早被引用昭躺，哪個(gè)頁面是最后被引用的。因此伪嫁，我們能做的就是置換 頁面3 领炫， 因?yàn)轫撁?3 在周期 0 - 1 內(nèi)都沒有被訪問過，而頁面 5 卻被引用過 张咳。

LRU 與老化之前的第 2 個(gè)區(qū)別是帝洪，在老化期間似舵，計(jì)數(shù)器具有有限數(shù)量的位（這個(gè)例子中是 8 位），這就限制了以往的訪問記錄葱峡。如果兩個(gè)頁面的計(jì)數(shù)器都是 0 砚哗，那么我們可以隨便選擇一個(gè)進(jìn)行置換。實(shí)際上砰奕，有可能其中一個(gè)頁面的訪問次數(shù)是在 9 個(gè)時(shí)鐘周期以前蛛芥，而另外一個(gè)頁面是在 1000 個(gè)時(shí)鐘周期之前，但是我們卻無法看到這些军援。在實(shí)際過程中仅淑，如果時(shí)鐘周期是 20 ms，8 位一般是夠用的胸哥。所以我們經(jīng)常拿 20 ms 來舉例涯竟。

工作集頁面置換算法

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

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

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

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

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

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

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

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

因?yàn)橹挥心切┰趦?nèi)存中的頁面才可以作為候選者被淘汰鳍侣，所以該算法忽略了那些不在內(nèi)存中的頁面丁稀。每個(gè)表項(xiàng)至少包含兩條信息：上次使用該頁面的近似時(shí)間和 R（訪問）位∫芯郏空白的矩形表示該算法不需要其他字段线衫，例如頁框數(shù)量、保護(hù)位惑折、修改位授账。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 沒有調(diào)度過寫操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

注意，inode 編號(hào)為 10低斋、11蜂厅、14、27膊畴、29 和 30 的目錄已經(jīng)被去掉了標(biāo)記掘猿，因?yàn)樗鼈兯膬?nèi)容 沒有修改 。它們也不會(huì)轉(zhuǎn)儲(chǔ)唇跨。相反稠通，inode 編號(hào)為 5 和 6 的目錄本身盡管沒有被修改過也要被轉(zhuǎn)儲(chǔ)衬衬，因?yàn)樵谛碌臋C(jī)器上恢復(fù)當(dāng)日的修改時(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ǔ)磁盤上還原文件系統(tǒng)非常簡(jiǎn)單峦耘。一開始，需要在磁盤上創(chuàng)建空文件系統(tǒng)趟畏。然后恢復(fù)最近一次的完整轉(zhuǎn)儲(chǔ)贡歧。由于磁帶上最先出現(xiàn)目錄，所以首先恢復(fù)目錄赋秀，給出文件系統(tǒng)的 框架(skeleton)利朵，然后恢復(fù)文件系統(tǒng)本身。在完整存儲(chǔ)之后是第一次增量存儲(chǔ)猎莲，然后是第二次重復(fù)這一過程绍弟，以此類推。

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

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

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

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

I/O 中的算法

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

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

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

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

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

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

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

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

一種對(duì)先來先服務(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)求言询，如果采用先來先服務(wù)的原則俯萎，如下圖所示

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

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

但是撇眯，最短路徑優(yōu)先的算法也不是完美無缺的，這種算法照樣存在問題虱咧，那就是 優(yōu)先級(jí) 問題熊榛，

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

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

我們舉個(gè)例子來描述一下電梯算法窃诉，比如各個(gè)柱面得到服務(wù)的順序是 4杨耙，7，10飘痛，14珊膜，9，6宣脉，3车柠，1 ，那么它的流程圖如下

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

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

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

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

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

磁盤控制器的高速緩存和操作系統(tǒng)的高速緩存有一些不同柬祠，磁盤控制器的高速緩存用于緩存沒有實(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)求來將磁盤臂移到下一個(gè)被請(qǐng)求的柱面。如果下一個(gè)尋道請(qǐng)求到來時(shí)恰好沒有磁盤臂處于正確的位置锨天，那么驅(qū)動(dòng)程序會(huì)在剛剛完成傳輸?shù)尿?qū)動(dòng)器上發(fā)出一個(gè)新的尋道命令并等待毯盈，等待下一次中斷到來時(shí)檢查哪個(gè)驅(qū)動(dòng)器處于閑置狀態(tài)。

死鎖中的算法

在死鎖的處理策略中病袄，其中一點(diǎn)是忽略死鎖帶來的影響（驚呆了）搂赋，出現(xiàn)過一個(gè)叫做 鴕鳥算法 的

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

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

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

如果有多種相同的資源存在斑司，就需要采用另一種方法來檢測(cè)死鎖》褪剑可以通過構(gòu)造一個(gè)矩陣來檢測(cè)從 P1 -> Pn 這 n 個(gè)進(jìn)程中的死鎖陡厘。

現(xiàn)在我們提供一種基于矩陣的算法來檢測(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ù)量

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

死鎖的檢測(cè)就是基于向量的比較戏罢。每個(gè)進(jìn)程起初都是沒有被標(biāo)記過的该编，算法會(huì)開始對(duì)進(jìn)程做標(biāo)記覆积，進(jìn)程被標(biāo)記后說明進(jìn)程被執(zhí)行了，不會(huì)進(jìn)入死鎖士飒，當(dāng)算法結(jié)束時(shí)悔耘，任何沒有被標(biāo)記過的進(jìn)程都會(huì)被判定為死鎖進(jìn)程讲岁。

上面我們探討了兩種檢測(cè)死鎖的方式，那么現(xiàn)在你知道怎么檢測(cè)后衬以，你何時(shí)去做死鎖檢測(cè)呢缓艳？一般來說，有兩個(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ù)量，就沒有多少進(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è)人的貸款總額加起來是 13鞭铆，馬上接近 15，銀行家只能給 A 和 C 進(jìn)行放貸焦影，可以拖著 B 和 D衔彻、所以，可以讓 A 和 C 首先完成偷办，釋放貸款額度，以此來滿足其他居民的貸款澄港。這是一種安全 的狀態(tài)椒涯。

如果每個(gè)人的請(qǐng)求導(dǎo)致總額會(huì)超過甚至接近 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è)資源的銀行家算法，讀者可以自行了解理澎。