需求
在《Linux進程調度淺析》 一文中提到，在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的影響，見《linux組調度淺析》。）
推廣到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而未能被遷移的那一個，可能更多，也可能一個沒有。
原文：http://hi.baidu.com/_kouu/item/479891211a84e3c9a5275ad9