Linux進(jìn)程調(diào)度的邏輯介紹

2024-08-27 23:54:58

字體：大中小

供稿：網(wǎng)友

　　這篇文章主要介紹“Linux進(jìn)程調(diào)度的邏輯是什么”，在日常操作中，相信很多人在Linux進(jìn)程調(diào)度的邏輯是什么問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”Linux進(jìn)程調(diào)度的邏輯是什么”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

　　Linux進(jìn)程調(diào)度的邏輯是什么

　　 pick_next_task()：從就緒隊(duì)列中選中一個(gè)進(jìn)程
　　內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候，會(huì)首先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度，如果沒(méi)有，執(zhí)行進(jìn)程遷移邏輯，從其他 CPU 遷移進(jìn)程，如果有，則選擇虛擬時(shí)間較小的進(jìn)程進(jìn)行調(diào)度。

　　內(nèi)核在選擇邏輯 CPU 進(jìn)行遷移進(jìn)程的時(shí)候，為了提升被遷移進(jìn)程的性能，即避免遷移之后 L1 L2 L3 高速緩存失效，盡可能遷移那些和當(dāng)前邏輯 CPU 共享高速緩存的目標(biāo)邏輯 CPU，離當(dāng)前邏輯 CPU 越近越好。

　　內(nèi)核將進(jìn)程抽象為調(diào)度實(shí)體，為的是可以將一批進(jìn)程進(jìn)行統(tǒng)一調(diào)度，在每一個(gè)調(diào)度層次上，都保證公平。

　　所謂選中高優(yōu)進(jìn)程，實(shí)際上選中的是虛擬時(shí)間較小的進(jìn)程，進(jìn)程的虛擬時(shí)間是根據(jù)進(jìn)程的實(shí)際優(yōu)先級(jí)和進(jìn)程的運(yùn)行時(shí)間等信息動(dòng)態(tài)計(jì)算出來(lái)的。

　　 context_switch()：執(zhí)行上下文切換
　　進(jìn)程上下文切換，核心要切換的是虛擬內(nèi)存及一些通用寄存器。

　　進(jìn)程切換虛擬內(nèi)存，需要切換對(duì)應(yīng)的 TLB 中的 ASID 及頁(yè)表，頁(yè)表也即不同進(jìn)程的虛擬內(nèi)存翻譯需要的 "map"。

　　進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中，有一個(gè)間接字段 cpu_context 保存了通用寄存器的值，寄存器切換的本質(zhì)就是將上一個(gè)進(jìn)程的寄存器保存到 cpu_context 字段，然后再將下一個(gè)進(jìn)程的 cpu_context 數(shù)據(jù)結(jié)構(gòu)中的字段加載到寄存器中，至此完成進(jìn)程的切換。

　　1 操作系統(tǒng)理論層面
　　學(xué)過(guò)操作系統(tǒng)的同學(xué)應(yīng)該都知道，進(jìn)程調(diào)度分為如下兩個(gè)步驟：

　　根據(jù)某種算法從就緒隊(duì)列中選中一個(gè)進(jìn)程。

　　執(zhí)行進(jìn)程上下文切換。

　　其中第二個(gè)步驟又可以分為：

　　切換虛擬內(nèi)存。

　　切換寄存器，即保存上一個(gè)進(jìn)程的寄存器到進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中，加載下一個(gè)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)到寄存器中。

　　關(guān)于虛擬內(nèi)存相關(guān)的邏輯，后續(xù)文章會(huì)詳細(xì)剖析，這篇文章會(huì)簡(jiǎn)要概括。

　　這篇文章，我們從內(nèi)核源碼的角度來(lái)剖析 Linux 是如何來(lái)實(shí)現(xiàn)進(jìn)程調(diào)度的核心邏輯，基本上遵從操作系統(tǒng)理論。

　　2 調(diào)度主函數(shù)
　　Linux 進(jìn)程調(diào)度的主函數(shù)是 schedule() 和 __schedule()，從源碼中可以看出兩者的關(guān)系：

　　// kernel/sched/core.c:3522
　　void schedule(void) {
　　    ...
　　    // 調(diào)度過(guò)程中禁止搶占
　　    preempt_disable();
　　    __schedule(false); //:3529
　　    // 調(diào)度完了，可以搶占了
　　    sched_preempt_enable_no_resched();
　　    ...
　　}
　　// kernel/sched/core.c:3395
　　__schedule(bool preempt) {
　　    ...
　　}
　　當(dāng)一個(gè)進(jìn)程主動(dòng)讓出 CPU，比如 yield 系統(tǒng)調(diào)用，會(huì)執(zhí)行 schedule() 方法，在執(zhí)行進(jìn)程調(diào)度的過(guò)程中，禁止其他進(jìn)程搶占當(dāng)前進(jìn)程，說(shuō)白了就是讓當(dāng)前進(jìn)程好好完成這一次進(jìn)程切換，不要?jiǎng)儕Z它的 CPU；

　　3529 行代碼表示 schedule() 調(diào)用了 __schedule(false) 方法，傳遞 fasle 參數(shù)，表示這是進(jìn)程的一次主動(dòng)調(diào)度，不可搶占。

　　等當(dāng)前的進(jìn)程執(zhí)行完調(diào)度邏輯之后，開(kāi)啟搶占，也就是說(shuō)，其他進(jìn)程可以剝奪當(dāng)前進(jìn)程的 CPU 了。

　　而如果某個(gè)進(jìn)程像個(gè)強(qiáng)盜一樣一直占著 CPU 不讓，內(nèi)核會(huì)通過(guò)搶占機(jī)制（比如上一篇文章提到的周期調(diào)度機(jī)制）進(jìn)行一次進(jìn)程調(diào)度，從而把當(dāng)前進(jìn)程從 CPU 上踢出去。

　　__schedule() 方法的框架便是這篇文章分析的主要內(nèi)容，由于代碼較多，我會(huì)挑選核心部分來(lái)描述。

　　3 __schedule() 方法核心邏輯概覽
　　我們先來(lái)看看 Linux 內(nèi)核中，進(jìn)程調(diào)度核心函數(shù) __schedule() 的框架：

　　// kernel/sched/core.c:3395
　　void __schedule(bool preempt) {
　　    struct task_struct *prev, *next;
　　    unsigned long *switch_count;
　　    struct rq *rq;
　　    int cpu;
　　    // 獲取當(dāng)前 CPU
　　    cpu = smp_processor_id();
　　    // 獲取當(dāng)前 CPU 上的進(jìn)程隊(duì)列
　　    rq = cpu_rq(cpu);
　　    // 獲取當(dāng)前隊(duì)列上正在運(yùn)行的進(jìn)程
　　    prev = rq->curr;
　　    ...
　　    // nivcsw：進(jìn)程非主動(dòng)切換次數(shù)
　　    switch_count = &prev->nivcsw; // :3430
　　    if (!preempt ...) {
　　        ...
　　        // nvcsw：進(jìn)程主動(dòng)切換次數(shù)
　　        switch_count = &prev->nvcsw; // :3456
　　    }
　　    ...
　　    // 1 根據(jù)某種算法從就緒隊(duì)列中選中一個(gè)進(jìn)程
　　    next = pick_next_task(rq, prev, &rf);
　　    ...
　　    if (prev != next) {
　　        rq->nr_switches++;
　　        rq->curr = next;
　　        ++*switch_count;
　　        // 2 執(zhí)行進(jìn)程上下文切換
　　        rq = context_switch(rq, prev, next, &rf);
　　    }
　　    ...
　　}
　　可以看到，__schedule() 方法中，進(jìn)程切換的核心步驟和操作系統(tǒng)理論中是一致的（1 和 2 兩個(gè)核心步驟）。

　　此外，進(jìn)程切換的過(guò)程中，內(nèi)核會(huì)根據(jù)是主動(dòng)發(fā)起調(diào)度（preempt 為 fasle）還是被動(dòng)發(fā)起調(diào)度，來(lái)統(tǒng)計(jì)進(jìn)程上下文切換的次數(shù)，分別保存在進(jìn)程的數(shù)據(jù)結(jié)構(gòu) task_struct 中：

　　// include/linux/sched.h:592
　　struct task_struct {
　　    ...
　　    // 主動(dòng)切換：Number of Voluntary（自愿） Context Switches
　　    unsigned long nvcsw; // :811
　　    // 非主動(dòng)切換：Number of InVoluntary（非自愿） Context Switches
　　    unsigned long nivcsw; // :812
　　    ...
　　};
　　在 Linux 中，我們可以通過(guò) pidstat 命令來(lái)查看一個(gè)進(jìn)程的主動(dòng)和被動(dòng)上下文切換的次數(shù)，我們寫(xiě)一個(gè)簡(jiǎn)單的 c 程序來(lái)做個(gè)測(cè)試：

　　// test.c
　　#include <stdlib.h>
　　#include <stdio.h>
　　int main() {
　　    while (1) {
　　        // 每隔一秒主動(dòng)休眠一次
　　        // 即主動(dòng)讓出 CPU
　　        // 理論上每秒都會(huì)主動(dòng)切換一次
　　        sleep(1)
　　    }
　　}
　　然后編譯運(yùn)行

　　gcc test.c -o test
　　./test
　　通過(guò) pidstat 來(lái)查看

　　Linux進(jìn)程調(diào)度的邏輯是什么

　　可以看到，test 應(yīng)用程序每秒主動(dòng)切換一次進(jìn)程上下文，和我們的預(yù)期相符，對(duì)應(yīng)的上下文切換數(shù)據(jù)就是從 task_struct 中獲取的。

　　接下來(lái)，詳細(xì)分析進(jìn)程調(diào)度的兩個(gè)核心步驟:

　　通過(guò) pick_next_task() 從就緒隊(duì)列中選中一個(gè)進(jìn)程。

　　通過(guò) context_switch 執(zhí)行上下文切換。

　　4 pick_next_task()：從就緒隊(duì)列中選中一個(gè)進(jìn)程
　　我們回顧一下 pick_next_task() 在 __schedule() 方法中的位置

　　// kernel/sched/core.c:3395
　　void __schedule(bool preempt) {
　　    ...
　　    // rq 是當(dāng)前 cpu 上的進(jìn)程隊(duì)列
　　    next = pick_next_task(rq, pre ...); // :3459
　　    ...
　　}
　　跟著調(diào)用鏈往下探索：

　　// kernel/sched/core.c:3316
　　/*
　　 * 找出優(yōu)先級(jí)最高的進(jìn)程
　　 * Pick up the highest-prio task:
　　 */
　　struct task_struct *pick_next_task(rq, pre ...) {
　　    struct task_struct *p;
　　    ...
　　    p = fair_sched_class.pick_next_task(rq, prev ...); // :3331
　　    ...
　　    if (!p)
　　        p = idle_sched_class.pick_next_task(rq, prev ...); // :3337
　　    return p;
　　}
　　從 pick_next_task() 方法的注釋上也能看到，這個(gè)方法的目的就是找出優(yōu)先級(jí)最高的進(jìn)程，由于系統(tǒng)中大多數(shù)進(jìn)程的調(diào)度類型都是公平調(diào)度，我們拿公平調(diào)度相關(guān)的邏輯來(lái)分析。

　　從上述的核心框架中可以看到，3331 行先嘗試從公平調(diào)度類型的隊(duì)列中獲取進(jìn)程，3337 行，如果沒(méi)有找到，就把每個(gè) CPU 上的 IDLE 進(jìn)程取出來(lái)運(yùn)行：

　　// kernel/sched/idle.c:442
　　const struct sched_class idle_sched_class = {
　　    ...
　　    .pick_next_task    = pick_next_task_idle, // :451
　　    ...
　　};
　　// kernel/sched/idle.c:385
　　struct task_struct * pick_next_task_idle(struct rq *rq ...) {
　　    ...
　　    // 每一個(gè) CPU 運(yùn)行隊(duì)列中都有一個(gè) IDLE 進(jìn)程
　　    return rq->idle; // :383
　　}
　　接下來(lái)，我們聚焦公平調(diào)度類的進(jìn)程選中算法 fair_sched_class.pick_next_task()

　　// kernel/sched/fair.c:10506
　　const struct sched_class fair_sched_class = {
　　   ...
　　   .pick_next_task = pick_next_task_fair, // : 10515
　　   ...
　　}
　　// kernel/sched/fair.c:6898
　　static struct task_struct * pick_next_task_fair(struct rq *rq ...) {
　　    // cfs_rq 是當(dāng)前 CPU 上公平調(diào)度類隊(duì)列
　　    struct cfs_rq *cfs_rq = &rq->cfs;
　　    struct sched_entity *se;
　　    struct task_struct *p;
　　    int new_tasks;
　　again:
　　    // 1 當(dāng)前 CPU 進(jìn)程隊(duì)列沒(méi)有進(jìn)程可調(diào)度，則執(zhí)行負(fù)載均衡邏輯
　　    if (!cfs_rq->nr_running)
　　        goto idle;
　　    // 2. 當(dāng)前 CPU 進(jìn)程隊(duì)列有進(jìn)程可調(diào)度，選中一個(gè)高優(yōu)進(jìn)程 p
　　    do {
　　        struct sched_entity *curr = cfs_rq->curr;
　　        ...
　　        se = pick_next_entity(cfs_rq, curr);
　　        cfs_rq = group_cfs_rq(se);
　　    } while (cfs_rq);
　　    p = task_of(se);
　　    ...
　　idle:
　　    // 通過(guò)負(fù)載均衡遷移進(jìn)程
　　    new_tasks = idle_balance(rq, rf); // :7017
　　    ...
　　
　　    if (new_tasks > 0)
　　        goto again;
　　    return NULL;
　　}
　　pick_next_task_fair() 的邏輯相對(duì)還是比較復(fù)雜的，但是，其中的核心思想分為兩步：

　　如果當(dāng)前 CPU 上已無(wú)進(jìn)程可調(diào)度，則執(zhí)行負(fù)載邏輯，從其他 CPU 上遷移進(jìn)程過(guò)來(lái)；

　　如果當(dāng)前 CPU 上有進(jìn)程可調(diào)度，從隊(duì)列中選擇一個(gè)高優(yōu)進(jìn)程，所謂高優(yōu)進(jìn)程，即虛擬時(shí)間最小的進(jìn)程；

　　下面，我們分兩步拆解上述步驟。

　　4.1 負(fù)載均衡邏輯
　　內(nèi)核為了讓各 CPU 負(fù)載能夠均衡，在某些 CPU 較為空閑的時(shí)候，會(huì)從繁忙的 CPU 上遷移進(jìn)程到空閑 CPU 上運(yùn)行，當(dāng)然，如果進(jìn)程設(shè)置了 CPU 的親和性，即進(jìn)程只能在某些 CPU 上運(yùn)行，則此進(jìn)程無(wú)法遷移。

　　負(fù)載均衡的核心邏輯是 idle_balance 方法：

　　// kernel/sched/fair.c:9851
　　static int idle_balance(struct rq *this_rq ...) {
　　    int this_cpu = this_rq->cpu;
　　    struct sched_domain *sd;
　　    int pulled_task = 0;
　　
　　    ...
　　    for_each_domain(this_cpu, sd) { // :9897
　　        ...
　　        pulled_task = load_balance(this_cpu...);
　　        ...
　　        if (pulled_task ...) // :9912
　　            break;
　　    }
　　
　　    ...
　　    return pulled_task;
　　}
　　idle_balance() 方法的邏輯也相對(duì)比較復(fù)雜：但是大體上概括就是，遍歷當(dāng)前 CPU 的所有調(diào)度域，直到遷移出進(jìn)程位置。

　　這里涉及到一個(gè)核心概念：sched_domain，即調(diào)度域，下面用一張圖介紹一下什么是調(diào)度域。

　　Linux進(jìn)程調(diào)度的邏輯是什么

　　內(nèi)核根據(jù)處理器與主存的距離將處理器分為兩個(gè) NUMA 節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有兩個(gè)處理器。NUMA 指的是非一致性訪問(wèn)，每個(gè) NUMA 節(jié)點(diǎn)中的處理器訪問(wèn)內(nèi)存節(jié)點(diǎn)的速度不一致，不同 NUMA 節(jié)點(diǎn)之間不共享 L1 L2 L3 Cache。

　　每個(gè) NUMA 節(jié)點(diǎn)下有兩個(gè)處理器，同一個(gè) NUMA 下的不同處理器共享 L3 Cache。

　　每個(gè)處理器下有兩個(gè) CPU 核，同個(gè)處理器下的不同核共享 L2 L3 Cache。

　　每個(gè)核下面有兩個(gè)超線程，同一個(gè)核的不同超線程共享 L1 L2 L3 Cache。

　　我們?cè)趹?yīng)用程序里面，通過(guò)系統(tǒng) API 拿到的都是超線程，也可以叫做邏輯 CPU，下文統(tǒng)稱邏輯 CPU。

　　進(jìn)程在訪問(wèn)一個(gè)某個(gè)地址的數(shù)據(jù)的時(shí)候，會(huì)先在 L1 Cache 中找，若未找到，則在 L2 Cache 中找，再未找到，則在 L3 Cache 上找，最后都沒(méi)找到，就訪問(wèn)主存，而訪問(wèn)速度方面 L1 > L2 > L3 > 主存，內(nèi)核遷移進(jìn)程的目標(biāo)是盡可能讓遷移出來(lái)的進(jìn)程能夠命中緩存。

　　內(nèi)核按照上圖中被虛線框起來(lái)的部分，抽象出調(diào)度域的概念，越靠近上層，調(diào)度域的范圍越大，緩存失效的概率越大，因此，遷移進(jìn)程的一個(gè)目標(biāo)是，盡可能在低級(jí)別的調(diào)度域中獲取可遷移的進(jìn)程。

　　上述代碼 idle_balance() 方法的 9897 行：for_each_domain(this_cpu, sd)，this_cpu 就是邏輯 CPU（也即是最底層的超線程概念），sd 是調(diào)度域，這行代碼的邏輯就是逐層往上擴(kuò)大調(diào)度域；

　　// kernel/sched/sched.h:1268
　　#define for_each_domain(cpu, __sd) /
　　    for (__sd = cpu_rq(cpu)->sd); /
　　            __sd; __sd = __sd->parent)
　　而 idle_balance() 方法的 9812 行，如果在某個(gè)調(diào)度域中，成功遷移出了進(jìn)程到當(dāng)前邏輯 CPU，就終止循環(huán)，可見(jiàn)，內(nèi)核為了提升應(yīng)用性能真是煞費(fèi)苦心。

　　經(jīng)過(guò)負(fù)載均衡之后，當(dāng)前空閑的邏輯 CPU 進(jìn)程隊(duì)列很有可能已經(jīng)存在就緒進(jìn)程了，于是，接下來(lái)從這個(gè)隊(duì)列中獲取最合適的進(jìn)程。

　　4.2 選中高優(yōu)進(jìn)程
　　接下來(lái)，我們把重點(diǎn)放到如何選擇高優(yōu)進(jìn)程，而在公平調(diào)度類中，會(huì)通過(guò)進(jìn)程的實(shí)際優(yōu)先級(jí)和運(yùn)行時(shí)間，來(lái)計(jì)算一個(gè)虛擬時(shí)間，虛擬時(shí)間越少，被選中的概率越高，所以叫做公平調(diào)度。

　　以下是選擇高優(yōu)進(jìn)程的核心邏輯：

　　// kernel/sched/fair.c:6898
　　static struct task_struct * pick_next_task_fair(struct rq *rq ...) {
　　    // cfs_rq 是當(dāng)前 CPU 上公平調(diào)度類隊(duì)列
　　    struct cfs_rq *cfs_rq = &rq->cfs;
　　    struct sched_entity *se;
　　    struct task_struct *p;
　　    // 2. 當(dāng)前 CPU 進(jìn)程隊(duì)列有進(jìn)程可調(diào)度，選中一個(gè)高優(yōu)進(jìn)程 p
　　    do {
　　        struct sched_entity *curr = cfs_rq->curr;
　　        ...
　　        se = pick_next_entity(cfs_rq, curr);
　　        cfs_rq = group_cfs_rq(se);
　　    } while (cfs_rq);
　　    // 拿到被調(diào)度實(shí)體包裹的進(jìn)程
　　    p = task_of(se); // :6956
　　    ...
　　    return p;
　　}
　　內(nèi)核提供一個(gè)調(diào)度實(shí)體的的概念，對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)叫 sched_entity，內(nèi)核實(shí)際上是根據(jù)調(diào)度實(shí)體為單位進(jìn)行調(diào)度的：

　　// include/linux/sched.h:447
　　struct sched_entity {
　　    ...
　　    // 當(dāng)前調(diào)度實(shí)體的父親
　　    struct sched_entity    *parent;
　　    // 當(dāng)前調(diào)度實(shí)體所在隊(duì)列
　　    struct cfs_rq *cfs_rq; // :468
　　    // 當(dāng)前調(diào)度實(shí)體擁有的隊(duì)列，及子調(diào)度實(shí)體隊(duì)列
　　    // 進(jìn)程是底層實(shí)體，不擁有隊(duì)列
　　    struct cfs_rq *my_q;
　　    ...
　　};
　　每一個(gè)進(jìn)程對(duì)應(yīng)一個(gè)調(diào)度實(shí)體，若干調(diào)度實(shí)體綁定到一起可以形成一個(gè)更高層次的調(diào)度實(shí)體，因此有個(gè)遞歸的效應(yīng)，上述 do while 循環(huán)的邏輯就是從當(dāng)前邏輯 CPU 頂層的公平調(diào)度實(shí)體（cfs_rq->curr）開(kāi)始，逐層選擇虛擬時(shí)間較少的調(diào)度實(shí)體進(jìn)行調(diào)度，直到最后一個(gè)調(diào)度實(shí)體是進(jìn)程。

　　內(nèi)核這樣做的原因是希望盡可能在每個(gè)層次上，都能夠保證調(diào)度是公平的。

　　拿 Docker 容器的例子來(lái)說(shuō)，一個(gè) Docker 容器中運(yùn)行了若干個(gè)進(jìn)程，這些進(jìn)程屬于同一個(gè)調(diào)度實(shí)體，和宿主機(jī)上的進(jìn)程的調(diào)度實(shí)體屬于同一層級(jí)，所以，如果 Docker 容器中瘋狂 fork 進(jìn)程，內(nèi)核會(huì)計(jì)算這些進(jìn)程的虛擬時(shí)間總和來(lái)和宿主機(jī)其他進(jìn)程進(jìn)行公平抉擇，這些進(jìn)程休想一直霸占著 CPU！

　　選擇虛擬時(shí)間最少的進(jìn)程的邏輯是 se = pick_next_entity(cfs_rq, curr); ，相應(yīng)邏輯如下：

　　// kernel/sched/fair.c:4102
　　struct sched_entity *
　　pick_next_entity(cfs_rq *cfs_rq, sched_entity *curr) {
　　    // 公平運(yùn)行隊(duì)列中虛擬時(shí)間最小的調(diào)度實(shí)體
　　    struct sched_entity *left = __pick_first_entity(cfs_rq);
　　    struct sched_entity *se;
　　    // 如果沒(méi)找到或者樹(shù)中的最小虛擬時(shí)間的進(jìn)程
　　    // 還沒(méi)當(dāng)前調(diào)度實(shí)體小，那就選擇當(dāng)前實(shí)體
　　    if (!left || (curr && entity_before(curr, left)))
　　        left = curr;
　　    se = left;
　　    return se;
　　}
　　// kernel/sched/fair.c:489
　　int entity_before(struct sched_entity *a, struct sched_entity *b) {
　　    // 比較兩者虛擬時(shí)間
　　    return (s64)(a->vruntime - b->vruntime) < 0;
　　}
　　上述代碼，我們可以分析出，pick_next_entity() 方法會(huì)在當(dāng)前公平調(diào)度隊(duì)列 cfs_rq 中選擇最靠左的調(diào)度實(shí)體，最靠左的調(diào)度實(shí)體的虛擬時(shí)間越小，即最優(yōu)。

　　而下面通過(guò) __pick_first_entity() 方法，我們了解到，公平調(diào)度隊(duì)列 cfs_rq 中的調(diào)度實(shí)體被組織為一棵紅黑樹(shù)，這棵樹(shù)的最左側(cè)節(jié)點(diǎn)即為最小節(jié)點(diǎn)：

　　// kernel/sched/fair.c:565
　　struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) {
　　    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
　　    if (!left)
　　        return NULL;
　　    return rb_entry(left, struct sched_entity, run_node);
　　}
　　// include/linux/rbtree.h:91
　　// 緩存了紅黑樹(shù)最左側(cè)節(jié)點(diǎn)
　　#define rb_first_cached(root) (root)->rb_leftmost
　　通過(guò)以上分析，我們依然通過(guò)一個(gè) Docker 的例子來(lái)分析：一個(gè)宿主機(jī)中有兩個(gè)普通進(jìn)程分別為 A，B，一個(gè) Docker 容器，容器中有 c1、c2、c3 進(jìn)程。

　　這種情況下，系統(tǒng)中有兩個(gè)層次的調(diào)度實(shí)體，最高層為 A、B、c1+c2+c3，再往下為 c1、c2、c3，下面我們分情況來(lái)討論進(jìn)程選中的邏輯：

　　1）若虛擬時(shí)間分布為：A:100s，B:200s，c1:50s，c2:100s，c3:80s

　　選中邏輯：先比較 A、B、c1+c2+c3 的虛擬時(shí)間，發(fā)現(xiàn) A 最小，由于 A 已經(jīng)是進(jìn)程，選中 A，如果 A 比當(dāng)前運(yùn)行進(jìn)程虛擬時(shí)間還小，下一個(gè)運(yùn)行的進(jìn)程就是 A，否則保持當(dāng)前進(jìn)程不變。

　　2）若虛擬時(shí)間分布為：A:100s，B:200s，c1:50s，c2:30s，c3:10s

　　選中邏輯：先比較 A、B、c1+c2+c3 的虛擬時(shí)間，發(fā)現(xiàn) c1+c2+c3 最小，由于選中的調(diào)度實(shí)體非進(jìn)程，而是一組進(jìn)程，繼續(xù)往下一層調(diào)度實(shí)體進(jìn)行選擇，比較 c1、c2、c3 的虛擬時(shí)間，發(fā)現(xiàn) c3 的虛擬時(shí)間最小，如果 c3 的虛擬時(shí)間小于當(dāng)前進(jìn)程的虛擬時(shí)間，下一個(gè)運(yùn)行的進(jìn)程就是 c3，否則保持當(dāng)前進(jìn)程不變。

　　到這里，選中高優(yōu)進(jìn)程進(jìn)行調(diào)度的邏輯就結(jié)束了，我們來(lái)做下小結(jié)。

　　4.3 pick_next_task() 小結(jié)
　　內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候，會(huì)先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度，如果沒(méi)有，執(zhí)行進(jìn)程遷移邏輯，從其他 CPU 遷移進(jìn)程，如果有，則選擇虛擬時(shí)間較小的進(jìn)程進(jìn)行調(diào)度。

　　內(nèi)核在選擇邏輯 CPU 進(jìn)行遷移進(jìn)程的時(shí)候，為了提升被遷移進(jìn)程的性能，即避免遷移之后 L1 L2 L3 高速緩存失效，盡可能遷移那些和當(dāng)前邏輯 CPU 共享高速緩存的目標(biāo)邏輯 CPU，離當(dāng)前邏輯 CPU 越近越好。

　　內(nèi)核將進(jìn)程抽象為調(diào)度實(shí)體，為的是可以將一批進(jìn)程進(jìn)行統(tǒng)一調(diào)度，在每一個(gè)調(diào)度層次上，都保證公平。

　　所謂選中高優(yōu)進(jìn)程，實(shí)際上選中的是虛擬時(shí)間較小的進(jìn)程，進(jìn)程的虛擬時(shí)間是根據(jù)進(jìn)程的實(shí)際優(yōu)先級(jí)和進(jìn)程的運(yùn)行時(shí)間等信息動(dòng)態(tài)計(jì)算出來(lái)的。

　　5 context_switch()：執(zhí)行上下文切換
　　選中一個(gè)合適的進(jìn)程之后，接下來(lái)就要執(zhí)行實(shí)際的進(jìn)程切換了，我們把目光重新聚焦到 __schedule() 方法

　　// kernel/sched/core.c:3395
　　void __schedule(bool preempt) {
　　    struct task_struct *prev, *next;
　　    ...
　　    // 1 根據(jù)某種算法從就緒隊(duì)列中選中一個(gè)進(jìn)程
　　    next = pick_next_task(rq, prev,...); // :3459
　　    ...
　　    if (prev != next) {
　　        rq->curr = next;
　　        // 2 執(zhí)行進(jìn)程上下文切換
　　        rq = context_switch(rq, prev, next ...); // ::3485
　　    }
　　    ...
　　}
　　其中，進(jìn)程上下文切換的核心邏輯就是 context_switch，對(duì)應(yīng)邏輯如下：

　　// kernel/sched/core.c:2804
　　struct rq *context_switch(... task_struct *prev, task_struct *next ...) {
　　    struct mm_struct *mm, *oldmm;
　　    ...
　　    mm = next->mm;
　　    oldmm = prev->active_mm;
　　    ...
　　    // 1 切換虛擬內(nèi)存
　　    switch_mm_irqs_off(oldmm, mm, next);
　　    ...
　　    // 2 切換寄存器狀態(tài)
　　    switch_to(prev, next, prev);
　　    ...
　　}
　　上述代碼，我略去了一些細(xì)節(jié)，保留我們關(guān)心的核心邏輯。context_switch() 核心邏輯分為兩個(gè)步驟，切換虛擬內(nèi)存和寄存器狀態(tài)，下面，我們展開(kāi)這兩段邏輯。

　　5.1 切換虛擬內(nèi)存
　　首先，簡(jiǎn)要介紹一下虛擬內(nèi)存的幾個(gè)知識(shí)點(diǎn)：

　　進(jìn)程無(wú)法直接訪問(wèn)到物理內(nèi)存，而是通過(guò)虛擬內(nèi)存到物理內(nèi)存的映射機(jī)制間接訪問(wèn)到物理內(nèi)存的。

　　每個(gè)進(jìn)程都有自己獨(dú)立的虛擬內(nèi)存地址空間。如，進(jìn)程 A 可以有一個(gè)虛擬地址 0x1234 映射到物理地址 0x4567，進(jìn)程 B 也可以有一個(gè)虛擬地址 0x1234 映射到 0x3456，即不同進(jìn)程可以有相同的虛擬地址。如果他們指向的物理內(nèi)存相同，則兩個(gè)進(jìn)程即可通過(guò)內(nèi)存共享進(jìn)程通信。

　　進(jìn)程通過(guò)多級(jí)頁(yè)表機(jī)制來(lái)執(zhí)行虛擬內(nèi)存到物理內(nèi)存的映射，如果我們簡(jiǎn)單地把這個(gè)機(jī)制當(dāng)做一個(gè) map<虛擬地址，物理地址> 數(shù)據(jù)結(jié)構(gòu)的話，那么可以理解為不同的進(jìn)程有維護(hù)著不同的 map；

　　map<虛擬地址，物理地址> 的翻譯是通過(guò)多級(jí)頁(yè)表來(lái)實(shí)現(xiàn)的，訪問(wèn)多級(jí)頁(yè)表需要多次訪問(wèn)內(nèi)存，效率太差，因此，內(nèi)核使用 TLB 緩存頻繁被訪問(wèn)的 <虛擬地址，物理地址> 的項(xiàng)目，感謝局部性原理。

　　由于不同進(jìn)程可以有相同的虛擬地址，這些虛擬地址往往指向了不同的物理地址，因此，TLB 實(shí)際上是通過(guò) <ASID + 虛擬地址，物理地址> 的方式來(lái)唯一確定某個(gè)進(jìn)程的物理地址的，ASID 叫做地址空間 ID（Address Space ID），每個(gè)進(jìn)程唯一，等價(jià)于多租戶概念中的租戶 ID。

　　進(jìn)程的虛擬地址空間用數(shù)據(jù)結(jié)構(gòu) mm_struct 來(lái)描述，進(jìn)程數(shù)據(jù)結(jié)構(gòu) task_struct 中的 mm 字段就指向此數(shù)據(jù)結(jié)構(gòu)，而上述所說(shuō)的進(jìn)程的 "map" 的信息就藏在 mm_struct 中。

　　關(guān)于虛擬內(nèi)存的介紹，后續(xù)的文章會(huì)繼續(xù)分析，這里，我們只需要了解上述幾個(gè)知識(shí)點(diǎn)即可，我們進(jìn)入到切換虛擬內(nèi)存核心邏輯：

　　// include/linux/mmu_context.h:14
　　# define switch_mm_irqs_off switch_mm
　　// arch/arm64/include/asm/mmu_context.h:241
　　void switch_mm(mm_struct *prev, mm_struct *next) {
　　    // 如果兩個(gè)進(jìn)程不是同一個(gè)進(jìn)程
　　    if (prev != next)
　　        __switch_mm(next);
　　    ...
　　}
　　// arch/arm64/include/asm/mmu_context.h:224
　　void __switch_mm(struct mm_struct *next) {
　　    unsigned int cpu = smp_processor_id();
　　    check_and_switch_context(next, cpu);
　　}
　　接下來(lái)，調(diào)用 check_and_switch_context 做實(shí)際的虛擬內(nèi)存切換操作：

　　// arch/arm64/mm/context.c:194
　　void check_and_switch_context(struct mm_struct *mm, unsigned int cpu) {
　　    ...
　　    u64 asid;
　　    // 拿到要將下一個(gè)進(jìn)程的 ASID
　　    asid = atomic64_read(&mm->context.id); // :218
　　    ...
　　    // 將下一個(gè)進(jìn)程的 ASID 綁定到當(dāng)前 CPU
　　    atomic64_set(&per_cpu(active_asids, cpu), asid); // :236
　　    // 切換頁(yè)表，及切換我們上述中的 "map"，
　　    // 將 ASID 和 "map" 設(shè)置到對(duì)應(yīng)的寄存器
　　    cpu_switch_mm(mm->pgd, mm); // :248
　　}
　　check_and_switch_context 總體上分為兩塊邏輯：

　　將下一個(gè)進(jìn)程的 ASID 綁定到當(dāng)前的 CPU，這樣 TLB 通過(guò)虛擬地址翻譯出來(lái)的物理地址，就屬于下個(gè)進(jìn)程的。
　　拿到下一個(gè)進(jìn)程的 "map"，也就是頁(yè)表，對(duì)應(yīng)的字段是 "mm->pgd"，然后執(zhí)行頁(yè)表切換邏輯，這樣后續(xù)如果 TLB 沒(méi)命中，當(dāng)前 CPU 就能夠知道通過(guò)哪個(gè) "map" 來(lái)翻譯虛擬地址。
　　cpu_switch_mm 涉及的匯編代碼較多，這里就不貼了，本質(zhì)上就是將 ASID 和頁(yè)表（"map"）的信息綁定到對(duì)應(yīng)的寄存器。

　　5.2 切換通用寄存器
　　虛擬內(nèi)存切換完畢之后，接下來(lái)切換進(jìn)程執(zhí)行相關(guān)的通用寄存器，對(duì)應(yīng)邏輯為 switch_to(prev, next ...); 方法，這個(gè)方法也是切換進(jìn)程的分水嶺，調(diào)用完之后的那一刻，當(dāng)前 CPU 上執(zhí)行就是 next 的代碼了。

　　拿 arm64 為例：

　　// arch/arm64/kernel/process.c:422
　　struct task_struct *__switch_to(task_struct *prev, task_struct *next) {
　　    ...
　　    // 實(shí)際切換方法
　　    cpu_switch_to(prev, next); // :444
　　    ...
　　}
　　cpu_switch_to 對(duì)應(yīng)的是一段經(jīng)典的匯編邏輯，看著很多，其實(shí)并不難理解。

　　// arch/arm64/kernel/entry.S:1040
　　// x0 -> pre
　　// x1 -> next
　　ENTRY(cpu_switch_to)
　　    // x10 存放 task_struct->thread.cpu_context 字段偏移量
　　    mov    x10, #THREAD_CPU_CONTEXT // :1041
　　
　　    // ===保存 pre 上下文===
　　    // x8 存放 prev->thread.cpu_context
　　    add    x8, x0, x10
　　    // 保存 prev 內(nèi)核棧指針到 x9
　　    mov    x9, sp
　　    // 將 x19 ~ x28 保存在 cpu_context 字段中
　　    // stp 是 store pair 的意思
　　    stp    x19, x20, [x8], #16
　　    stp    x21, x22, [x8], #16
　　    stp    x23, x24, [x8], #16
　　    stp    x25, x26, [x8], #16
　　    stp    x27, x28, [x8], #16
　　    // 將 x29 存在 fp 字段，x9 存在 sp 字段
　　    stp    x29, x9, [x8], #16
　　    // 將 pc 寄存器 lr 保存到 cpu_context 的 pc 字段
　　    str    lr, [x8]
　　
　　
　　    // ===加載 next 上下文===
　　    // x8 存放 next->thread.cpu_context
　　    add    x8, x1, x10
　　    // 將 cpu_context 中字段載入到 x19 ~ x28
　　    // ldp 是 load pair 的意思
　　    ldp    x19, x20, [x8], #16
　　    ldp    x21, x22, [x8], #16
　　    ldp    x23, x24, [x8], #16
　　    ldp    x25, x26, [x8], #16
　　    ldp    x27, x28, [x8], #16
　　    ldp    x29, x9, [x8], #16
　　    // 設(shè)置 pc 寄存器
　　    ldr    lr, [x8]
　　    // 切換到 next 的內(nèi)核棧
　　    mov    sp, x9
　　
　　    // 將 next 指針保存到 sp_el0 寄存器
　　    msr    sp_el0, x1
　　    ret
　　ENDPROC(cpu_switch_to)
　　上述匯編的邏輯可以和操作系統(tǒng)理論課里的內(nèi)容一一對(duì)應(yīng)，即先將通用寄存器的內(nèi)容保存到進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中對(duì)應(yīng)的字段，然后再?gòu)南乱粋€(gè)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中對(duì)應(yīng)的字段加載到通用寄存器中。

　　1041 行代碼是拿到 task_struct 結(jié)構(gòu)中的 thread_struct thread 字段的 cpu_contxt 字段：

　　// arch/arm64/kernel/asm-offsets.c:53
　　DEFINE(THREAD_CPU_CONTEXT,    offsetof(struct task_struct, thread.cpu_context));
　　我們來(lái)分析一下對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)：

　　// include/linux/sched.h:592
　　struct task_struct {
　　    ...
　　    struct thread_struct thread; // :1212
　　    ...
　　};
　　// arch/arm64/include/asm/processor.h:129
　　struct thread_struct {
　　    struct cpu_context cpu_context;
　　    ...
　　}
　　而 cpu_context 數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)就是為了保存與進(jìn)程有關(guān)的一些通用寄存器的值：

　　// arch/arm64/include/asm/processor.h:113
　　struct cpu_context {
　　    unsigned long x19;
　　    unsigned long x20;
　　    unsigned long x21;
　　    unsigned long x22;
　　    unsigned long x23;
　　    unsigned long x24;
　　    unsigned long x25;
　　    unsigned long x26;
　　    unsigned long x27;
　　    unsigned long x28;
　　    // 對(duì)應(yīng) x29 寄存器
　　    unsigned long fp;
　　    unsigned long sp;
　　    // 對(duì)應(yīng) lr 寄存器
　　    unsigned long pc;
　　};
　　這些值剛好與上述匯編片段的代碼一一對(duì)應(yīng)上，讀者應(yīng)該不需要太多匯編基礎(chǔ)就可以分析出來(lái)。

　　上述匯編中，最后一行 msr sp_el0, x1，x1 寄存器中保存了 next 的指針，這樣后續(xù)再調(diào)用 current 宏的時(shí)候，就指向了下一個(gè)指針：

　　// arch/arm64/include/asm/current.h:15
　　static struct task_struct *get_current(void) {
　　    unsigned long sp_el0;
　　    asm ("mrs %0, sp_el0" : "=r" (sp_el0));
　　    return (struct task_struct *)sp_el0;
　　}
　　// current 宏，很多地方會(huì)使用到
　　#define current get_current()
　　進(jìn)程上下文切換的核心邏輯到這里就結(jié)束了，最后我們做下小結(jié)。

　　5.3 context_switch() 小結(jié)
　　進(jìn)程上下文切換，核心要切換的是虛擬內(nèi)存及一些通用寄存器。

　　進(jìn)程切換虛擬內(nèi)存，需要切換對(duì)應(yīng)的 TLB 中的 ASID 及頁(yè)表，頁(yè)表也即不同進(jìn)程的虛擬內(nèi)存翻譯需要的 "map"。

　　進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中，有一個(gè)間接字段 cpu_context 保存了通用寄存器的值，寄存器切換的本質(zhì)就是將上一個(gè)進(jìn)程的寄存器保存到 cpu_context 字段，然后再將下一個(gè)進(jìn)程的 cpu_context 數(shù)據(jù)結(jié)構(gòu)中的字段加載到寄存器中，至此完成進(jìn)程的切換。