Linux 組調度淺析

cgroup 與組調度

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

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

linux內核中，傳統的調度程序是基于進程來調度的。假設用戶A和B共用一臺機器，這臺機器主要用來編譯程序。我們可能希望A和B能公平的分享CPU資源，但是如果用戶A使用make -j8（8個線程并行make）、而用戶B直接使用make的話（假設他們的make程序都使用了默認的優先級），A用戶的make程序將產生8倍于B用戶的進程數，從而占用（大致）8倍于B用戶的CPU。因為調度程序是基于進程的，A用戶的進程越多，被調度的機率就越大，就越具有對CPU的競爭力。

如何保證A、B用戶公平分享CPU呢？組調度就能做到這一點。把屬于用戶A和B的進程各分為一組，調度程序將先從兩個組中選擇一個組，再從選中的組中選擇一個進程來執行。如果兩個組被選中的機率相當，那么用戶A和B將各占有約50%的CPU。

相關數據結構

在linux內核中，使用task_group結構來管理組調度的組。所有存在的task_group組成一個樹型結構（與cgroup的目錄結構相對應）。

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

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

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

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

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

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

組的調度策略

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

實時進程的組調度

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

發展到組調度，組的優先級就被定義為“組內最高優先級的進程所擁有的優先級”。比如組內有三個優先級分別為10、20、30的進程，則組的優先級就是10（數值越小優先級越大）。

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

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

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

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

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

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

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

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

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

普通進程的組調度

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

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

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

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

示例

（環境：ubuntu 10.04，kernel 2.6.32，Intel Core2 雙核）

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

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

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

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

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

?

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

?

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

然后設置grp_a的rt_runtime值：

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

?

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

其他

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