1.確定每個cpu核心的負載均衡；
2.在cpu和cache以及記憶體布局的影響下權重執行1。
1.盡量不執行程序遷移，以確定cache的熱度；
2.除非各個cpu的負載已經嚴重失衡，執行負載均衡
這個道理看似簡單，然而如果對于一個大型的綜合系統，要想設計一個适用于各種情況的負載均衡體系，卻不是很簡單。Linux核心的負載均衡設計的相當完美。對于負載均衡，可以分為以下幾種情況：
以系統複雜度為核心的分類 ：
這種情況下，需要随時保持各cpu上運作的程序數量的均衡
這種情況下，進行負載均衡會影響處理器的cache使用率，負載均衡帶來的效益會被cache重新整理的開銷抵消掉一部分或大部分。
這種情況下，情況二是要考慮的，然而對于同一處理器的不同核心之間由于存在共享的二級cache，多個核心之間的負載均衡抵消掉的cache使用率收益遠遠小于不同處理器之間的負載均衡作同樣的事情。
由于超線程使用同一套計算資源，且共享cache，是以其上的負載均衡幾乎不會影響cache使用率。然而如果超線程核的排程算法以及作業系統的排程算法設計的不好，造成一個作業系統線程長期使用超線程核，也會造成上一個切換出的作業系統線程的cache被擠出去，遺憾的是，一般情況下我們無力優化作業系統的排程算法，并且無法接觸cpu的smt排程算法。
這種情況下，負載均衡對cache使用率的影響顯然是不可避免的，同時還會影響通路記憶體的時間，也就是記憶體的利用效率，這就是NUMA的情況...
以上五種情況基本就是一個複雜系統從最簡單到最複雜的排列，如果我們不以整個系統為核心，而以處理器為核心， 應該是以下四種排列情況：
以處理器為核心的分類：
這是我們熟知的SMT情況
這是我們熟知的多核處理器情況
這是我們熟知的SMP情況
這是我們熟知的NUMA情況，記憶體對于不同的處理器來講，其通路效率是不同的。
程序在不同cpu之間的遷移和cache使用率總的來說是對立的，并且根據源cpu和目的cpu之間的關系不同這種對立的程度 也不同。 由于程序遷移是基于cpu的，而cpu最小級别的就是超線程處理器的一個smt核，次小的一級就是一個多核cpu的核，然後就是一個實體cpu封裝，再往後就是cpu陣列，根據這些cpu級别的不同，Linux将所有同一級别的cpu歸為一個“排程組”，然後将同一級别的所有的排程組組成一個“排程域”， 負載均衡首先在排程域的各個排程組之間進行，然後再在最低一級的cpu上進行，注意負載均衡是基于最小一級的cpu的。整個架構如下圖所示：
遷移一個程序的代價就是削弱cache的作用。 是以，隻要在擁有cache的處理器之間遷移程序，勢必會付出這個代價，是以在設計中必然需要一種“阻力”來盡量不做程序遷移，除非萬不得已！這種“阻力”就是負載均衡原則2中的“權重”系數。
為防止處理器負載曲線的上下颠簸，用曆史值來權重目前值是一個不錯的方式 ，也就是說，所謂的負載曲線不再基于時間點 ，而是基于時間段 。 然而曆史負載值對總負載的影響肯定沒有目前的負載值對總負載的影響大，一個時間點的負載值随着時間的流逝，對負載均衡時總負載的計算的影響應該逐漸減小。是以Linux的負載均衡器設計了一個公式專門用于負載均衡過程中對cpu總負載的計算。該公式如下：
其中delta是一個可變的系數，在linux 2.6.18中設定了3個delta，分别為1，2，4，當然還可以更多，比如高一些版本的核心中delta的取值有CPU_LOAD_IDX_MAX種，CPU_LOAD_IDX_MAX由宏來定義。比如當delta為2的時候，上述公式成為：
total_load=(previous_load+nowa_load)/2
相當于曆史值占據整個load值一半，而目前值占據另一半。
讓曆史值參與計算總負載解決了同一條負載曲線颠簸的問題，但是在負載均衡時是比較兩條負載曲線同一時間點上的值 ，當二者相差大于一個閥值時，實施程序遷移。 為了做到“盡量不做程序遷移”這個原則，必須将兩條負載曲線的波峰和波谷平滑掉。 如果程序遷移源cpu的負載曲線此時正好在波峰，目的cpu的負載曲線此時正好在波谷，此時就需要将波峰和波谷削平，讓源cpu的負載下降a，而目的cpu的負載上升b，這樣它們之間的負載差就會減少a+b，這個“阻力”足以阻止很多的程序遷移操作。
負載均衡平滑操作時需要兩個值，即上述的a和b，這兩個值決定了削平波峰/波谷的幅度，幅度越大，阻礙負載均衡的“力度”也就越大，反之“力度”也就越小。根據參與負載均衡的cpu的層次級别的不同，這種幅度應該不同，幸運的是，可以根據調整“負載均衡過程中對cpu總負載的計算公式”中的delta來影響幅度的大小， 這樣，1)和2)就在這點上獲得了統一。對于目的cpu，取計算得到的total_load和nowa_load之間的最大值，而對于源cpu，則取二者最小值。可以看出，在公式中，如果delta等于1，則不執行削波峰/波谷操作，這适用于smt的情況，delta越大，曆史負載值的影響也就越大，削波峰/波谷後的源cpu負載曲線和目的cpu負載曲線的內插補點曲線越趨于平滑，這樣就越能阻止負載均衡操作(差分算法....)。
Linux在基于排程域進行負載均衡的時候采用的是自下而上的周遊方式，這樣就優先在對cache影響最小的cpu之間進行負載均衡，同時這種均衡操作會增加本cpu的負載，反過來在比較高的排程域級别上有力的阻止了對cache影響很大的cpu之間的負載均衡。 我們知道，排程域是從對cache影響最小的最底層向高層建構的。
随着cpu級别的提高，由于負載均衡對cache使用率的影響逐漸增大，“阻力”也應該逐漸加大，是以負載均衡對應排程域使用的delta也應該增加。 算法的根本要點是什麼呢？畫幅圖就一目了然了，delta越大，負載值受曆史值的影響越大，是以按照公式所示，隻有持續單調遞增 的cpu負載，在源cpu選擇時才會被選中，偶然一次的高負載并不足以引起其上的程序遷移至别處，相應的，隻有負載持續單調遞減 ，才會引起其它cpu上的程序遷移至此，這正展現了負載以一個時間段而不是一個時間點為統計周期！ 而級别越高的cpu間的程序遷移，需要的“阻力”越大，是以就越受曆史值的影響，因為隻要曆史中有一次負載很小，就會很明顯的反應在目前，同樣的道理，曆史中有一次的負載很大，也很容易反映在目前；反之，所需“阻力”越小，就越容易受目前負載值的影響，極端的情況下，超線程的不同邏輯cpu之間的負載計算公式中delta為1，是以它們的負載計算結果完全就是該cpu的目前負載！
結論有三：
total_load的計算公式實際上使用了一個數列，該數列是一個“等比數列+微擾數列”的和數列， 等比的比值的分母決定着數列的平滑程度，而微擾數列則是cpu的目前真實負載，它根據delta的取值不同對整個cpu的負載影響不同，為了連續化數列，我們設這兩個數列為函數f(x)和g(x)，證明如下：
不能從delta中得到随着d的增加，阻礙負載均衡的力度将加大這個事實雖然在技術上通過自下而上的周遊方式解決了，然而這使得算法依賴了一個操作方式，這在數學卻不是很完美， 是以可以改進，引入一個參數k來微調g(x) ，而不是依賴d來微調，如果配置k和d相等，那麼新算法将回退到老算法：
有了新的負載計算公式，我們可以控制一個變量k，然後得知，随着d的增加，負載均衡實際發生的可能性将降低。
對于每一個最低級别的cpu(比如超線程cpu)依次執行：
其中三個函數傳回了cpu在對應級别的編号，用于初始化排程組：
初始化了每一個邏輯cpu的排程域之後，依次初始化每一個排程域的各個排程組
該函數初始化了同一排程域中的所有的排程組，邏輯很簡單：
每次時鐘中斷時，要判斷是否要做負載均衡操作了，具體來講實作兩個邏輯：
可見，Linux将3個負載值儲存成了數組，随着索引的增加，曆史值影響逐漸加大，具體祥見第一部分的分析
j的設定是巧妙的，由于每次時鐘中斷都會導緻jiffies遞增，是以當某個時刻j-sd->last_balance正好等于interval的時候，比該cpu的cpu号大的cpu的結果将是j-sd->last_balance<interval，由此多個cpu同時操作同一個cpu的幾率将減少(有效避免了該cpu将别的cpu上的程序拉了過來，然而别的cpu在調用同一函數的時候又将程序拉了回去這種互相扯皮的事情)，鑒于随機數的産生會有很大的開銷，是以采用了jiffies+cpu*HZ/NR_CPUS這種算法來混亂化執行的時間。 然而，由于對于每一個cpu，balance_interval參數是可以配置的，是以配置不同的balance_interval參數可能會抵消掉這種混亂化操作的結果。
該函數比較複雜，它在同一個排程域的各個排程組之間進行負載均衡，總的來講分為三塊
該函數實作很複雜，然而邏輯很簡單，基本政策祥見第一部分的“負載均衡算法分析”。對于代碼，實際上就是一個兩層的循環加上資料的更新 ：
其中source_load取了cpu_load[delta]和nowa_load的最小值，削掉了波峰，而target_load則相反，削掉了波谷
可以看到，基于排程域的負載均衡是從下往上進行的，這樣做的好處在于，每次優先從最底層級别附近pull程序過來，這樣對cache的影響最小，比如兩個邏輯cpu之間遷移程序對cache的影響就會小到可以忽略。随着排程域的級别的增加以及pull過來的程序增加，本cpu的負載會增加，一般而言，到達實體cpu級别這個排程域，本cpu已經就已經很忙了，是以也就很難再進行負載均衡了，實際上這也是一種阻礙程序遷移的方式。
在最busy的組中尋找最busy的cpu，很簡單，就是一次冒泡算法。
遷移程序
核心代碼中的注釋解決本函數：
We do not migrate tasks that are:
1) running (obviously), or
2) cannot be migrated to this CPU due to cpus_allowed, or
3) are cache-hot on their current CPU.
Aggressive migration if:
1) task is cache cold, or
2) too many balance attempts have failed.
需要注意的是，cache的熱度是通過程序離開運作态到現在的時間差來決定的，而這個差的閥值到底是多少，則由排程域的一個cache_hot_time字段決定。
本文不談這種push模式的程序遷移，同時也不深究所謂的主動均衡和被動均衡，這些在了解了核心算法後都會很簡單的。故此處略過
值得注意的是，Linux所實作的排程域和排程組僅僅描述了一個cpu的靜态拓撲和一組預設的配置， 這組預設的配置生成的原則就是在第一部分中描述的各種情況的基礎上在負載均衡和cache使用率之間産生最小的對抗 ， Linux并沒有将這些配置定死，實際上Linux的負載均衡政策是可以動态配置的。
由于負載均衡實作的時候，對排程域資料結構對象使用了淺拷貝 ，是以對于每一個最小級别的cpu，都有自己的可配置參數，而對于所有屬于同一排程域的所有cpu而言，它們有擁有共享的排程組，這些共享的資訊在排程域資料結構中用指針實作，是以對于排程域參數而言，每個cpu是可以單獨配置的。每個cpu都可配置使得可以根據底層級别cpu上的負載情況(負載隻能在最底層級别的cpu上)進行靈活的參數配置，還可以完美支援虛拟化群組排程。
目錄/proc/sys/kernel/sched_domain 下有所有的最底層級别的cpu目錄，比如你的機器上有4個實體cpu，每個實體cpu有2個核心，每個核心都開啟了超線程，則總共的cpu數量是4*2*2=16，是以
root@ZY:/proc/sys/kernel/sched_domain# ls
cpu0 cpu1 cpu2 cpu3 cpu4 cpu5 cpu6 cpu7 ...cpu15
root@ZY:/proc/sys/kernel/sched_domain# cd cpu0/
root@ZY:/proc/sys/kernel/sched_domain/cpu0# ls
domain0 domain1 domain2
root@ZY:/proc/sys/kernel/sched_domain/cpu0# cat domain0/name
SIBLING
root@ZY:/proc/sys/kernel/sched_domain/cpu0# cat domain1/name
MC
root@ZY:/proc/sys/kernel/sched_domain/cpu0# cat domain2/name
CPU
root@ZY:/proc/sys/kernel/sched_domain/cpu0# ls domain0/ #以下這些參數都是可配置的，使用sysctl即可，含義見sched_domain結構體
busy_factor cache_nice_tries forkexec_idx imbalance_pct min_interval newidle_idx
busy_idx flags idle_idx max_interval name wake_idx
列舉一個性能調優的執行個體，當我們手工綁定了程序在各自cpu上運作，并且手工平衡了各個cpu的負載，每一個cpu都有特定的任務，比如cpu0處理網絡中斷和軟中斷，cpu1處理磁盤IO，cpu2運作web服務，...(暫不考慮dca等對cache的影響)，那麼也就不希望核心再做負載均衡了，是以需要針對每一個cpu的排程域進行配置，使之不再進行或者“很不頻繁”進行負載均衡操作：
root@ZY:/proc/sys/kernel/sched_domain# echo 100000000000 > cpu0/domain1/min_interval
root@ZY:/proc/sys/kernel/sched_domain# echo 100000000000 > cpu0/domain2/min_interval
...//針對cpuX依照上述執行，另外還要設定max_interval，要大于100000000000 。對于domain0，由于它是SMT級别的，是以負載均衡并不會破壞cache，是以不設定。
...//其實還有很多的參數可以設定，比如flags，imbalance_pct，busy_factor等。
注解： 由于fork和exec的行為是不同的，fork後的新程序還是要通路老程序的資料(寫時複制)，而exec則徹底告别老程序(雖然還可能會通路同樣載入老程序的共享庫)，是以排程域的flags中的SD_BALANCE_FORK和SD_BALANCE_EXEC最好應該差別開來，我們可以通過在SMT或者MC排程域中設定SD_BALANCE_FORK而SMP中不設定SD_BALANCE_FORK來優化fork後的程序的寫時複制，至于SD_BALANCE_EXEC則全部支援，不過這樣設定的前提是你對你的應用程序的脾氣很了解，如果exec後的程序和之前的程序共享大量的在之前之後都大量被讀寫的共享庫的話，說實話SD_BALANCE_EXEC标志也最好不要設定在SMP排程域中。
完全可以使用sysctl配置系統的debug級别或者重新編譯核心增加更多的列印資訊，然而編寫modules導出自己需要的資訊一直都是最好的方式，因為它隻輸出你需要的資訊，而核心的debug資訊雖然很詳細，但是你可能還真的需要花一番功夫才能明白其是以然。
以下是一個核心子產品的代碼，它揪出了兩個cpu的排程域和排程組資訊，然後列印出來，這種編寫子產品的好處在于，你可以做且僅做你需要的，且一切按照你自己的風格來！
對于一個單實體cpu開啟超線程的系統加載上述子產品，dmesg得到以下結果：
[63962.546289] domain address: ffff88000180fa20
[63962.546294] domain name: SIBLING
[63962.546297] domain busy: 3
[63962.546300] domain busy: 180fa98
[63962.546303] group address:ffff88000180fae0 #cpu0-第一個邏輯cpu的smt排程域的第一個組，包括它自身(1)
[63962.546306] group address:ffff88000184fae0 #cpu0-第一個邏輯cpu的smt排程域的第二個組，包括它兄弟(2)
[63962.546308] next domain
[63962.546311] domain address: ffff88000180fb30
[63962.546314] domain name: MC
[63962.546316] domain busy: 30
[63962.546319] domain busy: 180fba8
[63962.546321] group address:ffff88000180fbf0
[63962.546324] next domain
[63962.546326] NEXT CPU
[63962.546329] domain address: ffff88000184fa20
[63962.546332] domain name: SIBLING
[63962.546335] domain busy: 0
[63962.546337] domain busy: 184fa98
[63962.546340] group address:ffff88000184fae0 #cpu0-第一個邏輯cpu的smt排程域的第一個組，包括它自身，等于(2)
[63962.546343] group address:ffff88000180fae0 #cpu0-第一個邏輯cpu的smt排程域的第一個組，包括它兄弟，等于(1)
[63962.546345] next domain
[63962.546348] domain address: ffff88000184fb30
[63962.546351] domain name: MC
[63962.546354] domain busy: 2
[63962.546357] domain busy: 184fba8
[63962.546359] group address:ffff88000180fbf0
[63962.546362] next domain
要問關于Linux核心的那些資料最好，我覺得最好的有兩個，一個是LKML(Linux kernel maillist)還有一個就是核心文檔，核心文檔中的資訊相當豐富，涉及了幾乎所有的核心功能，是以閱讀它們是有幫助的，本文的最後，我嘗試将其中《sched-domains.txt》翻譯一下，“[]”中的是我的一切注釋，注意，以下并不是原文直譯，而是意譯(信，達，雅三境界中，我可能連“信”都談不上，是以找個理由，說是意譯！)。譯文如下：
每一個cpu都擁有一個“base”排程域(struct sched_domain)[注：基本的排程域，也就是最底層的排程域，以下的per-cpu指的就是最底層的cpu]。這些“base”排程域可以通過cpu_sched_domain(i)和this_sched_domain()這兩個宏來通路。排程域層次結構從這些“base”排程域開始[注：向上]建構，通過排程域的parent指針可以通路到其上級排程域。parent指針必須是NULL結尾的[注：最高一級别的排程域的parent指針為NULL]，排程域是per-cpu的，因為這樣可以在更新其字段時，鎖的開銷更小[注：同時每個排程域也是單獨可配置的]。
每一個排程域覆寫一定數量的cpu(存儲于span字段)。一個排程域的span必須是其子排程域span的超集。cpui的“base”排程域的span中起碼要包含cpui。最頂層的排程域需要覆寫系統所有的cpu，雖然嚴格來講這并不是必須的，會導緻一些cpu上從來都沒有程序運作。排程域的span的含義是“在這些cpu之間進行負載均衡”
每一個排程域必須擁有起碼一個cpu排程組(struct sched_groups)，這些組組織成一個環形連結清單，該連結清單從排程域的groups字段開始。同一個排程域的這些組的cpumasks的并集表示的cpu必須和該排程域的span字段表示的cpu完全相等，同時，屬于同一排程域的任意兩個組的cpumasks字段的交集必須是空集。一個排程域的排程組覆寫的cpu必須是該排程域所覆寫的。這些排程組的隻讀資料在cpu之間是共享的。
一個排程域的負載均衡操作發生在其各個排程組之間。此時，每一個排程組被當成了一個整體對待。一個排程組的負載定義為該組中所有的cpu成員的負載之和，并且隻有當組與組之間的負載失衡的時候，才會在組與組之間遷移程序。
從源檔案kernel/sched.c中可以看出，每一個cpu會周期性的調用rebalance_tick函數。該函數将從該cpu的“base”排程域開始檢查該排程域内的程序是否到達了其負載均衡的周期，如果是，則在該排程域調用load_balance，然後在“base”排程域的parent排程域中執行上述操作，這是一個周遊的過程，周遊過程以此類推。
*** 排程域的實作[和定制] ***
“base”排程域将構成排程域層級結構的第一級。舉例來講，在SMT的情況下，“base”排程域覆寫了一個實體cpu的所有邏輯cpu，每一個邏輯cpu構成了一個排程組。SMP的情況下，實體cpu排程域作為“base”排程域的parent，它将覆寫一個NUMA節點中的所有的cpu。其每一個排程組覆寫一個實體cpu。同樣的道理，在NUMA情況下，節點排程域作為實體cpu排程域的parent，它将覆寫整台機器的所有cpu，其每一個排程組覆寫一個節點的所有cpu。
實作者需要閱讀include/linux/sched.h檔案裡面關于sched_domain結構體的字段的注釋以及SD_FLAG_*和SD_*_INIT來了解更多的細節以及了解如何來調節這些參數進而影響核心負載均衡的行為。
如果你想支援SMT，必須定義CONFIG_SCHED_SMT宏，并且提供一個cpumask_t類型的數組cpu_sibling_map[NR_CPUS]，元素cpu_sibling_map[i]的含義是所有和cpui屬于同一個實體cpu[或者實體cpu核]的邏輯cpu的掩碼，這個掩碼中當然也包括cpui本身。
[針對特定的體系結構可以對Linux核心預設的排程域/排程組的預設參數以及設定進行重載，此處不再翻譯]
本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1271012