[[440610]]

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

進程概要及調度時機

這篇文章從 Linux 內核層面分析進程概要及調度時機。

0 本文內容一分鐘速覽

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

0.1 進程概要

• 進程是對物理世界的建模抽象，每個進程對應一個 task_struct 數據結構，這個數據結構包含了進程的所有的信息。
• 在 Linux 內核中，不會區分線程和進程的概念，線程也是通過進程來實現的，線程和進程的唯一區別就是：線程沒有獨立的資源，進程有。
• 所有的進程都是通過其他進程創建出來的，因此，整個進程組織為一棵進程樹。
• 0 號進程是 無中生有 憑空產生的，是靜態定義出來的，是所有進程的祖先，創建了 INIT(1號)和 kthreadd(2號進程)。

0.2 進程調度時機

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

1 進程概要

1.1 進程是對物理世界的建模抽象

人們在面對一個問題束手無策的時候，經常會創造一個概念，然后基于這個概念來演化出一個系統來解決這個問題。進程的概念就是人類發明出來，為了解決物理世界想要同時做若干件事情的需求，最終演化出了進程子系統。關于進程的基本知識網上有很多，這里說下我的理解：

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

1.2 進程的數據結構

由于歷史原因，內核中表示進程的數據結構叫做 task_struct，這個數據結構里面的字段有幾十個，我不太想一一列出來，然后占很大篇幅。我會列幾個大家比較關心的，在后面的分析過程中，會逐漸展開 task_struct 的其他字段。本篇文檔對應的 Linux 內核是 5.0。

// include/linux/sched.h:592 
// Linnux 進程底層對應的數據結構 
struct task_struct { 
//  進程的 ID 
    pid_t pid; 
//  進程的狀態     
    volatile long state; 
//  進程的父親     
    struct task_struct *parent; 
//  當前進程的子進程     
    struct list_head children;   
}; 

從上面的幾個關鍵的字段可以看出，每個進程都有唯一的 ID 和狀態，并且，在系統中，進程是通過一棵樹的方式來組織的，也就是說，所有的進程都有父親，通過我們熟悉的 fork 系統調用來創造。另外，Linux 內核中也是不區分進程和線程的，兩者均使用 task_struct 數據結構，線程的本質是共享進程的資源，對應這個數據結構，只要把里面涉及共享的指針指向進程的資源即可。

1.3 特殊的進程

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

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

init_task 類似于盤古，系統中所有的進程都是由它開辟出來的，在后續的 Linux 內核文章中，我們會逐漸了解這個機制的妙處，我們先把注意力調回到本篇文章的重點，進程切換的機制。

1.4 進程概要小結

• 進程是對物理世界的建模抽象，每個進程對應一個 task_struct 數據結構，這個數據結構包含了進程的所有的信息。
• 在 Linux 內核中，不會區分線程和進程的概念，線程也是通過進程來實現的，線程和進程的唯一區別就是：線程沒有獨立的資源，進程有。
• 所有的進程都是通過其他進程創建出來的，因此，整個進程組織為一棵進程樹。
• 0 號進程是 無中生有 憑空產生的，是靜態定義出來的，是所有進程的祖先。

2 進程調度時機

Linux 內核中，進程調度的時機無處不在，我們來了解幾個典型的時機。

2.1 yield 和 pause 讓出 cpu

通常情況下，我們的進程運行在用戶空間，通過系統調用進入到內核空間，從而做一些更高級的事情。

yield 系統調用可以讓當前進程放棄 cpu，進行系統的調度。

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

Linux 中的系統調用通過類似 SYSCALL_DEFINEx 這種方式定義，x 表示參數的個數，sched_yield 系統調用沒有參數，所以 x 是 0。

我們沿著調用鏈往下，來到 do_sched_yield 方法。

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

我們發現，在 4960 行，有一個命名非常簡單的函數調用，叫做 schedule()，這個函數就是內核中進程調度的入口，我們分析進程調度的時機，等價于查看有哪些地方調用了這個方法。

下面我們來看看 pause 這個系統調用：

// 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 系統調用首先將當前進程設置為 TASK_INTERRUPTIBLE 狀態，其實就是給 task_struct 結構中的 state 字段賦值，附上 TASK_INTERRUPTIBLE 之后，在后續進程調度中就可以過濾掉這個進程，選擇其他的進程進行調度。接著，同樣是一個簡單的 schedule 函數，進入到調度的邏輯。

2.2 futex 等待資源

futex (fast userspace mutex)，用來給上層應用構建更高級別的同步機制，是實現信號量和鎖的基礎，后面有機會可以單獨介紹。我們簡化一下場景：一個進程在等待某個信號的時候，最終會通過系統調用進入到 futex，其中某個關鍵參數為 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 
} 

這個系統調用有 6 個參數，參數類型和名稱并列展開，上層應用在等待一個信號量的時候，給 op 這個參數的傳遞的是 FUTEX_WAIT_BITSET，我們通過調用鏈往下追。

// 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 
    ... 
    } 
    ... 
} 

由于中間調用鏈有點長，下面我們就簡化一下調用邏輯，專注核心，這個在我們去閱讀源碼過程中，也是非常重要的一點，閱讀核心邏輯的時候，不要被太多的細節干擾。

// kernel/futex.c:2679 
static int futex_wait(...) { 
    ... 
    futex_wait_queue_me(...); // :2713 
    ... 
} 
 
// kernel/futex.c:2571  
static void futex_wait_queue_me(...) { 
    ... 
//  這里可以看到，調用 futex 的進程將變為睡眠狀態，與我們的認知一致 
    set_current_state(TASK_INTERRUPTIBLE); // :2580 
    ... 
    freezable_schedule(); // :2598 
    ... 
} 
 
// include/linux/freezer.h:169 
static inline void freezable_schedule(void) { 
    ... 
    schedule(); // :180 
    ... 
} 

沿著進程調用鏈下來，我們可以看到，進程系統調用 futex(wait) 時，可能會將自己設置為睡眠狀態并且進行一次進程調度。

2.3 exit 進程退出

多年的編程經驗告訴我們，在一個進程退出的時候會觸發進程調度，我們通過內核源碼來證明這一點。應用層的進程在退出時，最終會通過 exit 系統調用進入到內核，調用鏈如下：

// 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 
    ... 
} 

通過調用鏈，我們可以看到，進程在退出的時候，最終調用了 __schedule 方法，這里我們可以將這個方法等價于 schedule 方法，因為 schedule 方法最終會調用到這個方法，__schedule 中描述了進程調度的核心邏輯。

2.4 中斷返回時調度

除了上述調度時機，還有一類調度時機是中斷返回的時候。

介紹中斷之前，先描述一下什么是異常：進程的指令按照程序正常流程一直在 CPU 上跑，系統突然發生了一個帶有異常號的異常，強迫 CPU 停止執行當前的指令，CPU 隨后會在執行完當前指令之后，保存現場，根據異常號跳轉到異常處理程序，處理完之后，回到被異常終止的下一條機器指令繼續執行。

系統調用是常見一種類型的異常，也是應用代碼從用戶空間主動進入內核空間的唯一方式。另外一種常見的異常就是硬件中斷，比如我們點下鼠標、按下鍵盤、網卡接收到數據、磁盤數據讀寫完畢等，都會觸發一次硬件中斷，運行在用戶空間的進程會被動陷入到內核空間，進行中斷處理程序的處理。

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

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

// 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(也就是被中斷暫停的當前進程)數據結構中，偏移量為 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 
    ...         
} 

本質上，就是 task_struct 結構中的 thread_info 結構中的 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 中的這個邏輯就是，取出 task_struct->thread_info->flags 字段，然后通過與 _TIF_WORK_MASK 進行 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) 

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

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

到了這里，中斷返回到用戶空間的調度邏輯大家應該比較清楚了。我們總結一點就是：當中斷處理程序返回用戶空間的時候，如果被中斷的進程被設置了需要進程調度標志，那么就進行一次進程調度。

那么，什么時候當前進程會被設置這個標志?

只有進入到內核空間才能夠設置當前進程的需要調度標志，而系統調用是我們主動從用戶空間進入內核空間的唯一方式，下面我們就來分析有哪些系統調用會設置當前進程需要調度的標志。

2.4.1 創建新進程

第一類是是通過 fork 系統調用創建新的進程。相信大家應該或多或少聽過，大多數編程語言創建線程，比如 Java 的 new Thread(...).start()，最后都會落到 fork 系統調用。

接下來，我們來分析 fork 系統調用是如何來設置進程需要調度的標識的。

// kernel/fork.c:2291 
SYSCALL_DEFINE0(fork) { 
    ... 
    return _do_fork(...); 
} 
 
// kernel/fork.c:2196 
long _do_fork(...) { 
    struct task_struct *p; 
    ... 
//  大多數數據結構都是 copy 的父進程，也就是當前進程 
    p = copy_process(...); // :2227 
    ... 
//  創建完子進程之后，讓子進程 "蘇醒" 
    wake_up_new_task(p); // :2252 
    ... 
} 

這里我們可以看到，創建子進程的時候，有部分工作是復制父進程(2227 行)，也就是當前進程的數據結構，線程和進程的本質區別就在這個方法里面，用一個參數確定要復制哪些資源，我們在后面的文章中會詳細分析進程創建過程，這里我們點到為止。

創建完新進程之后，調用 wake_up_new_task 喚醒新進程，我們來看內核是如何喚醒新進程的。

// kernel/sched/core.c:2413 
void wake_up_new_task(struct task_struct *p) { 
    ... 
//  將當前進程設置為 RUNNING 狀態，后續即可調度 
    p->state = TASK_RUNNING; // :2419  
    ... 
//  判斷是否要搶占當前進程 
    check_preempt_curr(rq, p, WF_FORK); // :2439 
    ... 
} 

check_preempt_curr 會根據當前進程的調度類型，執行對應的方法：

// kernel/sched/core.c:854 
void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags) { 
    ... 
//  rq 是當前 cpu 上的進程隊列 
//  curr 是當前正在 cpu 運行的進程 
//  sched_class 是當前進程的調度 
    rq->curr->sched_class->check_preempt_curr(rq, p, flags); // :858 
    ... 
} 

sched_class 表示進程的調度類型，這個字段在每個 task_struct 中。

// include/linux/sched.h:592 
struct task_struct { 
    ... 
//  sched_class 在進程的數據結構中 
//  表示調度類型，我們后面的系列文章再詳細分析  
    const struct sched_class *sched_class; // :643 
    ... 
} 
 
// kernel/sched/sched.h:1715 
// Linux 中所有的調度類型 
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 中一共有五種調度類型，fair_sched_class 是一般進程的調度類型，稱為公平調度，我們后面的文章中再詳細分析這五個調度類型，這里，我們還是聚焦重點。

我們跟隨調用鏈，來到 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 的虛擬時間小于當前進程的虛擬時間，就搶占 
    if (wakeup_preempt_entity(se, pse) == 1) { // :6867 
        goto preempt; 
     } 
preempt: // :6879 
//  沒有在這里直接調度，而是設置了一個標志，在異常處理返回的時候統一調度 
    resched_curr(rq); 
} 

check_preempt_wakeup 方法中一處關鍵的地方，se 表示當前進程的調度實體，pse 表示 fork 出來的進程的調度實體。

調度實體這個對象也定義在進程的數據結構中。

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

調度實體是為了防止一個進程不斷地 fork 多個子進程，從而無限霸占 cpu，內核可以將一組線程綁定到一起進行統一調度，這里我們不用關心太多細節，仍然聚焦核心。

下面我們來看下 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 可以理解為進程運行的最小時間片 
    gran = wakeup_gran(se);  
    if (vdiff > gran) 
        return 1; 
 
    return 0; 
} 

公平調度類默認會通過進程的優先級和歷史運行情況來計算出一個進程運行的虛擬時間，虛擬時間小的進程可以搶占虛擬時間大的進程。

當然，為了防止頻繁搶占調度，要保證進程在 cpu 上的一個最小的運行時間，這個時間默認在 v5.0 內核中是 100 毫秒。

上面這段代碼的邏輯，總結來說就是，如果當前進程的時間片已到，并且當前進程的虛擬時間小于 fork 出來的進程的虛擬時間片(顯然是 0)，則返回 1，然后進入到標記為 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 給當前進程設置一個標志，需要進行一次調度，根據我們上一節的分析，下一次中斷返回到用戶空間的時候，就會進行一次調度。

2.4.2 futex 喚醒進程

除了 fork 系統調用，在 futex 系統調用的時候，也會設置需要調度的標志。

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

這種情況下，用戶傳遞的 op 參數是 FUTEX_WAKE_OP，即用戶需要進行喚醒操作，我們通過調用鏈往下追：

// 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 
} 
 
// 后續調用鏈路有些長，我們中間的代碼描述簡化處理，最終會落到下面的代碼 
 
// kernel/sched/core.c:1667 
static void ttwu_do_wakeup(...) { 
    check_preempt_curr(...); 
} 

可以看到，futex 的 wake 操作，最后同樣會落到和 fork 一樣的方法 check_preempt_curr，這個方法我們上面剛分析過，做的事情就是給當前線程設置一個需要調度的標志，在下一次中斷返回時進行一次調度。

2.4.3 周期調度

除了系統調用，內核還有一個定時調度機制：周期調度，內核會周期地調用 scheduler_tick 方法執行調度邏輯，我們來分析一下這個過程。

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

scheduler_tick 調用當前進程的調度類的 task_tick 方法，我們還是分析常見的公平調度類的 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 可以理解為當前 cpu 上公平調度類的進程隊列 
    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) { 
//  更新當前進程的運行時間 
    update_curr(cfs_q); 
    ... 
//  更新當前進程的 load 
    update_load_avg(cfs_rq, curr, UPDATE_TG); 
    ... 
//  如果 cpu 有就緒進程 
    if (cfs_rq->nr_running > 1) 
        check_preempt_tick(cfs_rq, curr); 
} 

cfs_rq->nr_running 可以理解為當前 cpu 上，公平調度類型的就緒進程和運行進程的和，大于 1 表示有待調度的就緒進程，于是調用 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 方法中，會計算一個進程的理想運行時間，理想運行時間是調度周期 * 當前調度實體權重 / 所有實體權重，如果當前進程運行的時間超過了這個理想運行時間，就嘗試一次調度，即調用 resched_curr，這個方法我們在上面分析過：給當前進程設置一個需要調度的標志，這樣在下一次中斷處理返回時，就會進行一次調度。

2.4.4 中斷處理返回時調度小結

• 異常的本質就是程序不按照正常的流程走。系統調用是一種異常，硬件中斷也是一種異常，比如我們點擊了鼠標，按下了鍵盤，都觸發了一次異常。
• 內核在處理中斷處理返回到用戶空間時，會判斷當前進程是否有設置需要調度的標志，如果有，就進行一次進程調度。
• 某些系統調用，如 fork、futex 會在系統調用處理邏輯中設置需要調度的標記，這樣在下一次中斷返回就可以進行調度。
• 除了系統調度，內核會周期性地給內核設置需要調度的標記，一旦當前進程總運行時間超了，就設置這個標記，下一次中斷返回就可以進行調度。

2.5 IDLE 進程調度

本文開篇提到了操作系統中的第一個進程，0 號進程，內核 無中生有 地創建完這個進程，這個進程總得干點啥。

其中一件事情就是不斷進行進程調度，我們來分析一下這個過程。

2.5.1 第一顆 CPU 上的 IDLE 進程

內核在啟動過程中，第一顆 CPU 進入到 start_kernel 方法，這個方法可以看做初始化整個內核的入口，在調用這個方法之前，0 號進程已經靜態地綁在了當前的 CPU 上，參考本文 1.3 小節。

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

關于內核的初始化，我們后面再分析，這里我們還是聚焦于 0 號進程的調度邏輯。

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

0 號進程創建了 1 號進程和 2 號進程，我們通過 ps -ef 指令是可以看到這兩個進程，如下圖所示。

1 號進程和 2 號進程

其中的 PPID 就是指的父進程的進程 ID。用戶空間的所有的進程的祖先都是 1 號進程，讀者可以在自己的 Linux 系統上使用 ps -ef 驗證這一點。

關乎這兩個頂級進程的詳細分析，我們后面的文章會提到，這里我們還是聚焦于 0 號進程的調度邏輯。

0 號進程創建了兩個頂級進程之后，調用 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 
    ... 
} 

從上面的調用鏈可以看到，0 號進程會用一個 while 死循環，不斷反復地做一件事情，這個事情就是調度。

0 號進程可以理解為系統中所有進程中優先級最低的進程，當沒有進程可選中被調度，就選擇 0 號進程，而 0 號進程所做的事情就是一個死循環邏輯，由此可見，這個進程確實閑得慌，所以也叫做 IDLE 進程，后面我們統稱為 IDLE 進程。

2.5.2 其余 CPU 上的 IDLE 進程

除了第一顆 CPU 上有個 IDLE 進程不斷在跑，其余 CPU 也都有 IDLE 進程不斷在跑，這些個進程是第一顆 CPU 上的 IDLE 進程創建出來的，我們來分析一下這個過程。

在上面的 rest_init 方法中，第一顆 CPU 上的 IDLE 進程調用 kernel_thread 創建了 1 號進程，它的入口函數是 kernel_init，所以也叫 INIT 進程。

下面，我們來追一下這個調用鏈。

// 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) { 
    ... 
//  創建出其他的 IDLE 進程  
    idle_threads_init();  
    pr_info("Bringing up secondary CPUs ...\n"); 
    ... 
//  啟動其他 CPU 
    for_each_present_cpu(cpu) { 
    ... 
        cpu_up(cpu); 
    } 
} 

在 smp_init 方法中，先通過 idle_threads_init 方法復制出一堆 IDLE 進程，假設有 4 顆 CPU，除去當前進程，就復制出 3 個 IDLE 進程。

// 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) { 
//      復制進程  
        tsk = fork_idle(cpu); 
        per_cpu(idle_threads, cpu) = tsk; 
    } 
} 

上面的邏輯即是，如果某個 CPU 上沒有綁定 IDLE 進程，就調用 fork_idle 進行創建，通過 per_cpu 進行綁定。

這些IDLE 進程初始化完成之后，開始加載其余 CPU，入口函數是 secondary_start_kernel，我們還是拿 arm64 架構為例來分析。

// 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(); 
} 

至此，我們發現，其余 CPU 的 IDLE 進程也是和第一顆 CPU 的 IDLE 進程做著一樣的事情，即不斷死循環進行進程調度，最終目的都是為了當前 CPU 一直可以有機器指令在跑。

2.5.3 IDLE 進程調度小結

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

2.6 進程調度時機小結

• 系統調用 yield、pause 會使得當前進程讓出 CPU，隨后進行一次進程調度。
• 系統調用 futex(wait) 等待某個信號量，將進程設置為 TASK_INTERRUPTIBLE 狀態，然后進行一次進程調度。
• 進程在退出的時候，會系統調用到 exit 方法，將當前進程設置為 TASK_DEAD 之后，進行一次進程調度。
• 在創建新進程、喚醒進程、周期調度過程中，內核會給當前進程設置一個需要調度的標志，然后在下一次中斷返回到用戶空間時，進行一次調度。

3 本文總結

我們通常意識上的進程在 Linux 內核中的實體是由 task_struct 來承載，這個數據結構有進程所有的信息。

0 號進程，即 IDLE 進程是在代碼中靜態定義的，是所有進程的祖先，它創造了 1 號進程，也就是 INIT 進程，這個進程是所有用戶空間進程的祖先。

在一些系統調用過程中，會直接觸發進程調度，在另一些系統調用中，會設置需要調度的標志，以便中斷返回時進行一次進程調度。

內核也會周期性地進行調度，其中一個是周期性地給進程設置需要調度的標志，另一個就是 IDLE 進程不斷嘗試調度。

4 結語

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

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

本文轉載自微信公眾號「閃電俠的博客」，可以通過以下二維碼關注。轉載本文請聯系閃電俠的博客公眾號。