概述

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

SMP負(fù)載均衡模型

問(wèn)題

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

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

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

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

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

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

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

SMP組織

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

邏輯視角

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

2路NUMA最為簡(jiǎn)單，如果是4路NUMA，那么這個(gè)視圖在NUMA層級(jí)將會(huì)復(fù)雜很多，因?yàn)榭鏝UMA訪問(wèn)根據(jù)訪問(wèn)距離導(dǎo)致訪問(wèn)延時(shí)還不相同，這部分最后討論。

分層視角

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

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

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

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

單CPU視角

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

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

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

負(fù)載均衡時(shí)機(jī)

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

• 某個(gè)CPU上無(wú)可運(yùn)行進(jìn)程，__schedule()準(zhǔn)備調(diào)度idle進(jìn)程前，會(huì)嘗試從其它CPU上pull一批進(jìn)程過(guò)來(lái)。

周期性負(fù)載均衡

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

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

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

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

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

CPU進(jìn)入idle前負(fù)載均衡

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

s

核心函數(shù)idle_balance()。基本上也是盡可能在低層調(diào)度域中負(fù)載均衡。

其它需要用到SMP負(fù)載均衡模型的時(shí)機(jī)

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

• 進(jìn)程A喚醒進(jìn)程B時(shí)，try_to_wake_up()中會(huì)考慮進(jìn)程B將在哪個(gè)CPU上運(yùn)行。

• 進(jìn)程調(diào)用execve()系統(tǒng)調(diào)用時(shí)。

• fork出子進(jìn)程，子進(jìn)程第一次被調(diào)度運(yùn)

喚醒進(jìn)程時(shí)

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

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

fork的子進(jìn)程第一次被調(diào)度運(yùn)行時(shí)

do_fork()->wake_up_new_task()

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