在講完多線程並發之後，我們終於可以進入進程管?的最後壹部分內容，任務調度。壹些參考書上把這壹部分內容叫做進程調度，我們之所以叫它任務調度，是因為在很多系統中、被調度的單位並?壹定是進程。上壹章開頭我們已經提到，Linux 系統中所有線程都是內核級線程，因此壹個線程可以作為壹個相對獨立的單位被調度?調度。我們將壹個被調度的單位稱為 任務（task） ，這壹章中我們就來認識壹下任務調度的常用算法。
任務調度發生的情境——上下文切換
上下文切換是從壹個任務向下壹個任務切換的過程，它有可能由兩種情形觸發。
我們所談到的任務調度是基於後壹種多任務系統，即操作系統必須擁有搶占處?的能?。
在搶占式多任務系統中，每個任務會被給予壹段時間，我們將這段時間稱為 時間片（time slice） 。
時間片耗盡後，系統會引發 計時器中斷（timer interrupt） ，使得現在正在運行的任務被切換至內核態，在系統空間中還行計時器中斷的處理函數，我們所關心的任務調度算法就發生在計時器中斷的處理函數中。
在這個處理函數中，系統會根據任務調度算法、從就緒隊列裏選擇下壹個運行的任務（有可能仍然是現在的這個任務），然後在處理上載入這個任務的處理器狀態、在存儲管理部件裏載入這個任務對應的頁表的起始地址、開始運行。
為了使用戶獲得流暢的體驗，我們希望壹個好的任務調度算法能夠讓所有任務在壹段時間內都產生壹定的進度、不讓任何任務等待太久、又不浪費太多時間在算法本身的計算中。為了能有效衡量壹個算法是否符合上面的標準，我們接下來要介紹幾個用來衡量任務調度算法表現的量。
學完了壹個理想調度算法應符合的標準後，我們就可以開始學習各種調度算法了。我們將在學習具體的算法的過程中，在不同的情境下用這些標準來衡量調度算法。妳很快就會意識到，所有算法都有其最優情境和最差情境。在選擇算法時，我們也要根據不同的情境來選擇合適的算法。
還記得在講頁面替換算法時，我們講的第壹個算法就是最佳頁面替換算法；雖然最佳頁面替換算法要求我們能夠預知未來，但它可以被證明是在同壹頁面使用序列下缺頁中斷率最低的算法。這壹節中我們要講的兩個算法也是這樣——它們實際上很難被實現，但是它們能夠保證最短的平均周轉時間，因此我們在學習其它可以實現的算法時就能以這兩個算法為基準衡量其它算法的表現。
從上面的例子我們可以看出，最短剩余時間優先算法是優於非搶占式的最短作業優先算法的。因此，我們在談到最短作業優先算法時指的壹般都是搶占式最短作業優先算法（最短剩余時間優先算法）。接下來我們就來證明下面這個結論：對於同壹個任務流，最短剩余時間優先算法可以使所有任務的平均周轉時間達到最短。
我們可以將 SRTF 看成是壹個動態的 SJF，它在每次有新任務進入系統時都重新運行 SJF。因此我們只要證明，對於壹個固定的任務流（沒有新任務加入的任務流）SJF 的平均周轉時間是最短的，我們就可以證明 SRTF 對於壹個有新任務加入的任務流的平均周轉時間是最短的。（因為我們在每壹個時間點上都做了最佳的選擇，那麽我們整體的選擇也是最佳的）
下面我們就來證明 SJF 能夠針對壹個固定的任務流給出最低的平均周轉時間。為了證明這個結論，我們先來證明壹個輔助定理：穿插運行幾個任務比連續運行幾個任務所需時間更長。這個證明是很簡單的，因為穿插運行的幾個任務中後結束的任務的周轉時間壹定大於等於它之間結束的幾個任務的運行時間與它的運行時間之和。因此為了減小周轉時間，我們希望上面的值取等，這就相當於要求所有的任務都連續運行至結束再切換至下壹個任務運行。
從上面的證明中我們已經看出，SRTF 和 SJF 的優點就是它們能夠縮短任務平均周轉時間。但 SRTF 和 SJF 也有明顯的缺點——在短任務不斷進入系統的情況下，它們會導致運行時間長的任務不斷等待，產生饑餓。下壹節中我們可以看到，為了減少任務的等待時間、提高公平性，我們可以采用壹些別的算法。
它跟頁面替換算法裏學習的先進先出算法類似，使先進入系統的任務先運行至結束，然後再使下壹個進入系統的任務運行。這種算法不會使後進入系統的短任務耽誤先進入系統的長任務，因此解決了 SJF 和 SRTF 的問題，但 FIFO 也有自己的問題。
如果壹個長任務先進入系統，後面有很多短任務進入系統，那麽這些短任務都需要等待長任務運行完之後才能運行，平均周轉時間會變得很長；另壹方面，如果壹個任務的大部分時間都花在 I/O 操作上，那麽 FIFO 這種非搶占式的算法會導致 CPU 長時間空閑，降低了資源利用率。
我們可以看到 FIFO 和 SJF、SRTF 壹樣都有公平性較差的問題，只不過 SJF 和 SRTF 偏向短任務，而 FIFO 偏向長任務。我們想要壹個更公平的算法，使得不同的任務在壹段時間內都能產生進度，這就是 輪轉調度算法（Round-Robin，RR）
在 RR 中，我們會規定壹個固定長度的時間片。處於就緒隊列中的進程將按照他們進入就緒隊列的順序輪流獲得壹個時間片運行，當時間片耗盡時任務就會被中斷、加入就緒隊列的結尾，下壹個任務開始運行。如果壹個任務因為 I/O 操作或無法獲取鎖等原因被阻塞，那麽即使它無法用完自己的時間片也會放棄處理器的使用權。
RR 與 SRTF 壹樣，都是搶占式算法，它的優點是對於計算密集型的任務分配資源較為公平，且不會產生饑餓。然而，I/O 密集型的任務在這種算法下會不斷因 I/O 放棄處理器使用權，因此獲取的資源較少。不僅如此，RR 算法的平均周轉時間較長，這主要有兩個原因——第壹，原本只需要幾個時間片就可以運行完的任務在 RR 中需要等待整個就緒隊列的任務都運行完壹遍以後才能獲得壹次時間片，因此等待時間很長；第二，每次時間片消耗完或任務主動讓出處理器時都會出現上下文切換，而上下文切換的代價是很大的，因此如果時間片太小、浪費在上下文切換上的時間比例就會很大。由於上述這種原因，在某些情況下 RR 的平均周轉時間可能比 FIFO 的平均周轉時間更長。
前幾節中我們講了 FIFO 和 RR 這兩種比較基本的算法，它們各自都有最適宜（optimal）和最不適宜（pessimal）的任務流種類。為了避免某壹種基本算法在壹些不適宜使用該算法的任務流下表現很差，我們需要以這些基本算法為基石、設計壹些更綜合的算法。這壹節中我們就來講壹個在很多系統中都得到應用的、比較綜合的算法： 多級反饋隊列調度算法（Multi-Level Feedback Queue，MLFQ）
優先級捐贈的過程看起來簡單，其實是很復雜的。比如，如果低優先級線程 1 持有鎖 B，中優先級線程 2 持有鎖 A，高優先級線程 3 試圖獲得 A 失敗後將被阻塞，將自己的優先級捐贈給線程 2；線程 2 運行後試圖獲得 B 失敗後也被阻塞，這時它就必須把線程 3 捐贈給它的優先級和它自己的優先級同時捐贈給線程 1，因為如果它只捐贈自己的優先級，那麽線程 1 的優先級仍然不壹定是最高的。 我們把這種循環式的捐贈叫做 recursive donation。
還有壹種情況我們必須考慮，那就是在壹個線程持有多個鎖並釋放其中壹個的時候，我們應該把它的優先級降到什麽程度呢？我們要避免剩下幾個鎖產生優先級倒置，就需要這個線程的優先級不低於任何壹個等待它的線程的優先級，否則兩個優先級之間就會出現能夠搶先運行的線程。因此我們應該把它的優先級降到所有它持有的鎖的等待者中的最高優先等級。我們甚至可能面臨這樣壹種情況：線程釋放的鎖不是把這個線程的優先級提高到目前等級的線程所等待的鎖，在這種情況下，線程的優先級就不會變化了。
雖然我們管這種提升優先級的方式叫捐贈，但更好的考慮方法應該是壹種“暫時提拔”。捐贈會給人壹種捐多少就要還多少的感覺，但實際上捐贈時線程優先級增加與它釋放鎖時優先級減少的值並不壹定相等（在線程持有多個鎖時很可能不相等）。對於這壹部分內容的理解至關重要，在下壹節中我們就來測試壹下妳對於這壹部分內容的掌握程度，幫助妳鞏固妳的理解。
上壹節中我們探討了優先級倒置的情況和它的解決方法；在探討這個問題時我們故意避開了幾個知識點沒有討論，這壹節裏就請妳自己來思考壹下下面幾個有關優先級捐贈的說法哪兩個是正確的。
這種看似相同的運行時間片長度從比例上來講相差是很多的。我們想要壹個更加公平、且普遍適用於各種類型的任務的算法。
如妳所知，現代的很多大型計算機都是多處理器的；在大的數據中心中（如谷歌的數據中心），壹整個裝滿處理器和磁盤的倉庫可能是同壹臺計算機（這種計算機被稱為 Warehouse-Scale Computer，WSC）。在這種情況下，壹個操作系統的調度器就需要處理將工作分攤到多個處理器上的功能。妳可能會問，為什麽不直接按照單處理器的調度算法給空閑的處理器分配任務呢？接下來我們就來看看，按照這種思路調度任務會有什麽問題。
我們知道，壹個任務不壹定等於壹個進程；壹個線程也可以是壹個任務。那麽，如果壹個進程希望充分利用多處理器的資源，它就可以分出多個線程，並行地完成壹段計算，完成這段計算後再合並線程或讓所有線程進入下壹階段的計算。然而，在計算機中，由於系統把這幾個線程當成獨立的任務，系統可能把它們分開運行，這樣就會出現所有線程都需要等待最慢的那個線程完成才能進入下壹階段的問題，並行對於運算速度的提升就大打折扣了。如果幾個線程中有壹個獲得了壹個鎖，然後它的處理器被搶占了，那麽剩余的線程即使獲得了處理器也只能等待鎖。如果這個鎖是自旋鎖的話，那麽所有這個進程下的線程都會在自旋中浪費處理器時間，導致其它進程也不能產生進度。
可見，這種盲目（oblivious）地利用單處理器的方法在多處理器計算機上調度任務的方法是不可行的。
我們要區分等待和運行這兩部分，因為我們使用排隊論的目的就是分析壹個任務在等待和運行這兩個部分分別花費的時間長度。前面幾節中我們已經說過，壹個任務的周轉時間等於它的等待時間與運行時間之和，假設其運行時間是不變的，那麽它的等待時間就成為了限制系統表現的主要問題。如果壹個系統中運行的部分時間較短、而等待時間很長，那麽我們就應該考慮換壹種調度算法或者多買幾個處理器；如果壹個系統中運行部分時間和等待時間都很長，那我們就應該考慮，等待時間過長可能是由系統處理速度慢於任務進入系統的速度導致的，那我們就有必要改壹改現在運行所使用的算法或買壹個更快的處理器了。
我們現在有壹個系統，每秒鐘可以處理 100 個請求，每個請求的處理時間（不包括排隊時間）是 100ms，，下面有關這個系統的說法正確的兩個是？