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

進程和線程管理中的算法

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

調度算法分類

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

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

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

實時操作系統(tǒng)

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

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

設計目標

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

在交互式用戶環(huán)境中，因為為了用戶體驗，所以會避免長時間占用進程，所以需要搶占式算法。由于某個進程出現(xiàn)錯誤也有可能無限期的排斥其他所有進程。為了避免這種情況，搶占式也是必須的。

在實時系統(tǒng)中，搶占式不是必須的，因為進程知道自己可能運行不了很長時間，通常很快的做完自己的工作并掛起。

關鍵指標

通常有三個指標來衡量系統(tǒng)工作狀態(tài)：吞吐量、周轉時間和 CPU 利用率

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

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

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

下面我們就來認識一下批處理中的算法。

先來先服務

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

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

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

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

批處理中的第二種調度算法是最短作業(yè)優(yōu)先(Shortest Job First)，我們假設運行時間已知。例如，一家保險公司，因為每天要做類似的工作，所以人們可以相當精確地預測處理 1000 個索賠的一批作業(yè)需要多長時間。當輸入隊列中有若干個同等重要的作業(yè)被啟動時，調度程序應使用最短優(yōu)先作業(yè)算法

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

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

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

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

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

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

交互式系統(tǒng)中在個人計算機、服務器和其他系統(tǒng)中都是很常用的，所以有必要來探討一下交互式調度

輪詢調度

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

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

優(yōu)先級調度

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

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

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

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

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

最短進程優(yōu)先

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

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

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

有時把這種通過當前測量值和先前估計值進行加權平均從而得到下一個估計值的技術稱作老化(aging)。這種方法會使用很多預測值基于當前值的情況。

保證調度

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

彩票調度

對用戶進行承諾并在隨后兌現(xiàn)承諾是一件好事，不過很難實現(xiàn)。但是有一種既可以給出預測結果而又有一種比較簡單的實現(xiàn)方式的算法，就是彩票調度(lottery scheduling)算法。

其基本思想是為進程提供各種系統(tǒng)資源（例如 CPU 時間）的彩票。當做出一個調度決策的時候，就隨機抽出一張彩票，擁有彩票的進程將獲得該資源。在應用到 CPU 調度時，系統(tǒng)可以每秒持有 50 次抽獎，每個中獎者將獲得比如 20 毫秒的 CPU 時間作為獎勵。

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

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

公平分享調度

到目前為止，我們假設被調度的都是各個進程自身，而不用考慮該進程的擁有者是誰。結果是，如果用戶 1 啟動了 9 個進程，而用戶 2 啟動了一個進程，使用輪轉或相同優(yōu)先級調度算法，那么用戶 1 將得到 90 % 的 CPU 時間，而用戶 2 將之得到 10 % 的 CPU 時間。

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

實時系統(tǒng)中的調度

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

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

只有滿足這個條件的實時系統(tǒng)稱為可調度的，這意味著它實際上能夠被實現(xiàn)。一個不滿足此檢驗標準的進程不能被調度，因為這些進程共同需要的 CPU 時間總和大于 CPU 能提供的時間。

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

調度策略和機制

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

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

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

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

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

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

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

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

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

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

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

如果為進程和空閑區(qū)維護各自獨立的鏈表，那么這四個算法的速度都能得到提高。這樣，這四種算法的目標都是為了檢查空閑區(qū)而不是進程。但這種分配速度的提高的一個不可避免的代價是增加復雜度和減慢內(nèi)存釋放速度，因為必須將一個回收的段從進程鏈表中刪除并插入空閑鏈表區(qū)。

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

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

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

頁面置換算法

頁面置換有非常多的算法，下面一起來認識一下

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

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

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

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

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

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

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

最近未使用頁面置換算法

為了能夠讓操作系統(tǒng)收集頁面使用信息，大部分使用虛擬地址的計算機都有兩個狀態(tài)位，R 和 M，來和每個頁面進行關聯(lián)。每當引用頁面（讀入或寫入）時都設置 R，寫入（即修改）頁面時設置 M，這些位包含在每個頁表項中，就像下面所示

因為每次訪問時都會更新這些位，因此由硬件來設置它們非常重要。一旦某個位被設置為 1，就會一直保持 1 直到操作系統(tǒng)下次來修改此位。

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

可以用 R 位和 M 位來構造一個簡單的頁面置換算法：當啟動一個進程時，操作系統(tǒng)將其所有頁面的兩個位都設置為 0。R 位定期的被清零（在每個時鐘中斷）。用來將最近未引用的頁面和已引用的頁面分開。

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

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

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

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

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

盡管看起來好像無法實現(xiàn)第一類頁面，但是當?shù)谌愴撁娴?R 位被時鐘中斷清除時，它們就會發(fā)生。時鐘中斷不會清除 M 位，因為需要這個信息才能知道是否寫回磁盤中。清除 R 但不清除 M 會導致出現(xiàn)一類頁面。

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

先進先出頁面置換算法

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

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

初始化的時候，沒有任何頁面，所以第一次的時候會檢查頁面 1 是否位于鏈表中，沒有在鏈表中，那么就是MISS，頁面1 進入鏈表，鏈表的先進先出的方向如圖所示。

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

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

下面來看第六次，此時的鏈表還是1 2 3，因為之前沒有執(zhí)行進入鏈表操作，頁面5會首先進行檢查，發(fā)現(xiàn)鏈表中沒有頁面 5 ，則執(zhí)行頁面 5 的進入鏈表操作，頁面 2 執(zhí)行出鏈表的操作，執(zhí)行完成后的鏈表順序為2 3 5。

第二次機會頁面置換算法

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

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

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

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

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

時鐘頁面置換算法

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

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

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

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

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

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

用軟件模擬 LRU

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

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

幸運的是只需要對 NFU 做一個簡單的修改就可以讓它模擬 LRU，這個修改有兩個步驟

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

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

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

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

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

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

它們在兩個時鐘周期內(nèi)都沒有被訪問過，在此之前的時鐘周期內(nèi)都引用了兩個頁面。根據(jù) LRU 算法，如果需要置換的話，那么應該在這兩個頁面中選擇一個。那么問題來了，我萌應該選擇哪個？現(xiàn)在的問題是我們不知道時鐘周期 1 到時鐘周期 2 內(nèi)它們中哪個頁面是后被訪問到的。因為在每個時鐘周期內(nèi)只記錄了一位，所以無法區(qū)分在一個時鐘周期內(nèi)哪個頁面最早被引用，哪個頁面是最后被引用的。因此，我們能做的就是置換頁面3，因為頁面 3 在周期 0 - 1 內(nèi)都沒有被訪問過，而頁面 5 卻被引用過。

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

工作集頁面置換算法

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

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

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

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

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

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

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

下面來簡單描述一下工作集的頁面置換算法，基本思路就是找出一個不在工作集中的頁面并淘汰它。下面是一部分機器頁表

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

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

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

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

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

工作集時鐘頁面置換算法

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

與時鐘算法一樣，所需的數(shù)據(jù)結構是一個以頁框為元素的循環(huán)列表，就像下面這樣

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

最初的時候，該表是空的。當裝入第一個頁面后，把它加載到該表中。隨著更多的頁面的加入，它們形成一個環(huán)形結構。每個表項包含來自基本工作集算法的上次使用時間，以及 R 位（已標明）和 M 位（未標明）。

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

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

原則上來說，所有的頁面都有可能因為磁盤I/O在某個時鐘周期內(nèi)被調度。為了降低磁盤阻塞，需要設置一個限制，即最大只允許寫回 n 個頁面。一旦達到該限制，就不允許調度新的寫操作。

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

至少調度了一次寫操作

沒有調度過寫操作

在第一種情況中，指針僅僅是不停的移動，尋找一個未被修改過的頁面。由于已經(jīng)調度了一個或者多個寫操作，最終會有某個寫操作完成，它的頁面會被標記為未修改。置換遇到的第一個未被修改過的頁面，這個頁面不一定是第一個被調度寫操作的頁面，因為硬盤驅動程序為了優(yōu)化性能可能會把寫操作重排序。

對于第二種情況，所有的頁面都在工作集中，否則將至少調度了一個寫操作。由于缺乏額外的信息，最簡單的方法就是置換一個未被修改的頁面來使用，掃描中需要記錄未被修改的頁面的位置，如果不存在未被修改的頁面，就選定當前頁面并把它寫回磁盤。

頁面置換算法小結

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

最優(yōu)算法在當前頁面中置換最后要訪問的頁面。不幸的是，沒有辦法來判定哪個頁面是最后一個要訪問的，因此實際上該算法不能使用。然而，它可以作為衡量其他算法的標準。

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

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

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

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

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

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

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

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

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

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

文件系統(tǒng)在備份的過程中會使用到算法，文件備份分為邏輯轉儲和物理轉儲

物理轉儲和邏輯轉儲

物理轉儲的主要優(yōu)點是簡單、極為快速（基本上是以磁盤的速度運行），缺點是全量備份，不能跳過指定目錄，也不能增量轉儲，也不能恢復個人文件的請求。因此絕大多數(shù)情況下不會使用物理轉儲，而使用邏輯轉儲。

邏輯轉儲(logical dump)從一個或幾個指定的目錄開始，遞歸轉儲自指定日期開始后更改的文件和目錄。因此，在邏輯轉儲中，轉儲磁盤上有一系列經(jīng)過仔細識別的目錄和文件，這使得根據(jù)請求輕松還原特定文件或目錄。

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

待轉儲的文件系統(tǒng)，其中方框代表目錄，圓圈代表文件。黃色的項目表是自上次轉儲以來修改過。每個目錄和文件都被標上其 inode 號。

此算法會轉儲位于修改文件或目錄路徑上的所有目錄（也包括未修改的目錄），原因有兩個。第一是能夠在不同電腦的文件系統(tǒng)中恢復轉儲的文件。通過這種方式，轉儲和重新存儲的程序能夠用來在兩個電腦之間傳輸整個文件系統(tǒng)。第二個原因是能夠對單個文件進行增量恢復。

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

在第一階段結束時，所有修改過的文件和全部目錄都在位圖中標記了，如下圖所示

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

注意，inode 編號為 10、11、14、27、29 和 30 的目錄已經(jīng)被去掉了標記，因為它們所包含的內(nèi)容沒有修改。它們也不會轉儲。相反，inode 編號為 5 和 6 的目錄本身盡管沒有被修改過也要被轉儲，因為在新的機器上恢復當日的修改時需要這些信息。為了提高算法效率，可以將這兩階段的目錄樹遍歷合二為一。

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

為了進行恢復，每個被轉儲的目錄都用目錄的屬性（所有者、時間）作為前綴。

最后，在第四階段，上圖中被標記的文件也被轉儲，同樣，由其文件屬性作為前綴。至此，轉儲結束。

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

盡管邏輯存儲十分簡單，但是也會有一些棘手的問題。首先，既然空閑塊列表并不是一個文件，那么在所有被轉儲的文件恢復完畢之后，就需要從零開始重新構造。

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

還有一個問題是，UNIX 文件實際上包含了許多空洞(holes)。打開文件，寫幾個字節(jié)，然后找到文件中偏移了一定距離的地址，又寫入更多的字節(jié)，這么做是合法的。但兩者之間的這些塊并不屬于文件本身，從而也不應該在其上進行文件轉儲和恢復。

最后，無論屬于哪一個目錄，特殊文件，命名管道以及類似的文件都不應該被轉儲。

I/O 中的算法

在 I/O 的磁盤調度中也出現(xiàn)過很多算法，關于尋址和磁盤臂的轉動都會對算法產(chǎn)生影響，下面我們就來一起看下

一般情況下，影響磁盤快讀寫的時間由下面幾個因素決定

尋道時間 - 尋道時間指的就是將磁盤臂移動到需要讀取磁盤塊上的時間

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

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

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

如果磁盤驅動程序每次接收一個請求并按照接收順序完成請求，這種處理方式也就是先來先服務(First-Come, First-served, FCFS)，這種方式很難優(yōu)化尋道時間。因為每次都會按照順序處理，不管順序如何，有可能這次讀完后需要等待一個磁盤旋轉一周才能繼續(xù)讀取，而其他柱面能夠馬上進行讀取，這種情況下每次請求也會排隊。

通常情況下，磁盤在進行尋道時，其他進程會產(chǎn)生其他的磁盤請求。磁盤驅動程序會維護一張表，表中會記錄著柱面號當作索引，每個柱面未完成的請求會形成鏈表，鏈表頭存放在表的相應表項中。

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

假如我們在對磁道 6 號進行尋址時，同時發(fā)生了對 11 , 2 , 4, 14, 8, 15, 3 的請求，如果采用先來先服務的原則，如下圖所示

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

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

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

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

電梯算法需要維護一個二進制位，也就是當前的方向位：UP(向上)或者是DOWN(向下)。當一個請求處理完成后，磁盤或電梯的驅動程序會檢查該位，如果此位是 UP 位，磁盤臂或者電梯倉移到下一個更高跌未完成的請求。如果高位沒有未完成的請求，則取相反方向。當方向位是DOWN時，同時存在一個低位的請求，磁盤臂會轉向該點。如果不存在的話，那么它只是停止并等待。

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

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

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

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

這里需要注意一點，當一個柱面有多條磁道時，相繼的請求可能針對不同的磁道，這種選擇沒有代價，因為選擇磁頭不需要移動磁盤臂也沒有旋轉延遲。

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

磁盤控制器的高速緩存和操作系統(tǒng)的高速緩存有一些不同，磁盤控制器的高速緩存用于緩存沒有實際被請求的塊，而操作系統(tǒng)維護的高速緩存由顯示地讀出的塊組成，并且操作系統(tǒng)會認為這些塊在近期仍然會頻繁使用。

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

死鎖中的算法

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

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

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

每種類型多個資源的死鎖檢測方式

如果有多種相同的資源存在，就需要采用另一種方法來檢測死鎖?？梢酝ㄟ^構造一個矩陣來檢測從 P1 -> Pn 這 n 個進程中的死鎖。

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

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

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

死鎖的檢測就是基于向量的比較。每個進程起初都是沒有被標記過的，算法會開始對進程做標記，進程被標記后說明進程被執(zhí)行了，不會進入死鎖，當算法結束時，任何沒有被標記過的進程都會被判定為死鎖進程。

上面我們探討了兩種檢測死鎖的方式，那么現(xiàn)在你知道怎么檢測后，你何時去做死鎖檢測呢？一般來說，有兩個考量標準：

每當有資源請求時就去檢測，這種方式會占用昂貴的 CPU 時間。

每隔 k 分鐘檢測一次，或者當 CPU 使用率降低到某個標準下去檢測?？紤]到 CPU 效率的原因，如果死鎖進程達到一定數(shù)量，就沒有多少進程可以運行，所以 CPU 會經(jīng)?？臻e。

還有死鎖避免的算法

銀行家算法

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

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

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

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

如果每個人的請求導致總額會超過甚至接近 15 ，就會處于一種不安全的狀態(tài)，如下所示

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

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

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

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