Linux 進程管理之CFS負載均衡
本文轉(zhuǎn)載自微信公眾號「人人都是極客」，作者布道師Peter。轉(zhuǎn)載本文請聯(lián)系人人都是極客公眾號。
什么是負載均衡?
前面的調(diào)度學習都是默認在單個CPU上的調(diào)度策略。我們知道為了CPU之間減少“干擾”，每個CPU上都有一個任務隊列。運行的過程種可能會出現(xiàn)有的CPU“忙的一筆”，有的CPU“閑的蛋疼”，于是便需要負載均衡。
將task從負載較重的CPU上轉(zhuǎn)移到負載相對較輕的CPU上執(zhí)行，這個過程就是負載均衡的過程。
在了解負載均衡前有必要了解soc上對CPU的拓撲關系。
我們知道一個多核心的soc片上系統(tǒng)，內(nèi)部結(jié)構(gòu)是很復雜的，內(nèi)核采用CPU拓撲結(jié)構(gòu)來描述一個SOC的架構(gòu)。內(nèi)核使用調(diào)度域來描述CPU之間的層次關系，對于低級別的調(diào)度域來說，CPU之間的負載均衡處理開銷比較小，而對于越高級別的調(diào)度域，其負載均衡的開銷就越大。
比如一個4核心的SOC，兩個核心是一個cluster，共享L2 cache，那么每個cluster可以認為是一個MC調(diào)度域，每個MC調(diào)度域中有兩個調(diào)度組，每個調(diào)度組中只有一個CPU。而整個SOC可以認為是高一級別的DIE調(diào)度域，其中有兩個調(diào)度組，cluster0屬于一個調(diào)度組，cluster1屬于另一個調(diào)度組?？鏲luster的負載均衡是需要清除L2 cache的，開銷是很大的，因此SOC級別的DIE調(diào)度域進行負載均衡的開銷會更大一些。
CPU對應的調(diào)度域和調(diào)度組可通過在設備模型文件 /proc/sys/kernel/sched_domain 里查看。
- 調(diào)度域 sched_domain 主要的成員如下：
| 成員 | 描述 |
|---|---|
| parent 和 child | sched domain會形成層級結(jié)構(gòu)，parent和child建立了不同層級結(jié)構(gòu)的父子關系。對于base domain而言，其child等于NULL；對于top domain而言，其parent等于NULL。 |
| groups | 一個調(diào)度域中有若干個調(diào)度組，這些調(diào)度組形成一個環(huán)形鏈表，groups成員就是鏈表頭 |
| min_interval 和 max_interval | 做均衡也是需要開銷的，不能時刻去檢查調(diào)度域的均衡狀態(tài)，這兩個參數(shù)定義了檢查該sched domain均衡狀態(tài)的時間間隔的范圍 |
| balance_interval | 定義了該sched domain均衡的時間間隔 |
| busy_factor | 正常情況下，balance_interval定義了均衡的時間間隔，如果cpu繁忙，那么均衡要時間間隔長一些，即時間間隔定義為busy_factor x balance_interval |
| imbalance_pct | 調(diào)度域內(nèi)的不均衡狀態(tài)達到了一定的程度之后就開始進行負載均衡的操作，imbalance_pct定義了不均衡的water mark。 |
| level | 該sched domain在整個調(diào)度域?qū)蛹壗Y(jié)構(gòu)中的level |
| span_weight | 該sched domain中cpu的個數(shù) |
| span | 該調(diào)度域的跨度 |
- 調(diào)度組 sched_group 主要的成員如下：
| 成員 | 描述 |
|---|---|
| next | sched domain中的所有sched group會形成環(huán)形鏈表，next指向groups鏈表中的下一個節(jié)點 |
| group_weight | 該調(diào)度組中有多少個cpu |
| sgc | 該調(diào)度組的算力信息 |
| cpumask | 該調(diào)度組包含哪些cpu |
CPU拓撲示例
為了減少鎖的競爭，每一個cpu都有自己的MC domain、DIE domain(sched domain是分成兩個level，base domain稱為MC domain(multi core domain)，頂層的domain稱為DIE domain)以及sched group，并且形成了sched domain之間的層級結(jié)構(gòu)，sched group的環(huán)形鏈表結(jié)構(gòu)?？梢酝ㄟ^/sys/devices/system/cpu/cpuX/topology查看cpu topology信息。
在上面的結(jié)構(gòu)中，sched domain是分成兩個level，base domain稱為MC domain，頂層的domain稱為DIE domain。頂層的DIE domain覆蓋了系統(tǒng)中所有的CPU，小核cluster的MC domain包括所有小核cluster中的cpu，大核cluster的MC domain包括所有大核cluster中的cpu。
通過DTS和CPU topo子系統(tǒng)，可以構(gòu)建sched domain層級結(jié)構(gòu)，用于具體的均衡算法。流程是：kernel_init() -> kernel_init_freeable() -> smp_prepare_cpus() -> init_cpu_topology() -> parse_dt_topology()
負載均衡的軟件架構(gòu)
圖中可以看出左邊主要分為CPU負載跟蹤和task負載跟蹤。
- CPU負載跟蹤：考慮每一個CPU的負載。匯聚cluster上所有負載，方便計算cluster之間負載的不均衡狀況。
- task負載跟蹤：判斷該任務是否適合當前CPU算力。如果判定需要均衡，那么需要在CPU之間遷移多少的任務才能達到平衡。
右邊是通過DTS和CPU topo子系統(tǒng)，構(gòu)建的sched domain層級結(jié)構(gòu)。流程是：kernel_init() -> kernel_init_freeable() -> smp_prepare_cpus() -> init_cpu_topology() -> parse_dt_topology()
有了左右兩邊的基礎設施，那么什么時候觸發(fā)負載均衡呢?這主要和調(diào)度事件相關，當發(fā)生任務喚醒、任務創(chuàng)建、tick到來等調(diào)度事件的時候，就可以檢查當前系統(tǒng)的不均衡情況，并酌情進行任務遷移，以便讓系統(tǒng)負載處于平衡狀態(tài)。
何時做負載均衡?
CFS任務的負載均衡器有兩種。一種是為繁忙CPU們準備的periodic balancer，用于CFS任務在busy cpu上的均衡;一種是為idle cpu們準備的idle balancer，用于把繁忙CPU上的任務均衡到idle cpu上來。
周期性負載均衡(periodic load balance或者tick load balance)是指在tick中，周期性的檢測系統(tǒng)的負載均衡狀況，找到系統(tǒng)中負載最重的domain、group和CPU，將其上的runnable任務拉到本CPU以便讓系統(tǒng)的負載處于均衡的狀態(tài)。
nohz load balance是指其他的cpu已經(jīng)進入idle，本CPU任務太重，需要通過 IPI 將其他idle的CPUs喚醒來進行負載均衡。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)。
負載均衡的基本過程
當一個CPU上進行負載均衡的時候，總是從base domain開始，檢查其所屬sched group之間的負載均衡情況，如果有不均衡情況，那么會在該cpu所屬cluster之間進行遷移，以便維護cluster內(nèi)各個cpu core的任務負載均衡。
load_balance是處理負載均衡的核心函數(shù)，它的處理單元是一個調(diào)度域，也就是sched domain，其中會包含對調(diào)度組的處理。
在該domain中找到最忙的sched group
在最忙的group中挑選最忙的CPU runqueue，該CPU就成為任務遷移的src
從該隊列中選擇要遷移的任務(判斷的依據(jù)主要是task load的大小，優(yōu)先選擇load重的任務)
向著作為dst的CPU runqueue遷移
