電子發(fā)燒友App
在SMP（對(duì)稱多處理器）環(huán)境下，每個(gè)CPU對(duì)應(yīng)一個(gè)run_queue（可執(zhí)行隊(duì)列）。如果一個(gè)進(jìn)程處于TASK_RUNNING狀態(tài)（可執(zhí)行狀態(tài)），則它會(huì)被加入到其中一個(gè)run_queue（且同一時(shí)刻僅會(huì)被加入到一個(gè)run_queue），以便讓調(diào)度程序安排它在這個(gè)run_queue對(duì)應(yīng)的CPU上面運(yùn)行。
一個(gè)CPU對(duì)應(yīng)一個(gè)run_queue這樣的設(shè)計(jì)，其好處是：
1、一個(gè)持續(xù)處于TASK_RUNNING狀態(tài)的進(jìn)程總是趨于在同一個(gè)CPU上面運(yùn)行（其間，這個(gè)進(jìn)程可能被搶占、然后又被調(diào)度），這有利于進(jìn)程的數(shù)據(jù)被CPU所緩存，提高運(yùn)行效率；
2、各個(gè)CPU上的調(diào)度程序只訪問自己的run_queue，避免了競爭；
然而，這樣的設(shè)計(jì)也可能使得各個(gè)run_queue里面的進(jìn)程不均衡，造成“一些CPU閑著、一些CPU忙不過來”混亂局面。為了解決這個(gè)問題，load_balance（負(fù)載均衡）就登場了。
load_balance所需要做的事情就是，在一定的時(shí)機(jī)，通過將進(jìn)程從一個(gè)run_queue遷移到另一個(gè)run_queue，來保持CPU之間的負(fù)載均衡。
這里的“均衡”二字如何定義？load_balance又具體要做哪些事情呢？對(duì)于不同調(diào)度策略（實(shí)時(shí)進(jìn)程 OR 普通進(jìn)程），有著不同的邏輯，需要分開來看。
實(shí)時(shí)進(jìn)程的負(fù)載均衡
實(shí)時(shí)進(jìn)程的調(diào)度是嚴(yán)格按照優(yōu)先級(jí)來進(jìn)行的。在單CPU環(huán)境下，CPU上運(yùn)行著的總是優(yōu)先級(jí)最高的進(jìn)程，直到這個(gè)進(jìn)程離開TASK_RUNNING狀態(tài)，新任的“優(yōu)先級(jí)最高的進(jìn)程”才開始得到運(yùn)行。直到所有實(shí)時(shí)進(jìn)程都離開TASK_RUNNING狀態(tài)，其他普通進(jìn)程才有機(jī)會(huì)得到運(yùn)行。（暫時(shí)忽略sched_rt_runtime_us和sched_rt_period_us的影響。）
推廣到SMP環(huán)境，假設(shè)有N個(gè)CPU，N個(gè)CPU上分別運(yùn)行著的也必須是優(yōu)先級(jí)最高的top-N個(gè)進(jìn)程。如果實(shí)時(shí)進(jìn)程不足N個(gè)，那么剩下的CPU才分給普通進(jìn)程去使用。對(duì)于實(shí)時(shí)進(jìn)程來說，這就是所謂的“均衡”。
實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)關(guān)系是很嚴(yán)格的，當(dāng)優(yōu)先級(jí)最高的top-N個(gè)進(jìn)程發(fā)生變化時(shí)，內(nèi)核必須馬上響應(yīng)：
1、如果這top-N個(gè)進(jìn)程當(dāng)中，有一個(gè)離開TASK_RUNNING狀態(tài)、或因?yàn)閮?yōu)先級(jí)被調(diào)低而退出top-N集團(tuán)，則原先處于(N+1)位的那個(gè)進(jìn)程將進(jìn)入top-N。內(nèi)核需要遍歷所有的run_queue，把這個(gè)新任的top-N進(jìn)程找出來，然后立馬讓它開始運(yùn)行；
2、反之，如果一個(gè)top-N之外的實(shí)時(shí)進(jìn)程的優(yōu)先級(jí)被調(diào)高，以至于擠占了原先處于第N位的進(jìn)程，則內(nèi)核需要遍歷所有的run_queue，把這個(gè)被擠出top-N的進(jìn)程找出來，將它正在占用的CPU讓給新進(jìn)top-N的那個(gè)進(jìn)程去運(yùn)行；
在這幾種情況下，新進(jìn)入top-N的進(jìn)程和退出top-N的進(jìn)程可能原本并不在同一個(gè)CPU上，那么在它得到運(yùn)行之前，內(nèi)核會(huì)先將其遷移到退出top-N的進(jìn)程所在的CPU上。
具體來說，內(nèi)核通過pull_rt_task和push_rt_task兩個(gè)函數(shù)來完成實(shí)時(shí)進(jìn)程的遷移：
pull_rt_task – 把其他CPU的run_queue中的實(shí)時(shí)進(jìn)程pull過來，放到當(dāng)前CPU的run_queue中。被pull過來的實(shí)時(shí)進(jìn)程要滿足以下條件：
1、進(jìn)程是其所在的run_queue中優(yōu)先級(jí)第二高的（優(yōu)先級(jí)最高的進(jìn)程必定正在運(yùn)行，不需要移動(dòng)）；
2、進(jìn)程的優(yōu)先級(jí)比當(dāng)前run_queue中最高優(yōu)先級(jí)的進(jìn)程還要高；
3、進(jìn)程允許在當(dāng)前CPU上運(yùn)行（沒有親和性限制）；
該函數(shù)會(huì)在以下時(shí)間點(diǎn)被調(diào)用：
1、發(fā)生調(diào)度之前，如果prev進(jìn)程（將要被替換下去的進(jìn)程）是實(shí)時(shí)進(jìn)程，且優(yōu)先級(jí)高于當(dāng)前run_queue中優(yōu)先級(jí)最高的實(shí)時(shí)進(jìn)程（這說明prev進(jìn)程已經(jīng)離開TASK_RUNNING狀態(tài)了，否則它不會(huì)讓位于比它優(yōu)先級(jí)低的進(jìn)程）；
2、正在運(yùn)行的實(shí)時(shí)進(jìn)程優(yōu)先級(jí)被調(diào)低時(shí)（比如通過sched_setparam系統(tǒng)調(diào)用）；
3、正在運(yùn)行的實(shí)時(shí)進(jìn)程變成普通進(jìn)程時(shí)（比如通過sched_setscheduler系統(tǒng)調(diào)用）；
push_rt_task – 把當(dāng)前run_queue中多余的實(shí)時(shí)進(jìn)程推給其他run_queue。需要滿足以下條件：
1、每次push一個(gè)進(jìn)程，這個(gè)進(jìn)程的優(yōu)先級(jí)在當(dāng)前run_queue中是第二高的（優(yōu)先級(jí)最高的進(jìn)程必定正在運(yùn)行，不需要移動(dòng)）；
2、目標(biāo)run_queue上正在運(yùn)行的不是實(shí)時(shí)進(jìn)程（是普通進(jìn)程），或者是top-N中優(yōu)先級(jí)最低的實(shí)時(shí)進(jìn)程，且優(yōu)先級(jí)低于被push的進(jìn)程；
3、被push的進(jìn)程允許在目標(biāo)CPU上運(yùn)行（沒有親和性限制）；
4、滿足條件的目標(biāo)run_queue可能存在多個(gè)（可能多個(gè)CPU上都沒有實(shí)時(shí)進(jìn)程在運(yùn)行），應(yīng)該選擇與當(dāng)前CPU最具親緣性的一組CPU中的第一個(gè)CPU所對(duì)應(yīng)的run_queue作為push的目標(biāo)（順著sched_domain–調(diào)度域–逐步往上，找到第一個(gè)包含目標(biāo)CPU的sched_domain。見后面關(guān)于sched_domain的描述）；
該函數(shù)會(huì)在以下時(shí)間點(diǎn)被調(diào)用：
1、非正在運(yùn)行的普通進(jìn)程變成實(shí)時(shí)進(jìn)程時(shí)（比如通過sched_setscheduler系統(tǒng)調(diào)用）；
2、發(fā)生調(diào)度之后（這時(shí)候可能有一個(gè)實(shí)時(shí)進(jìn)程被更高優(yōu)先級(jí)的實(shí)時(shí)進(jìn)程搶占了）；
3、實(shí)時(shí)進(jìn)程被喚醒之后，如果不能馬上在當(dāng)前CPU上運(yùn)行（它不是當(dāng)前CPU上優(yōu)先級(jí)最高的進(jìn)程）；
看起來，實(shí)時(shí)進(jìn)程的負(fù)載均衡對(duì)于每個(gè)CPU一個(gè)run_queue這種模式似乎有些別扭，每次需要選擇一個(gè)實(shí)時(shí)進(jìn)程，總是需要遍歷所有run_queue，在尚未能得到運(yùn)行的實(shí)時(shí)進(jìn)程之中找到優(yōu)先級(jí)最高的那一個(gè)。其實(shí)，如果所有CPU共用同一個(gè)run_queue，就沒有這么多的煩惱了。為什么不這樣做呢？
1、在CPU對(duì)run_queue的競爭方面，“每個(gè)CPU去競爭每一個(gè)run_queue”比“每個(gè)CPU去競爭一個(gè)總的run_queue”略微好一些，因?yàn)楦偁幍牧６雀×耍?br /> 2、在進(jìn)程的移動(dòng)方面，每個(gè)CPU一個(gè)run_queue這種模式其實(shí)也不能很好的把進(jìn)程留在同一個(gè)CPU上，因?yàn)閲?yán)格的優(yōu)先級(jí)關(guān)系使得進(jìn)程必須在出現(xiàn)不均衡時(shí)立刻被移動(dòng)。不過，一些特殊情況下進(jìn)程的遷移還是有一定選擇面的。比如優(yōu)先級(jí)相同的時(shí)候就可以盡量不做遷移、push_rt_task的時(shí)候可以選擇跟當(dāng)前CPU最為親近的CPU去遷移。
普通進(jìn)程的負(fù)載均衡
可以看出，實(shí)時(shí)進(jìn)程的負(fù)載均衡性能是不會(huì)太好的。為了滿足嚴(yán)格的優(yōu)先級(jí)關(guān)系，絲毫的不均衡都是不能容忍的。所以一旦top-N的平衡關(guān)系發(fā)生變化，內(nèi)核就必須即時(shí)完成負(fù)載均衡，形成新的top-N的平衡關(guān)系。這可能會(huì)使得每個(gè)CPU頻繁去競爭run_queue、進(jìn)程頻繁被遷移。
而普通進(jìn)程則并不要求嚴(yán)格的優(yōu)先級(jí)關(guān)系，可以容忍一定程度的不均衡。所以普通進(jìn)程的負(fù)載均衡可以不必在進(jìn)程發(fā)生變化時(shí)即時(shí)完成，而采用一些異步調(diào)整的策略。
普通進(jìn)程的負(fù)載均衡在以下情況下會(huì)被觸發(fā)：
1、當(dāng)前進(jìn)程離開TASK_RUNNING狀態(tài)（進(jìn)入睡眠或退出），而對(duì)應(yīng)的run_queue中已無進(jìn)程可用時(shí)。這時(shí)觸發(fā)負(fù)載均衡，試圖從別的run_queue中pull一個(gè)進(jìn)程過來運(yùn)行；
2、每隔一定的時(shí)間，啟動(dòng)負(fù)載均衡過程，試圖發(fā)現(xiàn)并解決系統(tǒng)中不均衡；
另外，對(duì)于調(diào)用exec的進(jìn)程，它的地址空間已經(jīng)完全重建了，當(dāng)前CPU上已經(jīng)不會(huì)再緩存對(duì)它有用的信息。這時(shí)內(nèi)核也會(huì)考慮負(fù)載均衡，為它們找一個(gè)合適的CPU。
那么，對(duì)于普通進(jìn)程來說，“均衡”到底意味著什么呢？
在單CPU環(huán)境下，處于TASK_RUNNING狀態(tài)的進(jìn)程會(huì)以其優(yōu)先級(jí)為權(quán)重，瓜分CPU時(shí)間。優(yōu)先級(jí)越高的進(jìn)程，權(quán)重越高，分得的CPU時(shí)間也就越多。在CFS調(diào)度（完全公平調(diào)度，針對(duì)普通進(jìn)程的調(diào)度程序）中，這里的權(quán)重被稱作load。假設(shè)某個(gè)進(jìn)程的load為m，所有處于TASK_RUNNING狀態(tài)的進(jìn)程的load之和為M，那么這個(gè)進(jìn)程所能分到的CPU時(shí)間是m/M。比如系統(tǒng)中有兩個(gè)TASK_RUNNING狀態(tài)的進(jìn)程，一個(gè)load為1、一個(gè)load為2，總的load是1+2=3。則它們分到的CPU時(shí)間分別是1/3和2/3。
推廣到SMP環(huán)境，假設(shè)有N個(gè)CPU，那么一個(gè)load為m的進(jìn)程所能分到的CPU時(shí)間應(yīng)該是N*m/M（如果不是，則要么這個(gè)進(jìn)程擠占了別的進(jìn)程的CPU時(shí)間、要么是被別的進(jìn)程擠占）。對(duì)于普通進(jìn)程來說，這就是所謂的“均衡”。
那么，如何讓進(jìn)程能夠分到N*m/M的CPU時(shí)間呢？其實(shí)，只需要把所有進(jìn)程的load平分到每一個(gè)run_queue上，使得每個(gè)run_queue的load（它上面的進(jìn)程的load之和）都等于M/N，這樣就好了。于是，每個(gè)run_queue的load就成了是否“均衡”的判斷依據(jù)。
下面看看load_balance里面做些什么。注意，不管load_balance是怎樣被觸發(fā)的，它總是在某個(gè)CPU上被執(zhí)行。而load_balance過程被實(shí)現(xiàn)得非常簡單，只需要從最繁忙（load最高）的run_queue中pull幾個(gè)進(jìn)程到當(dāng)前run_queue中（只pull，不push），使得當(dāng)前run_queue與最繁忙的run_queue得到均衡（使它們的load接近于所有run_queue的平均load），僅此而已。load_balance并不需要考慮所有run_queue全局的均衡，但是當(dāng)load_balance在各個(gè)CPU上分別得到運(yùn)行之后，全局的均衡也就實(shí)現(xiàn)了。這樣的實(shí)現(xiàn)極大程度減小了負(fù)載均衡的開銷。
load_balance的過程大致如下：
1、找出最繁忙的一個(gè)run_queue；
2、如果找到的run_queue比本地run_queue繁忙，且本地run_queue的繁忙程度低于平均水平，那么遷移幾個(gè)進(jìn)程過來，使兩個(gè)run_queue的load接近平均水平。反之則什么都不做；
在比較兩個(gè)run_queue繁忙程度的問題上，其實(shí)是很有講究的。這個(gè)地方很容易想當(dāng)然地理解為：把run_queue中所有進(jìn)程的load加起來，比較一下就OK了。而實(shí)際上，需要比較的往往并不是實(shí)時(shí)的load。
這就好比我們用top命令查看CPU占用率一樣，top命令默認(rèn)1秒刷新一次，每次刷新你將看到這1秒內(nèi)所有進(jìn)程各自對(duì)CPU的占用情況。這里的占用率是個(gè)統(tǒng)計(jì)值，假設(shè)有一個(gè)進(jìn)程在這1秒內(nèi)持續(xù)運(yùn)行了100毫秒，那么我們認(rèn)為它占用了10%的CPU。如果把1秒刷新一次改成1毫秒刷新一次呢？那么我們將有90%的機(jī)率看到這個(gè)進(jìn)程占用0%的CPU、10%的機(jī)率占用100%的CPU。而無論是0%、還是100%，都不是這個(gè)進(jìn)程真實(shí)的CPU占用率的體現(xiàn)。必須把一段時(shí)間以內(nèi)的CPU占用率綜合起來看，才能得到我們需要的那個(gè)值。
run_queue的load值也是這樣。有些進(jìn)程可能頻繁地在TASK_RUNNING和非TASK_RUNNING狀態(tài)之間變換，導(dǎo)致run_queue的load值不斷抖動(dòng)。光看某一時(shí)刻的load值，我們是體會(huì)不到run_queue的負(fù)載情況的，必須將一段時(shí)間內(nèi)的load值綜合起來看才行。于是，run_queue結(jié)構(gòu)中維護(hù)了一個(gè)保存load值的數(shù)組：
unsigned long cpu_load[CPU_LOAD_IDX_MAX] （目前CPU_LOAD_IDX_MAX值為5）
每個(gè)CPU上，每個(gè)tick的時(shí)鐘中斷會(huì)調(diào)用到update_cpu_load函數(shù)，來更新該CPU所對(duì)應(yīng)的run_queue的cpu_load值。這個(gè)函數(shù)值得羅列一下：
/* this_load就是run_queue實(shí)時(shí)的load值 */
unsigned long this_load = this_rq->load.weight;
for (i = 0, scale = 1; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
unsigned long old_load = this_rq->cpu_load[i];
unsigned long new_load = this_load;
/* 因?yàn)樽罱K結(jié)果是要除以scale的，這里相當(dāng)于上取整 */
if (new_load > old_load)
new_load += scale-1;
/* cpu_load[i] = old_load + (new_load - old_load) / 2^i */
this_rq->cpu_load[i] = (old_load*(scale-1) + new_load) >> i;
}
cpu_load[i] = old_load + (new_load – old_load) / 2^i。i值越大，cpu_load[i]受load的實(shí)時(shí)值的影響越小，代表著越長時(shí)間內(nèi)的平均負(fù)載情況。而cpu_load[0]就是實(shí)時(shí)的load。
盡管我們需要的是一段時(shí)間內(nèi)的綜合的負(fù)載情況，但是，為什么不是保存一個(gè)最合適的統(tǒng)計(jì)值，而要保存這么多的值呢？這是為了便于在不同場景下選擇不同的load。如果希望進(jìn)行進(jìn)程遷移，那么應(yīng)該選擇較小的i值，因?yàn)榇藭r(shí)的cpu_load[i]抖動(dòng)比較大，容易發(fā)現(xiàn)不均衡；反之，如果希望保持穩(wěn)定，那么應(yīng)該選擇較大的i值。
那么，什么時(shí)候傾向于進(jìn)行遷移、什么時(shí)候又傾向于保持穩(wěn)定呢？這要從兩個(gè)維度來看：
第一個(gè)維度，是當(dāng)前CPU的狀態(tài)。這里會(huì)考慮三種CPU狀態(tài)：
1、CPU剛進(jìn)入IDLE（比如說CPU上唯一的TASK_RUNNING狀態(tài)的進(jìn)程睡眠去了），這時(shí)候是很渴望馬上弄一個(gè)進(jìn)程過來運(yùn)行的，應(yīng)該選擇較小的i值；
2、CPU處于IDLE，這時(shí)候還是很渴望弄一個(gè)進(jìn)程過來運(yùn)行的，但是可能已經(jīng)嘗試過幾次都無果了，故選擇略大一點(diǎn)的i值；
3、CPU非IDLE，有進(jìn)程正在運(yùn)行，這時(shí)候就不太希望進(jìn)程遷移了，會(huì)選擇較大的i值；
第二個(gè)維度，是CPU的親緣性。離得越近的CPU，進(jìn)程遷移所造成的緩存失效的影響越小，應(yīng)該選擇較小的i值。比如兩個(gè)CPU是同一物理CPU的同一核心通過SMT（超線程技術(shù)）虛擬出來的，那么它們的緩存大部分是共享的。進(jìn)程在它們之間遷移代價(jià)較小。反之則應(yīng)該選擇較大的i值。（后面將會(huì)看到linux通過調(diào)度域來管理CPU的親緣性。）
至于具體的i的取值，就是具體策略的問題了，應(yīng)該是根據(jù)經(jīng)驗(yàn)或?qū)嶒?yàn)結(jié)果得出來的，這里就不贅述了。
調(diào)度域
前面已經(jīng)多次提到了調(diào)度域（sched_domain）。在復(fù)雜的SMP系統(tǒng)中，為了描述CPU與CPU之間的親緣關(guān)系，引入了調(diào)度域。
兩個(gè)CPU之間的親緣關(guān)系主要有以下幾種：
1、超線程。超線程CPU是一個(gè)可以“同時(shí)”執(zhí)行幾個(gè)線程的CPU。就像操作系統(tǒng)通過進(jìn)程調(diào)度能夠讓多個(gè)進(jìn)程“同時(shí)”在一個(gè)CPU上運(yùn)行一樣，超線程CPU也是通過這樣的分時(shí)復(fù)用技術(shù)來實(shí)現(xiàn)幾個(gè)線程的“同時(shí)”執(zhí)行的。這樣做之所以能夠提高執(zhí)行效率，是因?yàn)镃PU的速度比內(nèi)存速度快很多（一個(gè)數(shù)量級(jí)以上）。如果cache不能命中，CPU在等待內(nèi)存的時(shí)間內(nèi)將無事可做，可以切換到其他線程去執(zhí)行。這樣的多個(gè)線程對(duì)于操作系統(tǒng)來說就相當(dāng)于多個(gè)CPU，它們共享著大部分的cache，非常之親近；
2、同一物理CPU上的不同核心?，F(xiàn)在的多核CPU大多屬于這種情況，每個(gè)CPU核心都有獨(dú)立執(zhí)行程序的能力，而它們之間也會(huì)共享著一些cache；
3、同一NUMA結(jié)點(diǎn)上的CPU；
4、不同NUMA結(jié)點(diǎn)上的CPU；
在NUMA（非一致性內(nèi)存體系）中，CPU和RAM以“結(jié)點(diǎn)”為單位分組。當(dāng)CPU訪問與它同在一個(gè)結(jié)點(diǎn)的“本地”RAM芯片時(shí)，幾乎不會(huì)有競爭，訪問速度通常很快。相反的，CPU訪問它所屬結(jié)點(diǎn)之外的“遠(yuǎn)程”RAM芯片就會(huì)非常慢。
（調(diào)度域可以支持非常復(fù)雜的硬件系統(tǒng)，但是我們通常遇到的SMP一般是：一個(gè)物理CPU包含N個(gè)核心。這種情況下，所有CPU之間的親緣性都是相同的，引入調(diào)度域的意義其實(shí)并不大。）
進(jìn)程在兩個(gè)很親近的CPU之間遷移，代價(jià)較小，因?yàn)檫€有一部分cache可以繼續(xù)使用；在屬于同一NUMA結(jié)點(diǎn)上的兩個(gè)CPU之間遷移，雖然cache會(huì)全部丟失，但是好歹內(nèi)存訪問的速度是相同的；如果進(jìn)程在屬于不同NUMA結(jié)點(diǎn)的兩個(gè)CPU之間遷移，那么這個(gè)進(jìn)程將在新NUMA結(jié)點(diǎn)的CPU上被執(zhí)行，卻還是要訪問舊NUMA結(jié)點(diǎn)的內(nèi)存（進(jìn)程可以遷移，內(nèi)存卻沒法遷移），速度就要慢很多了。
通過調(diào)度域的描述，內(nèi)核就可以知道CPU與CPU的親緣關(guān)系。對(duì)于關(guān)系遠(yuǎn)的CPU，盡量少在它們之間遷移進(jìn)程；而對(duì)于關(guān)系近的CPU，則可以容忍較多一些的進(jìn)程遷移。
對(duì)于實(shí)時(shí)進(jìn)程的負(fù)載均衡，調(diào)度域的作用比較小，主要是在push_rt_task將當(dāng)前run_queue中的實(shí)時(shí)進(jìn)程推到其他run_queue時(shí)，如果有多個(gè)run_queue可以接收實(shí)時(shí)進(jìn)程，則按照調(diào)度域的描述，選擇親緣性最高的那個(gè)CPU對(duì)應(yīng)的run_queue（如果這樣的CPU有多個(gè)，那么約定選擇編號(hào)最小那一個(gè)）。所以，下面著重討論普通進(jìn)程的負(fù)載均衡。
首先，調(diào)度域具體是如何描述CPU之間的親緣關(guān)系的呢？假設(shè)系統(tǒng)中有兩個(gè)物理CPU、每個(gè)物理CPU有兩個(gè)核心、每個(gè)核心又通過超線程技術(shù)虛擬出兩個(gè)CPU，則調(diào)度域的結(jié)構(gòu)如下：
1、一個(gè)調(diào)度域是若干CPU的集合，這些CPU都是滿足一定的親緣關(guān)系的（比如至少是屬于同一NUMA結(jié)點(diǎn)的）；
2、調(diào)度域之間存在層次關(guān)系，一個(gè)調(diào)度域可能包括多個(gè)子調(diào)度域，每個(gè)子調(diào)度域包含了父調(diào)度域的一個(gè)CPU子集，并且子調(diào)度域中的CPU滿足比父調(diào)度域更嚴(yán)格的親緣關(guān)系（比如父調(diào)度域中的CPU至少是屬于同一NUMA結(jié)點(diǎn)的，子調(diào)度域中的CPU至少是屬于同一物理CPU的）；
3、每個(gè)CPU分別具有其對(duì)應(yīng)的一組sched_domain結(jié)構(gòu)，這些調(diào)度域處于不同層次，但是都包含了這個(gè)CPU；
4、每個(gè)調(diào)度域被依次劃分成多個(gè)組，每個(gè)組代表調(diào)度域的一個(gè)CPU子集；
5、最低層次的調(diào)度域包含了親緣性最近的幾個(gè)CPU、而最低層次的調(diào)度組則只包含一個(gè)CPU；
對(duì)于普通進(jìn)程的負(fù)載均衡來說，在一個(gè)CPU上，每次觸發(fā)load_balance總是在某個(gè)sched_domain上進(jìn)行的。低層次的sched_domain包含的CPU有著較高的親緣性，將以較高的頻率被觸發(fā)load_balance；而高層次的sched_domain包含的CPU有著較低的親緣性，將以較低的頻率被觸發(fā)load_balance。為了實(shí)現(xiàn)這個(gè)，sched_domain里面記錄著每次load_balance的時(shí)間間隔，以及下次觸發(fā)load_balance的時(shí)間。
前面討論過，普通進(jìn)程的load_balance第一步是需要找出一個(gè)最繁忙的CPU，實(shí)際上這是通過兩個(gè)步驟來實(shí)現(xiàn)的：
1、找出sched_domain下最繁忙的一個(gè)sched_group（組內(nèi)的CPU對(duì)應(yīng)的run_queue的load之和最高）；
2、從該sched_group下找出最繁忙的CPU；
可見，load_balance實(shí)際上是實(shí)現(xiàn)了對(duì)應(yīng)sched_domain下的sched_group之間的平衡。較高層次的sched_domain包含了很多CPU，但是在這個(gè)sched_domain上的load_balance并不直接解決這些CPU之間的負(fù)載均衡，而只是解決sched_group之間的平衡（這又是load_balance的一大簡化）。而最底層的sched_group是跟CPU一一對(duì)應(yīng)的，所以最終還是實(shí)現(xiàn)了CPU之間的平衡。
其他問題
CPU親和力
linux下的進(jìn)程可以通過sched_setaffinity系統(tǒng)調(diào)用設(shè)置進(jìn)程親和力，限定進(jìn)程只能在某些特定的CPU上運(yùn)行。負(fù)載均衡必須考慮遵守這個(gè)限制（前面也多次提到）。
遷移線程
前面說到，在普通進(jìn)程的load_balance過程中，如果負(fù)載不均衡，當(dāng)前CPU會(huì)試圖從最繁忙的run_queue中pull幾個(gè)進(jìn)程到自己的run_queue來。
但是如果進(jìn)程遷移失敗呢？當(dāng)失敗達(dá)到一定次數(shù)的時(shí)候，內(nèi)核會(huì)試圖讓目標(biāo)CPU主動(dòng)push幾個(gè)進(jìn)程過來，這個(gè)過程叫做active_load_balance。這里的“一定次數(shù)”也是跟調(diào)度域的層次有關(guān)的，越低層次，則“一定次數(shù)”的值越小，越容易觸發(fā)active_load_balance。
這里需要先解釋一下，為什么load_balance的過程中遷移進(jìn)程會(huì)失敗呢？最繁忙run_queue中的進(jìn)程，如果符合以下限制，則不能遷移：
1、進(jìn)程的CPU親和力限制了它不能在當(dāng)前CPU上運(yùn)行；
2、進(jìn)程正在目標(biāo)CPU上運(yùn)行（正在運(yùn)行的進(jìn)程顯然是不能直接遷移的）；
（此外，如果進(jìn)程在目標(biāo)CPU上前一次運(yùn)行的時(shí)間距離當(dāng)前時(shí)間很小，那么該進(jìn)程被cache的數(shù)據(jù)可能還有很多未被淘汰，則稱該進(jìn)程的cache還是熱的。對(duì)于cache熱的進(jìn)程，也盡量不要遷移它們。但是在滿足觸發(fā)active_load_balance的條件之前，還是會(huì)先試圖遷移它們。）
對(duì)于CPU親和力有限制的進(jìn)程（限制1），即使active_load_balance被觸發(fā)，目標(biāo)CPU也不能把它push過來。所以，實(shí)際上，觸發(fā)active_load_balance的目的是要嘗試把當(dāng)時(shí)正在目標(biāo)CPU上運(yùn)行的那個(gè)進(jìn)程弄過來（針對(duì)限制2）。
在每個(gè)CPU上都會(huì)運(yùn)行一個(gè)遷移線程，active_load_balance要做的事情就是喚醒目標(biāo)CPU上的遷移線程，讓它執(zhí)行active_load_balance的回調(diào)函數(shù)。在這個(gè)回調(diào)函數(shù)中嘗試把原先因?yàn)檎谶\(yùn)行而未能遷移的那個(gè)進(jìn)程push過來。為什么load_balance的時(shí)候不能遷移，active_load_balance的回調(diào)函數(shù)中就可以了呢？因?yàn)檫@個(gè)回調(diào)函數(shù)是運(yùn)行在目標(biāo)CPU的遷移線程上的。一個(gè)CPU在同一時(shí)刻只能運(yùn)行一個(gè)進(jìn)程，既然這個(gè)遷移線程正在運(yùn)行，那么期望被遷移的那個(gè)進(jìn)程肯定不是正在被執(zhí)行的，限制2被打破。
當(dāng)然，在active_load_balance被觸發(fā)，到回調(diào)函數(shù)在目標(biāo)CPU上被執(zhí)行之間，目標(biāo)CPU上的TASK_RUNNING狀態(tài)的進(jìn)程可能發(fā)生一些變化，所以回調(diào)函數(shù)發(fā)起遷移的進(jìn)程未必就只有之前因?yàn)橄拗?而未能被遷移的那一個(gè)，可能更多，也可能一個(gè)沒有。
工商網(wǎng)監(jiān)
評(píng)論