cgroup 與組調(diào)度

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

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

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

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

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

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

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

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

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

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

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

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

組的調(diào)度策略

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

實(shí)時(shí)進(jìn)程的組調(diào)度

實(shí)時(shí)進(jìn)程是對(duì)CPU有著實(shí)時(shí)性要求的進(jìn)程，它的優(yōu)先級(jí)是跟具體任務(wù)相關(guān)的，完全由用戶來(lái)定義的。調(diào)度器總是會(huì)選擇優(yōu)先級(jí)最高的實(shí)時(shí)進(jìn)程來(lái)運(yùn)行。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

示例

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

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

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

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

回到cgroup目錄下，確認(rèn)這幾個(gè)shell都被加進(jìn)去了：

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

?

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

?

接下來(lái)再試試實(shí)時(shí)進(jìn)程，把a(bǔ).out程序改造如下：

然后設(shè)置grp_a的rt_runtime值：

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

?

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

其他

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