深入剖析CPU的調(diào)度原理

前言

軟件工程師們總習(xí)慣把 OS （Operating System，操作系統(tǒng)）當(dāng)成是一個非常值得信賴的管家，我們只管把程序托管到OS上運行，卻很少深入了解操作系統(tǒng)的運行原理。

確實，OS作為一個通用的軟件系統(tǒng)，在大多數(shù)的場景下都表現(xiàn)得足夠的優(yōu)秀。但仍會有一些特殊的場景，需要我們對OS進行各項調(diào)優(yōu)，才能讓業(yè)務(wù)系統(tǒng)更高效地完成任務(wù)。

這就要求我們必須深入了解OS的原理，不僅僅只會使喚這個管家，還能懂得如何讓管家做得更好 。

OS是一個非常龐大的軟件系統(tǒng)，本文主要探索其中的冰山一角： CPU的調(diào)度原理 。

說起CPU的調(diào)度原理，很多人的第一反應(yīng)是基于時間片的調(diào)度，也即每個進程都有占用CPU運行的時間片，時間片用完之后，就讓出CPU給其他進程。

至于OS是如何判斷一個時間片是否用完的、如何切換到另一個進程等等更深層的原理，了解的人似乎并不多。

其實，基于時間片的調(diào)度只是眾多CPU的調(diào)度算法的一類，本文將會從最基礎(chǔ)的調(diào)度算法說起，逐個分析各種主流調(diào)度算法的原理，帶大家一起探索CPU調(diào)度的奧秘。

CPU的上下文切換

在探索CPU調(diào)度原理之前，我們先了解一下CPU的上下文切換，它是CPU調(diào)度的基礎(chǔ)。

如今的OS幾乎都支持"同時"運行遠大于CPU數(shù)量的任務(wù)，OS會將CPU輪流分配給它們使用。

這就要求OS必須知道從哪里加載任務(wù)，以及加載后從哪里開始運行，而這些信息都保存在CPU的寄存器中，其中即將執(zhí)行的下一條指令的地址被保存在 程序計數(shù)器 （PC）這一特殊寄存器上。 我們將寄存器的這些信息稱為CPU的上下文，也叫硬件上下文 。

OS在切換運行任務(wù)時， 將上一任務(wù)的上下文保存下來，并將即將運行的任務(wù)的上下文加載到CPU寄存器上的這一動作，被稱為CPU上下文切換 。

CPU上下文屬于進程上下文的一部分，我們常說的進程上下文由如下兩部分組成：

• 用戶級上下文 ：包含進程的運行時堆棧、數(shù)據(jù)塊、代碼塊等信息。
• 系統(tǒng)級上下文 ：包含進程標(biāo)識信息、進程現(xiàn)場信息（CPU上下文）、進程控制信息等信息。

這涉及到兩個問題：（1）上一任務(wù)的CPU上下文如何保存下來？（2）什么時候執(zhí)行上下文切換？

問題1: 上一任務(wù)的CPU上下文如何保存下來 ？

CPU上下文會被保存在進程的 內(nèi)核空間 （kernel space）上。OS在給每個進程分配虛擬內(nèi)存空間時，會分配一個內(nèi)核空間，這部分內(nèi)存只能由內(nèi)核代碼訪問。

OS在切換CPU上下文前，會先將當(dāng)前CPU的通用寄存器、PC等進程現(xiàn)場信息保存在進程的內(nèi)核空間上，待下次切換時，再取出重新裝載到CPU上，以恢復(fù)任務(wù)的運行。

問題2: 什么時候執(zhí)行上下文切換 ？

OS要想進行任務(wù)上下文切換，必須占用CPU來執(zhí)行切換邏輯。然而，用戶程序運行的過程中，CPU已經(jīng)被用戶程序所占用，也即OS在此刻并未處于運行狀態(tài)，自然也無法執(zhí)行上下文切換。針對該問題，有兩種解決策略，協(xié)作式策略與搶占式策略。

協(xié)作式策略依賴用戶程序主動讓出CPU，比如執(zhí)行系統(tǒng)調(diào)用（System Call）或者出現(xiàn)除零等異常。但該策略并不靠譜，如果用戶程序沒有主動讓出CPU，甚至是惡意死循環(huán)，那么該程序?qū)恢闭加肅PU，唯一的恢復(fù)手段就是重啟系統(tǒng)了。

搶占式策略則依賴硬件的定時中斷機制（Timer Interrupt），OS會在初始化時向硬件注冊中斷處理回調(diào)（Interrupt Handler）。當(dāng)硬件產(chǎn)生中斷時，硬件會將CPU的處理權(quán)交給來OS，OS就可以在中斷回調(diào)上實現(xiàn)CPU上下文的切換。

調(diào)度的衡量指標(biāo)

對于一種CPU調(diào)度算法的好壞，一般都通過如下兩個指標(biāo)來進行衡量：

• 周轉(zhuǎn)時間 （turnaround time），指從任務(wù)到達至任務(wù)完成之間的時間，即
• 響應(yīng)時間 （response time），指從任務(wù)到達至任務(wù)首次被調(diào)度的時間，即

兩個指標(biāo)從某種程度上是對立的，要求高的平均周轉(zhuǎn)時間，必然會降低平均響應(yīng)時間。具體追求哪種指標(biāo)與任務(wù)類型有關(guān)，比如程序編譯類的任務(wù)，要求周轉(zhuǎn)時間要小，盡可能快的完成編譯；用戶交互類的任務(wù)，則要求響應(yīng)時間要小，避免影響用戶體驗。

工作負載假設(shè)

OS上的工作負載（也即各類任務(wù)運行的狀況）總是千變?nèi)f化的，為了更好的理解各類CPU調(diào)度算法原理，我們先對工作負載進行來如下幾種假設(shè)：

• 假設(shè)1 ：所有任務(wù)都運行時長都相同。
• 假設(shè)2 ：所有任務(wù)的開始時間都是相同的
• 假設(shè)3 ：一旦任務(wù)開始，就會一直運行，直至任務(wù)完成。
• 假設(shè)4 ：所有任務(wù)只使用CPU資源（比如不產(chǎn)生I/O操作）。
• 假設(shè)5 ：預(yù)先知道所有任務(wù)的運行時長。

準(zhǔn)備工作已經(jīng)做好，下面我們開始進入CPU調(diào)度算法的奇妙世界。

FIFO：先進先出

FIFO（First In First Out，先進先出）調(diào)度算法以原理簡單，容易實現(xiàn)著稱，它 先調(diào)度首先到達的任務(wù)直至結(jié)束，然后再調(diào)度下一個任務(wù)，以此類推 。如果有多個任務(wù)同時到達，則隨機選一個。

在我們假設(shè)的工作負載狀況下，F(xiàn)IFO效率良好。比如有A、B、C三個任務(wù)滿足上述所有負載假設(shè)，每個任務(wù)運行時長為10s，在t=0時刻到達，那么任務(wù)調(diào)度情況是這樣的：

根據(jù)FIFO的調(diào)度原理，A、B、C分別在10、20、30時刻完成任務(wù)，平均周轉(zhuǎn)時間為20s（ ），效果很好。

然而現(xiàn)實總是殘酷的，如果假設(shè)1被打破，比如A的運行時間變成100s，B和C的還是10s，那么調(diào)度情況是這樣的：

根據(jù)FIFO的調(diào)度原理，由于A的運行時間過長，B和C長時間得不到調(diào)度，導(dǎo)致平均周轉(zhuǎn)時間惡化為110（ ）。

因此， FIFO調(diào)度策略在任務(wù)運行時間差異較大的場景下，容易出現(xiàn)任務(wù)餓死的問題 ！

針對這個問題，如果運行時間較短的B和C先被調(diào)度，問題就可以解決了，這正是SJF調(diào)度算法的思想。

SJF：最短任務(wù)優(yōu)先

SJF（Shortest Job First，最短任務(wù)優(yōu)先） 從相同到達時間的多個任務(wù)中選取運行時長最短的一個任務(wù)進行調(diào)度，接著再調(diào)度第二短的任務(wù)，以此類推 。

針對上一節(jié)的工作負載，使用SJF進行調(diào)度的情況如下，周轉(zhuǎn)時間變成了50s（ ），相比FIFO的110s，有了2倍多的提升。

讓我們繼續(xù)打破 假設(shè)2 ，A在t=0時刻，B和C則在t=10時刻到達，那么調(diào)度情況會變成這樣：

因為任務(wù)B和C比A后到，它們不得不一直等待A運行結(jié)束后才有機會調(diào)度，即使A需要長時間運行。周轉(zhuǎn)時間惡化為103.33s（），再次出現(xiàn)任務(wù)餓死的問題！

STCF：最短時間完成優(yōu)先

為了解決SJF的任務(wù)餓死問題，我們需要打破 假設(shè)3 ，也即任務(wù)在運行過程中是允許被打斷的。如果B和C在到達時就立即被調(diào)度，問題就解決了。

這屬于搶占式調(diào)度，原理就是CPU上下文切換一節(jié)提到的，在中斷定時器到達之后，OS完成任務(wù)A和B的上下文切換。

我們在協(xié)作式調(diào)度的SJF算法的基礎(chǔ)上，加上搶占式調(diào)度算法，就演變成了STCF算法（Shortest Time-to-Completion First，最短時間完成優(yōu)先），調(diào)度原理是 當(dāng)運行時長較短的任務(wù)到達時，中斷當(dāng)前的任務(wù)，優(yōu)先調(diào)度運行時長較短的任務(wù) 。

使用STCF算法對該工作負載進行調(diào)度的情況如下，周轉(zhuǎn)時間優(yōu)化為50s（），再次解決了任務(wù)餓死問題！

到目前為止，我們只關(guān)心了周轉(zhuǎn)時間這一衡量指標(biāo)，那么FIFO、SJF和STCF調(diào)度算法的響應(yīng)時間又是多長呢？

不妨假設(shè)A、B、C三個任務(wù)都在t=0時刻到達，運行時長都是5s，那么這三個算法的調(diào)度情況如下，平均響應(yīng)時長為5s（）：

更糟糕的是，隨著任務(wù)運行時長的增長，平均響應(yīng)時長也隨之增長，這對于交互類任務(wù)來說將會是災(zāi)難性的，嚴(yán)重影響用戶體驗。

該問題的根源在于，當(dāng)任務(wù)都同時到達且運行時長相同時，最后一個任務(wù)必須等待其他任務(wù)全部完成之后才開始調(diào)度。

為了優(yōu)化響應(yīng)時間，我們熟悉的基于時間片的調(diào)度出現(xiàn)了。

RR：基于時間片的輪詢調(diào)度

RR（Round Robin，輪訓(xùn)）算法給每個任務(wù)分配一個時間片，當(dāng)任務(wù)的時間片用完之后，調(diào)度器會中斷當(dāng)前任務(wù)，切換到下一個任務(wù)，以此類推 。

需要注意的是，時間片的長度設(shè)置必須是中斷定時器的整數(shù)倍，比如中斷定時器時長為2ms，那么任務(wù)的時間片可以設(shè)置為2ms、4ms、6ms ... 否則即使任務(wù)的時間片用完之后，定時中斷沒發(fā)生，OS也無法切換任務(wù)。

現(xiàn)在，使用RR進行調(diào)度，給A、B、C分配一個1s的時間片，那么調(diào)度情況如下，平均響應(yīng)時長為1s（）：

從RR的調(diào)度原理可以發(fā)現(xiàn)，把時間片設(shè)置得越小，平均響應(yīng)時間也越小。但隨著時間片的變小，任務(wù)切換的次數(shù)也隨之上升，也就是上下文切換的消耗會變大。

因此，時間片大小的設(shè)置是一個trade-off的過程，不能一味追求響應(yīng)時間而忽略CPU上下文切換帶來的消耗。

CPU上下文切換的消耗，不只是保存和恢復(fù)寄存器所帶來的消耗。程序在運行過程中，會逐漸在CPU各級緩存、TLB、分支預(yù)測器等硬件上建立屬于自己的緩存數(shù)據(jù)。當(dāng)任務(wù)被切換后，就意味著又得重來一遍緩存預(yù)熱，這會帶來巨大的消耗。

另外，RR調(diào)度算法的周轉(zhuǎn)時間為14s（），相比于FIFO、SJF和STCF的10s（）差了不少。

這也驗證了之前所說的，周轉(zhuǎn)時間和響應(yīng)時間在某種程度上是對立的，如果想要優(yōu)化周轉(zhuǎn)時間，建議使用SJF和STCF；如果想要優(yōu)化響應(yīng)時間，則建議使用RR。

I/O操作對調(diào)度的影響

到目前為止，我們并未考慮任何的I/O操作。我們知道，當(dāng)觸發(fā)I/O操作時，進程并不會占用CPU，而是阻塞等待I/O操作的完成。

現(xiàn)在讓我們打破 假設(shè)4 ，考慮任務(wù)A和B都在t=0時刻到達，運行時長都是50ms，但A每隔10ms執(zhí)行一次阻塞10ms的I/O操作，而B沒有I/O。

如果使用STCF進行調(diào)度，調(diào)度的情況是這樣的：

從上圖看出，任務(wù)A和B的調(diào)度總時長達到了140ms，比實際A和B運行時長總和100ms要大。而且A阻塞在I/O操作期間，調(diào)度器并沒有切換到B，導(dǎo)致了CPU的空轉(zhuǎn)！

要解決該問題，只需使用RR的調(diào)度算法，給任務(wù)A和B分配10ms的時間片，這樣當(dāng)A阻塞在I/O操作時，就可以調(diào)度B，而B用完時間片后，恰好A也從I/O阻塞中返回，以此類推，調(diào)度總時長優(yōu)化至100ms。

該調(diào)度方案是建立在假設(shè)5之上的，也即要求調(diào)度器預(yù)先知道A和B的運行時長、I/O操作時間長等信息，才能如此充分地利用CPU。

然而，實際的情況遠比這復(fù)雜，I/O阻塞時長不會每次都一樣，調(diào)度器也無法準(zhǔn)確知道A和B的運行信息。當(dāng)假設(shè)5也被打破時，調(diào)度器又該如何實現(xiàn)才能最大程度保證CPU利用率，以及調(diào)度的合理性呢？

接下來，我們將介紹一個能夠在所有工作負載假設(shè)被打破的情況下依然表現(xiàn)良好，被許多現(xiàn)代操作系統(tǒng)采用的CPU調(diào)度算法，MLFQ。

MLFQ：多級反饋隊列

MLFQ（Multi-Level Feedback Queue，多級反饋隊列）調(diào)度算法的目標(biāo)如下：

1. 優(yōu)化周轉(zhuǎn)時間。
2. 降低交互類任務(wù)的響應(yīng)時間，提升用戶體驗。

從前面分析我們知道，要優(yōu)化周轉(zhuǎn)時間，可以優(yōu)先調(diào)度運行時長短的任務(wù)（像SJF和STCF的做法）；要優(yōu)化響應(yīng)時間，則采用類似RR的基于時間片的調(diào)度。然而，這兩個目標(biāo)看起來是矛盾的，要降低響應(yīng)時間，必然會增加周轉(zhuǎn)時間。

那么對MLFQ來說，就需要解決如下兩個問題：

1. 在不預(yù)先清楚任務(wù)的運行信息（包括運行時長、I/O操作等）的前提下，如何權(quán)衡周轉(zhuǎn)時間和響應(yīng)時間？
2. 如何從歷史調(diào)度中學(xué)習(xí)，以便未來做出更好的決策？

劃分任務(wù)的優(yōu)先級

MLFQ與前文介紹的幾種調(diào)度算法最顯著的特點就是新增了優(yōu)先級隊列存放不同優(yōu)先級的任務(wù)，并定下了如下兩個規(guī)則：

• 規(guī)則1 ：如果Priority(A) > Priority(B)，則調(diào)度A
• 規(guī)則2 ：如果Priority(A) = Priority(B)，則按照RR算法調(diào)度A和B

優(yōu)先級的變化

MLFQ必須考慮改變?nèi)蝿?wù)的優(yōu)先級，否則根據(jù) 規(guī)則1 和 規(guī)則2 ，對于上圖中的任務(wù)C，在A和B運行結(jié)束之前，C都不會獲得運行的機會，導(dǎo)致C的響應(yīng)時間很長。因此，可以定下了如下幾個優(yōu)先級變化規(guī)則：

• 規(guī)則3 ：當(dāng)一個新的任務(wù)到達時，將它放到最高優(yōu)先級隊列中
• 規(guī)則4a ：如果任務(wù)A運行了一個時間片都沒有主動讓出CPU（比如I/O操作），則優(yōu)先級降低一級
• 規(guī)則4b ：如果任務(wù)A在時間片用完之前，有主動讓出CPU，則優(yōu)先級保持不變

規(guī)則3主要考慮到讓新加入的任務(wù)都能得到調(diào)度機會，避免出現(xiàn)任務(wù)餓死的問題

規(guī)則4a和4b主要考慮到，交互類任務(wù)大都是short-running的，并且會頻繁讓出CPU，因此為了保證響應(yīng)時間，需要保持現(xiàn)有的優(yōu)先級；而CPU密集型任務(wù)，往往不會太關(guān)注響應(yīng)時間，因此可以降低優(yōu)先級。

按照上述規(guī)則，當(dāng)一個long-running任務(wù)A到達時，調(diào)度情況是這樣的：

如果在任務(wù)A運行到t=100時，short-time任務(wù)B到達，調(diào)度情況是這樣的：

從上述調(diào)度情況可以看出，MLFQ具備了STCF的優(yōu)點，即可以優(yōu)先完成short-running任務(wù)的調(diào)度，縮短了周轉(zhuǎn)時間。

如果任務(wù)A運行到t=100時，交互類任務(wù)C到達，那么調(diào)度情況是這樣的：

MLFQ會在任務(wù)處于阻塞時按照優(yōu)先級選擇其他任務(wù)運行，避免CPU空轉(zhuǎn) 。因此，在上圖中，當(dāng)任務(wù)C處于I/O阻塞狀態(tài)時，任務(wù)A得到了運行時間片，當(dāng)任務(wù)C從I/O阻塞上返回時，A再次掛起，以此類推。

另外，因為任務(wù)C在時間片之內(nèi)出現(xiàn)主動讓出CPU的行為，C的優(yōu)先級一直保持不變，這對于交互類任務(wù)而言，有效提升了用戶體驗。

CPU密集型任務(wù)餓死問題

到目前為止，MLFQ似乎能夠同時兼顧周轉(zhuǎn)時間，以及交互類任務(wù)的響應(yīng)時間，它真的完美了嗎？

考慮如下場景，任務(wù)A運行到t=100時，交互類任務(wù)C和D同時到達，那么調(diào)度情況會是這樣的：

由此可見，如果當(dāng)前系統(tǒng)上存在很多交互類任務(wù)時，CPU密集型任務(wù)將會存在餓死的可能！

為了解決該問題，可以設(shè)立了如下規(guī)則：

• 規(guī)則5 ：系統(tǒng)運行S時長之后，將所有任務(wù)放到最高優(yōu)先級隊列上（ Priority Boost ）

加上該規(guī)則之后，假設(shè)設(shè)置S為50ms，那么調(diào)度情況是這樣的，餓死問題得到解決！

惡意任務(wù)問題

考慮如下一個惡意任務(wù)E，為了長時間占用CPU，任務(wù)E在時間片還剩1%時故意執(zhí)行I/O操作，并很快返回。根據(jù) 規(guī)則4b ，E將會維持在原來的最高優(yōu)先級隊列上，因此下次調(diào)度時仍然獲得調(diào)度優(yōu)先權(quán)：

為了解決該問題，我們需要將規(guī)則4調(diào)整為如下規(guī)則：

• 規(guī)則4 ：給每個優(yōu)先級分配一個時間片，當(dāng)任務(wù)用完該優(yōu)先級的時間片后，優(yōu)先級降一級

應(yīng)用新的規(guī)則4后，相同的工作負載，調(diào)度情況變成了如下所述，不再出現(xiàn)惡意任務(wù)E占用大量CPU的問題。

到目前為止，MLFQ的基本原理已經(jīng)介紹完，最后，我們總結(jié)下MLFQ最關(guān)鍵的5項規(guī)則：

• 規(guī)則1 ：如果Priority(A) > Priority(B)，則調(diào)度A
• 規(guī)則2 ：如果Priority(A) = Priority(B)，則按照RR算法調(diào)度A和B
• 規(guī)則3 ：當(dāng)一個新的任務(wù)到達時，將它放到最高優(yōu)先級隊列中
• 規(guī)則4 ：給每個優(yōu)先級分配一個時間片，當(dāng)任務(wù)用完該優(yōu)先級的時間片后，優(yōu)先級降一級
• 規(guī)則5 ：系統(tǒng)運行S時長之后，將所有任務(wù)放到最高優(yōu)先級隊列上（ Priority Boost ）

現(xiàn)在，再回到本節(jié)開始時提出的兩個問題：

1、在不預(yù)先清楚任務(wù)的運行信息（包括運行時長、I/O操作等）的前提下，MLFQ如何權(quán)衡周轉(zhuǎn)時間和響應(yīng)時間 ？

在預(yù)先不清楚任務(wù)到底是long-running或short-running的情況下，MLFQ會先假設(shè)任務(wù)屬于shrot-running任務(wù)，如果假設(shè)正確，任務(wù)就會很快完成，周轉(zhuǎn)時間和響應(yīng)時間都得到優(yōu)化；即使假設(shè)錯誤，任務(wù)的優(yōu)先級也能逐漸降低，把更多的調(diào)度機會讓給其他short-running任務(wù)。

2、MLFQ如何從歷史調(diào)度中學(xué)習(xí)，以便未來做出更好的決策 ？

MLFQ主要根據(jù)任務(wù)是否有主動讓出CPU的行為來判斷其是否是交互類任務(wù)，如果是，則維持在當(dāng)前的優(yōu)先級，保證該任務(wù)的調(diào)度優(yōu)先權(quán)，提升交互類任務(wù)的響應(yīng)性。

當(dāng)然，MLFQ并非完美的調(diào)度算法，它也存在著各種問題，其中最讓人困擾的就是MLFQ各項參數(shù)的設(shè)定，比如優(yōu)先級隊列的數(shù)量，時間片的長度、Priority Boost的間隔等。

這些參數(shù)并沒有完美的參考值，只能根據(jù)不同的工作負載來進行設(shè)置。

比如，我們可以將低優(yōu)先級隊列上任務(wù)的時間片設(shè)置長一些，因為低優(yōu)先級的任務(wù)往往是CPU密集型任務(wù)，它們不太關(guān)心響應(yīng)時間，較長的時間片長能夠減少上下文切換帶來的消耗。

CFS：Linux的完全公平調(diào)度

本節(jié)我們將介紹一個平時打交道最多的調(diào)度算法，Linux系統(tǒng)下的CFS（Completely Fair Scheduler，完全公平調(diào)度）。與上一節(jié)介紹的MLFQ不同， CFS并非以優(yōu)化周轉(zhuǎn)時間和響應(yīng)時間為目標(biāo)，而是希望將CPU公平地均分給每個任務(wù) 。

當(dāng)然，CFS也提供了給進程設(shè)置優(yōu)先級的功能，讓用戶/管理員決定哪些進程需要獲得更多的調(diào)度時間。

基本原理

大部分調(diào)度算法都是基于固定時間片來進行調(diào)度，而CFS另辟蹊徑，采用基于計數(shù)的調(diào)度方法，該技術(shù)被稱為 virtual runtime 。

CFS給每個任務(wù)都維護一個vruntime值，每當(dāng)任務(wù)被調(diào)度之后，就累加它的vruntime。

比如，當(dāng)任務(wù)A運行了5ms的時間片之后，則更新為vruntime += 5ms。 CFS在下次調(diào)度時，選擇vruntime值最小的任務(wù)來調(diào)度 ，比如：

那CFS應(yīng)該什么時候進行任務(wù)切換呢？切換得頻繁些，任務(wù)的調(diào)度會更加的公平，但是上下文切換帶來的消耗也越大。因此，CFS給用戶提供了個可配參數(shù)sched_latency，讓用戶來決定切換的時機。

CFS將每個任務(wù)分到的時間片設(shè)置為 time_slice = sched_latency / n（n為當(dāng)前的任務(wù)數(shù)） ，以確保在sched_latency周期內(nèi)，各任務(wù)能夠均分CPU，保證公平性。

比如將sched_latency設(shè)置為48ms，當(dāng)前有4個任務(wù)A、B、C和D，那么每個任務(wù)分到的時間片為12ms；后面C和D結(jié)束之后，A和B分到的時間片也更新為24ms：

從上述原理上看，在sched_latency 不變的情況下，隨著系統(tǒng)任務(wù)數(shù)的增加，每個任務(wù)分到的時間片也隨之減少，任務(wù)切換所帶來的消耗也會增大。為了避免過多的任務(wù)切換消耗，CFS提供了可配參數(shù)min_granularity來設(shè)置任務(wù)的最小時間片。

比如sched_latency設(shè)置為48ms，min_granularity設(shè)置為 6ms，那么即使當(dāng)前任務(wù)數(shù)有12，每個任務(wù)數(shù)分到的時間片也是6ms，而不是4ms。

給任務(wù)分配權(quán)重

有時候，我們希望給系統(tǒng)中某個重要的業(yè)務(wù)進程多分配些時間片，而其他不重要的進程則少分配些時間片。但按照上一節(jié)介紹的基本原理，使用CFS調(diào)度時，每個任務(wù)都是均分CPU的，有沒有辦法可以做到這一點呢？

可以給任務(wù)分配權(quán)重，讓權(quán)重高的任務(wù)更多的CPU ！

加上權(quán)重機制后，任務(wù)時間片的計算方式變成了這樣：

比如，sched_latency還是設(shè)置為48ms，現(xiàn)有A和B兩個任務(wù)，A的權(quán)重設(shè)置為1024，B的權(quán)重設(shè)置為3072，按照上述的公式，A的時間片是12ms，B的時間片是36ms。

從上一節(jié)可知，CFS每次選取vruntime值最小的任務(wù)來調(diào)度，而每次調(diào)度完成后，vruntime的計算規(guī)則為vruntime += runtime，因此僅僅改變時間片的計算規(guī)則不會生效，還需將vruntime的計算規(guī)則調(diào)整為：

還是前面的例子，假設(shè)A和B都沒有I/O操作，更新vruntime計算規(guī)則后，調(diào)度情況如下，任務(wù)B比任務(wù)A能夠分得更多的CPU了。

使用紅黑樹提升vruntime查找效率

CFS每次切換任務(wù)時，都會選取vruntime值最小的任務(wù)來調(diào)度，因此需要它有個數(shù)據(jù)結(jié)構(gòu)來存儲各個任務(wù)及其vruntime信息。

最直觀的當(dāng)然就是選取一個有序列表來存儲這些信息，列表按照vruntime排序。這樣在切換任務(wù)時，CFS只需獲取列表頭的任務(wù)即可，時間復(fù)雜度為O(1)。

比如當(dāng)前有10個任務(wù)，vruntime保存為有序鏈表[1, 5, 9, 10, 14, 18, 17, 21, 22, 24]，但是每次插入或刪除任務(wù)時，時間復(fù)雜度會是O(N)，而且耗時隨著任務(wù)數(shù)的增多而線性增長！

為了兼顧查詢、插入、刪除的效率，CFS使用紅黑樹來保存任務(wù)和vruntime信息，這樣，查詢、插入、刪除操作的復(fù)雜度變成了log(N)，并不會隨著任務(wù)數(shù)的增多而線性增長，極大提升了效率。

另外，為了提升存儲效率，CFS在紅黑樹中只保存了處于Running狀態(tài)的任務(wù)的信息。

應(yīng)對I/O與休眠

每次都選取vruntime值最小的任務(wù)來調(diào)度這種策略，也會存在任務(wù)餓死的問題。考慮有A和B兩個任務(wù)，時間片為1s，起初A和B均分CPU輪流運行，在某次調(diào)度后，B進入了休眠，假設(shè)休眠了10s。

等B醒來后，就會比小10s，在接下來的10s中，B將會一直被調(diào)度，從而任務(wù)A出現(xiàn)了餓死現(xiàn)象。

為了解決該問題，CFS規(guī)定當(dāng)任務(wù)從休眠或I/O中返回時，該任務(wù)的vruntime會被設(shè)置為當(dāng)前紅黑樹中的最小vruntime值。上述例子，B從休眠中醒來后，會被設(shè)置為11，因此也就不會餓死任務(wù)A了。

這種做法其實也存在瑕疵，如果任務(wù)的休眠時間很短，那么它醒來后依舊是優(yōu)先調(diào)度，這對于其他任務(wù)來說是不公平的。

寫在最后

本文花了很長的篇幅講解了幾種常見CPU調(diào)度算法的原理，每種算法都有各自的優(yōu)缺點，并不存在一種完美的調(diào)度策略。在應(yīng)用中，我們需要根據(jù)實際的工作負載，選取合適的調(diào)度算法，配置合理的調(diào)度參數(shù)，權(quán)衡周轉(zhuǎn)時間和響應(yīng)時間、任務(wù)公平和切換消耗。

這些都應(yīng)驗了《Fundamentals of Software Architecture》中的那句名言： Everything in software architecture is a trade-off .

本文中描述的調(diào)度算法都是基于單核處理器進行分析的，而多核處理器上的調(diào)度算法要比這復(fù)雜很多，比如需要考慮處理器之間共 享數(shù)據(jù)同步 、緩存親和性等，但本質(zhì)原理依然離不開本文所描述的幾種基礎(chǔ)調(diào)度算法。