在SMP（對稱多處理器）環境下，每個CPU對應一個run_queue（可執行隊列）。如果一個進程處于TASK_RUNNING狀態（可執行狀態），則它會被加入到其中一個run_queue（且同一時刻僅會被加入到一個run_queue），以便讓調度程序安排它在這個run_queue對應的CPU上面運行。

一個CPU對應一個run_queue這樣的設計，其好處是：

1、一個持續處于TASK_RUNNING狀態的進程總是趨于在同一個CPU上面運行（其間，這個進程可能被搶占、然后又被調度），這有利于進程的數據被CPU所緩存，提高運行效率；
2、各個CPU上的調度程序只訪問自己的run_queue，避免了競爭；

然而，這樣的設計也可能使得各個run_queue里面的進程不均衡，造成“一些CPU閑著、一些CPU忙不過來”混亂局面。為了解決這個問題，load_balance（負載均衡）就登場了。

load_balance所需要做的事情就是，在一定的時機，通過將進程從一個run_queue遷移到另一個run_queue，來保持CPU之間的負載均衡。

這里的“均衡”二字如何定義？load_balance又具體要做哪些事情呢？對于不同調度策略（實時進程 OR 普通進程），有著不同的邏輯，需要分開來看。

實時進程的負載均衡

實時進程的調度是嚴格按照優先級來進行的。在單CPU環境下，CPU上運行著的總是優先級最高的進程，直到這個進程離開TASK_RUNNING狀態，新任的“優先級最高的進程”才開始得到運行。直到所有實時進程都離開TASK_RUNNING狀態，其他普通進程才有機會得到運行。（暫時忽略sched_rt_runtime_us和sched_rt_period_us的影響。）

推廣到SMP環境，假設有N個CPU，N個CPU上分別運行著的也必須是優先級最高的top-N個進程。如果實時進程不足N個，那么剩下的CPU才分給普通進程去使用。對于實時進程來說，這就是所謂的“均衡”。

實時進程的優先級關系是很嚴格的，當優先級最高的top-N個進程發生變化時，內核必須馬上響應：

1、如果這top-N個進程當中，有一個離開TASK_RUNNING狀態、或因為優先級被調低而退出top-N集團，則原先處于(N+1)位的那個進程將進入top-N。內核需要遍歷所有的run_queue，把這個新任的top-N進程找出來，然后立馬讓它開始運行；
2、反之，如果一個top-N之外的實時進程的優先級被調高，以至于擠占了原先處于第N位的進程，則內核需要遍歷所有的run_queue，把這個被擠出top-N的進程找出來，將它正在占用的CPU讓給新進top-N的那個進程去運行；

在這幾種情況下，新進入top-N的進程和退出top-N的進程可能原本并不在同一個CPU上，那么在它得到運行之前，內核會先將其遷移到退出top-N的進程所在的CPU上。

具體來說，內核通過pull_rt_task和push_rt_task兩個函數來完成實時進程的遷移：

pull_rt_task – 把其他CPU的run_queue中的實時進程pull過來，放到當前CPU的run_queue中。被pull過來的實時進程要滿足以下條件：

1、進程是其所在的run_queue中優先級第二高的（優先級最高的進程必定正在運行，不需要移動）；
2、進程的優先級比當前run_queue中最高優先級的進程還要高；
3、進程允許在當前CPU上運行（沒有親和性限制）；

該函數會在以下時間點被調用：

1、發生調度之前，如果prev進程（將要被替換下去的進程）是實時進程，且優先級高于當前run_queue中優先級最高的實時進程（這說明prev進程已經離開TASK_RUNNING狀態了，否則它不會讓位于比它優先級低的進程）；
2、正在運行的實時進程優先級被調低時（比如通過sched_setparam系統調用）；
3、正在運行的實時進程變成普通進程時（比如通過sched_setscheduler系統調用）；

push_rt_task – 把當前run_queue中多余的實時進程推給其他run_queue。需要滿足以下條件：

1、每次push一個進程，這個進程的優先級在當前run_queue中是第二高的（優先級最高的進程必定正在運行，不需要移動）；
2、目標run_queue上正在運行的不是實時進程（是普通進程），或者是top-N中優先級最低的實時進程，且優先級低于被push的進程；
3、被push的進程允許在目標CPU上運行（沒有親和性限制）；
4、滿足條件的目標run_queue可能存在多個（可能多個CPU上都沒有實時進程在運行），應該選擇與當前CPU最具親緣性的一組CPU中的第一個CPU所對應的run_queue作為push的目標（順著sched_domain–調度域–逐步往上，找到第一個包含目標CPU的sched_domain。見后面關于sched_domain的描述）；

該函數會在以下時間點被調用：

1、非正在運行的普通進程變成實時進程時（比如通過sched_setscheduler系統調用）；
2、發生調度之后（這時候可能有一個實時進程被更高優先級的實時進程搶占了）；
3、實時進程被喚醒之后，如果不能馬上在當前CPU上運行（它不是當前CPU上優先級最高的進程）；

看起來，實時進程的負載均衡對于每個CPU一個run_queue這種模式似乎有些別扭，每次需要選擇一個實時進程，總是需要遍歷所有run_queue，在尚未能得到運行的實時進程之中找到優先級最高的那一個。其實，如果所有CPU共用同一個run_queue，就沒有這么多的煩惱了。為什么不這樣做呢？

1、在CPU對run_queue的競爭方面，“每個CPU去競爭每一個run_queue”比“每個CPU去競爭一個總的run_queue”略微好一些，因為競爭的粒度更小了；
2、在進程的移動方面，每個CPU一個run_queue這種模式其實也不能很好的把進程留在同一個CPU上，因為嚴格的優先級關系使得進程必須在出現不均衡時立刻被移動。不過，一些特殊情況下進程的遷移還是有一定選擇面的。比如優先級相同的時候就可以盡量不做遷移、push_rt_task的時候可以選擇跟當前CPU最為親近的CPU去遷移。

普通進程的負載均衡

可以看出，實時進程的負載均衡性能是不會太好的。為了滿足嚴格的優先級關系，絲毫的不均衡都是不能容忍的。所以一旦top-N的平衡關系發生變化，內核就必須即時完成負載均衡，形成新的top-N的平衡關系。這可能會使得每個CPU頻繁去競爭run_queue、進程頻繁被遷移。

而普通進程則并不要求嚴格的優先級關系，可以容忍一定程度的不均衡。所以普通進程的負載均衡可以不必在進程發生變化時即時完成，而采用一些異步調整的策略。

普通進程的負載均衡在以下情況下會被觸發：

1、當前進程離開TASK_RUNNING狀態（進入睡眠或退出），而對應的run_queue中已無進程可用時。這時觸發負載均衡，試圖從別的run_queue中pull一個進程過來運行；
2、每隔一定的時間，啟動負載均衡過程，試圖發現并解決系統中不均衡；
另外，對于調用exec的進程，它的地址空間已經完全重建了，當前CPU上已經不會再緩存對它有用的信息。這時內核也會考慮負載均衡，為它們找一個合適的CPU。

那么，對于普通進程來說，“均衡”到底意味著什么呢？

在單CPU環境下，處于TASK_RUNNING狀態的進程會以其優先級為權重，瓜分CPU時間。優先級越高的進程，權重越高，分得的CPU時間也就越多。在CFS調度（完全公平調度，針對普通進程的調度程序）中，這里的權重被稱作load。假設某個進程的load為m，所有處于TASK_RUNNING狀態的進程的load之和為M，那么這個進程所能分到的CPU時間是m/M。比如系統中有兩個TASK_RUNNING狀態的進程，一個load為1、一個load為2，總的load是1+2=3。則它們分到的CPU時間分別是1/3和2/3。

推廣到SMP環境，假設有N個CPU，那么一個load為m的進程所能分到的CPU時間應該是N*m/M（如果不是，則要么這個進程擠占了別的進程的CPU時間、要么是被別的進程擠占）。對于普通進程來說，這就是所謂的“均衡”。

那么，如何讓進程能夠分到N*m/M的CPU時間呢？其實，只需要把所有進程的load平分到每一個run_queue上，使得每個run_queue的load（它上面的進程的load之和）都等于M/N，這樣就好了。于是，每個run_queue的load就成了是否“均衡”的判斷依據。

下面看看load_balance里面做些什么。注意，不管load_balance是怎樣被觸發的，它總是在某個CPU上被執行。而load_balance過程被實現得非常簡單，只需要從最繁忙（load最高）的run_queue中pull幾個進程到當前run_queue中（只pull，不push），使得當前run_queue與最繁忙的run_queue得到均衡（使它們的load接近于所有run_queue的平均load），僅此而已。load_balance并不需要考慮所有run_queue全局的均衡，但是當load_balance在各個CPU上分別得到運行之后，全局的均衡也就實現了。這樣的實現極大程度減小了負載均衡的開銷。

load_balance的過程大致如下：

1、找出最繁忙的一個run_queue；
2、如果找到的run_queue比本地run_queue繁忙，且本地run_queue的繁忙程度低于平均水平，那么遷移幾個進程過來，使兩個run_queue的load接近平均水平。反之則什么都不做；

在比較兩個run_queue繁忙程度的問題上，其實是很有講究的。這個地方很容易想當然地理解為：把run_queue中所有進程的load加起來，比較一下就OK了。而實際上，需要比較的往往并不是實時的load。

這就好比我們用top命令查看CPU占用率一樣，top命令默認1秒刷新一次，每次刷新你將看到這1秒內所有進程各自對CPU的占用情況。這里的占用率是個統計值，假設有一個進程在這1秒內持續運行了100毫秒，那么我們認為它占用了10%的CPU。如果把1秒刷新一次改成1毫秒刷新一次呢？那么我們將有90%的機率看到這個進程占用0%的CPU、10%的機率占用100%的CPU。而無論是0%、還是100%，都不是這個進程真實的CPU占用率的體現。必須把一段時間以內的CPU占用率綜合起來看，才能得到我們需要的那個值。

run_queue的load值也是這樣。有些進程可能頻繁地在TASK_RUNNING和非TASK_RUNNING狀態之間變換，導致run_queue的load值不斷抖動。光看某一時刻的load值，我們是體會不到run_queue的負載情況的，必須將一段時間內的load值綜合起來看才行。于是，run_queue結構中維護了一個保存load值的數組：

unsigned long cpu_load[CPU_LOAD_IDX_MAX] （目前CPU_LOAD_IDX_MAX值為5）
每個CPU上，每個tick的時鐘中斷會調用到update_cpu_load函數，來更新該CPU所對應的run_queue的cpu_load值。這個函數值得羅列一下：

/* this_load就是run_queue實時的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;

/* 因為最終結果是要除以scale的，這里相當于上取整 */

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的實時值的影響越小，代表著越長時間內的平均負載情況。而cpu_load[0]就是實時的load。

盡管我們需要的是一段時間內的綜合的負載情況，但是，為什么不是保存一個最合適的統計值，而要保存這么多的值呢？這是為了便于在不同場景下選擇不同的load。如果希望進行進程遷移，那么應該選擇較小的i值，因為此時的cpu_load[i]抖動比較大，容易發現不均衡；反之，如果希望保持穩定，那么應該選擇較大的i值。

那么，什么時候傾向于進行遷移、什么時候又傾向于保持穩定呢？這要從兩個維度來看：

第一個維度，是當前CPU的狀態。這里會考慮三種CPU狀態：

1、CPU剛進入IDLE（比如說CPU上唯一的TASK_RUNNING狀態的進程睡眠去了），這時候是很渴望馬上弄一個進程過來運行的，應該選擇較小的i值；
2、CPU處于IDLE，這時候還是很渴望弄一個進程過來運行的，但是可能已經嘗試過幾次都無果了，故選擇略大一點的i值；
3、CPU非IDLE，有進程正在運行，這時候就不太希望進程遷移了，會選擇較大的i值；

第二個維度，是CPU的親緣性。離得越近的CPU，進程遷移所造成的緩存失效的影響越小，應該選擇較小的i值。比如兩個CPU是同一物理CPU的同一核心通過SMT（超線程技術）虛擬出來的，那么它們的緩存大部分是共享的。進程在它們之間遷移代價較小。反之則應該選擇較大的i值。（后面將會看到linux通過調度域來管理CPU的親緣性。）

至于具體的i的取值，就是具體策略的問題了，應該是根據經驗或實驗結果得出來的，這里就不贅述了。

調度域

前面已經多次提到了調度域（sched_domain）。在復雜的SMP系統中，為了描述CPU與CPU之間的親緣關系，引入了調度域。

兩個CPU之間的親緣關系主要有以下幾種：

1、超線程。超線程CPU是一個可以“同時”執行幾個線程的CPU。就像操作系統通過進程調度能夠讓多個進程“同時”在一個CPU上運行一樣，超線程CPU也是通過這樣的分時復用技術來實現幾個線程的“同時”執行的。這樣做之所以能夠提高執行效率，是因為CPU的速度比內存速度快很多（一個數量級以上）。如果cache不能命中，CPU在等待內存的時間內將無事可做，可以切換到其他線程去執行。這樣的多個線程對于操作系統來說就相當于多個CPU，它們共享著大部分的cache，非常之親近；
2、同一物理CPU上的不同核心。現在的多核CPU大多屬于這種情況，每個CPU核心都有獨立執行程序的能力，而它們之間也會共享著一些cache；
3、同一NUMA結點上的CPU；
4、不同NUMA結點上的CPU；

在NUMA（非一致性內存體系）中，CPU和RAM以“結點”為單位分組。當CPU訪問與它同在一個結點的“本地”RAM芯片時，幾乎不會有競爭，訪問速度通常很快。相反的，CPU訪問它所屬結點之外的“遠程”RAM芯片就會非常慢。

（調度域可以支持非常復雜的硬件系統，但是我們通常遇到的SMP一般是：一個物理CPU包含N個核心。這種情況下，所有CPU之間的親緣性都是相同的，引入調度域的意義其實并不大。）

進程在兩個很親近的CPU之間遷移，代價較小，因為還有一部分cache可以繼續使用；在屬于同一NUMA結點上的兩個CPU之間遷移，雖然cache會全部丟失，但是好歹內存訪問的速度是相同的；如果進程在屬于不同NUMA結點的兩個CPU之間遷移，那么這個進程將在新NUMA結點的CPU上被執行，卻還是要訪問舊NUMA結點的內存（進程可以遷移，內存卻沒法遷移），速度就要慢很多了。

通過調度域的描述，內核就可以知道CPU與CPU的親緣關系。對于關系遠的CPU，盡量少在它們之間遷移進程；而對于關系近的CPU，則可以容忍較多一些的進程遷移。

對于實時進程的負載均衡，調度域的作用比較小，主要是在push_rt_task將當前run_queue中的實時進程推到其他run_queue時，如果有多個run_queue可以接收實時進程，則按照調度域的描述，選擇親緣性最高的那個CPU對應的run_queue（如果這樣的CPU有多個，那么約定選擇編號最小那一個）。所以，下面著重討論普通進程的負載均衡。

首先，調度域具體是如何描述CPU之間的親緣關系的呢？假設系統中有兩個物理CPU、每個物理CPU有兩個核心、每個核心又通過超線程技術虛擬出兩個CPU，則調度域的結構如下：

1、一個調度域是若干CPU的集合，這些CPU都是滿足一定的親緣關系的（比如至少是屬于同一NUMA結點的）；
2、調度域之間存在層次關系，一個調度域可能包括多個子調度域，每個子調度域包含了父調度域的一個CPU子集，并且子調度域中的CPU滿足比父調度域更嚴格的親緣關系（比如父調度域中的CPU至少是屬于同一NUMA結點的，子調度域中的CPU至少是屬于同一物理CPU的）；
3、每個CPU分別具有其對應的一組sched_domain結構，這些調度域處于不同層次，但是都包含了這個CPU；
4、每個調度域被依次劃分成多個組，每個組代表調度域的一個CPU子集；
5、最低層次的調度域包含了親緣性最近的幾個CPU、而最低層次的調度組則只包含一個CPU；

對于普通進程的負載均衡來說，在一個CPU上，每次觸發load_balance總是在某個sched_domain上進行的。低層次的sched_domain包含的CPU有著較高的親緣性，將以較高的頻率被觸發load_balance；而高層次的sched_domain包含的CPU有著較低的親緣性，將以較低的頻率被觸發load_balance。為了實現這個，sched_domain里面記錄著每次load_balance的時間間隔，以及下次觸發load_balance的時間。

前面討論過，普通進程的load_balance第一步是需要找出一個最繁忙的CPU，實際上這是通過兩個步驟來實現的：

1、找出sched_domain下最繁忙的一個sched_group（組內的CPU對應的run_queue的load之和最高）；
2、從該sched_group下找出最繁忙的CPU；

可見，load_balance實際上是實現了對應sched_domain下的sched_group之間的平衡。較高層次的sched_domain包含了很多CPU，但是在這個sched_domain上的load_balance并不直接解決這些CPU之間的負載均衡，而只是解決sched_group之間的平衡（這又是load_balance的一大簡化）。而最底層的sched_group是跟CPU一一對應的，所以最終還是實現了CPU之間的平衡。

其他問題

CPU親和力

linux下的進程可以通過sched_setaffinity系統調用設置進程親和力，限定進程只能在某些特定的CPU上運行。負載均衡必須考慮遵守這個限制（前面也多次提到）。

遷移線程

前面說到，在普通進程的load_balance過程中，如果負載不均衡，當前CPU會試圖從最繁忙的run_queue中pull幾個進程到自己的run_queue來。

但是如果進程遷移失敗呢？當失敗達到一定次數的時候，內核會試圖讓目標CPU主動push幾個進程過來，這個過程叫做active_load_balance。這里的“一定次數”也是跟調度域的層次有關的，越低層次，則“一定次數”的值越小，越容易觸發active_load_balance。

這里需要先解釋一下，為什么load_balance的過程中遷移進程會失敗呢？最繁忙run_queue中的進程，如果符合以下限制，則不能遷移：

1、進程的CPU親和力限制了它不能在當前CPU上運行；
2、進程正在目標CPU上運行（正在運行的進程顯然是不能直接遷移的）；

（此外，如果進程在目標CPU上前一次運行的時間距離當前時間很小，那么該進程被cache的數據可能還有很多未被淘汰，則稱該進程的cache還是熱的。對于cache熱的進程，也盡量不要遷移它們。但是在滿足觸發active_load_balance的條件之前，還是會先試圖遷移它們。）

對于CPU親和力有限制的進程（限制1），即使active_load_balance被觸發，目標CPU也不能把它push過來。所以，實際上，觸發active_load_balance的目的是要嘗試把當時正在目標CPU上運行的那個進程弄過來（針對限制2）。

在每個CPU上都會運行一個遷移線程，active_load_balance要做的事情就是喚醒目標CPU上的遷移線程，讓它執行active_load_balance的回調函數。在這個回調函數中嘗試把原先因為正在運行而未能遷移的那個進程push過來。為什么load_balance的時候不能遷移，active_load_balance的回調函數中就可以了呢？因為這個回調函數是運行在目標CPU的遷移線程上的。一個CPU在同一時刻只能運行一個進程，既然這個遷移線程正在運行，那么期望被遷移的那個進程肯定不是正在被執行的，限制2被打破。

當然，在active_load_balance被觸發，到回調函數在目標CPU上被執行之間，目標CPU上的TASK_RUNNING狀態的進程可能發生一些變化，所以回調函數發起遷移的進程未必就只有之前因為限制2而未能被遷移的那一個，可能更多，也可能一個沒有。