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

這篇文章主要介紹“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í)吧！

 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)查看

可以看到，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)度域。

內(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)程的切換。

到此，關(guān)于“Linux進(jìn)程調(diào)度的邏輯是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！