Linux 組調(diào)度淺析

cgroup 與組調(diào)度

linux內(nèi)核實現(xiàn)了control group功能（cgroup，since linux 2.6.24），可以支持將進程分組，然后按組來劃分各種資源。比如：group-1擁有30%的CPU和50%的磁盤IO、group-2擁有10%的CPU和20%的磁盤IO、等等。具體參閱cgroup相關文章。

cgroup支持很多種資源的劃分，CPU資源就是其中之一，這就引出了組調(diào)度。

linux內(nèi)核中，傳統(tǒng)的調(diào)度程序是基于進程來調(diào)度的。假設用戶A和B共用一臺機器，這臺機器主要用來編譯程序。我們可能希望A和B能公平的分享CPU資源，但是如果用戶A使用make -j8（8個線程并行make）、而用戶B直接使用make的話（假設他們的make程序都使用了默認的優(yōu)先級），A用戶的make程序?qū)a(chǎn)生8倍于B用戶的進程數(shù)，從而占用（大致）8倍于B用戶的CPU。因為調(diào)度程序是基于進程的，A用戶的進程越多，被調(diào)度的機率就越大，就越具有對CPU的競爭力。

如何保證A、B用戶公平分享CPU呢？組調(diào)度就能做到這一點。把屬于用戶A和B的進程各分為一組，調(diào)度程序?qū)⑾葟膬蓚€組中選擇一個組，再從選中的組中選擇一個進程來執(zhí)行。如果兩個組被選中的機率相當，那么用戶A和B將各占有約50%的CPU。

相關數(shù)據(jù)結(jié)構(gòu)

在linux內(nèi)核中，使用task_group結(jié)構(gòu)來管理組調(diào)度的組。所有存在的task_group組成一個樹型結(jié)構(gòu)（與cgroup的目錄結(jié)構(gòu)相對應）。

一個task_group可以包含具有任意調(diào)度類別的進程（具體來說是實時進程和普通進程兩種類別），于是task_group需要為每一種調(diào)度策略提供一組調(diào)度結(jié)構(gòu)。這里所說的一組調(diào)度結(jié)構(gòu)主要包括兩個部分，調(diào)度實體和運行隊列（兩者都是每CPU一份的）。調(diào)度實體會被添加到運行隊列中，對于一個task_group，它的調(diào)度實體會被添加到其父task_group的運行隊列。

為什么要有調(diào)度實體這樣的東西呢？因為被調(diào)度的對象有task_group和task兩種，所以需要一個抽象的結(jié)構(gòu)來代表它們。如果調(diào)度實體代表task_group，則它的my_q字段指向這個調(diào)度組對應的運行隊列；否則my_q字段為NULL，調(diào)度實體代表task。在調(diào)度實體中與my_q相對的是X_rq（具體是針對普通進程的cfs_rq和針對實時進程的rt_rq），前者指向這個組自己的運行隊列，里面會放入它的子節(jié)點；后者指向這個組的父節(jié)點的運行隊列，也就是這個調(diào)度實體應該被放入的運行隊列。

于是，調(diào)度實體和運行隊列又組成了另一個樹型結(jié)構(gòu)，它的每一個非葉子節(jié)點都跟task_group的樹型結(jié)構(gòu)是相對應的，而葉子節(jié)點都對應到具體的task。就像非TASK_RUNNING狀態(tài)的進程不會被放入運行隊列一樣，如果一個組中不存在TASK_RUNNING狀態(tài)的進程，則這個組（對應的調(diào)度實體）也不會被放入它的上一級運行隊列。明確一點，只要調(diào)度組創(chuàng)建了，其對應的task_group就肯定存在于由task_group組成的樹型結(jié)構(gòu)中；而其對應的調(diào)度實體是否存在于由運行隊列和調(diào)度實體組成的樹型結(jié)構(gòu)中，要取決于這個組中是否存在TASK_RUNNING狀態(tài)的進程。

作為根節(jié)點的task_group是沒有調(diào)度實體的，調(diào)度程序總是從它的運行隊列出發(fā)，來選擇下一個調(diào)度實體（根節(jié)點必定是第一個被選中的，沒有其他候選者，所以根節(jié)點不需要調(diào)度實體）。根節(jié)點task_group所對應的運行隊列被包裝在一個rq結(jié)構(gòu)中，里面除了包含具體的運行隊列以外，還有一些全局統(tǒng)計信息等字段。

調(diào)度發(fā)生的時候，調(diào)度程序從根task_group的運行隊列中選擇一個調(diào)度實體。如果這個調(diào)度實體代表一個task_group，則調(diào)度程序需要從這個組對應的運行隊列繼續(xù)選擇一個調(diào)度實體。如此遞歸下去，直到選中一個進程。除非根task_group的運行隊列為空，否則遞歸下去一定能找到一個進程。因為如果一個task_group對應的運行隊列為空，它對應的調(diào)度實體就不會被添加到其父節(jié)點對應的運行隊列中。

最后，對于一個task_group來說，它的調(diào)度實體和運行隊列都是每CPU一份的，一個（task_group對應的）調(diào)度實體只會被加入到相同CPU所對應的運行隊列。而對于task來說，它的調(diào)度實體則只有一份（沒有按CPU劃分），調(diào)度程序的負載均衡功能可能會將（task對應的）調(diào)度實體從不同CPU所對應的運行隊列移來移去。（參見《linux內(nèi)核SMP負載均衡淺析》）

組的調(diào)度策略

組調(diào)度的主要數(shù)據(jù)結(jié)構(gòu)已經(jīng)理清了，這里還有一個很重要的問題。我們知道task擁有其對應的優(yōu)先級（靜態(tài)優(yōu)先級 or 動態(tài)優(yōu)先級），調(diào)度程序根據(jù)優(yōu)先級來選擇運行隊列中的進程。那么，既然task_group和task一樣，都被抽象成調(diào)度實體，接受同樣的調(diào)度，task_group的優(yōu)先級又該如何定義呢？這個問題需要具體到調(diào)度類別來解答（不同的調(diào)度類別，其優(yōu)先級定義方式不一樣），具體來說就是rt（實時調(diào)度）和cfs（完全公平調(diào)度）兩種類別。

實時進程的組調(diào)度

實時進程是對CPU有著實時性要求的進程，它的優(yōu)先級是跟具體任務相關的，完全由用戶來定義的。調(diào)度器總是會選擇優(yōu)先級最高的實時進程來運行。

發(fā)展到組調(diào)度，組的優(yōu)先級就被定義為“組內(nèi)最高優(yōu)先級的進程所擁有的優(yōu)先級”。比如組內(nèi)有三個優(yōu)先級分別為10、20、30的進程，則組的優(yōu)先級就是10（數(shù)值越小優(yōu)先級越大）。

組的優(yōu)先級如此定義，引出了一個有趣的現(xiàn)象。當task入隊或者出隊時，要把它的所有祖先節(jié)點都先出隊，然后再重新由底向上依次入隊。因為組節(jié)點的優(yōu)先級是依賴于它的子節(jié)點的，task的入隊和出隊將影響它的每一個祖先節(jié)點。

于是，當調(diào)度程序從根節(jié)點的task_group出發(fā)選擇調(diào)度實體時，總是能沿著正確的路徑，找到所有TASK_RUNNING狀態(tài)的實時進程中優(yōu)先級最高的那一個。這個實現(xiàn)似乎理所當然，但是仔細想想，這樣一來，將實時進程分組還有什么意義呢？無論分組與否，調(diào)度程序要做的事情都是“在所有TASK_RUNNING狀態(tài)的實時進程中選擇優(yōu)先級最高的那一個”。這里似乎還缺了些什么……

現(xiàn)在需要先介紹一下linux系統(tǒng)中的兩個proc文件：/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us。這兩個文件規(guī)定了，在以sched_rt_period_us為一個周期的時間內(nèi)，所有實時進程的運行時間之和不超過sched_rt_runtime_us。這兩個文件的默認值是1s和0.95s，表示每秒種為一個周期，在這個周期中，所有實時進程運行的總時間不超過0.95秒，剩下的至少0.05秒會留給普通進程。也就是說，實時進程占有不超過95%的CPU。而在這兩個文件出現(xiàn)之前，實時進程的運行時間是沒有限制的，如果一直有處于TASK_RUNNING狀態(tài)的實時進程，則普通進程會一直不能得到運行。相當于sched_rt_runtime_us等于sched_rt_period_us。

為什么要有sched_rt_runtime_us和sched_rt_period_us兩個變量呢？直接使用一個表示CPU占有百分比的變量不可以么？我想這應該是由于很多實時進程實際上都是周期性地在干某件事情，比如某語音程序每20ms發(fā)送一個語音包、某視頻程序每40ms刷新一幀、等等。周期是很重要的，僅僅使用一個宏觀的CPU占有比無法準確描述實時進程需求。

而實時進程的分組就把sched_rt_runtime_us和sched_rt_period_us的概念擴展了，每個task_group都有自己的sched_rt_runtime_us和sched_rt_period_us，保證自己組內(nèi)的進程在以sched_rt_period_us為周期的時間內(nèi)，最多只能運行sched_rt_runtime_us這么多時間。CPU占有比為sched_rt_runtime_us/sched_rt_period_us。

對于根節(jié)點的task_group，它的sched_rt_runtime_us和sched_rt_period_us就等于上面兩個proc文件中的值。而對于一個task_group節(jié)點來說，假設它下面有n個調(diào)度子組和m個TASK_RUNNING狀態(tài)的進程，它的CPU占有比為A、這n個子組的CPU占有比為B，則B必須小于等于A，而A-B剩下的CPU時間將分給那m個TASK_RUNNING狀態(tài)的進程。（這里討論的是CPU占有比，因為每個調(diào)度組可能有著不同的周期值。）

為了實現(xiàn)sched_rt_runtime_us和sched_rt_period_us的邏輯，內(nèi)核在更新進程的運行時間的時候（比如由周期性的時鐘中斷觸發(fā)的時間更新）會給當前進程的調(diào)度實體及其所有祖先節(jié)點都增加相應的runtime。如果一個調(diào)度實體達到了sched_rt_runtime_us所限定的時間，則將其從對應的運行隊列中剔除，并將對應的rt_rq置throttled狀態(tài)。在這個狀態(tài)下，這個rt_rq對應的調(diào)度實體不會再次進入運行隊列。而每個rt_rq都會維護一個周期性的定時器，定時周期為sched_rt_period_us。每次定時器觸發(fā)，其對應的回調(diào)函數(shù)就會將rt_rq的runtime減去一個sched_rt_period_us單位的值（但要保持runtime不小于0），然后將rt_rq從throttled狀態(tài)中恢復回來。

還有一個問題，前面說到，默認情況下，系統(tǒng)中每秒鐘內(nèi)實時進程的運行時間不超過0.95秒。如果實時進程實際對CPU的需求不足0.95秒（大于等于0秒、小于0.95秒），則剩下的時間都會分配給普通進程。而如果實時進程的對CPU的需求大于0.95秒，它也只能夠運行0.95秒，剩下的0.05秒會分給其他普通進程。但是，如果這0.05秒內(nèi)沒有任何普通進程需要使用CPU（一直沒有TASK_RUNNING狀態(tài)的普通進程）呢？這種情況下既然普通進程對CPU沒有需求，實時進程是否可以運行超過0.95秒呢？不能。在剩下的0.05秒中內(nèi)核寧可讓CPU一直閑著，也不讓實時進程使用?？梢妔ched_rt_runtime_us和sched_rt_period_us是很有強制性的。

最后還有多CPU的問題，前面也提到，對于每一個task_group，它的調(diào)度實體和運行隊列是每CPU維護一份的。而sched_rt_runtime_us和sched_rt_period_us是作用在調(diào)度實體上的.所以如果系統(tǒng)中有N個CPU，實時進程實際占有CPU的上限N*sched_rt_runtime_us/sched_rt_period_us。也就是說，盡管默認情況下限制了每秒鐘之內(nèi)，實時進程只能運行0.95秒。但是對于某個實時進程來說，如果CPU有兩個核，也還是能滿足它100%占有CPU的需求的（比如執(zhí)行死循環(huán)）。然后，按道理說，這個實時進程占有的100%的CPU應該是由兩部分組成的（每個CPU占有一部分，但都不超過95%）。但是實際上，為了避免進程在CPU間的遷移導致上下文切換、緩存失效等一系列問題，一個CPU上的調(diào)度實體可以向另一個CPU上對應的調(diào)度實體借用時間。其結(jié)果就是，宏觀上既滿足了sched_rt_runtime_us的限制，又避免了進程的遷移。

普通進程的組調(diào)度

文章一開頭提到了希望A、B兩個用戶在進程數(shù)不相同的情況下也能平分CPU的需求，但是上面關于實時進程的組調(diào)度策略好像與此不太相干，其實這就是普通進程的組調(diào)度所要干的事。

相比實時進程，普通進程的組調(diào)度就沒有這么多講究。組被看作是跟進程幾乎完全相同的實體，它擁有自己的靜態(tài)優(yōu)先級、調(diào)度程序也動態(tài)地調(diào)整它的優(yōu)先級。對于一個組來說，組內(nèi)進程的優(yōu)先級并不影響組的優(yōu)先級，只有這個組被調(diào)度程序選中時，這些進程的優(yōu)先級才被考慮。

為了設置組的優(yōu)先級，每個task_group都有一個shares參數(shù)（跟前面提到的sched_rt_runtime_us和sched_rt_period_us兩個參數(shù)并列）。shares并不是優(yōu)先級，而是調(diào)度實體的權(quán)重（這是CFS調(diào)度器的玩法），這個權(quán)重和優(yōu)先級是有一一對應的關系的。普通進程的優(yōu)先級也會被轉(zhuǎn)換成其對應調(diào)度實體的權(quán)重，所以可以說shares就代表了優(yōu)先級。

shares的默認值跟普通進程默認優(yōu)先級對應的權(quán)重是一樣的。所以在默認情況下，組和進程是平分CPU的。

示例

（環(huán)境：ubuntu 10.04，kernel 2.6.32，Intel Core2 雙核）

掛載一個只劃分CPU資源的cgroup，并創(chuàng)建grp_a和grp_b兩個子組：

分別開三個shell，第一個加入grp_a，后兩個加入grp_b：

（為什么要用ttt.sh來寫cgroup下的tasks文件呢？因為寫這個文件需要root權(quán)限，當前shell沒有root權(quán)限，而sudo只能賦予被它執(zhí)行的程序的root權(quán)限。其實sudo sh，然后再在新開的shell里面執(zhí)行echo操作也是可以的。）

回到cgroup目錄下，確認這幾個shell都被加進去了：

現(xiàn)在準備在這三個shell下同時執(zhí)行一個死循環(huán)的程序（a.out），為了避免多CPU帶來的影響，將進程綁定到第二個核上：

?

編譯生成a.out，然后在前面的三個shell中分別運行。三個shell分別會fork出一個子進程來執(zhí)行a.out，這些子進程都會繼承其父進程的cgroup分組信息。然后top一下，可以觀察到屬于grp_a的a.out占了50%的CPU，而屬于grp_b的兩個a.out各占25%的CPU（加起來也是50%）：

?

接下來再試試實時進程，把a.out程序改造如下：

然后設置grp_a的rt_runtime值：

現(xiàn)在的配置是每秒為一個周期，屬于grp_a的實時進程每秒種只能執(zhí)行300毫秒。運行a.out（設置實時進程需要root權(quán)限），然后top看看：

?

可以看到，CPU雖然閑著，但是卻不分給a.out程序使用。由于雙核的原因，a.out實際的CPU占用是60%而不是30%。

其他

前段時間，有一篇“200+行Kernel補丁顯著改善Linux桌面性能”的新聞比較火。這個內(nèi)核補丁能讓高負載條件下的桌面程序響應延遲得到大幅度降低。其實現(xiàn)原理是，自動創(chuàng)建基于TTY的task_group，所有進程都會被放置在它所關聯(lián)的TTY組中。通過這樣的自動分組，就將桌面程序（Xwindow會占用一個TTY）和其他終端或偽終端（各自占用一個TTY）劃分開了。終端上運行的高負載程序（比如make -j64）對桌面程序的影響將大大減少。（根據(jù)前面描述的普通進程的組調(diào)度的實現(xiàn)可以知道，如果一個任務給系統(tǒng)帶來了很高的負載，只會影響到與它同組的進程。這個任務包含一個或是一萬個TASK_RUNNING狀態(tài)的進程，對于其他組的進程來說是沒有影響的。）