[[440610]]

 本文涉及的 Linux 內(nèi)核版本是 v5.0，可在 「https://elixir.bootlin.com/linux/v5.0/source」 在線瀏覽，文中每段源碼均標(biāo)注了文件路徑及行數(shù)，建議讀者對(duì)著源碼讀此文。

進(jìn)程概要及調(diào)度時(shí)機(jī)

這篇文章從 Linux 內(nèi)核層面分析進(jìn)程概要及調(diào)度時(shí)機(jī)。

0 本文內(nèi)容一分鐘速覽

如果讀者沒有耐心看完整篇文章，下面是本文的核心內(nèi)容預(yù)覽，一分鐘內(nèi)能讀完。

0.1 進(jìn)程概要

• 進(jìn)程是對(duì)物理世界的建模抽象，每個(gè)進(jìn)程對(duì)應(yīng)一個(gè) task_struct 數(shù)據(jù)結(jié)構(gòu)，這個(gè)數(shù)據(jù)結(jié)構(gòu)包含了進(jìn)程的所有的信息。
• 在 Linux 內(nèi)核中，不會(huì)區(qū)分線程和進(jìn)程的概念，線程也是通過進(jìn)程來實(shí)現(xiàn)的，線程和進(jìn)程的唯一區(qū)別就是：線程沒有獨(dú)立的資源，進(jìn)程有。
• 所有的進(jìn)程都是通過其他進(jìn)程創(chuàng)建出來的，因此，整個(gè)進(jìn)程組織為一棵進(jìn)程樹。
• 0 號(hào)進(jìn)程是 無中生有 憑空產(chǎn)生的，是靜態(tài)定義出來的，是所有進(jìn)程的祖先，創(chuàng)建了 INIT(1號(hào))和 kthreadd(2號(hào)進(jìn)程)。

0.2 進(jìn)程調(diào)度時(shí)機(jī)

• 系統(tǒng)調(diào)用 yield、pause 會(huì)使得當(dāng)前進(jìn)程讓出 CPU，隨后進(jìn)行一次進(jìn)程調(diào)度。
• 系統(tǒng)調(diào)用 futex(wait) 等待某個(gè)信號(hào)量，將進(jìn)程設(shè)置為 TASK_INTERRUPTIBLE 狀態(tài)，然后進(jìn)行一次進(jìn)程調(diào)度。
• 進(jìn)程在退出的時(shí)候，會(huì)系統(tǒng)調(diào)用到 exit 方法，將當(dāng)前進(jìn)程設(shè)置為 TASK_DEAD 之后，進(jìn)行一次進(jìn)程調(diào)度。
• 在創(chuàng)建新進(jìn)程、喚醒進(jìn)程、周期調(diào)度過程中，內(nèi)核會(huì)給當(dāng)前進(jìn)程設(shè)置一個(gè)需要調(diào)度的標(biāo)志，然后在下一次中斷返回到用戶空間時(shí)，進(jìn)行一次調(diào)度。
• 每顆 CPU 都會(huì)綁定一個(gè) IDLE 進(jìn)程，沒事就在 CPU 上無聊地空轉(zhuǎn)，偶爾進(jìn)行一次進(jìn)程調(diào)度。

1 進(jìn)程概要

1.1 進(jìn)程是對(duì)物理世界的建模抽象

人們?cè)诿鎸?duì)一個(gè)問題束手無策的時(shí)候，經(jīng)常會(huì)創(chuàng)造一個(gè)概念，然后基于這個(gè)概念來演化出一個(gè)系統(tǒng)來解決這個(gè)問題。進(jìn)程的概念就是人類發(fā)明出來，為了解決物理世界想要同時(shí)做若干件事情的需求，最終演化出了進(jìn)程子系統(tǒng)。關(guān)于進(jìn)程的基本知識(shí)網(wǎng)上有很多，這里說下我的理解：

• 加載器將可執(zhí)行程序文件(Linux 中是 ELF 格式)加載到操作系統(tǒng)，操作系統(tǒng)中就多了一個(gè)進(jìn)程。
• 進(jìn)程的核心由代碼段和數(shù)據(jù)段組成，代碼段就是進(jìn)程在執(zhí)行過程中按照正常流程一條條執(zhí)行的指令，數(shù)據(jù)段就是指令需要的數(shù)據(jù)。
• 每顆 CPU 都有一個(gè) PC(Program Counter)寄存器，這個(gè)寄存器指向了下一條要執(zhí)行的指令地址，由于這個(gè)指令必然屬于某個(gè)進(jìn)程，所以，每個(gè) CPU 每一時(shí)刻只能運(yùn)行一個(gè)進(jìn)程。
• 多線程在內(nèi)核空間本質(zhì)上也是多進(jìn)程，多個(gè)進(jìn)程在時(shí)間較大的尺度上給人一種可以同時(shí)執(zhí)行的錯(cuò)覺，本質(zhì)上是通過進(jìn)程調(diào)度交叉執(zhí)行，只不過這個(gè)時(shí)間太短，我們感覺不到而已。
• JVM 中的一個(gè)線程對(duì)應(yīng)了 Linux 內(nèi)核中的一個(gè)進(jìn)程，了解了底層進(jìn)程的機(jī)制，也就了解了上層的很多現(xiàn)象。

1.2 進(jìn)程的數(shù)據(jù)結(jié)構(gòu)

由于歷史原因，內(nèi)核中表示進(jìn)程的數(shù)據(jù)結(jié)構(gòu)叫做 task_struct，這個(gè)數(shù)據(jù)結(jié)構(gòu)里面的字段有幾十個(gè)，我不太想一一列出來，然后占很大篇幅。我會(huì)列幾個(gè)大家比較關(guān)心的，在后面的分析過程中，會(huì)逐漸展開 task_struct 的其他字段。本篇文檔對(duì)應(yīng)的 Linux 內(nèi)核是 5.0。

// include/linux/sched.h:592 
// Linnux 進(jìn)程底層對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu) 
struct task_struct { 
//  進(jìn)程的 ID 
    pid_t pid; 
//  進(jìn)程的狀態(tài)     
    volatile long state; 
//  進(jìn)程的父親     
    struct task_struct *parent; 
//  當(dāng)前進(jìn)程的子進(jìn)程     
    struct list_head children;   
}; 

從上面的幾個(gè)關(guān)鍵的字段可以看出，每個(gè)進(jìn)程都有唯一的 ID 和狀態(tài)，并且，在系統(tǒng)中，進(jìn)程是通過一棵樹的方式來組織的，也就是說，所有的進(jìn)程都有父親，通過我們熟悉的 fork 系統(tǒng)調(diào)用來創(chuàng)造。另外，Linux 內(nèi)核中也是不區(qū)分進(jìn)程和線程的，兩者均使用 task_struct 數(shù)據(jù)結(jié)構(gòu)，線程的本質(zhì)是共享進(jìn)程的資源，對(duì)應(yīng)這個(gè)數(shù)據(jù)結(jié)構(gòu)，只要把里面涉及共享的指針指向進(jìn)程的資源即可。

1.3 特殊的進(jìn)程

「所有的進(jìn)程都有父親」，這句話不一定全對(duì)，就像演繹邏輯鏈一樣，我們一直順著大前提往上追，總會(huì)追到第一個(gè) 大 bug，這個(gè) 大 bug 我們無法證明，只能默認(rèn)它是對(duì)的，它是我們系統(tǒng)的第一性原理。扯遠(yuǎn)了，Linux 中，這個(gè) 大 bug 就是 0 號(hào)進(jìn)程，它的另一個(gè)外號(hào)叫 IDLE，這個(gè) 大 bug 在內(nèi)核初始化的時(shí)候，被顯示地定義出來(而不是通過 fork)，下面我們來感受一下 Linux 進(jìn)程子系統(tǒng)中第一個(gè)進(jìn)程 無中生有 的過程。

// include/linux/sched/task.h:26 
extern struct task_struct init_task; // 這個(gè)就是 0 號(hào)進(jìn)程 
 
// init/init_task.c:57 
struct task_struct init_task = { 
//  這個(gè)字段沒有顯示定義出來，而是通過 struct pid 來描述，效果一樣         
    .pid = 0, 
//  對(duì)應(yīng)了 TASK_RUNNING     
    .state = 0, 
//  我就是第一個(gè)進(jìn)程，我沒有 parent     
    .parent = &init_task, 
//  初始化子進(jìn)程鏈表     
    .children = LIST_HEAD_INIT(init_task.children), 
}; 

init_task 類似于盤古，系統(tǒng)中所有的進(jìn)程都是由它開辟出來的，在后續(xù)的 Linux 內(nèi)核文章中，我們會(huì)逐漸了解這個(gè)機(jī)制的妙處，我們先把注意力調(diào)回到本篇文章的重點(diǎn)，進(jìn)程切換的機(jī)制。

1.4 進(jìn)程概要小結(jié)

• 進(jìn)程是對(duì)物理世界的建模抽象，每個(gè)進(jìn)程對(duì)應(yīng)一個(gè) task_struct 數(shù)據(jù)結(jié)構(gòu)，這個(gè)數(shù)據(jù)結(jié)構(gòu)包含了進(jìn)程的所有的信息。
• 在 Linux 內(nèi)核中，不會(huì)區(qū)分線程和進(jìn)程的概念，線程也是通過進(jìn)程來實(shí)現(xiàn)的，線程和進(jìn)程的唯一區(qū)別就是：線程沒有獨(dú)立的資源，進(jìn)程有。
• 所有的進(jìn)程都是通過其他進(jìn)程創(chuàng)建出來的，因此，整個(gè)進(jìn)程組織為一棵進(jìn)程樹。
• 0 號(hào)進(jìn)程是 無中生有 憑空產(chǎn)生的，是靜態(tài)定義出來的，是所有進(jìn)程的祖先。

2 進(jìn)程調(diào)度時(shí)機(jī)

Linux 內(nèi)核中，進(jìn)程調(diào)度的時(shí)機(jī)無處不在，我們來了解幾個(gè)典型的時(shí)機(jī)。

2.1 yield 和 pause 讓出 cpu

通常情況下，我們的進(jìn)程運(yùn)行在用戶空間，通過系統(tǒng)調(diào)用進(jìn)入到內(nèi)核空間，從而做一些更高級(jí)的事情。

yield 系統(tǒng)調(diào)用可以讓當(dāng)前進(jìn)程放棄 cpu，進(jìn)行系統(tǒng)的調(diào)度。

// kernel/sched/core.c:4963 
SYSCALL_DEFINE0(sched_yield) { 
    do_sched_yield(); 
    return 0; 
} 

Linux 中的系統(tǒng)調(diào)用通過類似 SYSCALL_DEFINEx 這種方式定義，x 表示參數(shù)的個(gè)數(shù)，sched_yield 系統(tǒng)調(diào)用沒有參數(shù)，所以 x 是 0。

我們沿著調(diào)用鏈往下，來到 do_sched_yield 方法。

//  kernel/sched/core.c:4942 
static void do_sched_yield(void) {    
    ... 
    schedule(); // :4960 
    ... 
} 

我們發(fā)現(xiàn)，在 4960 行，有一個(gè)命名非常簡(jiǎn)單的函數(shù)調(diào)用，叫做 schedule()，這個(gè)函數(shù)就是內(nèi)核中進(jìn)程調(diào)度的入口，我們分析進(jìn)程調(diào)度的時(shí)機(jī)，等價(jià)于查看有哪些地方調(diào)用了這個(gè)方法。

下面我們來看看 pause 這個(gè)系統(tǒng)調(diào)用：

// kernel/signal.c:4170 
SYSCALL_DEFINE0(pause) {    
    __set_current_state(TASK_INTERRUPTIBLE); 
    schedule(); 
} 
 
// include/linux/sched.h:185 
#define __set_current_state(state_value) \ 
 current->state = (state_value) 

pause 系統(tǒng)調(diào)用首先將當(dāng)前進(jìn)程設(shè)置為 TASK_INTERRUPTIBLE 狀態(tài)，其實(shí)就是給 task_struct 結(jié)構(gòu)中的 state 字段賦值，附上 TASK_INTERRUPTIBLE 之后，在后續(xù)進(jìn)程調(diào)度中就可以過濾掉這個(gè)進(jìn)程，選擇其他的進(jìn)程進(jìn)行調(diào)度。接著，同樣是一個(gè)簡(jiǎn)單的 schedule 函數(shù)，進(jìn)入到調(diào)度的邏輯。

2.2 futex 等待資源

futex (fast userspace mutex)，用來給上層應(yīng)用構(gòu)建更高級(jí)別的同步機(jī)制，是實(shí)現(xiàn)信號(hào)量和鎖的基礎(chǔ)，后面有機(jī)會(huì)可以單獨(dú)介紹。我們簡(jiǎn)化一下場(chǎng)景：一個(gè)進(jìn)程在等待某個(gè)信號(hào)的時(shí)候，最終會(huì)通過系統(tǒng)調(diào)用進(jìn)入到 futex，其中某個(gè)關(guān)鍵參數(shù)為 wait：

// kernel/futex.c:3633 
SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val, 
struct __kernel_timespec __user *, utime, u32 __user *, uaddr2, 
u32, val3) { 
    ... 
    return do_futex(... op, ...); // :3665 
} 

這個(gè)系統(tǒng)調(diào)用有 6 個(gè)參數(shù)，參數(shù)類型和名稱并列展開，上層應(yīng)用在等待一個(gè)信號(hào)量的時(shí)候，給 op 這個(gè)參數(shù)的傳遞的是 FUTEX_WAIT_BITSET，我們通過調(diào)用鏈往下追。

// kernel/futex.c:3573 
long do_futex(...int op,...) { 
    int cmd = op & FUTEX_CMD_MASK; 
 
    switch (cmd) { 
        case FUTEX_WAIT_BITSET: 
            return futex_wait(uaddr, flags, val, timeout, val3); // :3604 
    ... 
    } 
    ... 
} 

由于中間調(diào)用鏈有點(diǎn)長，下面我們就簡(jiǎn)化一下調(diào)用邏輯，專注核心，這個(gè)在我們?nèi)ラ喿x源碼過程中，也是非常重要的一點(diǎn)，閱讀核心邏輯的時(shí)候，不要被太多的細(xì)節(jié)干擾。

// kernel/futex.c:2679 
static int futex_wait(...) { 
    ... 
    futex_wait_queue_me(...); // :2713 
    ... 
} 
 
// kernel/futex.c:2571  
static void futex_wait_queue_me(...) { 
    ... 
//  這里可以看到，調(diào)用 futex 的進(jìn)程將變?yōu)樗郀顟B(tài)，與我們的認(rèn)知一致 
    set_current_state(TASK_INTERRUPTIBLE); // :2580 
    ... 
    freezable_schedule(); // :2598 
    ... 
} 
 
// include/linux/freezer.h:169 
static inline void freezable_schedule(void) { 
    ... 
    schedule(); // :180 
    ... 
} 

沿著進(jìn)程調(diào)用鏈下來，我們可以看到，進(jìn)程系統(tǒng)調(diào)用 futex(wait) 時(shí)，可能會(huì)將自己設(shè)置為睡眠狀態(tài)并且進(jìn)行一次進(jìn)程調(diào)度。

2.3 exit 進(jìn)程退出

多年的編程經(jīng)驗(yàn)告訴我們，在一個(gè)進(jìn)程退出的時(shí)候會(huì)觸發(fā)進(jìn)程調(diào)度，我們通過內(nèi)核源碼來證明這一點(diǎn)。應(yīng)用層的進(jìn)程在退出時(shí)，最終會(huì)通過 exit 系統(tǒng)調(diào)用進(jìn)入到內(nèi)核，調(diào)用鏈如下：

// kernel/exit.c:946 
SYSCALL_DEFINE1(exit, int, error_code) { 
    do_exit((error_code&0xff)<<8); 
} 
 
// kernel/exit.c:773 
void do_exit(long code) { 
    ... 
    do_task_dead(); // :933 
} 
 
// kernel/sched/core.c:3494 
void do_task_dead(void) { 
// 這個(gè)地方也是給 task_struct 中的 state 字段賦值 
    set_special_state(TASK_DEAD); 
    ... 
    __schedule(false); // :3502 
    ... 
} 

通過調(diào)用鏈，我們可以看到，進(jìn)程在退出的時(shí)候，最終調(diào)用了 __schedule 方法，這里我們可以將這個(gè)方法等價(jià)于 schedule 方法，因?yàn)? schedule 方法最終會(huì)調(diào)用到這個(gè)方法，__schedule 中描述了進(jìn)程調(diào)度的核心邏輯。

2.4 中斷返回時(shí)調(diào)度

除了上述調(diào)度時(shí)機(jī)，還有一類調(diào)度時(shí)機(jī)是中斷返回的時(shí)候。

介紹中斷之前，先描述一下什么是異常：進(jìn)程的指令按照程序正常流程一直在 CPU 上跑，系統(tǒng)突然發(fā)生了一個(gè)帶有異常號(hào)的異常，強(qiáng)迫 CPU 停止執(zhí)行當(dāng)前的指令，CPU 隨后會(huì)在執(zhí)行完當(dāng)前指令之后，保存現(xiàn)場(chǎng)，根據(jù)異常號(hào)跳轉(zhuǎn)到異常處理程序，處理完之后，回到被異常終止的下一條機(jī)器指令繼續(xù)執(zhí)行。

系統(tǒng)調(diào)用是常見一種類型的異常，也是應(yīng)用代碼從用戶空間主動(dòng)進(jìn)入內(nèi)核空間的唯一方式。另外一種常見的異常就是硬件中斷，比如我們點(diǎn)下鼠標(biāo)、按下鍵盤、網(wǎng)卡接收到數(shù)據(jù)、磁盤數(shù)據(jù)讀寫完畢等，都會(huì)觸發(fā)一次硬件中斷，運(yùn)行在用戶空間的進(jìn)程會(huì)被動(dòng)陷入到內(nèi)核空間，進(jìn)行中斷處理程序的處理。

而中斷處理程序處理完之后，勢(shì)必要返回到用戶空間，在返回至用戶空間之前，會(huì)順帶做一件事情，判斷是否要進(jìn)行進(jìn)程調(diào)度，如果需要，則順帶做一次進(jìn)程調(diào)度。我們通過調(diào)用鏈來分析一下這個(gè)過程。

我們拿 arm64 處理器為例，中斷處理程序的的入口是 el0_irq，這里看不懂匯編沒有關(guān)系，我們抓關(guān)鍵部分即可。

// arch/arm64/kernel/entry.S:838 
// 這里即是 arm64 的中斷入口 
el0_irq: 
    ... 
    處理中斷 
    ... 
//  回到用戶空間 
    b ret_to_user // :834 
     
// arch/arm64/kernel/entry.S:895 
ret_to_user: 
    ... 
    ldr x1, [tsk, #TSK_TI_FLAGS] // :890 
    and x2, x1, #_TIF_WORK_MASK 
    cbnz x2, work_pending 

890 行代碼想要表述的是，將 tsk(也就是被中斷暫停的當(dāng)前進(jìn)程)數(shù)據(jù)結(jié)構(gòu)中，偏移量為 TSK_TI_FLAGS 傳遞給 x1 寄存器，順帶說一下，arm64 中有 x0 ~ x31 寄存器。

TSK_TI_FLAGS 常量在 asm-offsets.c 文件中被定義。

// arch/arm64/kernel/asm-offsets.c:48 
int main(void) { 
    ... 
    DEFINE(TSK_TI_FLAGS, offsetof(struct task_struct, thread_info.flags)) // :442 
    ...         
} 

本質(zhì)上，就是 task_struct 結(jié)構(gòu)中的 thread_info 結(jié)構(gòu)中的 flags 字段的偏移量：

// include/linux/sched.h:592 
struct task_struct { 
    ... 
    struct thread_info thread_info; // :598 
    ... 
} 
 
// arch/arm64/include/asm/thread_info.h:39 
struct thread_info { 
    ... 
    unsigned long flags; // :40 
    ... 
} 

所以 ret_to_user 中的這個(gè)邏輯就是，取出 task_struct->thread_info->flags 字段，然后通過與 _TIF_WORK_MASK 進(jìn)行 and 操作：

// arch/arm64/include/asm/thread_info.h:118 
#define _TIF_WORK_MASK  (_TIF_NEED_RESCHED | _TIF_SIGPENDING | \ 
     _TIF_NOTIFY_RESUME | _TIF_FOREIGN_FPSTATE | \ 
     _TIF_UPROBE | _TIF_FSCHECK) 

進(jìn)程中的 flags 與 _TIF_WORK_MASK 進(jìn)行 and 操作之后，如果二進(jìn)制位的值不為 0，就跳轉(zhuǎn)(cbnz)到 work_pending 方法。

// arch/arm64/kernel/entry.S:884  
work_pending: 
    ... 
    bl  do_notify_resume // :886 
    ... 
     
// arch/arm64/kernel/signal.c:915    
// 參數(shù)中 thread_flags 的值就是上面保存在 x1 寄存器中的值，也就是 `task_struct->thread_info->flags` 
void do_notify_resume(... long thread_flags) { 
    ... 
    if (thread_flags & _TIF_NEED_RESCHED) { 
        schedule(); // :933 
    }  
    ... 
} 

到了這里，中斷返回到用戶空間的調(diào)度邏輯大家應(yīng)該比較清楚了。我們總結(jié)一點(diǎn)就是：當(dāng)中斷處理程序返回用戶空間的時(shí)候，如果被中斷的進(jìn)程被設(shè)置了需要進(jìn)程調(diào)度標(biāo)志，那么就進(jìn)行一次進(jìn)程調(diào)度。

那么，什么時(shí)候當(dāng)前進(jìn)程會(huì)被設(shè)置這個(gè)標(biāo)志?

只有進(jìn)入到內(nèi)核空間才能夠設(shè)置當(dāng)前進(jìn)程的需要調(diào)度標(biāo)志，而系統(tǒng)調(diào)用是我們主動(dòng)從用戶空間進(jìn)入內(nèi)核空間的唯一方式，下面我們就來分析有哪些系統(tǒng)調(diào)用會(huì)設(shè)置當(dāng)前進(jìn)程需要調(diào)度的標(biāo)志。

2.4.1 創(chuàng)建新進(jìn)程

第一類是是通過 fork 系統(tǒng)調(diào)用創(chuàng)建新的進(jìn)程。相信大家應(yīng)該或多或少聽過，大多數(shù)編程語言創(chuàng)建線程，比如 Java 的 new Thread(...).start()，最后都會(huì)落到 fork 系統(tǒng)調(diào)用。

接下來，我們來分析 fork 系統(tǒng)調(diào)用是如何來設(shè)置進(jìn)程需要調(diào)度的標(biāo)識(shí)的。

// kernel/fork.c:2291 
SYSCALL_DEFINE0(fork) { 
    ... 
    return _do_fork(...); 
} 
 
// kernel/fork.c:2196 
long _do_fork(...) { 
    struct task_struct *p; 
    ... 
//  大多數(shù)數(shù)據(jù)結(jié)構(gòu)都是 copy 的父進(jìn)程，也就是當(dāng)前進(jìn)程 
    p = copy_process(...); // :2227 
    ... 
//  創(chuàng)建完子進(jìn)程之后，讓子進(jìn)程 "蘇醒" 
    wake_up_new_task(p); // :2252 
    ... 
} 

這里我們可以看到，創(chuàng)建子進(jìn)程的時(shí)候，有部分工作是復(fù)制父進(jìn)程(2227 行)，也就是當(dāng)前進(jìn)程的數(shù)據(jù)結(jié)構(gòu)，線程和進(jìn)程的本質(zhì)區(qū)別就在這個(gè)方法里面，用一個(gè)參數(shù)確定要復(fù)制哪些資源，我們?cè)诤竺娴奈恼轮袝?huì)詳細(xì)分析進(jìn)程創(chuàng)建過程，這里我們點(diǎn)到為止。

創(chuàng)建完新進(jìn)程之后，調(diào)用 wake_up_new_task 喚醒新進(jìn)程，我們來看內(nèi)核是如何喚醒新進(jìn)程的。

// kernel/sched/core.c:2413 
void wake_up_new_task(struct task_struct *p) { 
    ... 
//  將當(dāng)前進(jìn)程設(shè)置為 RUNNING 狀態(tài)，后續(xù)即可調(diào)度 
    p->state = TASK_RUNNING; // :2419  
    ... 
//  判斷是否要搶占當(dāng)前進(jìn)程 
    check_preempt_curr(rq, p, WF_FORK); // :2439 
    ... 
} 

check_preempt_curr 會(huì)根據(jù)當(dāng)前進(jìn)程的調(diào)度類型，執(zhí)行對(duì)應(yīng)的方法：

// kernel/sched/core.c:854 
void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags) { 
    ... 
//  rq 是當(dāng)前 cpu 上的進(jìn)程隊(duì)列 
//  curr 是當(dāng)前正在 cpu 運(yùn)行的進(jìn)程 
//  sched_class 是當(dāng)前進(jìn)程的調(diào)度 
    rq->curr->sched_class->check_preempt_curr(rq, p, flags); // :858 
    ... 
} 

sched_class 表示進(jìn)程的調(diào)度類型，這個(gè)字段在每個(gè) task_struct 中。

// include/linux/sched.h:592 
struct task_struct { 
    ... 
//  sched_class 在進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中 
//  表示調(diào)度類型，我們后面的系列文章再詳細(xì)分析  
    const struct sched_class *sched_class; // :643 
    ... 
} 
 
// kernel/sched/sched.h:1715 
// Linux 中所有的調(diào)度類型 
extern const struct sched_class stop_sched_class; 
extern const struct sched_class dl_sched_class; 
extern const struct sched_class rt_sched_class; 
extern const struct sched_class fair_sched_class; 
extern const struct sched_class idle_sched_class; 

可以看到，Linux 中一共有五種調(diào)度類型，fair_sched_class 是一般進(jìn)程的調(diào)度類型，稱為公平調(diào)度，我們后面的文章中再詳細(xì)分析這五個(gè)調(diào)度類型，這里，我們還是聚焦重點(diǎn)。

我們跟隨調(diào)用鏈，來到 fair_sched_class 的 check_preempt_check 方法。

// kernel/sched/fair.c:10506 
const struct sched_class fair_sched_class = { 
    .check_preempt_curr = check_preempt_wakeup // :10513 
} 
 
// kernel/sched/fair.c:6814 
static void check_preempt_wakeup(rq *rq, task_struct *p...) { 
    struct task_struct *curr = rq->curr; 
    struct sched_entity *se = &curr->se, *pse = &p->se; 
  
//  如果 pse 的虛擬時(shí)間小于當(dāng)前進(jìn)程的虛擬時(shí)間，就搶占 
    if (wakeup_preempt_entity(se, pse) == 1) { // :6867 
        goto preempt; 
     } 
preempt: // :6879 
//  沒有在這里直接調(diào)度，而是設(shè)置了一個(gè)標(biāo)志，在異常處理返回的時(shí)候統(tǒng)一調(diào)度 
    resched_curr(rq); 
} 

check_preempt_wakeup 方法中一處關(guān)鍵的地方，se 表示當(dāng)前進(jìn)程的調(diào)度實(shí)體，pse 表示 fork 出來的進(jìn)程的調(diào)度實(shí)體。

調(diào)度實(shí)體這個(gè)對(duì)象也定義在進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中。

// include/linux/sched.h:592 
struct task_struct { 
    ... 
    struct sched_entity se; // :644 
    ... 
} 

調(diào)度實(shí)體是為了防止一個(gè)進(jìn)程不斷地 fork 多個(gè)子進(jìn)程，從而無限霸占 cpu，內(nèi)核可以將一組線程綁定到一起進(jìn)行統(tǒng)一調(diào)度，這里我們不用關(guān)心太多細(xì)節(jié)，仍然聚焦核心。

下面我們來看下 check_preempt_wakeup 方法中 6867 行的 wakeup_preempt_entity 代碼做了什么事情。

// kernel/sched/fair.c:6767 
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se) { 
    s64 gran, vdiff = curr->vruntime - se->vruntime; 
 
    if (vdiff <= 0) 
        return -1; 
     
//  gran 可以理解為進(jìn)程運(yùn)行的最小時(shí)間片 
    gran = wakeup_gran(se);  
    if (vdiff > gran) 
        return 1; 
 
    return 0; 
} 

公平調(diào)度類默認(rèn)會(huì)通過進(jìn)程的優(yōu)先級(jí)和歷史運(yùn)行情況來計(jì)算出一個(gè)進(jìn)程運(yùn)行的虛擬時(shí)間，虛擬時(shí)間小的進(jìn)程可以搶占虛擬時(shí)間大的進(jìn)程。

當(dāng)然，為了防止頻繁搶占調(diào)度，要保證進(jìn)程在 cpu 上的一個(gè)最小的運(yùn)行時(shí)間，這個(gè)時(shí)間默認(rèn)在 v5.0 內(nèi)核中是 100 毫秒。

上面這段代碼的邏輯，總結(jié)來說就是，如果當(dāng)前進(jìn)程的時(shí)間片已到，并且當(dāng)前進(jìn)程的虛擬時(shí)間小于 fork 出來的進(jìn)程的虛擬時(shí)間片(顯然是 0)，則返回 1，然后進(jìn)入到標(biāo)記為 preempt 的代碼，即 resched_curr。

// kernel/sched/core.c:465 
void resched_curr(struct rq *rq) { 
    ... 
    set_tsk_need_resched(curr); // :483 
    ... 
}     
 
// include/linux/sched.h:1676 
static inline void set_tsk_need_resched(struct task_struct *tsk) { 
    set_tsk_thread_flag(tsk,TIF_NEED_RESCHED); 
} 

resched_curr 給當(dāng)前進(jìn)程設(shè)置一個(gè)標(biāo)志，需要進(jìn)行一次調(diào)度，根據(jù)我們上一節(jié)的分析，下一次中斷返回到用戶空間的時(shí)候，就會(huì)進(jìn)行一次調(diào)度。

2.4.2 futex 喚醒進(jìn)程

除了 fork 系統(tǒng)調(diào)用，在 futex 系統(tǒng)調(diào)用的時(shí)候，也會(huì)設(shè)置需要調(diào)度的標(biāo)志。

// kernel/futex.c:3633 
SYSCALL_DEFINE6(futex, ... op, ...) { 
    ... 
    return do_futex(... op, ...); // :3665 
} 

這種情況下，用戶傳遞的 op 參數(shù)是 FUTEX_WAKE_OP，即用戶需要進(jìn)行喚醒操作，我們通過調(diào)用鏈往下追：

// kernel/futex.c:3573 
long do_futex(...int op,...) { 
 int cmd = op & FUTEX_CMD_MASK; 
 
 switch (cmd) { 
        case FUTEX_WAKE_OP: 
            return futex_wake_op(...); // :3615 
    ... 
    } 
    ... 
} 
 
// kernel/futex.c:1683 
static int futex_wake_op(...) { 
    ... 
    wake_up_q(...); // :1766 
    ... 
} 
 
// kernel/sched/core.c:436 
void wake_up_q(...) { 
    wake_up_process(task); // :453 
} 
 
// 后續(xù)調(diào)用鏈路有些長，我們中間的代碼描述簡(jiǎn)化處理，最終會(huì)落到下面的代碼 
 
// kernel/sched/core.c:1667 
static void ttwu_do_wakeup(...) { 
    check_preempt_curr(...); 
} 

可以看到，futex 的 wake 操作，最后同樣會(huì)落到和 fork 一樣的方法 check_preempt_curr，這個(gè)方法我們上面剛分析過，做的事情就是給當(dāng)前線程設(shè)置一個(gè)需要調(diào)度的標(biāo)志，在下一次中斷返回時(shí)進(jìn)行一次調(diào)度。

2.4.3 周期調(diào)度

除了系統(tǒng)調(diào)用，內(nèi)核還有一個(gè)定時(shí)調(diào)度機(jī)制：周期調(diào)度，內(nèi)核會(huì)周期地調(diào)用 scheduler_tick 方法執(zhí)行調(diào)度邏輯，我們來分析一下這個(gè)過程。

// kernel/sched/core.c:3049 
/* 
 * This function gets called by the timer code, with HZ frequency. 
 */ 
void scheduler_tick(void) { 
    ... 
//  當(dāng)前是哪個(gè) cpu？ 
    int cpu = smp_processor_id(); 
//  拿到 cpu 上的進(jìn)程隊(duì)列 
    struct rq *rq = cpu_rq(cpu); 
//  拿到 cpu 上當(dāng)前運(yùn)行的進(jìn)程 
    struct task_struct *curr = rq->curr; 
    ... 
    curr->sched_class->task_tick(rq, curr, 0); // :3061 
    ... 
} 

scheduler_tick 調(diào)用當(dāng)前進(jìn)程的調(diào)度類的 task_tick 方法，我們還是分析常見的公平調(diào)度類的 task_tick 方法。

// kernel/sched/fair.c:10506  
const struct sched_class fair_sched_class = { 
    ...     
    .task_tick = task_tick_fair, // :10530 
    ... 
} 
 
// kernel/sched/fair.c:10030 
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) { 
 struct cfs_rq *cfs_rq; 
 struct sched_entity *se = &curr->se; 
    ... 
//  cfs_rq 可以理解為當(dāng)前 cpu 上公平調(diào)度類的進(jìn)程隊(duì)列 
    cfs_rq = cfs_rq_of(se); 
    entity_tick(cfs_rq, se, queued); // :10037 
    ... 
} 
 
// kernel/sched/fair.c:4179 
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) { 
//  更新當(dāng)前進(jìn)程的運(yùn)行時(shí)間 
    update_curr(cfs_q); 
    ... 
//  更新當(dāng)前進(jìn)程的 load 
    update_load_avg(cfs_rq, curr, UPDATE_TG); 
    ... 
//  如果 cpu 有就緒進(jìn)程 
    if (cfs_rq->nr_running > 1) 
        check_preempt_tick(cfs_rq, curr); 
} 

cfs_rq->nr_running 可以理解為當(dāng)前 cpu 上，公平調(diào)度類型的就緒進(jìn)程和運(yùn)行進(jìn)程的和，大于 1 表示有待調(diào)度的就緒進(jìn)程，于是調(diào)用 check_preempt_tick：

// kernel/sched/fair.c:4023 
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) { 
    unsigned long ideal_runtime, delta_exec; 
    struct sched_entity *se; 
    ... 
    ideal_runtime = sched_slice(cfs_rq, curr); 
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime; 
    if (delta_exec > ideal_runtime) { 
        resched_curr(rq_of(cfs_rq)); // :4056 
    } 
    ... 
} 

check_preempt_tick 方法中，會(huì)計(jì)算一個(gè)進(jìn)程的理想運(yùn)行時(shí)間，理想運(yùn)行時(shí)間是調(diào)度周期 * 當(dāng)前調(diào)度實(shí)體權(quán)重 / 所有實(shí)體權(quán)重，如果當(dāng)前進(jìn)程運(yùn)行的時(shí)間超過了這個(gè)理想運(yùn)行時(shí)間，就嘗試一次調(diào)度，即調(diào)用 resched_curr，這個(gè)方法我們?cè)谏厦娣治鲞^：給當(dāng)前進(jìn)程設(shè)置一個(gè)需要調(diào)度的標(biāo)志，這樣在下一次中斷處理返回時(shí)，就會(huì)進(jìn)行一次調(diào)度。

2.4.4 中斷處理返回時(shí)調(diào)度小結(jié)

• 異常的本質(zhì)就是程序不按照正常的流程走。系統(tǒng)調(diào)用是一種異常，硬件中斷也是一種異常，比如我們點(diǎn)擊了鼠標(biāo)，按下了鍵盤，都觸發(fā)了一次異常。
• 內(nèi)核在處理中斷處理返回到用戶空間時(shí)，會(huì)判斷當(dāng)前進(jìn)程是否有設(shè)置需要調(diào)度的標(biāo)志，如果有，就進(jìn)行一次進(jìn)程調(diào)度。
• 某些系統(tǒng)調(diào)用，如 fork、futex 會(huì)在系統(tǒng)調(diào)用處理邏輯中設(shè)置需要調(diào)度的標(biāo)記，這樣在下一次中斷返回就可以進(jìn)行調(diào)度。
• 除了系統(tǒng)調(diào)度，內(nèi)核會(huì)周期性地給內(nèi)核設(shè)置需要調(diào)度的標(biāo)記，一旦當(dāng)前進(jìn)程總運(yùn)行時(shí)間超了，就設(shè)置這個(gè)標(biāo)記，下一次中斷返回就可以進(jìn)行調(diào)度。

2.5 IDLE 進(jìn)程調(diào)度

本文開篇提到了操作系統(tǒng)中的第一個(gè)進(jìn)程，0 號(hào)進(jìn)程，內(nèi)核 無中生有 地創(chuàng)建完這個(gè)進(jìn)程，這個(gè)進(jìn)程總得干點(diǎn)啥。

其中一件事情就是不斷進(jìn)行進(jìn)程調(diào)度，我們來分析一下這個(gè)過程。

2.5.1 第一顆 CPU 上的 IDLE 進(jìn)程

內(nèi)核在啟動(dòng)過程中，第一顆 CPU 進(jìn)入到 start_kernel 方法，這個(gè)方法可以看做初始化整個(gè)內(nèi)核的入口，在調(diào)用這個(gè)方法之前，0 號(hào)進(jìn)程已經(jīng)靜態(tài)地綁在了當(dāng)前的 CPU 上，參考本文 1.3 小節(jié)。

// init/main.c:537 
// 在第一顆 CPU 上執(zhí)行，當(dāng)前進(jìn)程的是 0 號(hào)進(jìn)程 
void start_kernel(void) { 
   ... 
// 一系列初始化操作 
   ... 
   arch_call_rest_init(); // :739 
} 

關(guān)于內(nèi)核的初始化，我們后面再分析，這里我們還是聚焦于 0 號(hào)進(jìn)程的調(diào)度邏輯。

// init/main.c:532 
void arch_call_rest_init(void) { 
 rest_init(); // :534 
} 
 
// init/main.c:397 
void rest_init(void) { 
 int pid; 
    ... 
//  0 號(hào)進(jìn)程創(chuàng)建了 1 號(hào)進(jìn)程 init 
    pid = kernel_thread(kernel_init,...); // :408 
    ... 
//  0 號(hào)進(jìn)程創(chuàng)建了 2 號(hào)進(jìn)程 kthreadd 
    pid = kernel_thread(kthreadd,...); // :420  
    ... 
//  調(diào)度邏輯 
    cpu_startup_entry(CPUHP_ONLINE); 
} 

0 號(hào)進(jìn)程創(chuàng)建了 1 號(hào)進(jìn)程和 2 號(hào)進(jìn)程，我們通過 ps -ef 指令是可以看到這兩個(gè)進(jìn)程，如下圖所示。

1 號(hào)進(jìn)程和 2 號(hào)進(jìn)程

其中的 PPID 就是指的父進(jìn)程的進(jìn)程 ID。用戶空間的所有的進(jìn)程的祖先都是 1 號(hào)進(jìn)程，讀者可以在自己的 Linux 系統(tǒng)上使用 ps -ef 驗(yàn)證這一點(diǎn)。

關(guān)乎這兩個(gè)頂級(jí)進(jìn)程的詳細(xì)分析，我們后面的文章會(huì)提到，這里我們還是聚焦于 0 號(hào)進(jìn)程的調(diào)度邏輯。

0 號(hào)進(jìn)程創(chuàng)建了兩個(gè)頂級(jí)進(jìn)程之后，調(diào)用 cpu_startup_entry

// kernel/sched/idle.c:348 
void cpu_startup_entry(...) { 
    while (1) 
        do_idle(); 
} 
// kernel/sched/idle.c:224 
static void do_idle(void) { 
    ... 
    schedule_idle(); // :286 
    ... 
} 
 
// kernel/sched/core.c:3545 
void schedule_idle(void) { 
    ... 
    __schedule(false); // :3556 
    ... 
} 

從上面的調(diào)用鏈可以看到，0 號(hào)進(jìn)程會(huì)用一個(gè) while 死循環(huán)，不斷反復(fù)地做一件事情，這個(gè)事情就是調(diào)度。

0 號(hào)進(jìn)程可以理解為系統(tǒng)中所有進(jìn)程中優(yōu)先級(jí)最低的進(jìn)程，當(dāng)沒有進(jìn)程可選中被調(diào)度，就選擇 0 號(hào)進(jìn)程，而 0 號(hào)進(jìn)程所做的事情就是一個(gè)死循環(huán)邏輯，由此可見，這個(gè)進(jìn)程確實(shí)閑得慌，所以也叫做 IDLE 進(jìn)程，后面我們統(tǒng)稱為 IDLE 進(jìn)程。

2.5.2 其余 CPU 上的 IDLE 進(jìn)程

除了第一顆 CPU 上有個(gè) IDLE 進(jìn)程不斷在跑，其余 CPU 也都有 IDLE 進(jìn)程不斷在跑，這些個(gè)進(jìn)程是第一顆 CPU 上的 IDLE 進(jìn)程創(chuàng)建出來的，我們來分析一下這個(gè)過程。

在上面的 rest_init 方法中，第一顆 CPU 上的 IDLE 進(jìn)程調(diào)用 kernel_thread 創(chuàng)建了 1 號(hào)進(jìn)程，它的入口函數(shù)是 kernel_init，所以也叫 INIT 進(jìn)程。

下面，我們來追一下這個(gè)調(diào)用鏈。

// init/main.c:1050 
static int kernel_init(void *unused) { 
    ... 
    kernel_init_freeable(); // :1054 
    ... 
} 
 
// init/main.c:1103 
static void kernel_init_freeable(void) { 
    ... 
    smp_init(); // :1129 
    ... 
} 
 
// kernel/smp.c:563 
void smp_init(void) { 
    ... 
//  創(chuàng)建出其他的 IDLE 進(jìn)程  
    idle_threads_init();  
    pr_info("Bringing up secondary CPUs ...\n"); 
    ... 
//  啟動(dòng)其他 CPU 
    for_each_present_cpu(cpu) { 
    ... 
        cpu_up(cpu); 
    } 
} 

在 smp_init 方法中，先通過 idle_threads_init 方法復(fù)制出一堆 IDLE 進(jìn)程，假設(shè)有 4 顆 CPU，除去當(dāng)前進(jìn)程，就復(fù)制出 3 個(gè) IDLE 進(jìn)程。

// kernel/smpboot.c:66 
void idle_threads_init(void) { 
    unsigned int cpu, boot_cpu; 
 
    boot_cpu = smp_processor_id(); 
 
    for_each_possible_cpu(cpu) { 
       if (cpu != boot_cpu) 
           idle_init(cpu); 
     } 
} 
 
// kernel/smpboot.c:50 
static void idle_init(unsigned int cpu) { 
    struct task_struct *tsk = per_cpu(idle_threads, cpu); 
 
    if (!tsk) { 
//      復(fù)制進(jìn)程  
        tsk = fork_idle(cpu); 
        per_cpu(idle_threads, cpu) = tsk; 
    } 
} 

上面的邏輯即是，如果某個(gè) CPU 上沒有綁定 IDLE 進(jìn)程，就調(diào)用 fork_idle 進(jìn)行創(chuàng)建，通過 per_cpu 進(jìn)行綁定。

這些IDLE 進(jìn)程初始化完成之后，開始加載其余 CPU，入口函數(shù)是 secondary_start_kernel，我們還是拿 arm64 架構(gòu)為例來分析。

// arch/arm64/kernel/smp.c:187 
void secondary_start_kernel(void) { 
    ... 
    cpu_startup_entry(CPUHP_AP_ONLINE_IDLE); // :252  
} 
 
// kernel/sched/idle.c:348 
void cpu_startup_entry(...) { 
    while (1) 
        do_idle(); 
} 

至此，我們發(fā)現(xiàn)，其余 CPU 的 IDLE 進(jìn)程也是和第一顆 CPU 的 IDLE 進(jìn)程做著一樣的事情，即不斷死循環(huán)進(jìn)行進(jìn)程調(diào)度，最終目的都是為了當(dāng)前 CPU 一直可以有機(jī)器指令在跑。

2.5.3 IDLE 進(jìn)程調(diào)度小結(jié)

• 內(nèi)核的核心初始化流程是由第一顆 CPU 來做的，在這個(gè)流程中，第一個(gè) IDLE 進(jìn)程創(chuàng)建了 1 號(hào)進(jìn)程和 2 號(hào)進(jìn)程。
• 所有用戶空間的祖先進(jìn)程都是 1 號(hào)進(jìn)程，也叫 INIT 進(jìn)程，我們熟悉的 "僵尸進(jìn)程" 最后都會(huì)被 INIT 進(jìn)程給清理。
• INIT 進(jìn)程還給其余 CPU 創(chuàng)建了 IDLE 進(jìn)程。
• IDLE 進(jìn)程帶有一個(gè)死循環(huán)邏輯，持續(xù)不斷嘗試進(jìn)程調(diào)度，為的就是 CPU 上一直可以有機(jī)器指令在執(zhí)行。

2.6 進(jìn)程調(diào)度時(shí)機(jī)小結(jié)

• 系統(tǒng)調(diào)用 yield、pause 會(huì)使得當(dāng)前進(jìn)程讓出 CPU，隨后進(jìn)行一次進(jìn)程調(diào)度。
• 系統(tǒng)調(diào)用 futex(wait) 等待某個(gè)信號(hào)量，將進(jìn)程設(shè)置為 TASK_INTERRUPTIBLE 狀態(tài)，然后進(jìn)行一次進(jìn)程調(diào)度。
• 進(jìn)程在退出的時(shí)候，會(huì)系統(tǒng)調(diào)用到 exit 方法，將當(dāng)前進(jìn)程設(shè)置為 TASK_DEAD 之后，進(jìn)行一次進(jìn)程調(diào)度。
• 在創(chuàng)建新進(jìn)程、喚醒進(jìn)程、周期調(diào)度過程中，內(nèi)核會(huì)給當(dāng)前進(jìn)程設(shè)置一個(gè)需要調(diào)度的標(biāo)志，然后在下一次中斷返回到用戶空間時(shí)，進(jìn)行一次調(diào)度。

3 本文總結(jié)

我們通常意識(shí)上的進(jìn)程在 Linux 內(nèi)核中的實(shí)體是由 task_struct 來承載，這個(gè)數(shù)據(jù)結(jié)構(gòu)有進(jìn)程所有的信息。

0 號(hào)進(jìn)程，即 IDLE 進(jìn)程是在代碼中靜態(tài)定義的，是所有進(jìn)程的祖先，它創(chuàng)造了 1 號(hào)進(jìn)程，也就是 INIT 進(jìn)程，這個(gè)進(jìn)程是所有用戶空間進(jìn)程的祖先。

在一些系統(tǒng)調(diào)用過程中，會(huì)直接觸發(fā)進(jìn)程調(diào)度，在另一些系統(tǒng)調(diào)用中，會(huì)設(shè)置需要調(diào)度的標(biāo)志，以便中斷返回時(shí)進(jìn)行一次進(jìn)程調(diào)度。

內(nèi)核也會(huì)周期性地進(jìn)行調(diào)度，其中一個(gè)是周期性地給進(jìn)程設(shè)置需要調(diào)度的標(biāo)志，另一個(gè)就是 IDLE 進(jìn)程不斷嘗試調(diào)度。

4 結(jié)語

本來這篇文章的規(guī)劃是將進(jìn)程切換的核心邏輯也包含在內(nèi)的，沒想到光是前面一部分就耗費(fèi)了如此多的篇幅，所以進(jìn)程切換的詳細(xì)邏輯就放在下一篇文章中寫了。

進(jìn)程切換的邏輯非常有意思：包括如何切換虛擬內(nèi)存，切換寄存器和棧，甚至在多個(gè) CPU 之間進(jìn)行負(fù)載均衡等等。歡迎大家關(guān)注后續(xù)的 Linux 內(nèi)核系列文章。

本文轉(zhuǎn)載自微信公眾號(hào)「閃電俠的博客」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系閃電俠的博客公眾號(hào)。