Linux核心原始碼分析之程序排程的邏輯（總結分享）

0.1 本文目錄結構

1 作業系統理論層面

2 排程主函數

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

4 pick_next_task()：從就緒佇列中選中一個程序

• 4.1 負載均衡邏輯

• 4.2 選中高優程序

• 4.3 pick_next_task() 小結

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

• 5.1 切換虛擬記憶體

• 5.2 切換通用暫存器

• 5.3 context_switch() 小結

6 本文總結

0.2 pick_next_task()：從就緒佇列中選中一個程序

核心在選擇程序進行排程的時候，會首先判斷當前 CPU 上是否有程序可以排程，如果沒有，執行程序遷移邏輯，從其他 CPU 遷移程序，如果有，則選擇虛擬時間較小的程序進行排程。

核心在選擇邏輯 CPU 進行遷移程序的時候，為了提升被遷移程序的效能，即避免遷移之後 L1 L2 L3 快取記憶體失效，儘可能遷移那些和當前邏輯 CPU 共用快取記憶體的目標邏輯 CPU，離當前邏輯 CPU 越近越好。

核心將程序抽象為排程實體，為的是可以將一批程序進行統一排程，在每一個排程層次上，都保證公平。

所謂選中高優程序，實際上選中的是虛擬時間較小的程序，程序的虛擬時間是根據程序的實際優先順序和程序的執行時間等資訊動態計算出來的。

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

程序上下文切換，核心要切換的是虛擬記憶體及一些通用暫存器。

程序切換虛擬記憶體，需要切換對應的 TLB 中的 ASID 及頁表，頁表也即不同程序的虛擬記憶體翻譯需要的 "map"。

程序的資料結構中，有一個間接欄位 cpu_context 儲存了通用暫存器的值，暫存器切換的本質就是將上一個程序的暫存器儲存到 cpu_context 欄位，然後再將下一個程序的 cpu_context 資料結構中的欄位載入到暫存器中，至此完成程序的切換。

1 作業系統理論層面

學過作業系統的同學應該都知道，程序排程分為如下兩個步驟：

根據某種演演算法從就緒佇列中選中一個程序。

執行程序上下文切換。

其中第二個步驟又可以分為：

切換虛擬記憶體。

切換暫存器，即儲存上一個程序的暫存器到程序的資料結構中，載入下一個程序的資料結構到暫存器中。

關於虛擬記憶體相關的邏輯，後續文章會詳細剖析，這篇文章會簡要概括。

這篇文章，我們從核心原始碼的角度來剖析 Linux 是如何來實現程序排程的核心邏輯，基本上遵從作業系統理論。

2 排程主函數

Linux 程序排程的主函數是 schedule() 和 __schedule()，從原始碼中可以看出兩者的關係：

// kernel/sched/core.c:3522
void schedule(void) {
    ...
    // 排程過程中禁止搶佔
    preempt_disable(); 
    __schedule(false); //:3529
    // 排程完了，可以搶佔了
    sched_preempt_enable_no_resched();
    ...
}
// kernel/sched/core.c:3395
__schedule(bool preempt) { 
    ... 
}

當一個程序主動讓出 CPU，比如 yield 系統呼叫，會執行 schedule() 方法，在執行程序排程的過程中，禁止其他程序搶佔當前程序，說白了就是讓當前程序好好完成這一次程序切換，不要剝奪它的 CPU；

3529 行程式碼錶示 schedule() 呼叫了 __schedule(false) 方法，傳遞 fasle 引數，表示這是程序的一次主動排程，不可搶佔。

等當前的程序執行完排程邏輯之後，開啟搶佔，也就是說，其他程序可以剝奪當前程序的 CPU 了。

而如果某個程序像個強盜一樣一直佔著 CPU 不讓，核心會通過搶佔機制（比如上一篇文章提到的週期排程機制）進行一次程序排程，從而把當前程序從 CPU 上踢出去。

__schedule() 方法的框架便是這篇文章分析的主要內容，由於程式碼較多，我會挑選核心部分來描述。

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

我們先來看看 Linux 核心中，程序排程核心函數 __schedule() 的框架：

// kernel/sched/core.c:3395
void __schedule(bool preempt) {
    struct task_struct *prev, *next;
    unsigned long *switch_count;
    struct rq *rq;
    int cpu;
    // 獲取當前 CPU
    cpu = smp_processor_id();
    // 獲取當前 CPU 上的程序佇列
    rq = cpu_rq(cpu);
    // 獲取當前佇列上正在執行的程序
    prev = rq->curr;
    ...
    // nivcsw：程序非主動切換次數
    switch_count = &prev->nivcsw; // :3430
    if (!preempt ...) {
        ...
        // nvcsw：程序主動切換次數 
        switch_count = &prev->nvcsw; // :3456
    }
    ...
    // 1 根據某種演演算法從就緒佇列中選中一個程序
    next = pick_next_task(rq, prev, &rf);
    ...
    if (prev != next) {
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;
        // 2 執行程序上下文切換
        rq = context_switch(rq, prev, next, &rf);
    } 
    ...
}

可以看到，__schedule() 方法中，程序切換的核心步驟和作業系統理論中是一致的（1 和 2 兩個核心步驟）。

此外，程序切換的過程中，核心會根據是主動發起排程（preempt 為 fasle）還是被動發起排程，來統計程序上下文切換的次數，分別儲存在程序的資料結構 task_struct 中：

// include/linux/sched.h:592
struct task_struct {
    ...
    // 主動切換：Number of Voluntary（自願） Context Switches
    unsigned long nvcsw; // :811
    // 非主動切換：Number of InVoluntary（非自願） Context Switches
    unsigned long nivcsw; // :812
    ...
};

在 Linux 中，我們可以通過 pidstat 命令來檢視一個程序的主動和被動上下文切換的次數，我們寫一個簡單的 c 程式來做個測試：

// test.c
#include <stdlib.h>
#include <stdio.h>
int main() {
    while (1) {
        // 每隔一秒主動休眠一次
        // 即主動讓出 CPU
        // 理論上每秒都會主動切換一次
        sleep(1)
    }
}

然後編譯執行

gcc test.c -o test
./test

通過 pidstat 來檢視

可以看到，test 應用程式每秒主動切換一次程序上下文，和我們的預期相符，對應的上下文切換資料就是從 task_struct 中獲取的。

接下來，詳細分析程序排程的兩個核心步驟:

通過 pick_next_task() 從就緒佇列中選中一個程序。

通過 context_switch 執行上下文切換。

4 pick_next_task()：從就緒佇列中選中一個程序

我們回顧一下 pick_next_task() 在 __schedule() 方法中的位置

// kernel/sched/core.c:3395
void __schedule(bool preempt) {
    ...
    // rq 是當前 cpu 上的程序佇列
    next = pick_next_task(rq, pre ...); // :3459
    ...
}

跟著呼叫鏈往下探索：

// kernel/sched/core.c:3316
/* 
 * 找出優先順序最高的程序
 * 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() 方法的註釋上也能看到，這個方法的目的就是找出優先順序最高的程序，由於系統中大多數程序的排程型別都是公平排程，我們拿公平排程相關的邏輯來分析。

從上述的核心框架中可以看到，3331 行先嚐試從公平排程型別的佇列中獲取程序，3337 行，如果沒有找到，就把每個 CPU 上的 IDLE 程序取出來執行：

// 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 ...) {
    ...
    // 每一個 CPU 執行佇列中都有一個 IDLE 程序 
    return rq->idle; // :383
}

接下來，我們聚焦公平排程類的程序選中演演算法 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 是當前 CPU 上公平排程類佇列
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    struct task_struct *p;
    int new_tasks;
again:
    // 1 當前 CPU 程序佇列沒有程序可排程，則執行負載均衡邏輯
    if (!cfs_rq->nr_running) 
        goto idle;
    // 2. 當前 CPU 程序佇列有程序可排程，選中一個高優程序 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:
    // 通過負載均衡遷移程序
    new_tasks = idle_balance(rq, rf); // :7017
    ...
    
    if (new_tasks > 0)
        goto again;
    return NULL;
}

pick_next_task_fair() 的邏輯相對還是比較複雜的，但是，其中的核心思想分為兩步：

如果當前 CPU 上已無程序可排程，則執行負載邏輯，從其他 CPU 上遷移程序過來；

如果當前 CPU 上有程序可排程，從佇列中選擇一個高優程序，所謂高優程序，即虛擬時間最小的程序；

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

4.1 負載均衡邏輯

核心為了讓各 CPU 負載能夠均衡，在某些 CPU 較為空閒的時候，會從繁忙的 CPU 上遷移程序到空閒 CPU 上執行，當然，如果程序設定了 CPU 的親和性，即程序只能在某些 CPU 上執行，則此程序無法遷移。

負載均衡的核心邏輯是 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() 方法的邏輯也相對比較複雜：但是大體上概括就是，遍歷當前 CPU 的所有排程域，直到遷移出程序位置。

這裡涉及到一個核心概念：sched_domain，即排程域，下面用一張圖介紹一下什麼是排程域。

核心根據處理器與主記憶體的距離將處理器分為兩個 NUMA 節點，每個節點有兩個處理器。NUMA 指的是非一致性存取，每個 NUMA 節點中的處理器存取記憶體節點的速度不一致，不同 NUMA 節點之間不共用 L1 L2 L3 Cache。

每個 NUMA 節點下有兩個處理器，同一個 NUMA 下的不同處理器共用 L3 Cache。

每個處理器下有兩個 CPU 核，同個處理器下的不同核共用 L2 L3 Cache。

每個核下面有兩個超執行緒，同一個核的不同超執行緒共用 L1 L2 L3 Cache。

我們在應用程式裡面，通過系統 API 拿到的都是超執行緒，也可以叫做邏輯 CPU，下文統稱邏輯 CPU。

程序在存取一個某個地址的資料的時候，會先在 L1 Cache 中找，若未找到，則在 L2 Cache 中找，再未找到，則在 L3 Cache 上找，最後都沒找到，就存取主記憶體，而存取速度方面 L1 > L2 > L3 > 主記憶體，核心遷移程序的目標是儘可能讓遷移出來的程序能夠命中快取。

核心按照上圖中被虛線框起來的部分，抽象出排程域的概念，越靠近上層，排程域的範圍越大，快取失效的概率越大，因此，遷移程序的一個目標是，儘可能在低階別的排程域中獲取可遷移的程序。

上述程式碼 idle_balance() 方法的 9897 行：for_each_domain(this_cpu, sd)，this_cpu 就是邏輯 CPU（也即是最底層的超執行緒概念），sd 是排程域，這行程式碼的邏輯就是逐層往上擴大排程域；

// kernel/sched/sched.h:1268
#define for_each_domain(cpu, __sd) \
    for (__sd = cpu_rq(cpu)->sd); \
            __sd; __sd = __sd->parent)

而 idle_balance() 方法的 9812 行，如果在某個排程域中，成功遷移出了程序到當前邏輯 CPU，就終止迴圈，可見，核心為了提升應用效能真是煞費苦心。

經過負載均衡之後，當前空閒的邏輯 CPU 程序佇列很有可能已經存在就緒程序了，於是，接下來從這個佇列中獲取最合適的程序。

4.2 選中高優程序

接下來，我們把重點放到如何選擇高優程序，而在公平排程類中，會通過程序的實際優先順序和執行時間，來計算一個虛擬時間，虛擬時間越少，被選中的概率越高，所以叫做公平排程。

以下是選擇高優程序的核心邏輯：

// kernel/sched/fair.c:6898
static struct task_struct * pick_next_task_fair(struct rq *rq ...) {
    // cfs_rq 是當前 CPU 上公平排程類佇列
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    struct task_struct *p;
    // 2. 當前 CPU 程序佇列有程序可排程，選中一個高優程序 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); // :6956
    ...
    return p;
}

核心提供一個排程實體的的概念，對應資料結構叫 sched_entity，核心實際上是根據排程實體為單位進行排程的：

// include/linux/sched.h:447
struct sched_entity {
    ...
    // 當前排程實體的父親
    struct sched_entity    *parent;
    // 當前排程實體所在佇列
    struct cfs_rq *cfs_rq;  // :468
    // 當前排程實體擁有的佇列，及子排程實體佇列
    // 程序是底層實體，不擁有佇列
    struct cfs_rq *my_q;
    ...
};

每一個程序對應一個排程實體，若干排程實體系結到一起可以形成一個更高層次的排程實體，因此有個遞迴的效應，上述 do while 迴圈的邏輯就是從當前邏輯 CPU 頂層的公平排程實體（cfs_rq->curr）開始，逐層選擇虛擬時間較少的排程實體進行排程，直到最後一個排程實體是程序。

核心這樣做的原因是希望儘可能在每個層次上，都能夠保證排程是公平的。

拿 Docker 容器的例子來說，一個 Docker 容器中執行了若干個程序，這些程序屬於同一個排程實體，和宿主機上的程序的排程實體屬於同一層級，所以，如果 Docker 容器中瘋狂 fork 程序，核心會計算這些程序的虛擬時間總和來和宿主機其他程序進行公平抉擇，這些程序休想一直霸佔著 CPU！

選擇虛擬時間最少的程序的邏輯是 se = pick_next_entity(cfs_rq, curr); ，相應邏輯如下：

// kernel/sched/fair.c:4102
struct sched_entity *
pick_next_entity(cfs_rq *cfs_rq, sched_entity *curr) {
    // 公平執行佇列中虛擬時間最小的排程實體
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;
    // 如果沒找到或者樹中的最小虛擬時間的程序
    // 還沒當前排程實體小，那就選擇當前實體
    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) {
    // 比較兩者虛擬時間
    return (s64)(a->vruntime - b->vruntime) < 0;
}

上述程式碼，我們可以分析出，pick_next_entity() 方法會在當前公平排程佇列 cfs_rq 中選擇最靠左的排程實體，最靠左的排程實體的虛擬時間越小，即最優。

而下面通過 __pick_first_entity() 方法，我們瞭解到，公平排程佇列 cfs_rq 中的排程實體被組織為一棵紅黑樹，這棵樹的最左側節點即為最小節點：

// 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
// 快取了紅黑樹最左側節點
#define rb_first_cached(root) (root)->rb_leftmost

通過以上分析，我們依然通過一個 Docker 的例子來分析： 一個宿主機中有兩個普通程序分別為 A，B，一個 Docker 容器，容器中有 c1、c2、c3 程序。

這種情況下，系統中有兩個層次的排程實體，最高層為 A、B、c1+c2+c3，再往下為 c1、c2、c3，下面我們分情況來討論程序選中的邏輯：

1）若虛擬時間分佈為：A:100s，B:200s，c1:50s，c2:100s，c3:80s

選中邏輯：先比較 A、B、c1+c2+c3 的虛擬時間，發現 A 最小，由於 A 已經是程序，選中 A，如果 A 比當前執行程序虛擬時間還小，下一個執行的程序就是 A，否則保持當前程序不變。

2）若虛擬時間分佈為：A:100s，B:200s，c1:50s，c2:30s，c3:10s

選中邏輯：先比較 A、B、c1+c2+c3 的虛擬時間，發現 c1+c2+c3 最小，由於選中的排程實體非程序，而是一組程序，繼續往下一層排程實體進行選擇，比較 c1、c2、c3 的虛擬時間，發現 c3 的虛擬時間最小，如果 c3 的虛擬時間小於當前程序的虛擬時間，下一個執行的程序就是 c3，否則保持當前程序不變。

到這裡，選中高優程序進行排程的邏輯就結束了，我們來做下小結。

4.3 pick_next_task() 小結

核心在選擇程序進行排程的時候，會先判斷當前 CPU 上是否有程序可以排程，如果沒有，執行程序遷移邏輯，從其他 CPU 遷移程序，如果有，則選擇虛擬時間較小的程序進行排程。

核心在選擇邏輯 CPU 進行遷移程序的時候，為了提升被遷移程序的效能，即避免遷移之後 L1 L2 L3 快取記憶體失效，儘可能遷移那些和當前邏輯 CPU 共用快取記憶體的目標邏輯 CPU，離當前邏輯 CPU 越近越好。

核心將程序抽象為排程實體，為的是可以將一批程序進行統一排程，在每一個排程層次上，都保證公平。

所謂選中高優程序，實際上選中的是虛擬時間較小的程序，程序的虛擬時間是根據程序的實際優先順序和程序的執行時間等資訊動態計算出來的。

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

選中一個合適的程序之後，接下來就要執行實際的程序切換了，我們把目光重新聚焦到 __schedule() 方法

// kernel/sched/core.c:3395
void __schedule(bool preempt) {
    struct task_struct *prev, *next;
    ...
    // 1 根據某種演演算法從就緒佇列中選中一個程序
    next = pick_next_task(rq, prev,...); // :3459
    ...
    if (prev != next) {
        rq->curr = next;
        // 2 執行程序上下文切換
        rq = context_switch(rq, prev, next ...); // ::3485
    } 
    ...
}

其中，程序上下文切換的核心邏輯就是 context_switch，對應邏輯如下：

// 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 切換虛擬記憶體
    switch_mm_irqs_off(oldmm, mm, next);
    ...
    // 2 切換暫存器狀態
    switch_to(prev, next, prev);
    ...
}

上述程式碼，我略去了一些細節，保留我們關心的核心邏輯。context_switch() 核心邏輯分為兩個步驟，切換虛擬記憶體和暫存器狀態，下面，我們展開這兩段邏輯。

5.1 切換虛擬記憶體

首先，簡要介紹一下虛擬記憶體的幾個知識點：

程序無法直接存取到實體記憶體，而是通過虛擬記憶體到實體記憶體的對映機制間接存取到實體記憶體的。

每個程序都有自己獨立的虛擬記憶體地址空間。如，程序 A 可以有一個虛擬地址 0x1234 對映到實體地址 0x4567，程序 B 也可以有一個虛擬地址 0x1234 對映到 0x3456，即不同程序可以有相同的虛擬地址。如果他們指向的實體記憶體相同，則兩個程序即可通過記憶體共用程序通訊。

程序通過多級頁表機制來執行虛擬記憶體到實體記憶體的對映，如果我們簡單地把這個機制當做一個 map<虛擬地址，實體地址> 資料結構的話，那麼可以理解為不同的程序有維護著不同的 map；

map<虛擬地址，實體地址> 的翻譯是通過多級頁表來實現的，存取多級頁表需要多次存取記憶體，效率太差，因此，核心使用 TLB 快取頻繁被存取的 <虛擬地址，實體地址> 的專案，感謝區域性性原理。

由於不同程序可以有相同的虛擬地址，這些虛擬地址往往指向了不同的實體地址，因此，TLB 實際上是通過 <ASID + 虛擬地址，實體地址> 的方式來唯一確定某個程序的實體地址的，ASID 叫做地址空間 ID（Address Space ID），每個程序唯一，等價於多租戶概念中的租戶 ID。

程序的虛擬地址空間用資料結構 mm_struct 來描述，程序資料結構 task_struct 中的 mm 欄位就指向此資料結構，而上述所說的程序的 "map" 的資訊就藏在 mm_struct 中。

關於虛擬記憶體的介紹，後續的文章會繼續分析，這裡，我們只需要瞭解上述幾個知識點即可，我們進入到切換虛擬記憶體核心邏輯：

// 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) {
    // 如果兩個程序不是同一個程序
    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);
}

接下來，呼叫 check_and_switch_context 做實際的虛擬記憶體切換操作：

// arch/arm64/mm/context.c:194
void check_and_switch_context(struct mm_struct *mm, unsigned int cpu) {
    ...
    u64 asid;
    // 拿到要將下一個程序的 ASID
    asid = atomic64_read(&mm->context.id); // :218
    ...
    // 將下一個程序的 ASID 繫結到當前 CPU
    atomic64_set(&per_cpu(active_asids, cpu), asid);  // :236
    // 切換頁表，及切換我們上述中的 "map"，
    // 將 ASID 和 "map" 設定到對應的暫存器
    cpu_switch_mm(mm->pgd, mm); // :248
}

check_and_switch_context 總體上分為兩塊邏輯：

• 將下一個程序的 ASID 繫結到當前的 CPU，這樣 TLB 通過虛擬地址翻譯出來的實體地址，就屬於下個程序的。

• 拿到下一個程序的 "map"，也就是頁表，對應的欄位是 "mm->pgd"，然後執行頁表切換邏輯，這樣後續如果 TLB 沒命中，當前 CPU 就能夠知道通過哪個 "map" 來翻譯虛擬地址。

cpu_switch_mm 涉及的組合程式碼較多，這裡就不貼了，本質上就是將 ASID 和頁表（"map"）的資訊系結到對應的暫存器。

5.2 切換通用暫存器

虛擬記憶體切換完畢之後，接下來切換程序執行相關的通用暫存器，對應邏輯為 switch_to(prev, next ...); 方法，這個方法也是切換程序的分水嶺，呼叫完之後的那一刻，當前 CPU 上執行就是 next 的程式碼了。

拿 arm64 為例：

// arch/arm64/kernel/process.c:422
struct task_struct *__switch_to(task_struct *prev, task_struct *next) {
    ...
    // 實際切換方法
    cpu_switch_to(prev, next); // :444
    ...
}

cpu_switch_to 對應的是一段經典的組合邏輯，看著很多，其實並不難理解。

// 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 核心棧指標到 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
    // 設定 pc 暫存器
    ldr    lr, [x8]
    // 切換到 next 的核心棧
    mov    sp, x9
    
    // 將 next 指標儲存到 sp_el0 暫存器
    msr    sp_el0, x1 
    ret
ENDPROC(cpu_switch_to)

上述組合的邏輯可以和作業系統理論課裡的內容一一對應，即先將通用暫存器的內容儲存到程序的資料結構中對應的欄位，然後再從下一個程序的資料結構中對應的欄位載入到通用暫存器中。

1041 行程式碼是拿到 task_struct 結構中的 thread_struct thread 欄位的 cpu_contxt 欄位：

// arch/arm64/kernel/asm-offsets.c:53
DEFINE(THREAD_CPU_CONTEXT,    offsetof(struct task_struct, thread.cpu_context));

我們來分析一下對應的資料結構：

// 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 資料結構的設計就是為了儲存與程序有關的一些通用暫存器的值：

// 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;
    // 對應 x29 暫存器
    unsigned long fp;
    unsigned long sp;
    // 對應 lr 暫存器
    unsigned long pc;
};

這些值剛好與上述組合片段的程式碼一一對應上，讀者應該不需要太多組合基礎就可以分析出來。

上述組合中，最後一行 msr sp_el0, x1，x1 暫存器中儲存了 next 的指標，這樣後續再呼叫 current 宏的時候，就指向了下一個指標：

// 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 宏，很多地方會使用到
#define current get_current()

程序上下文切換的核心邏輯到這裡就結束了，最後我們做下小結。

5.3 context_switch() 小結

程序上下文切換，核心要切換的是虛擬記憶體及一些通用暫存器。

程序切換虛擬記憶體，需要切換對應的 TLB 中的 ASID 及頁表，頁表也即不同程序的虛擬記憶體翻譯需要的 "map"。

程序的資料結構中，有一個間接欄位 cpu_context 儲存了通用暫存器的值，暫存器切換的本質就是將上一個程序的暫存器儲存到 cpu_context 欄位，然後再將下一個程序的 cpu_context 資料結構中的欄位載入到暫存器中，至此完成程序的切換。

6 本文總結

最後，我們全文做下總結：

程序排程分為主動（非搶佔）和被動排程（搶佔），排程的核心邏輯在 __schedule() 方法中。

程序排程的核心邏輯分為兩個大步驟，其一是選擇一個合適的程序，其二是進行程序切換。

在選擇合適的程序中，如果當前邏輯 CPU 沒有可排程的程序，就從其他 CPU 來排程，遷移的程序儘可能靠近當前 CPU。

程序排程的單位其實是排程實體，一個排程實體對應一個或多個程序，這樣就能夠在各個層次上完成公平排程，通過排程實體的虛擬時間選擇最優排程實體對應的程序。

程序切換，本質上就是切換虛擬記憶體及通用暫存器。

程序排程的邏輯幾乎都完全遵循作業系統理論來設計的，學完作業系統之後，希望大家能夠理論聯絡實際，對照著核心去翻一翻原始碼。

相關推薦：《Linux視訊教學》

以上就是Linux核心原始碼分析之程序排程的邏輯（總結分享）的詳細內容，更多請關注TW511.COM其它相關文章！