本篇文章給大家?guī)砹岁P(guān)于linux中內(nèi)核源碼分析進(jìn)程調(diào)度邏輯的相關(guān)知識(shí)，希望對(duì)大家有幫助。

0.1 本文目錄結(jié)構(gòu)

1 操作系統(tǒng)理論層面

2 調(diào)度主函數(shù)

3 __schedule() 方法核心邏輯概覽

4 pick_next_task()：從就緒隊(duì)列中選中一個(gè)進(jìn)程

• 4.1 負(fù)載均衡邏輯

• 4.2 選中高優(yōu)進(jìn)程

• 4.3 pick_next_task() 小結(jié)

5 context_switch()：執(zhí)行上下文切換

• 5.1 切換虛擬內(nèi)存

• 5.2 切換通用寄存器

• 5.3 context_switch() 小結(jié)

6 本文總結(jié)

0.2 pick_next_task()：從就緒隊(duì)列中選中一個(gè)進(jìn)程

內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候，會(huì)首先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度，如果沒有，執(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ì)算出來的。

0.3 5 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é)過操作系統(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)核源碼的角度來剖析 Linux 是如何來實(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)度過程中禁止搶占     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)度的過程中，禁止其他進(jìn)程搶占當(dāng)前進(jìn)程，說白了就是讓當(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)度邏輯之后，開啟搶占，也就是說，其他進(jìn)程可以剝奪當(dāng)前進(jìn)程的 CPU 了。

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

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

3 __schedule() 方法核心邏輯概覽

我們先來看看 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)程切換的過程中，內(nèi)核會(huì)根據(jù)是主動(dòng)發(fā)起調(diào)度（preempt 為 fasle）還是被動(dòng)發(fā)起調(diào)度，來統(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 中，我們可以通過 pidstat 命令來查看一個(gè)進(jìn)程的主動(dòng)和被動(dòng)上下文切換的次數(shù)，我們寫一個(gè)簡(jiǎn)單的 c 程序來做個(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

通過 pidstat 來查看

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

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

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

通過 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)的邏輯來分析。

從上述的核心框架中可以看到，3331 行先嘗試從公平調(diào)度類型的隊(duì)列中獲取進(jìn)程，3337 行，如果沒有找到，就把每個(gè) CPU 上的 IDLE 進(jìn)程取出來運(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 }

接下來，我們聚焦公平調(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ì)列沒有進(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:     // 通過負(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)程過來；

如果當(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)度域。

內(nèi)核根據(jù)處理器與主存的距離將處理器分為兩個(gè) NUMA 節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)有兩個(gè)處理器。NUMA 指的是非一致性訪問，每個(gè) NUMA 節(jié)點(diǎ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)用程序里面，通過系統(tǒng) API 拿到的都是超線程，也可以叫做邏輯 CPU，下文統(tǒng)稱邏輯 CPU。

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

內(nè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)，可見，內(nèi)核為了提升應(yīng)用性能真是煞費(fèi)苦心。

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

4.2 選中高優(yōu)進(jìn)程

接下來，我們把重點(diǎn)放到如何選擇高優(yōu)進(jìn)程，而在公平調(diào)度類中，會(huì)通過進(jìn)程的實(shí)際優(yōu)先級(jí)和運(yùn)行時(shí)間，來計(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）開始，逐層選擇虛擬時(shí)間較少的調(diào)度實(shí)體進(jìn)行調(diào)度，直到最后一個(gè)調(diào)度實(shí)體是進(jìn)程。

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

拿 Docker 容器的例子來說，一個(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í)間總和來和宿主機(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;     // 如果沒找到或者樹中的最小虛擬時(shí)間的進(jìn)程     // 還沒當(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)。

而下面通過 __pick_first_entity() 方法，我們了解到，公平調(diào)度隊(duì)列 cfs_rq 中的調(diào)度實(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 // 緩存了紅黑樹最左側(cè)節(jié)點(diǎn) #define rb_first_cached(root) (root)->rb_leftmost

通過以上分析，我們依然通過一個(gè) Docker 的例子來分析： 一個(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，下面我們分情況來討論進(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é)束了，我們來做下小結(jié)。

4.3 pick_next_task() 小結(jié)

內(nèi)核在選擇進(jìn)程進(jìn)行調(diào)度的時(shí)候，會(huì)先判斷當(dāng)前 CPU 上是否有進(jìn)程可以調(diào)度，如果沒有，執(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ì)算出來的。

5 context_switch()：執(zhí)行上下文切換

選中一個(gè)合適的進(jìn)程之后，接下來就要執(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)，下面，我們展開這兩段邏輯。

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

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

進(jìn)程無(wú)法直接訪問到物理內(nèi)存，而是通過虛擬內(nèi)存到物理內(nèi)存的映射機(jī)制間接訪問到物理內(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)程即可通過內(nèi)存共享進(jìn)程通信。

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

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

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

進(jìn)程的虛擬地址空間用數(shù)據(jù)結(jié)構(gòu) mm_struct 來描述，進(jìn)程數(shù)據(jù)結(jié)構(gòu) task_struct 中的 mm 字段就指向此數(shù)據(jù)結(jié)構(gòu)，而上述所說的進(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); }

接下來，調(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 通過虛擬地址翻譯出來的物理地址，就屬于下個(gè)進(jìn)程的。

• 拿到下一個(gè)進(jìn)程的 "map"，也就是頁(yè)表，對(duì)應(yīng)的字段是 "mm->pgd"，然后執(zhí)行頁(yè)表切換邏輯，這樣后續(xù)如果 TLB 沒命中，當(dāng)前 CPU 就能夠知道通過哪個(gè) "map" 來翻譯虛擬地址。

cpu_switch_mm 涉及的匯編代碼較多，這里就不貼了，本質(zhì)上就是將 ASID 和頁(yè)表（"map"）的信息綁定到對(duì)應(yīng)的寄存器。

5.2 切換通用寄存器

虛擬內(nè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));

我們來分析一下對(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ǔ)就可以分析出來。

上述匯編中，最后一行 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)程的切換。

6 本文總結(jié)

最后，我們?nèi)淖鱿驴偨Y(jié)：

進(jìn)程調(diào)度分為主動(dòng)（非搶占）和被動(dòng)調(diào)度（搶占），調(diào)度的核心邏輯在 __schedule() 方法中。

進(jìn)程調(diào)度的核心邏輯分為兩個(gè)大步驟，其一是選擇一個(gè)合適的進(jìn)程，其二是進(jìn)行進(jìn)程切換。

在選擇合適的進(jìn)程中，如果當(dāng)前邏輯 CPU 沒有可調(diào)度的進(jìn)程，就從其他 CPU 來調(diào)度，遷移的進(jìn)程盡可能靠近當(dāng)前 CPU。

進(jìn)程調(diào)度的單位其實(shí)是調(diào)度實(shí)體，一個(gè)調(diào)度實(shí)體對(duì)應(yīng)一個(gè)或多個(gè)進(jìn)程，這樣就能夠在各個(gè)層次上完成公平調(diào)度，通過調(diào)度實(shí)體的虛擬時(shí)間選擇最優(yōu)調(diào)度實(shí)體對(duì)應(yīng)的進(jìn)程。

進(jìn)程切換，本質(zhì)上就是切換虛擬內(nèi)存及通用寄存器。

進(jìn)程調(diào)度的邏輯幾乎都完全遵循操作系統(tǒng)理論來設(shè)計(jì)的，學(xué)完操作系統(tǒng)之后，希望大家能夠理論聯(lián)系實(shí)際，對(duì)照著內(nèi)核去翻一翻源碼。