本文所有的源碼都可以在 https://elixir.bootlin.com/linux/v5.0/source 中找到流济，文中每一段源碼都標(biāo)注了文件地址及對應(yīng)行數(shù)揩懒，建議讀者閱讀文章時參考。

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

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

0 本文核心內(nèi)容預(yù)覽

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

1 進(jìn)程概要

• 進(jìn)程是人類創(chuàng)造出來的虛擬概念，每個進(jìn)程對應(yīng)一個 task_struct 數(shù)據(jù)結(jié)構(gòu)塘娶，這個數(shù)據(jù)結(jié)構(gòu)包含了進(jìn)程的所有的信息。
• 在 Linux 內(nèi)核中痊夭，不會區(qū)分線程和進(jìn)程的概念刁岸，線程也是通過進(jìn)程來實(shí)現(xiàn)的，線程和進(jìn)程的唯一區(qū)別就是：線程沒有獨(dú)立的資源她我，進(jìn)程有虹曙。
• 所有的進(jìn)程都是通過其他進(jìn)程創(chuàng)建出來的，因此番舆，整個進(jìn)程組織為一顆進(jìn)程樹酝碳。
• 0 號進(jìn)程是 無中生有 憑空產(chǎn)生的，是靜態(tài)定義出來的恨狈，是所有進(jìn)程的祖先击敌。

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

• 系統(tǒng)調(diào)用 yield、pause 將當(dāng)前進(jìn)程讓出 CPU拴事，隨后會進(jìn)行一次進(jìn)程調(diào)度沃斤。
• 系統(tǒng)調(diào)用 futex（wait） 等待某個信號量，將進(jìn)程設(shè)置為 TASK_INTERRUPTIBLE 狀態(tài)刃宵，然后進(jìn)行一次進(jìn)程調(diào)度衡瓶。
• 進(jìn)程在退出的時候，會系統(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)核會將當(dāng)前的進(jìn)程設(shè)置需要調(diào)度的標(biāo)志捂齐，然后在下一次中斷返回到用戶空間時蛮放，進(jìn)行一次調(diào)度。

1 進(jìn)程概要

1.1 進(jìn)程是虛擬的概念

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

• 加載器將可執(zhí)行程序文件（Linux 中是 ELF 格式）加載到操作系統(tǒng)岳悟，操作系統(tǒng)中就多了一個進(jìn)程佃迄。
• 進(jìn)程的核心由代碼段和數(shù)據(jù)段組成，代碼段就是進(jìn)程在執(zhí)行過程中按照正常流程一條條執(zhí)行的指令贵少，數(shù)據(jù)段就是指令需要的數(shù)據(jù)呵俏。
• 每顆 CPU 都有一個 PC（Program Counter）寄存器，這個寄存器指向了下一條要執(zhí)行的指令地址春瞬，由于這個指令必然屬于某個進(jìn)程，所以套啤，每個 CPU 每一時刻只能運(yùn)行一個進(jìn)程宽气。
• 多線程在內(nèi)核空間本質(zhì)上也是多進(jìn)程，多個進(jìn)程在時間較大的尺度上給人一種可以同時執(zhí)行的錯覺潜沦，本質(zhì)上是通過調(diào)度程序交叉執(zhí)行萄涯，只不過這個時間太短，我們感覺不到而已唆鸡。
• JVM 中的一個線程對應(yīng)了 Linux 內(nèi)核中的一個進(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，這個數(shù)據(jù)結(jié)構(gòu)里面的字段有幾十個臂痕，我不太想一一列出來伯襟，然后占很大篇幅，我會列幾個大家比較關(guān)心的握童，在后面的分析過程中姆怪，會逐漸展開 task_struct 的其他字段。
本篇文檔對應(yīng)的 Linux 內(nèi)核是 5.0

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

從上面的幾個關(guān)鍵的字段可以看出澡绩，每個進(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)程的資源沮稚，對應(yīng)這個數(shù)據(jù)結(jié)構(gòu)，只要把里面涉及共享的指針指向進(jìn)程的資源即可册舞。

1.3 特殊的進(jìn)程

"所有的進(jìn)程都有父親"蕴掏，這句話不一定全對，就像演繹邏輯鏈一樣调鲸，我們一直順著大前提往上追盛杰，總會追到第一個 大 bug，這個 大 bug 我們無法證明藐石，只能默認(rèn)它是對的即供，它是我們系統(tǒng)的第一性原理。
扯遠(yuǎn)了于微，Linux 中逗嫡，這個 大 bug 就是 0 號進(jìn)程，它的另一個外號叫 idle株依，這個 大 bug 在內(nèi)核初始化的時候驱证，被顯示地定義出來（而不是通過 fork），下面我們來感受一下 Linux 進(jìn)程子系統(tǒng)中第一個進(jìn)程 無中生有 的過程恋腕。

// include/linux/sched/task.h:26
extern struct task_struct init_task; // 這個就是 0 號進(jìn)程

// init/init_task.c:57
struct task_struct init_task = {
    .pid        = 0,   // 這個字段沒有顯示定義出來抹锄，而是通過 struct pid 來描述，效果一樣
    .state      = 0, // 對應(yīng)了 TASK_RUNNING
    .parent     = &init_task, // 我就是第一個進(jìn)程荠藤，我沒有 parent
    .children   = LIST_HEAD_INIT(init_task.children), // 初始化子進(jìn)程鏈表
};

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

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

• 進(jìn)程是人類創(chuàng)造出來的虛擬概念输瓜，每個進(jìn)程對應(yīng)一個 task_struct 數(shù)據(jù)結(jié)構(gòu)纵潦，這個數(shù)據(jù)結(jié)構(gòu)包含了進(jìn)程的所有的信息溺健。
• 在 Linux 內(nèi)核中丘喻，不會區(qū)分線程和進(jìn)程的概念膝但，線程也是通過進(jìn)程來實(shí)現(xiàn)的荒辕，線程和進(jìn)程的唯一區(qū)別就是：線程沒有獨(dú)立的資源总寻，進(jìn)程有器罐。
• 所有的進(jìn)程都是通過其他進(jìn)程創(chuàng)建出來的渐行，因此轰坊，整個進(jìn)程組織為一刻進(jìn)程樹铸董。
• 0 號進(jìn)程是 無中生有 憑空產(chǎn)生的，是靜態(tài)定義出來的肴沫，是所有進(jìn)程的祖先粟害。

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

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

2.1 yield 和 pause 讓出 cpu

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

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ù)的個數(shù)，sched_yield 系統(tǒng)調(diào)用沒有參數(shù)澜倦，所以 x 是零聚蝶。

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

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

我們發(fā)現(xiàn)既荚，在 4960 行稚失，有一個命名非常簡單的函數(shù)調(diào)用栋艳，叫做 schedule()，這個函數(shù)就是內(nèi)核中進(jìn)程調(diào)度及切換的始源句各，我們分析進(jìn)程調(diào)度的時機(jī)吸占，等價于查看有哪些地方調(diào)用了這個方法。

下面我們來看看 pause 這個系統(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)度中就可以忽略這個進(jìn)程初厚，選擇其他的進(jìn)行件蚕。
接著，同樣是一個簡單的 schedule 函數(shù)产禾，進(jìn)入到調(diào)度的邏輯排作。

2.2 futex 等待資源

futex (fast userspace mutex)，用來給上層應(yīng)用構(gòu)建更高級別的同步機(jī)制亚情，是實(shí)現(xiàn)信號量和鎖的基礎(chǔ)妄痪，后面有機(jī)會可以單獨(dú)介紹。
我們簡化一下：一個進(jìn)程在等待某個信號的時候楞件，最終會通過系統(tǒng)調(diào)用進(jìn)入到 futex衫生，其中某個關(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
}

這個系統(tǒng)調(diào)用有 6 個參數(shù)裳瘪，參數(shù)類型和名稱并列展開，上層應(yīng)用在等待一個信號量的時候罪针，這里的 op 是 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)長站故，下面我們就簡化一下調(diào)用邏輯皆怕，專注核心，這個在我們?nèi)ラ喿x源碼過程中西篓，也是非常重要的一點(diǎn)愈腾，閱讀核心邏輯的時候，不要被太多的細(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)用鏈下來吮成，我們可以看到橱乱，調(diào)用 futex 的 wait 操作，可能會將自己設(shè)置為睡眠狀態(tài)并且進(jìn)行一次進(jìn)程調(diào)度粱甫。

2.3 exit 進(jìn)程退出

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

// 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)
{
    // 這個地方也是給 task_struct 中的 state 字段賦值
    set_special_state(TASK_DEAD);
    ...
    __schedule(false); // :3502
    ...
}

通過調(diào)用鏈，我們可以看到乌庶，進(jìn)程在退出的時候种蝶，最終調(diào)用了 __schedule 方法，這里我們可以將這個方法等價于 schedule 方法瞒大，schedule 方法最終會調(diào)用到這個方法螃征，__schedule 中描述了進(jìn)程調(diào)度的核心邏輯。

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

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

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

系統(tǒng)調(diào)用是常見一種類型的異常退渗，也是用戶空間主動進(jìn)入內(nèi)核空間的唯一方式移稳。另外一種常見的異常就是硬件中斷，比如我們點(diǎn)下鼠標(biāo)会油，按下鍵盤个粱，網(wǎng)卡接受到數(shù)據(jù)，都是一次硬件中斷翻翩，運(yùn)行在用戶空間的進(jìn)程會被動陷入到內(nèi)核空間都许，進(jìn)行中斷處理程序的處理。

而中斷處理程序在返回至用戶空間之前嫂冻，會順帶做一件事情胶征，判斷是否要進(jìn)行進(jìn)程調(diào)度，我們通過調(diào)用鏈來分析一下這個過程桨仿。

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

// arch/arm64/kernel/entry.S:838
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 寄存器罩抗。

#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 中的這個邏輯就是，取出這個 flags 字段阱扬，然后通過 and 操作取出 work_pending 這個方法關(guān)心的二進(jìn)制位的值泣懊。

// 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 寄存器中的值
asmlinkage void do_notify_resume(struct pt_regs *regs, unsigned long thread_flags) {
    ...
    if (thread_flags & _TIF_NEED_RESCHED) {
        schedule(); // :933
    } 
    ...
}

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

系統(tǒng)調(diào)用是我們主動從用戶空間進(jìn)入內(nèi)核空間的唯一方式，進(jìn)入到內(nèi)核空間才能夠設(shè)置當(dāng)前進(jìn)程的需要調(diào)度的標(biāo)志振湾，下面我們就來分析有哪些系統(tǒng)調(diào)用會設(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()浅碾，最后都會落到 fork 系統(tǒng)調(diào)用。

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

// 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)程的時候，有部分工作是復(fù)制父進(jìn)程力试，也就是當(dāng)前進(jìn)程的數(shù)據(jù)結(jié)構(gòu)徙邻，線程和進(jìn)程的本質(zhì)區(qū)別就在這個方法里面，用一個參數(shù)確定要復(fù)制哪些資源畸裳，我們在后面的文章中會詳細(xì)分析鹃栽，這里我們點(diǎn)到為止。

創(chuàng)建完當(dāng)前進(jìn)程之后躯畴，調(diào)用 wake_up_new_task 喚醒當(dāng)前進(jìn)程民鼓，我們來看內(nèi)核是如何喚醒當(dāng)前進(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 會根據(jù)當(dāng)前進(jìn)程的調(diào)度類型丰嘉，執(zhí)行對應(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)度類型嚷缭，這個字段在每個 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ì)分析這五個調(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(struct rq *rq, struct task_struct *p, int wake_flags) {
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;
 
    // 如果 pse 的虛擬時間小于當(dāng)前進(jìn)程的虛擬時間佣渴，就搶占
    if (wakeup_preempt_entity(se, pse) == 1) { // :6867
        goto preempt;
    }
preempt: // :6879
    // 沒有在這里直接調(diào)度辫狼，而是設(shè)置了一個標(biāo)志，在異常處理返回的時候統(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í)體這個對象也定義在進(jìn)程的數(shù)據(jù)結(jié)構(gòu)中。

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

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

下面我們來看下 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)行的最小時間片
    gran = wakeup_gran(se); 
    if (vdiff > gran)
        return 1;

    return 0;
}

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

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

上面這段代碼的邏輯黄琼，總結(jié)來說就是樊销，如果當(dāng)前進(jìn)程的時間片已到，并且當(dāng)前進(jìn)程的虛擬時間小于 fork 出來的進(jìn)程的虛擬時間片（顯然是 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è)置一個標(biāo)記剂府，需要進(jìn)行一次調(diào)度，根據(jù)我們上一節(jié)的分析剃盾，下一次中斷返回到用戶空間的時候腺占，就會進(jìn)行一次調(diào)度。

2.4.2 futex 喚醒進(jìn)程

除了 fork 系統(tǒng)調(diào)用痒谴，在 futex 系統(tǒng)調(diào)用的時候衰伯，也會設(shè)置需要調(diào)度的標(biāo)記。

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

這里的 op 是 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)用鏈路有些長库倘，我們中間的代碼描述簡化處理临扮，最終會落到下面的代碼

// kernel/sched/core.c:1667
static void ttwu_do_wakeup(...) {
    check_preempt_curr(...);
}

即 futex 的 wake 操作论矾，最后同樣會落到和 fork 系統(tǒng)調(diào)用一樣的方法 check_preempt_curr教翩，這個方法我們上面剛分析過，做的事情就是給當(dāng)前線程設(shè)置一個需要調(diào)度的標(biāo)記贪壳，在下一次中斷返回時進(jìn)行一次調(diào)度饱亿。

2.4.3 周期調(diào)度

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

// kernel/sched/core.c:3049
/*
 * This function gets called by the timer code, with HZ frequency.
 */
void scheduler_tick(void) {
    ...
    // 當(dāng)前是哪個 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)行時間
    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就緒進(jìn)程和運(yùn)行進(jìn)程的個數(shù)泵肄，大于 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 方法中腐巢，會計(jì)算一個進(jìn)程的理想運(yùn)行時間品追，理想運(yùn)行時間是調(diào)度周期 * 當(dāng)前調(diào)度實(shí)體權(quán)重 / 所有實(shí)體權(quán)重，如果當(dāng)前進(jìn)程運(yùn)行的時間超過了這個理想運(yùn)行時間冯丙，就嘗試一次調(diào)度肉瓦，即調(diào)用 resched_curr，這個方法我們在上面分析過：給當(dāng)前進(jìn)程設(shè)置一個需要調(diào)度的標(biāo)志胃惜，這樣在下一次中斷處理返回時泞莉，就會進(jìn)行一次調(diào)度。

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

關(guān)于中斷處理返回時調(diào)度船殉，我們做小結(jié)：

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

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

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

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

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

內(nèi)核在啟動過程中酥夭，第一顆 CPU 進(jìn)入到 start_kernel 方法，這個方法可以看做初始化整個內(nèi)核的入口脊奋，在調(diào)用這個方法之前采郎，0 號進(jìn)程已經(jīng)靜態(tài)地綁在了當(dāng)前的 CPU 上。

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

關(guān)于內(nèi)核的初始化蒜埋，我們后面再分析，這里我們還是聚焦于 0 號線程的調(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 號進(jìn)程創(chuàng)建了 1 號進(jìn)程 init
    pid = kernel_thread(kernel_init,...); // :408
    ...
    // 0 號進(jìn)程創(chuàng)建了 2 號進(jìn)程 kthreadd
    pid = kernel_thread(kthreadd,...); // :420 
    ...
    // 調(diào)度邏輯
    cpu_startup_entry(CPUHP_ONLINE);
}

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

1號和2號進(jìn)程.png

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

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

0 號進(jìn)程創(chuàng)建了兩個頂級進(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 號進(jìn)程會用一個 while 死循環(huán)玻熙，不斷反復(fù)地做一件事情否彩，這個事情就是調(diào)度。

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

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

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

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

下面蔚袍，我們來追一下這個調(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(); // smp.c:563
    ...
}

// kernel/smp.c:563
void smp_init(void) {
    ...
    // 創(chuàng)建出其他的 IDLE 進(jìn)程 
    idle_threads_init(); 
    pr_info("Bringing up secondary CPUs ...\n");
    ...
    // 啟動其他 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 個 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;
    }
}

上面的邏輯即是，如果某個 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 來做的鸯匹，在這個流程中剃斧，第一個 IDLE 進(jìn)程創(chuàng)建了 1 號進(jìn)程和 2 號進(jìn)程。
• 所有用戶空間的祖先進(jìn)程都是 1 號進(jìn)程忽你，也叫 INIT 進(jìn)程幼东，我們熟悉的 "僵尸進(jìn)程" 最后都會被 INIT 進(jìn)程給清理。
• INIT 進(jìn)程還給其余 CPU 創(chuàng)建了 IDLE 進(jìn)程科雳。
• IDLE 進(jìn)程帶有一個死循環(huán)邏輯根蟹，持續(xù)不斷嘗試進(jìn)程調(diào)度，為的就是 CPU 上一直可以有機(jī)器指令在執(zhí)行糟秘。

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

• 系統(tǒng)調(diào)用 yield简逮、pause 將當(dāng)前進(jìn)程讓出 CPU，隨后會進(jìn)行一次進(jìn)程調(diào)度尿赚。
• 系統(tǒng)調(diào)用 futex（wait） 等待某個信號量散庶，將進(jìn)程設(shè)置為 TASK_INTERRUPTIBLE 狀態(tài)蕉堰，然后進(jìn)行一次進(jìn)程調(diào)度。
• 進(jìn)程在退出的時候悲龟，會系統(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)核會將當(dāng)前的進(jìn)程設(shè)置需要調(diào)度的標(biāo)志尉桩，然后在下一次中斷返回到用戶空間時，進(jìn)行一次調(diào)度。

3 本文總結(jié)

• 我們通常意識上的進(jìn)程在 Linux 內(nèi)核中的實(shí)體是由 task_struct 來承載埃唯，這個數(shù)據(jù)結(jié)構(gòu)有進(jìn)程所有的信息漠趁。
• 0 號進(jìn)程卤妒，即 IDLE 進(jìn)程是在代碼中靜態(tài)定義的洗出，是所有進(jìn)程的祖先，它創(chuàng)造了 1 號進(jìn)程，也就是 INIT 進(jìn)程，這個進(jìn)程是所有用戶空間進(jìn)程的祖先。
• 在一些系統(tǒng)調(diào)用過程中，會直接觸發(fā)進(jìn)程調(diào)度，在另一些系統(tǒng)調(diào)用中，會設(shè)置需要調(diào)度的標(biāo)志熊杨，以便中斷返回時進(jìn)行一次進(jìn)程調(diào)度岭皂。
• 內(nèi)核也會周期性地進(jìn)行調(diào)度进倍，其中一個是周期性地給進(jìn)程設(shè)置需要調(diào)度的標(biāo)志垂蜗，另一個就是 IDLE 進(jìn)程不斷嘗試調(diào)度片部。

4 結(jié)語

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

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