概述

在多核系統(tǒng)中，為了更好的利用多CPU并行能力，進程調(diào)度器可以將進程負載盡可能的平均到各個CPU上。再具體實現(xiàn)中，如何選擇將進程遷移到的目標(biāo)CPU，除了考慮各個CPU的負載平衡，還需要將Cache利用納入權(quán)衡因素。同時，對于進程A喚醒進程B這個模型，還做了特殊的處理。本文分析以Centos kernel 3.10.0-975源碼為藍本。

SMP負載均衡模型

問題

如果只是將CPU負載平均的分布在各個CPU上，那么就無所謂需要調(diào)度域。但是由于Cache以及內(nèi)存Numa的存在，使得進程最好能遷移到與之前運行所在CPU更'近'的CPU上。

以我們常用的Intel X86為例。Cache基本視圖如下圖：

從Cache和內(nèi)存訪問的視角，如果進程負載均衡需要把進程A遷移到另一個CPU上，

• 如果目標(biāo)CPU和進程A之前所在CPU正好是同一個物理CPU同一個核心上(超線程)，那么Cache利用率最好，畢竟L1，L2和L3中還是'熱'的。

• 如果目標(biāo)CPU和進程A之前所在CPU正好是同一個物理CPU但不同核心上(多核)，那么Cache利用率次之，L3中還有'熱'數(shù)據(jù)。

• 如果目標(biāo)CPU和進程A之前所在CPU正好是同一個NUMA但是不同物理CPU上(多NUMA結(jié)構(gòu))，雖然Cache已經(jīng)是'冷'了，但至少內(nèi)存訪問還是在本NUMA中。

• 如果目標(biāo)CPU和進程A之前所在CPU在不同NUMA中，不但Cache是'冷'的，跨NUMA內(nèi)存還有懲罰，此時內(nèi)存訪問速度最差。

SMP組織

為了更好地利用Cache，內(nèi)核將CPU(如果開啟了超線程，那么以邏輯CPU為單位，否則以物理CPU核心為單位)組織成了調(diào)度域。

邏輯視角

假設(shè)某機器為2路4核8核心CPU，它的CPU調(diào)度域邏輯上如下圖：

2路NUMA最為簡單，如果是4路NUMA，那么這個視圖在NUMA層級將會復(fù)雜很多，因為跨NUMA訪問根據(jù)訪問距離導(dǎo)致訪問延時還不相同，這部分最后討論。

分層視角

所有CPU一共分為三個層次：SMT，MC，NUMA，每層都包含了所有CPU，但是劃分粒度不同。根據(jù)Cache和內(nèi)存的相關(guān)性劃分調(diào)度域，調(diào)度域內(nèi)的CPU又劃分一次調(diào)度組。越往下層調(diào)度域越小，越往上層調(diào)度域越大。進程負載均衡會盡可能的在底層調(diào)度域內(nèi)部解決，這樣Cache利用率最優(yōu)。

從分層的視角分析，下圖是調(diào)度域?qū)嶋H組織方式，每層都有per-cpu數(shù)組保存每個CPU對應(yīng)的調(diào)度域和調(diào)度組，它們是在初始化時已經(jīng)提前分配的內(nèi)存。值得注意的是

• 每個CPU對應(yīng)的調(diào)度域數(shù)據(jù)結(jié)構(gòu)都包含了有效的內(nèi)容，比如說SMT層中，CPU0和CPU1對應(yīng)的不同調(diào)度域數(shù)據(jù)結(jié)構(gòu)，內(nèi)容是一模一樣的。

• 每個CPU對應(yīng)的調(diào)度組數(shù)據(jù)結(jié)構(gòu)不一定包含了有效內(nèi)容，比如說MC層中，CPU0和CPU1指向不同的struct sched_domain,但是sched_domain->groups指向的調(diào)度組確是同樣的數(shù)據(jù)結(jié)構(gòu)，這些調(diào)度組組成了環(huán)。

單CPU視角

從單個CPU的視角分析，下圖是調(diào)度域?qū)嶋H組織方式。

每個CPU的進程運行隊列有一個成員指向其所在調(diào)度域。從最低層到最高層。

我們可以在/proc/sys/kernel/sched_domain/cpuX/ 中看到CPU實際使用的調(diào)度域個數(shù)以及每個調(diào)度域的名字和配置參數(shù)。

負載均衡時機

• 周期性調(diào)用進程調(diào)度程序scheduler_tick()->trigger_load_balance()中，通過軟中斷觸發(fā)負載均衡。

• 某個CPU上無可運行進程，__schedule()準(zhǔn)備調(diào)度idle進程前，會嘗試從其它CPU上pull一批進程過來。

周期性負載均衡

CPU對應(yīng)的運行隊列數(shù)據(jù)結(jié)構(gòu)中記錄了下一次周期性負載均衡的時間，當(dāng)超過這個時間點后，將觸發(fā)SCHED_SOFTIRQ軟中斷來進行負載均衡。

以下是rebalance_domains()函數(shù)核心流程，值得注意的是，每個層級的調(diào)度間隔不是固定的，而是臨時計算出來，他在一個可通過proc接口配置的最小值和最大值之間。

以下是對CPU的每個層級調(diào)度域調(diào)用load_balance()函數(shù)核心流程，目的是把一些進程遷移到指定的CPU(該場景就是當(dāng)前CPU)。

以我的服務(wù)器為例，觀察不同層級調(diào)度域的調(diào)度間隔范圍，時間單位為jiffies。

可見，SMT負載均衡頻率最高，越往上層越低。這也符合體系結(jié)構(gòu)特點，在越低層次遷移進程代價越小(Cache利用率高)，所以可以更加頻繁一點。

CPU進入idle前負載均衡

當(dāng)進程調(diào)度函數(shù)__schedule()把即將切換到idle進程前，會發(fā)生一次負載均衡來避免當(dāng)前CPU空閑。

s

核心函數(shù)idle_balance()?；旧弦彩潜M可能在低層調(diào)度域中負載均衡。

其它需要用到SMP負載均衡模型的時機

內(nèi)核運行中，還有部分情況中需要用掉SMP負載均衡模型來確定最佳運行CPU:

• 進程A喚醒進程B時，try_to_wake_up()中會考慮進程B將在哪個CPU上運行。

• 進程調(diào)用execve()系統(tǒng)調(diào)用時。

• fork出子進程，子進程第一次被調(diào)度運

喚醒進程時

當(dāng)A進程喚醒B進程時，假設(shè)都是普通進程，那么將會調(diào)用try_to_wake_up()->select_task_rq()->select_task_rq_fair()

調(diào)用execve()系統(tǒng)調(diào)用時

fork的子進程第一次被調(diào)度運行時

do_fork()->wake_up_new_task()

Linux、C/C++技術(shù)交流群:960994558整理了一些個人覺得比較好的學(xué)習(xí)書籍、大廠面試題、和熱門技術(shù)教學(xué)視頻資料共享在里面（包括C/C++，Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協(xié)程，DPDK等等.），有需要的可以自行添加哦！~