vlambda
2022-04-15

【原创】Linux 内核源码分析之进程概要及调度时机

❝
本文涉及的 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 内核系列文章。

vlambda博客
学习文章列表

【原创】Linux 内核源码分析之进程概要及调度时机

进程概要及调度时机

0 本文内容一分钟速览

0.1 进程概要

0.2 进程调度时机

1 进程概要

1.1 进程是对物理世界的建模抽象

1.2 进程的数据结构

1.3 特殊的进程

1.4 进程概要小结

2 进程调度时机

2.1 yield 和 pause 让出 cpu

2.2 futex 等待资源

2.3 exit 进程退出

2.4 中断返回时调度

2.4.1 创建新进程

2.4.2 futex 唤醒进程

2.4.3 周期调度

2.4.4 中断处理返回时调度小结

2.5 IDLE 进程调度

2.5.1 第一颗 CPU 上的 IDLE 进程

2.5.2 其余 CPU 上的 IDLE 进程

2.5.3 IDLE 进程调度小结

2.6 进程调度时机小结

3 本文总结

4 结语

标签:

推荐阅读

相关文章

linux常用工具及脚本

linux中50个有用命令汇总

linux命令部分总结

vlambda博客 学习文章列表

【原创】Linux 内核源码分析之进程概要及调度时机

进程概要及调度时机

0 本文内容一分钟速览

0.1 进程概要

0.2 进程调度时机

1 进程概要

1.1 进程是对物理世界的建模抽象

1.2 进程的数据结构

1.3 特殊的进程

1.4 进程概要小结

2 进程调度时机

2.1 yield 和 pause 让出 cpu

2.2 futex 等待资源

2.3 exit 进程退出

2.4 中断返回时调度

2.4.1 创建新进程

2.4.2 futex 唤醒进程

2.4.3 周期调度

2.4.4 中断处理返回时调度小结

2.5 IDLE 进程调度

2.5.1 第一颗 CPU 上的 IDLE 进程

2.5.2 其余 CPU 上的 IDLE 进程

2.5.3 IDLE 进程调度小结

2.6 进程调度时机小结

3 本文总结

4 结语

标签:

推荐阅读

相关文章

linux常用工具及脚本

linux中50个有用命令汇总

linux命令部分总结

vlambda博客
学习文章列表