摘要：本文将會從最基礎的排程算法說起，逐個分析各種主流排程算法的原理，帶大家一起探索CPU排程的奧秘。
本文分享自華為雲社群《探索CPU的排程原理》，作者：元閏子。
前言
軟體工程師們總習慣把OS（Operating System，作業系統）當成是一個非常值得信賴的管家，我們隻管把程式托管到OS上運作，卻很少深入了解作業系統的運作原理。确實，OS作為一個通用的軟體系統，在大多數的場景下都表現得足夠的優秀。但仍會有一些特殊的場景，需要我們對OS進行各項調優，才能讓業務系統更高效地完成任務。這就要求我們必須深入了解OS的原理，不僅僅隻會使喚這個管家，還能懂得如何讓管家做得更好。
OS是一個非常龐大的軟體系統，本文主要探索其中的冰山一角：CPU的排程原理。
說起CPU的排程原理，很多人的第一反應是基于時間片的排程，也即每個程序都有占用CPU運作的時間片，時間片用完之後，就讓出CPU給其他程序。至于OS是如何判斷一個時間片是否用完的、如何切換到另一個程序等等更深層的原理，了解的人似乎并不多。
其實，基于時間片的排程隻是衆多CPU的排程算法的一類，本文将會從最基礎的排程算法說起，逐個分析各種主流排程算法的原理，帶大家一起探索CPU排程的奧秘。
CPU的上下文切換
在探索CPU排程原理之前，我們先了解一下CPU的上下文切換，它是CPU排程的基礎。
如今的OS幾乎都支援"同時"運作遠大于CPU數量的任務，OS會将CPU輪流配置設定給它們使用。這就要求OS必須知道從哪裡加載任務，以及加載後從哪裡開始運作，而這些資訊都儲存在CPU的寄存器中，其中即将執行的下一條指令的位址被儲存在程式計數器（PC）這一特殊寄存器上。我們将寄存器的這些資訊稱為CPU的上下文，也叫硬體上下文。
OS在切換運作任務時，将上一任務的上下文儲存下來，并将即将運作的任務的上下文加載到CPU寄存器上的這一動作，被稱為CPU上下文切換。
CPU上下文屬于程序上下文的一部分，我們常說的程序上下文由如下兩部分組成：
- 使用者級上下文：包含程序的運作時堆棧、資料塊、代碼塊等資訊。
- 系統級上下文：包含程序辨別資訊、程序現場資訊（CPU上下文）、程序控制資訊等資訊。
這涉及到兩個問題：（1）上一任務的CPU上下文如何儲存下來？（2）什麼時候執行上下文切換？
問題1: 上一任務的CPU上下文如何儲存下來？
CPU上下文會被儲存在程序的核心空間（kernel space）上。OS在給每個程序配置設定虛拟記憶體空間時，會配置設定一個核心空間，這部分記憶體隻能由核心代碼通路。OS在切換CPU上下文前，會先将目前CPU的通用寄存器、PC等程序現場資訊儲存在程序的核心空間上，待下次切換時，再取出重新裝載到CPU上，以恢複任務的運作。
問題2: 什麼時候執行上下文切換？
OS要想進行任務上下文切換，必須占用CPU來執行切換邏輯。然而，使用者程式運作的過程中，CPU已經被使用者程式所占用，也即OS在此刻并未處于運作狀态，自然也無法執行上下文切換。針對該問題，有兩種解決政策，協作式政策與搶占式政策。
協作式政策依賴使用者程式主動讓出CPU，比如執行系統調用（System Call）或者出現除零等異常。但該政策并不靠譜，如果使用者程式沒有主動讓出CPU，甚至是惡意死循環，那麼該程式将會一直占用CPU，唯一的恢複手段就是重新開機系統了。
搶占式政策則依賴硬體的定時中斷機制（Timer Interrupt），OS會在初始化時向硬體注冊中斷處理回調（Interrupt Handler）。當硬體産生中斷時，硬體會将CPU的處理權交給來OS，OS就可以在中斷回調上實作CPU上下文的切換。
排程的衡量名額
對于一種CPU排程算法的好壞，一般都通過如下兩個名額來進行衡量：
- 周轉時間（turnaround time），指從任務到達至任務完成之間的時間，即T_{turnaround}=T_{completiong}-T_{arrival}Tturnaround=Tcompletiong−Tarrival
- 響應時間（response time），指從任務到達至任務首次被排程的時間，即T_{response}=T_{firstrun}-T_{arrival}Tresponse=Tfirstrun−Tarrival
兩個名額從某種程度上是對立的，要求高的平均周轉時間，必然會降低平均響應時間。具體追求哪種名額與任務類型有關，比如程式編譯類的任務，要求周轉時間要小，盡可能快的完成編譯；使用者互動類的任務，則要求響應時間要小，避免影響使用者體驗。
工作負載假設
OS上的工作負載（也即各類任務運作的狀況）總是千變萬化的，為了更好的了解各類CPU排程算法原理，我們先對工作負載進行來如下幾種假設：
- 假設1：所有任務都運作時長都相同。
- 假設2：所有任務的開始時間都是相同的
- 假設3：一旦任務開始，就會一直運作，直至任務完成。
- 假設4：所有任務隻使用CPU資源（比如不産生I/O操作）。
- 假設5：預先知道所有任務的運作時長。
準備工作已經做好，下面我們開始進入CPU排程算法的奇妙世界。
FIFO：先進先出
FIFO（First In First Out，先進先出）排程算法以原理簡單，容易實作著稱，它先排程首先到達的任務直至結束，然後再排程下一個任務，以此類推。如果有多個任務同時到達，則随機選一個。
在我們假設的工作負載狀況下，FIFO效率良好。比如有A、B、C三個任務滿足上述所有負載假設，每個任務運作時長為10s，在t=0時刻到達，那麼任務排程情況是這樣的：
根據FIFO的排程原理，A、B、C分别在10、20、30時刻完成任務，平均周轉時間為20s（ \frac {10+20+30}{3}310+20+30），效果很好。
然而現實總是殘酷的，如果假設1被打破，比如A的運作時間變成100s，B和C的還是10s，那麼排程情況是這樣的：
根據FIFO的排程原理，由于A的運作時間過長，B和C長時間得不到排程，導緻平均周轉時間惡化為110（ \frac {100+110+120}{3}3100+110+120）。
是以，FIFO排程政策在任務運作時間差異較大的場景下，容易出現任務餓死的問題！
針對這個問題，如果運作時間較短的B和C先被排程，問題就可以解決了，這正是SJF排程算法的思想。
SJF：最短任務優先
SJF（Shortest Job First，最短任務優先）從相同到達時間的多個任務中選取運作時長最短的一個任務進行排程，接着再排程第二短的任務，以此類推。
針對上一節的工作負載，使用SJF進行排程的情況如下，周轉時間變成了50s（ \frac {10+20+120}{3}310+20+120），相比FIFO的110s，有了2倍多的提升。
讓我們繼續打破假設2，A在t=0時刻，B和C則在t=10時刻到達，那麼排程情況會變成這樣：
因為任務B和C比A後到，它們不得不一直等待A運作結束後才有機會排程，即使A需要長時間運作。周轉時間惡化為103.33s（\frac {100+(110-10)+(120-10)}{3}3100+(110−10)+(120−10)），再次出現任務餓死的問題！
STCF：最短時間完成優先
為了解決SJF的任務餓死問題，我們需要打破假設3，也即任務在運作過程中是允許被打斷的。如果B和C在到達時就立即被排程，問題就解決了。這屬于搶占式排程，原理就是CPU上下文切換一節提到的，在中斷定時器到達之後，OS完成任務A和B的上下文切換。
我們在協作式排程的SJF算法的基礎上，加上搶占式排程算法，就演變成了STCF算法（Shortest Time-to-Completion First，最短時間完成優先），排程原理是當運作時長較短的任務到達時，中斷目前的任務，優先排程運作時長較短的任務。
使用STCF算法對該工作負載進行排程的情況如下，周轉時間優化為50s（\frac {120+(20-10)+(30-10)}{3}3120+(20−10)+(30−10)），再次解決了任務餓死問題！
到目前為止，我們隻關心了周轉時間這一衡量名額，那麼FIFO、SJF和STCF排程算法的響應時間又是多長呢？
不妨假設A、B、C三個任務都在t=0時刻到達，運作時長都是5s，那麼這三個算法的排程情況如下，平均響應時長為5s（\frac {0+(5-0)+(10-0)}{3}30+(5−0)+(10−0)）：
更糟糕的是，随着任務運作時長的增長，平均響應時長也随之增長，這對于互動類任務來說将會是災難性的，嚴重影響使用者體驗。該問題的根源在于，當任務都同時到達且運作時長相同時，最後一個任務必須等待其他任務全部完成之後才開始排程。
為了優化響應時間，我們熟悉的基于時間片的排程出現了。
RR：基于時間片的輪詢排程
RR（Round Robin，輪訓）算法給每個任務配置設定一個時間片，當任務的時間片用完之後，排程器會中斷目前任務，切換到下一個任務，以此類推。
需要注意的是，時間片的長度設定必須是中斷定時器的整數倍，比如中斷定時器時長為2ms，那麼任務的時間片可以設定為2ms、4ms、6ms … 否則即使任務的時間片用完之後，定時中斷沒發生，OS也無法切換任務。
現在，使用RR進行排程，給A、B、C配置設定一個1s的時間片，那麼排程情況如下，平均響應時長為1s（\frac {0+(1-0)+(2-0)}{3}30+(1−0)+(2−0)）：
從RR的排程原理可以發現，把時間片設定得越小，平均響應時間也越小。但随着時間片的變小，任務切換的次數也随之上升，也就是上下文切換的消耗會變大。是以，時間片大小的設定是一個trade-off的過程，不能一味追求響應時間而忽略CPU上下文切換帶來的消耗。
CPU上下文切換的消耗，不隻是儲存和恢複寄存器所帶來的消耗。程式在運作過程中，會逐漸在CPU各級緩存、TLB、分支預測器等硬體上建立屬于自己的緩存資料。當任務被切換後，就意味着又得重來一遍緩存預熱，這會帶來巨大的消耗。
另外，RR排程算法的周轉時間為14s（\frac {(13-0)+(14-0)+(15-0)}{3}3(13−0)+(14−0)+(15−0)），相比于FIFO、SJF和STCF的10s（\frac {(5-0)+(10-0)+(15-0)}{3}3(5−0)+(10−0)+(15−0)）差了不少。這也驗證了之前所說的，周轉時間和響應時間在某種程度上是對立的，如果想要優化周轉時間，建議使用SJF和STCF；如果想要優化響應時間，則建議使用RR。
I/O操作對排程的影響
到目前為止，我們并未考慮任何的I/O操作。我們知道，當觸發I/O操作時，程序并不會占用CPU，而是阻塞等待I/O操作的完成。現在讓我們打破假設4，考慮任務A和B都在t=0時刻到達，運作時長都是50ms，但A每隔10ms執行一次阻塞10ms的I/O操作，而B沒有I/O。
如果使用STCF進行排程，排程的情況是這樣的：
從上圖看出，任務A和B的排程總時長達到了140ms，比實際A和B運作時長總和100ms要大。而且A阻塞在I/O操作期間，排程器并沒有切換到B，導緻了CPU的空轉！
要解決該問題，隻需使用RR的排程算法，給任務A和B配置設定10ms的時間片，這樣當A阻塞在I/O操作時，就可以排程B，而B用完時間片後，恰好A也從I/O阻塞中傳回，以此類推，排程總時長優化至100ms。
該排程方案是建立在假設5之上的，也即要求排程器預先知道A和B的運作時長、I/O操作時間長等資訊，才能如此充分地利用CPU。然而，實際的情況遠比這複雜，I/O阻塞時長不會每次都一樣，排程器也無法準确知道A和B的運作資訊。當假設5也被打破時，排程器又該如何實作才能最大程度保證CPU使用率，以及排程的合理性呢？
接下來，我們将介紹一個能夠在所有工作負載假設被打破的情況下依然表現良好，被許多現代作業系統采用的CPU排程算法，MLFQ。
MLFQ：多級回報隊列
MLFQ（Multi-Level Feedback Queue，多級回報隊列）排程算法的目标如下：
- 優化周轉時間。
- 降低互動類任務的響應時間，提升使用者體驗。
從前面分析我們知道，要優化周轉時間，可以優先排程運作時長短的任務（像SJF和STCF的做法）；要優化響應時間，則采用類似RR的基于時間片的排程。然而，這兩個目标看起來是沖突的，要降低響應時間，必然會增加周轉時間。
那麼對MLFQ來說，就需要解決如下兩個問題：
- 在不預先清楚任務的運作資訊（包括運作時長、I/O操作等）的前提下，如何權衡周轉時間和響應時間？
- 如何從曆史排程中學習，以便未來做出更好的決策？
劃分任務的優先級
MLFQ與前文介紹的幾種排程算法最顯著的特點就是新增了優先級隊列存放不同優先級的任務，并定下了如下兩個規則：
- 規則1：如果Priority(A) > Priority(B)，則排程A
- 規則2：如果Priority(A) = Priority(B)，則按照RR算法排程A和B
優先級的變化
MLFQ必須考慮改變任務的優先級，否則根據 規則1 和 規則2 ，對于上圖中的任務C，在A和B運作結束之前，C都不會獲得運作的機會，導緻C的響應時間很長。是以，可以定下了如下幾個優先級變化規則：
- 規則3：當一個新的任務到達時，将它放到最高優先級隊列中
- 規則4a：如果任務A運作了一個時間片都沒有主動讓出CPU（比如I/O操作），則優先級降低一級
- 規則4b：如果任務A在時間片用完之前，有主動讓出CPU，則優先級保持不變
規則3主要考慮到讓新加入的任務都能得到排程機會，避免出現任務餓死的問題
規則4a和4b主要考慮到，互動類任務大都是short-running的，并且會頻繁讓出CPU，是以為了保證響應時間，需要保持現有的優先級；而CPU密集型任務，往往不會太關注響應時間，是以可以降低優先級。
按照上述規則，當一個long-running任務A到達時，排程情況是這樣的：
如果在任務A運作到t=100時，short-time任務B到達，排程情況是這樣的：
從上述排程情況可以看出，MLFQ具備了STCF的優點，即可以優先完成short-running任務的排程，縮短了周轉時間。
如果任務A運作到t=100時，互動類任務C到達，那麼排程情況是這樣的：
MLFQ會在任務處于阻塞時按照優先級選擇其他任務運作，避免CPU空轉。是以，在上圖中，當任務C處于I/O阻塞狀态時，任務A得到了運作時間片，當任務C從I/O阻塞上傳回時，A再次挂起，以此類推。另外，因為任務C在時間片之内出現主動讓出CPU的行為，C的優先級一直保持不變，這對于互動類任務而言，有效提升了使用者體驗。
CPU密集型任務餓死問題
到目前為止，MLFQ似乎能夠同時兼顧周轉時間，以及互動類任務的響應時間，它真的完美了嗎？
考慮如下場景，任務A運作到t=100時，互動類任務C和D同時到達，那麼排程情況會是這樣的：
由此可見，如果目前系統上存在很多互動類任務時，CPU密集型任務将會存在餓死的可能！
為了解決該問題，可以設立了如下規則：
- 規則5：系統運作S時長之後，将所有任務放到最高優先級隊列上（Priority Boost）
加上該規則之後，假設設定S為50ms，那麼排程情況是這樣的，餓死問題得到解決！
惡意任務問題
考慮如下一個惡意任務E，為了長時間占用CPU，任務E在時間片還剩1%時故意執行I/O操作，并很快傳回。根據規則4b，E将會維持在原來的最高優先級隊列上，是以下次排程時仍然獲得排程優先權：
為了解決該問題，我們需要将規則4調整為如下規則：
- 規則4：給每個優先級配置設定一個時間片，當任務用完該優先級的時間片後，優先級降一級
應用新的規則4後，相同的工作負載，排程情況變成了如下所述，不再出現惡意任務E占用大量CPU的問題。
到目前為止，MLFQ的基本原理已經介紹完，最後，我們總結下MLFQ最關鍵的5項規則：
現在，再回到本節開始時提出的兩個問題：
1、在不預先清楚任務的運作資訊（包括運作時長、I/O操作等）的前提下，MLFQ如何權衡周轉時間和響應時間？
在預先不清楚任務到底是long-running或short-running的情況下，MLFQ會先假設任務屬于shrot-running任務，如果假設正确，任務就會很快完成，周轉時間和響應時間都得到優化；即使假設錯誤，任務的優先級也能逐漸降低，把更多的排程機會讓給其他short-running任務。
2、MLFQ如何從曆史排程中學習，以便未來做出更好的決策？
MLFQ主要根據任務是否有主動讓出CPU的行為來判斷其是否是互動類任務，如果是，則維持在目前的優先級，保證該任務的排程優先權，提升互動類任務的響應性。
當然，MLFQ并非完美的排程算法，它也存在着各種問題，其中最讓人困擾的就是MLFQ各項參數的設定，比如優先級隊列的數量，時間片的長度、Priority Boost的間隔等。這些參數并沒有完美的參考值，隻能根據不同的工作負載來進行設定。
比如，我們可以将低優先級隊列上任務的時間片設定長一些，因為低優先級的任務往往是CPU密集型任務，它們不太關心響應時間，較長的時間片長能夠減少上下文切換帶來的消耗。
CFS：Linux的完全公平排程
本節我們将介紹一個平時打交道最多的排程算法，Linux系統下的CFS（Completely Fair Scheduler，完全公平排程）。與上一節介紹的MLFQ不同，CFS并非以優化周轉時間和響應時間為目标，而是希望将CPU公平地均分給每個任務。
當然，CFS也提供了給程序設定優先級的功能，讓使用者/管理者決定哪些程序需要獲得更多的排程時間。
基本原理
大部分排程算法都是基于固定時間片來進行排程，而CFS另辟蹊徑，采用基于計數的排程方法，該技術被稱為virtual runtime。
CFS給每個任務都維護一個vruntime值，每當任務被排程之後，就累加它的vruntime。比如，當任務A運作了5ms的時間片之後，則更新為vruntime += 5ms。CFS在下次排程時，選擇vruntime值最小的任務來排程，比如：
那CFS應該什麼時候進行任務切換呢？切換得頻繁些，任務的排程會更加的公平，但是上下文切換帶來的消耗也越大。是以，CFS給使用者提供了個可配參數sched_latency，讓使用者來決定切換的時機。CFS将每個任務分到的時間片設定為 time_slice = sched_latency / n（n為目前的任務數） ，以確定在sched_latency周期内，各任務能夠均分CPU，保證公平性。
比如将sched_latency設定為48ms，目前有4個任務A、B、C和D，那麼每個任務分到的時間片為12ms；後面C和D結束之後，A和B分到的時間片也更新為24ms：
從上述原理上看，在sched_latency 不變的情況下，随着系統任務數的增加，每個任務分到的時間片也随之減少，任務切換所帶來的消耗也會增大。為了避免過多的任務切換消耗，CFS提供了可配參數min_granularity來設定任務的最小時間片。比如sched_latency設定為48ms，min_granularity設定為 6ms，那麼即使目前任務數有12，每個任務數分到的時間片也是6ms，而不是4ms。
給任務配置設定權重
有時候，我們希望給系統中某個重要的業務程序多配置設定些時間片，而其他不重要的程序則少配置設定些時間片。但按照上一節介紹的基本原理，使用CFS排程時，每個任務都是均分CPU的，有沒有辦法可以做到這一點呢？
可以給任務配置設定權重，讓權重高的任務更多的CPU！
加上權重機制後，任務時間片的計算方式變成了這樣：
比如，sched_latency還是設定為48ms，現有A和B兩個任務，A的權重設定為1024，B的權重設定為3072，按照上述的公式，A的時間片是12ms，B的時間片是36ms。
從上一節可知，CFS每次選取vruntime值最小的任務來排程，而每次排程完成後，vruntime的計算規則為vruntime += runtime，是以僅僅改變時間片的計算規則不會生效，還需将vruntime的計算規則調整為：
還是前面的例子，假設A和B都沒有I/O操作，更新vruntime計算規則後，排程情況如下，任務B比任務A能夠分得更多的CPU了。
使用紅黑樹提升vruntime查找效率
CFS每次切換任務時，都會選取vruntime值最小的任務來排程，是以需要它有個資料結構來存儲各個任務及其vruntime資訊。
最直覺的當然就是選取一個有序清單來存儲這些資訊，清單按照vruntime排序。這樣在切換任務時，CFS隻需擷取清單頭的任務即可，時間複雜度為O(1)。比如目前有10個任務，vruntime儲存為有序連結清單[1, 5, 9, 10, 14, 18, 17, 21, 22, 24]，但是每次插入或删除任務時，時間複雜度會是O(N)，而且耗時随着任務數的增多而線性增長！
為了兼顧查詢、插入、删除的效率，CFS使用紅黑樹來儲存任務和vruntime資訊，這樣，查詢、插入、删除操作的複雜度變成了log(N)，并不會随着任務數的增多而線性增長，極大提升了效率。
另外，為了提升存儲效率，CFS在紅黑樹中隻儲存了處于Running狀态的任務的資訊。
應對I/O與休眠
每次都選取vruntime值最小的任務來排程這種政策，也會存在任務餓死的問題。考慮有A和B兩個任務，時間片為1s，起初A和B均分CPU輪流運作，在某次排程後，B進入了休眠，假設休眠了10s。等B醒來後，vruntime_{B}vruntimeB就會比vruntime_{A}vruntimeA小10s，在接下來的10s中，B将會一直被排程，進而任務A出現了餓死現象。
為了解決該問題，CFS規定當任務從休眠或I/O中傳回時，該任務的vruntime會被設定為目前紅黑樹中的最小vruntime值。上述例子，B從休眠中醒來後，vruntime_{B}vruntimeB會被設定為11，是以也就不會餓死任務A了。
這種做法其實也存在瑕疵，如果任務的休眠時間很短，那麼它醒來後依舊是優先排程，這對于其他任務來說是不公平的。
寫在最後
本文花了很長的篇幅講解了幾種常見CPU排程算法的原理，每種算法都有各自的優缺點，并不存在一種完美的排程政策。在應用中，我們需要根據實際的工作負載，選取合适的排程算法，配置合理的排程參數，權衡周轉時間和響應時間、任務公平和切換消耗。這些都應驗了《Fundamentals of Software Architecture》中的那句名言：Everything in software architecture is a trade-off.
本文中描述的排程算法都是基于單核處理器進行分析的，而多核處理器上的排程算法要比這複雜很多，比如需要考慮處理器之間共享資料同步、緩存親和性等，但本質原理依然離不開本文所描述的幾種基礎排程算法。
參考
- Operating Systems: Three Easy Pieces, Remzi H Arpaci-Dusseau / Andrea C Arpaci-Dusseau
- 計算機系統基礎(三)：異常、中斷和輸入/輸出, 袁春風 南京大學
點選關注，第一時間了解華為雲新鮮技術~