本文出現(xiàn)的內(nèi)核代碼來自Linux5.4.28，為了減少篇幅，我們盡量不引用代碼，如果有興趣，讀者可以配合代碼閱讀本文。

一、有幾種負載均衡的方式？

整個Linux的負載均衡器有下面的幾個類型：

實際上內(nèi)核的負載均衡器（本文都是特指CFS任務的）有兩種，一種是為繁忙CPU們準備的periodic balancer，用于CFS任務在busy cpu上的均衡。還有一種是為idle cpu們準備的idle balancer，用于把繁忙CPU上的任務均衡到idle cpu上來。idle balancer有兩種，一種是nohz idle balancer，另外一種是new idle balancer。
周期性負載均衡（periodic load balance或者tick load balance）是指在tick中，周期性的檢測系統(tǒng)的負載均衡狀況，找到系統(tǒng)中負載最重的domain、group和CPU，將其上的runnable任務拉到本CPU以便讓系統(tǒng)的負載處于均衡的狀態(tài)。周期性負載均衡只能在busy cpu之間均衡，要想讓系統(tǒng)中的idle cpu“燥起來”就需要借助idle load balance。
NOHZ load balance是指其他的cpu已經(jīng)進入idle，本CPU任務太重，需要通過ipi將其他idle的CPUs喚醒來進行負載均衡。為什么叫NOHZ load balance呢？那是因為這個balancer只有在內(nèi)核配置了NOHZ（即tickless mode）下才會生效。如果CPU進入idle之后仍然有周期性的tick，那么通過tick load balance就能完成負載均衡了，不需要IPI來喚醒idle的cpu。和周期性均衡一樣，NOHZ idle load balance也是通過busy cpu上tick驅(qū)動的，如果需要kick idle load balancer，那么就會通過GIC發(fā)送一個ipi中斷給選中的idle cpu，讓它代表系統(tǒng)所有的idle cpu們進行負載均衡。
New idle load balance比較好理解，就是在CPU上沒有任務執(zhí)行，馬上要進入idle狀態(tài)的時候，看看其他CPU是否需要幫忙，從來從busy cpu上拉任務，讓整個系統(tǒng)的負載處于均衡狀態(tài)。NOHZ load balance涉及系統(tǒng)中所有的idle cpu，但New idle load balance只是和即將進入idle的本CPU相關。?

二、周期性負載均衡的大概過程為何？

當tick到來的時候，在scheduler_tick函數(shù)中會調(diào)用trigger_load_balance來觸發(fā)周期性負載均衡，相關的代碼如下：

整個代碼非常的簡單，主要的邏輯就是調(diào)用raise_softirq觸發(fā)SCHED_SOFTIRQ，當然要滿足均衡間隔時間的要求（后面會詳述）。nohz_balancer_kick用來觸發(fā)nohz idle balance的，這是后面兩個章節(jié)要仔細描述的內(nèi)容。上面的圖片，我特地保留了函數(shù)的注釋，這里看起似乎注釋不對，因為這個函數(shù)不但觸發(fā)的周期性均衡，也觸發(fā)了nohz idle balance。然而，其實nohz idle balance本質(zhì)上也是另外一種意義上的周期性負載均衡，只是因為CPU進入idle，無法產(chǎn)生tick，因此讓能產(chǎn)生tick的busy CPU來幫忙觸發(fā)tick balance。而實際上tick balance和nohz idle balance都是通過SCHED_SOFTIRQ的軟中斷來處理，最后都是執(zhí)行run_rebalance_domains這個函數(shù)。?

三、整個nohz idle balance的過程是怎樣的？

這個問題可以拆解成兩個問題：

1）系統(tǒng)中有多個idle的cpu，如何選擇執(zhí)行nohz idle balance的那個cpu？

2）怎么通知到idle的CPU，喚醒的CPU如何進行均衡？

如果不考慮功耗，那么從所有的idle cpu中選擇一個就OK了，然而，在異構(gòu)系統(tǒng)中（例如手機環(huán)境），我們要考慮更多。例如：如果大核CPU和小核CPU都處于idle狀態(tài)，那么選擇喚醒大核CPU還是小核CPU？大核CPU雖然算力強，但是功耗高。如果選擇小核，雖然能省功耗，但是提供的算力是否足夠。此外，發(fā)起idle balance請求的CPU在那個cluster？是否首選同一個cluster的cpu來執(zhí)行nohz idle balance？還有cpu idle的深度如何？很多思考點，不過本文就不詳述了，畢竟標準內(nèi)核選擇的最簡單的算法：隨便選擇一個idle cpu（也就是idle cpu mask中的第一個）。
我們定義發(fā)起nohz idle balance的CPU叫做kicker；接收請求來執(zhí)行均衡操作的CPU叫做kickee。Kicker和kickee之間的交互是這樣的：

1）Kicker通知kickee已經(jīng)被選中執(zhí)行nohz idle balance，具體是通過設定kickee cpu runqueue的nohz_flags成員來完成的。

2）Send ipi把kickee喚醒

3）Kickee被中斷喚醒，執(zhí)行scheduler_ipi來處理這個ipi中斷。當發(fā)現(xiàn)其runqueue的nohz_flags成員被設定了，那么知道自己被選中，后續(xù)的流程其實和周期性均衡一樣的，都是觸發(fā)一次SCHED_SOFTIRQ類型的軟中斷

我們再強調(diào)一下：被kick的那個idle cpu并不是負責拉其他繁忙cpu上的任務到本CPU上就完事了，kickee是為了重新均衡所有idle cpu（tick被停掉）的負載，也就是說被選中的idle cpu僅僅是一個系統(tǒng)所有idle cpu的代表，它被喚醒是要把系統(tǒng)中繁忙CPU的任務均衡到系統(tǒng)中所有的idle cpu們。此外，在上面的步驟1中，有可能有多個kicker同時選中一個kickee，因此這里需要檢測pending的請求，避免重復操作。具體的代碼可以參考nohz_balancer_kick函數(shù)。
SCHED_SOFTIRQ軟中斷的處理函數(shù)如下：

nohz idle balance和periodic load balance都是通過SCHED_SOFTIRQ類型的軟中斷來完成，也就是說它們兩個都是通過SCHED_SOFTIRQ注冊的handler函數(shù)run_rebalance_domains來完成其功能的，那么如果一個CPU被選中做nohz idle balance，于此同時tick也到了，那么怎么處理？這個時候調(diào)度器優(yōu)先處理nohz idle balance，畢竟nohz idle balance是一個全局的事情（代表系統(tǒng)所有idle cpu做均衡），而periodic load balance只是均衡自己的各階sched domain。?

四、什么條件下才需要喚醒idle CPU來執(zhí)行NOHZ idle load balance？

在一個active的CPU上，tick會周期性到來，我們在該CPU的tick中檢測是否需要觸發(fā)NOHZ load balance。顯然一個輕載的CPU可以“自力更生”，不需要其他idle的CPU來協(xié)助，那么如何界定一個CPU上的任務的輕和重？以至于需要冒險（功耗損失）要將其他idle的CPU喚醒？主要考慮下面幾點：

• 本CPU不能處于idle狀態(tài)，且其runqueue中的任務數(shù)大于等于2（load balance主要是遷移runnable的任務，>=2保證了至少有一個可以被遷移的任務）

• 系統(tǒng)中有其他的CPU處于tickless mode的idle狀態(tài)

• NOHZ load balance不宜觸發(fā)的過于頻繁。下一章會詳細描述。

• 本CPU runqueue有至少1個CFS任務，并且CPU的算力被大量消耗在RT task或者IRQ處理上，可以用于執(zhí)行cfs的算力大大降低了，這時候也需要其他idle cpu來幫忙。

• 在異構(gòu)計算系統(tǒng)中，如果當前CPU上有misfit task，并且系統(tǒng)中有更高算力的idle cpu，那么也會發(fā)起balance，讓算力更高的處理器來承接該misfit task。和提高cache命中率相比，調(diào)度器更期待任務可以獲得更適合算力的CPU。

具體的代碼可以參考nohz_balancer_kick函數(shù)。?

五、如何控制觸發(fā)nohz idle balance的頻次？

雖然nohz idle balance本質(zhì)上是tick balance，但是它會發(fā)IPI，會喚醒idle的cpu，帶來額外的開銷，所以還是要控制觸發(fā)觸發(fā)nohz idle balance的頻次。為了方便控制觸發(fā)nohz idle balance，調(diào)度器定義了一個nohz的全局變量，其數(shù)據(jù)結(jié)構(gòu)如下：

nr_cpus和idle_cpus_mask這兩個成員可以讓調(diào)度器了解當前系統(tǒng)idle CPU的情況，從而選擇合適的CPU來執(zhí)行nohz idle balance。一個idle的cpu被kick并不總是完成負載均衡，有時候也可能是因為要更新blocked load，讓系統(tǒng)中的CPU負載符合當前的狀態(tài)。這部分不是本文的內(nèi)容，不再詳述。next_balance是用來控制觸發(fā)nohz idle balance的時間點，這個時間點應該是和系統(tǒng)中所有idle cpu的rq->next_balance相關的，也就是說，如果系統(tǒng)中所有idle cpu都還不需要均衡，那么根本也就沒有必要觸發(fā)nohz idle balance，因此，在執(zhí)行nohz idle balance的時候，調(diào)度器實際上會遍歷idle cpu找到rq->next_balance最小的（即最近需要均衡的）賦值給nohz.next_balance。
具體執(zhí)行nohz idle balance非常簡單，遍歷系統(tǒng)所有的idle cpu，調(diào)用rebalance_domains來完成該cpu上的各個level的sched domain的負載均衡。?具體的代碼可以參考nohz_idle_balance函數(shù)。

【文章福利】小編推薦自己的Linux內(nèi)核技術交流群:【749907784】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ? ?

六、做new idle load balance需要考慮哪些因素？

目前調(diào)度器做new idle load balance主要考慮兩個因素：當前cpu的cache狀態(tài)和當前的整機負載情況。如果該CPU平均idle時間非常短，那么當CPU重新回來執(zhí)行的任務的時候，CPU cache還是熱的，如果從其他CPU上拉取任務，那么這些新的任務會破壞其他任務的cache，從而影響過去任務的性能，同時也有功耗的增加。整機負載的影響記錄在root domain中的overload成員中，所謂overload就是指滿足下面的條件：

• 大于1個runnable task，即該CPU上有等待執(zhí)行的任務

• 只有一個正在運行的任務，但是是misfit task

滿足上面的條件我們稱這個CPU是overload狀態(tài)的，如果系統(tǒng)中至少有一個CPU是overload狀態(tài)，那么我們認為系統(tǒng)是overload狀態(tài)的。如果系統(tǒng)沒有overload，那么也就沒有必要做new idle load balance了。
上面是從CPU視角做的決定，降低了new idlebalance的次數(shù)，此外，調(diào)度器也從sched domain的角度進行檢查，進一步避免了無效new idlebalance發(fā)生的次數(shù)。首先我們要明確一點：做new idle load balance是有開銷的，我們辛辛苦苦找到了繁忙的CPU，從它的runqueue中拉了任務來，然而如果自己其實也沒有那么閑，可能很快就有任務放置到自己的runqueue上來，這樣，那些用于均衡的CPU時間其實都白白浪費了。怎么避免這個尷尬狀況？我們需要兩個數(shù)據(jù)：一個是當前CPU的平均idle時間，另外一個是在new idle load balance引入的開銷（max_newidle_lb_cost成員）。如果CPU的平均idle時間小于max_newidle_lb_cost+本次均衡的開銷，那么就不啟動均衡。
為了控制cpu無效進入new idle load balance，runqueue數(shù)據(jù)結(jié)構(gòu)中有下面的成員：

計算avg_idle的算法非常簡單，如下：

和nohz idle balance一樣，new idle balance不僅僅要處理負載均衡，同時也要負責處理blocked load的更新。如果條件不滿足，該cpu不需要進行均衡，那么在進入idle狀態(tài)之前，還需要看看系統(tǒng)中的那些idle cpu們的blocked load是否需要更新了，如果需要，那么該CPU就會執(zhí)行blocked load的負載更新。其背后的邏輯是：與其在nohz idle balance過程中遍歷選擇一個idle CPU來做負載更新，還不如就讓這個即將進入idle的cpu來處理。?具體的代碼可以參考newidle_balance函數(shù)。?

七、對于一個sched domain而言，多久做一次負載均衡比較適合？

負載均衡執(zhí)行的頻次其實是在延遲和開銷之間進行平衡。不同level的sched domain上負載均衡帶來的開銷是不一樣的。在手機平臺上，MC domain在inter-cluster之內(nèi)進行均衡，對性能的影響小一點。但是DIE domain上的均衡需要在cluster之間遷移任務，對性能和功耗的影響都比較大一些（例如cache命中率，或者一個任務遷移到原來深度睡眠的大核CPU）。因此執(zhí)行均衡的時間間隔應該是和domain的層級相關的。此外，負載狀況也會影響均衡的時間間隔，在各個CPU負載比較重的時候，均衡的時間間隔可以拉大，畢竟大家都忙，讓子彈先飛一會，等塵埃落定之后在執(zhí)行均衡也不遲。
struct sched_domain和均衡相關的數(shù)據(jù)成員包括：

對于一個4+4的手機平臺，在MC domain上，小核和大核cluster的min_interval都是4ms，而max_interval等于8ms。而在DIE domain層級上，由于CPU個數(shù)是8，其min_interval是8ms，而max_interval等于16ms。真正的均衡間隔是定義在balance_interval中，是一個不斷跟隨sched domain的不均衡程度而變化的值。初值一般從min_interval開始，隨著不均衡的狀況在變好，balance_interval會逐漸變大，從而讓均衡的間隔變大，直到max_interval。

八、結(jié)束語

周期性均衡和nohz idle balance都是SCHED類型的軟中斷觸發(fā)，最后都調(diào)用了rebalance_domains來執(zhí)行該CPU上各個level的sched domain的均衡，具體在某個sched domain執(zhí)行均衡的函數(shù)是load_balance函數(shù)。對于new idle load balance，也是遍歷該CPU上各個level的sched domain執(zhí)行均衡動作，調(diào)用的函數(shù)仍然是load_balance。因此，無論哪一種均衡，最后都萬法歸宗來到load_balance。由于篇幅原因，本文不再詳細分析load_balance的邏輯，想要了解細節(jié)且聽下回分解吧。

原文作者：內(nèi)核工匠