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