Linux 的进程创建与调度：代码解读

October 23, 2021

image courtesy of Sonja Langford

This post is only available in Chinese at this moment.

这是我在实验室学习过程中撰写的读书笔记的一部分。下面的内容基于撰文时最新的 Linux 5.14.12 进行分析。

进程的创建

Linux 的代码没有对进程和线程作明显的区分，因此下面统一使用“进程”这个词来指代二者，具体的语义根据上下文来判断。

Linux 中提供了三个与进程创建相关的系统调用，即 fork、vfork 和 clone。三者的定义都在 /kernel/fork.c 文件中，如：

// /kernel/fork.c
// 下方代码为节选，省略了结构与配置相关的定义
SYSCALL_DEFINE0(fork)
{
	struct kernel_clone_args args = {
		.exit_signal = SIGCHLD,
	};

	return kernel_clone(&args);
}

顺着 kernel_clone 的调用向下追踪，则有：

// /kernel/fork.c
// 下方代码为节选，省略了参数检查和 trace 等内容
pid_t kernel_clone(struct kernel_clone_args *args)
{
	u64 clone_flags = args->flags;
	struct task_struct *p;
	p = copy_process(NULL, trace, NUMA_NO_NODE, args);
    // ...
	wake_up_new_task(p);
	// ...
}

通过这段代码不难看出，kernel_clone 主要做了两件事：

  1. 复制进程本身；
  2. 唤醒新的进程。

复制一个进程，不仅仅是要复制 task_struct 这个结构体，还需要根据结构体内各个属性的语义以及调用参数去对这些属性进行调整，例如设置新的内存映射等。这些工作都是在 copy_process 函数中完成的：

[kernel_clone() > copy_process()]
// /kernel/fork.c
// 下方代码为节选，省略了结构与配置相关的定义
static __latent_entropy struct task_struct *copy_process(
					struct pid *pid,
					int trace,
					int node,
					struct kernel_clone_args *args)
{
	struct task_struct *p;
	u64 clone_flags = args->flags;

	// 这个函数会复制 task_struct 结构体，具体的过程涉及到 NUMA 相
	// 关的技术，而 NUMA 与多 CPU 有关。举例来说，在多核心 CPU 上，
	// 每个核心都有自己的缓存，跨核心的缓存访问会比访问同核心缓存更慢，
	// 因此 Linux 需要根据情况分配缓存。这种情况下，这里的 node 可以
	// 理解为核心的 ID。
	p = dup_task_struct(current, node);

	// LSM 钩函数，可参考《Linux 内核安全模块深入剖析》一书
	retval = security_task_alloc(p, clone_flags);
	// if (retval) {} 是在做错误处理，每个中间函数在正常返回时，返回
	// 值都是 0；如果返回值为非 0，则需要撤销此前的所有操作。为了方便阅
	// 读，只摘录了第一个这样的错误处理语句。
	if (retval)
		goto bad_fork_cleanup_audit;
	retval = copy_semundo(clone_flags, p);
	retval = copy_files(clone_flags, p);
	retval = copy_fs(clone_flags, p);
	retval = copy_sighand(clone_flags, p);
	retval = copy_signal(clone_flags, p);
	retval = copy_mm(clone_flags, p);
	retval = copy_namespaces(clone_flags, p);
	retval = copy_io(clone_flags, p);
	retval = copy_thread(clone_flags, args->stack, args->stack_size, p, args->tls);

	// 如果 pid != &init_struct_pid，说明我们不是在创建内核线程；需
	// 要分配一个新的 pid。
	if (pid != &init_struct_pid) {
		pid = alloc_pid(p->nsproxy->pid_ns_for_children, args->set_tid,
				args->set_tid_size);
	}
}
__latent_entropy 与密码学有关，可参考 Reference 3。

在这些处理中，最重要的是 copy_mm，即对进程虚拟内存的复制。实际上，在整个进程创建的过程中，最复杂的就是这个部分，以至于 Linus Torvalds 本人在 fork.c 文件的开头写道：

Fork is rather simple, once you get the hang of it, but the memory management can be a b***h.（只要你了解了大概，fork 本身很简单；内存管理才是真正烦人的。）

[kernel_clone() > copy_process() > copy_mm()]
// /kernel/fork.c
// 下方代码为节选，省略了一些内容
static int copy_mm(unsigned long clone_flags, struct task_struct *tsk)
{
	struct mm_struct *mm, *oldmm;
	// 如果父进程是一个内核线程，则它是没有用户空间内存的，因此直接返回
	oldmm = current->mm;
	if (!oldmm)
		return 0;
	// 如果设置了 CLONE_VM 这一 flag，则新进程与其父进程共享虚拟内存，
	// 即相当于创建的是一个线程。只需要复制 mm 指针即可。
	if (clone_flags & CLONE_VM) {
		// 调用 mmget 来增加 oldmm 的引用计数
		mmget(oldmm);
		mm = oldmm;
	} else {
		mm = dup_mm(tsk, current->mm);
		if (!mm)
			return -ENOMEM;
	}

	tsk->mm = mm;
	tsk->active_mm = mm;
	return 0;
}

上面代码中，最关键的是 dup_mm：

[kernel_clone() > copy_process() > copy_mm() > dup_mm()]
// /kernel/fork.c
// 下方代码为节选，省略了一些内容
static struct mm_struct *dup_mm(struct task_struct *tsk,
				struct mm_struct *oldmm)
{
	struct mm_struct *mm;
	int err;

	mm = allocate_mm();
	if (!mm)
		goto fail_nomem;

	memcpy(mm, oldmm, sizeof(*mm));

	if (!mm_init(mm, tsk, mm->user_ns))
		goto fail_nomem;

	err = dup_mmap(mm, oldmm);
	if (err)
		goto free_pt;

	return mm;
}

上面的这段代码大部分都不难理解，可以发现最重要的是 dup_mmap 函数：

[kernel_clone() > copy_process() > copy_mm() > dup_mm() > dup_mmap()]
// /kernel/fork.c
// 下方代码为节选，省略了一些内容
static __latent_entropy int dup_mmap(struct mm_struct *mm,
					struct mm_struct *oldmm)
{
	struct vm_area_struct *mpnt, *tmp, *prev, **pprev;
	mm->total_vm = oldmm->total_vm;
	mm->data_vm = oldmm->data_vm;
	mm->exec_vm = oldmm->exec_vm;
	mm->stack_vm = oldmm->stack_vm;
	for (mpnt = oldmm->mmap; mpnt; mpnt = mpnt->vm_next) {
		tmp = vm_area_dup(mpnt);
		mm->map_count++;
		if (!(tmp->vm_flags & VM_WIPEONFORK))
			retval = copy_page_range(tmp, mpnt);
	}
}

当中最重要的自然是 copy_page_range 函数，即对虚存页面的复制。从这里开始，事情就变得复杂起来。简单地说：

P4D、PUD 等为自 Linux 4.11-rc2 进入主线代码的五级页表机制的一部分，大致原理与原书中的三级页表机制类似，具体可见 Reference 4。

  • copy_page_range 会遍历所有 P4G 并调用 copy_p4d_range
  • copy_p4d_range 会遍历所有 PUG 并调用 copy_pud_range
  • copy_pud_range 会遍历所有 PMG 并调用 copy_pmd_range
  • copy_pmd_range 会遍历所有 PTE 并调用 copy_pte_range
  • copy_pte_range 会调用 copy_present_pte 复制单个 PTE：
[ ... > 
	dup_mmap() > copy_page_range() >
	copy_p4d_range() > copy_pud_range() >
	copy_pmd_range() > copy_pte_range() >
	copy_present_pte()]
// /mm/memory.c
// 下方代码为节选，省略了一些内容
static inline int
copy_present_pte(struct vm_area_struct *dst_vma, struct vm_area_struct *src_vma,
		 pte_t *dst_pte, pte_t *src_pte, unsigned long addr, int *rss,
		 struct page **prealloc)
{
	if (is_cow_mapping(vm_flags) && pte_write(pte)) {
		ptep_set_wrprotect(src_mm, addr, src_pte);
		pte = pte_wrprotect(pte);
	}
}

这里是最关键的部分。Linux 之所以能非常迅速地创建新进程，得益于其 copy-on-write（写时复制，COW）机制。创建新进程时，父子进程先共享内存页面，直到父子进程其中之一实际上真的要对页面进行写操作时，再去复制该页面。如果 flags 中的设定没有禁止 COW 机制，则不复制该页面，而是将原页面设定为“写保护”，并直接建立新进程与该页面的映射。这样做避免了大量不必要的内存复制，加速了进程创建并节省了内存空间。

is_cow_mapping 的定义很清楚地说明了哪些页面可以启用 COW 机制：

// /include/linux/mm.h
static inline bool is_cow_mapping(vm_flags_t flags)
{
	// 只有非共享且可写的页面可以启用 COW
	return (flags & (VM_SHARED | VM_MAYWRITE)) == VM_MAYWRITE;
}

共享的页面不能打开 COW 机制，因为打开 COW 机制后页面变为写保护状态，之后对共享内存的写入会触发异常处理。只读的页面似乎也能打开 COW 机制，但其实只读的页面本身就是写保护的，因此没有必要在后面进行新的属性设置，从而稍微加速这个过程。

当父子进程其中之一尝试向开启了 COW 的页面上写入数据时，由于开启了写保护，会触发系统的异常处理，进入 handle_pte_fault 函数，该函数会调用 do_wp_page ，进而调用 wp_page_copy() > cow_user_page() > copy_user_highpage() 来拷贝页面：

[... > handle_pte_fault() > do_wp_page() > wp_page_copy() >
	cow_user_page() > copy_user_highpage()]
// /include/linux/highmem.h
// 有一些特殊的 CPU 架构会有自己的实现方案，这里展示的是默认的 fallback 方案
static inline void copy_user_highpage(struct page *to, struct page *from,
	unsigned long vaddr, struct vm_area_struct *vma)
{
	char *vfrom, *vto;

	vfrom = kmap_atomic(from); // 暂时关闭调度并关闭页面异常，建立页面映射
	vto = kmap_atomic(to);
	copy_user_page(vto, vfrom, vaddr, to); // memcpy((vto), (vfrom), PAGE_SIZE)
	kunmap_atomic(vto);
	kunmap_atomic(vfrom);
}

上面介绍的只是最基本的框架，还有很多边界条件处理的情况没有说明，例如页面实际上可能是由文件通过 mmap 系统调用得来的，此时内存管理又是另一套方案，可自行查阅源码。

进程调度

Linux 的调度全部发生在 __schedule() 函数被调用时，其实现位于 /kernel/sched/core.c 中。这个函数在系统内的调用有三种情形：

  1. 使用其他机制显式地导致当前进程阻塞，例如访问互斥锁、信号量等导致当前进程阻塞时；
  2. 中断完成，将从内核态回到用户态，并且设置了 TIF_NEED_RESCHED 这一标志时 (Reference 6)；
  3. 进程被唤醒之后某个符合条件的最近时刻。wake_up() 并不会立马导致 __schedule() 被调用，只是暂时将需要唤醒的进程加入到调度队列中去。对于支持抢占式调用（CONFIG_PREEMPTIVE=y）的内核来说，这个“最近时刻”指的是以下事件中最先发生的那个：
    1. 系统调用或异常处理的上下文对 preempt_enable() 的调用；
    2. 中断处理结束后回到可抢占的上下文。

__schedule() 接着会调用 pick_next_task() > __pick_next_task() 来选择下一个应当被调度的进程。

CFS 调度器

为了适用于不同应用场景，我们需要不同的进程调度策略。例如，在一般的应用场景下，我们希望尽可能公平地在各个进程之间分配 CPU 时间，并且允许任务在一定范围内延迟作出响应；而对于一些实时任务，它们要求能立即响应，例如火箭发射过程中对于异常传感器参数的处理就必须是立刻响应，稍微迟缓一些的响应都可能导致致命的后果。为了支持这种需求，Linux 提供了多种调度策略，包括适用于前文提到的实时任务的 SCHED_RR 以及普通情况下的 SCHED_NORMAL。针对不同的调度策略，调度器又可以被分为多种类别，其中一种类型是 CFS 调度器 (completely fair scheduler)，它是 Linux 进程的默认调度器，实现在 /kernel/sched/fair.c 中。

为了介绍 CFS 调度器，有必要首先介绍其中涉及到的各类概念。

系统维护了一组队列，称为 运行队列，运行队列中维护的对象称为 调度实体。调度实体可以是一个进程（为了方便介绍，后面称为 PSE），也可以是一个进程组 （后面称为 GSE）。每个 GSE 还有自己的运行队列。

正是因为需要支持按组调度，Linux 才没有直接在队列中维护进程，而是实现了一个抽象度更高的调度实体。支持按组调度的意义有很多，比如两个用户同时在使用一台计算机，那么不仅要保证进程间 CPU 时间分配要相对合理，还要保证用户间分配的合理性，否则一个用户可以创建大量进程来抢占 CPU 时间。

可以将支持了按组调度的运行队列与一个树类比，形成一个多层结构，则树的根节点为这个队列（见下一段），叶节点要么是 PSE，要么是一个空队列；中间节点要么是 GSE，要么是非空队列。

运行队列又可分为两类：

  1. 普通运行队列，这类运行队列不直接管辖调度实体，而是通过管辖多个子队列来实现调度；每个 CPU 都会有一个普通运行队列。
  2. 调度器专用队列。这些队列均对应一类调度器，如 CFS 队列、RT 队列等。

普通运行队列的部分定义为：

// /kernel/sched/sched.h
// 代码为节选
struct rq {
	unsigned int		nr_running; // 队列中当前维护的实体数量
	struct cfs_rq		cfs; // CFS 子队列
	struct rt_rq		rt; // RT 子队列
	struct task_struct __rcu	*curr; // 当前实际在运行的任务
};

从上面的代码能够看出，普通运行队列管辖了多个调度器专用队列，这些子队列分别对应一种调度器。

CFS 运行队列的定义为：

// /include/linux/sched.h
// 代码为节选
struct cfs_rq {
	struct load_weight	load;
	unsigned int		nr_running; // 第一层节点的数量，即 PSE 和 GSE 的数量和
	unsigned int		h_nr_running;  // 所有层中 PSE 数量的和
	struct sched_entity	*curr;  // 队列当前运行的实体
	struct sched_entity	*next;
	struct sched_entity	*last;
	struct sched_entity	*skip;
};

对于使用 CFS 进行调度的调度实体，其定义为：

// /include/linux/sched.h
// 代码为节选
struct sched_entity {
	struct rb_node			run_node; // 红黑树节点
	struct list_head		group_node;  // 进程组节点
	u64				vruntime; // virtual runtime，虚拟单位上的已调度时间
#ifdef CONFIG_FAIR_GROUP_SCHED // 如果配置选择支持 GSE
	int				depth;  // GSE 的深度
	struct sched_entity		*parent; // GSE 的父组
	struct cfs_rq			*cfs_rq; // 当前组在哪一条队列上
	struct cfs_rq			*my_q; // 当前组所管辖的那一条队列
	unsigned long			runnable_weight; // my_q->h_nr_running 的缓存
#endif
};

从 CFS 调度实体的定义可以看出，CFS 队列实际上是一个红黑树，树根据每个节点的权重来动态调整，从而快速获得下一个应当被调度的实体。

看完概念，现在回到调度过程中去。当 __pick_next_task() 被调用时，它将会根据当前调度队列的情况来选择调度器。如果选用 CFS 调度器，__pick_next_task() 调用 pick_next_task_fair() ：

[schedule() > __schedule() > pick_next_task() > __pick_next_task() > pick_next_task_fair()]
// /kernel/sched/fair.c
// 代码为节选

struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;
	struct task_struct *p;

	// 下面的循环用于在进程组中最终确定一个进程。见后方代码注释。
	do {
		struct sched_entity *curr = cfs_rq->curr;
		// 调度前，如果当前实体还在队列中，则首先更新当前实体的 vruntime，否则直接忽略
		if (curr) {
			if (curr->on_rq)
				update_curr(cfs_rq);
			else
				curr = NULL;
		}

		se = pick_next_entity(cfs_rq, curr);
		// 如果 se 是一个进程组，则 group_cfs_rq 会返回此进程组中的 CFS 运行队列，
		// 否则为 NULL。
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);
		// 类似于 container_of 的实现
		p = task_of(se);
		if (prev != p) {
			// 更新运行队列，代码略
	}
	return p;
}

上面代码中最重要的部分就是 pick_next_entity() ，它决定在当前队列中选取哪一个实体来继续调度。其实现为：

[schedule() > __schedule() > pick_next_task() > __pick_next_task() > pick_next_task_fair() > pick_next_entity()]
// /kernel/sched/fair.c
// 代码为节选
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	struct sched_entity *left = __pick_first_entity(cfs_rq); // 调用红黑树相关借口来获取队列中最靠前的那个实体
	struct sched_entity *se;

	/*
	 * 如果当前运行的实体比队列中最靠前的实体还要靠前，则直接更新 left 为当前实体
	 */
	if (!left || (curr && entity_before(curr, left)))
		left = curr;

	se = left; /* 理想情况下，最终选定的运行实体就应该是这个最靠前的 */

	/*
	 * 但是还有一些条件需要注意。只要不会太不公平，要避免运行标记为 skip 的实体。
	 */
	if (cfs_rq->skip && cfs_rq->skip == se) {
		struct sched_entity *second;

		// 挑选一个备选实体来替换当前选择的 se。如果 se 就是当前正在运行的实体，那我们只需要
		// 从队列中选取最左侧的那个实体来替换它。如果 se 不是当前在运行的，则需要从队列中获取
		// se 的下一个节点，并与 curr 进行对比，选择两者之间更靠前的那个。
		if (se == curr) {
			second = __pick_first_entity(cfs_rq);
		} else {
			second = __pick_next_entity(se);  // 对红黑树相关接口调用的封装
			if (!second || (curr && entity_before(curr, second)))
				second = curr;
		}

		// wakeup_preempt_entity 用于计算 second 和 left 是否大于某个最小抢占粒度，如果是则
		// 返回 1，否则返回 -1 或 0。简单地说，这个函数在
		//     second->vruntime - left->vruntime <= some_threshold
		// 时返回 -1 或 0，表示此时让 second 运行更符合调度策略、更公平。实际的计算比较复杂，可
		// 自行阅读源码。
		if (second && wakeup_preempt_entity(second, left) < 1)
			se = second;
	}

	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
		// 标记为 next 的实体表示某些地方希望这个实体尽可能先运行。只要不会太不公平，就允许优先运行。
		se = cfs_rq->next;
	} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
		// 标记为 last 的实体是上次被抢占的实体。只要不会太不公平，考虑到缓存的本地性，优先运行这个实体。
		se = cfs_rq->last;
	}

	return se;
}

进程切换

上面的调度过程中已经通过调度器选择了一个进程来执行，接下来就要开始实际地切换进程了。__schedule() 接下来将调用 context_switch() 来切换任务。切换任务具体的工作，在代码开头的注释中已经说得非常清楚：

// /kernel/sched/core.c
// 代码为节选
/*
 * context_switch - switch to the new MM and the new thread's register state.
 * 切换到新的内存映射并更新寄存器
 */
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next, struct rq_flags *rf)
{
	/*
	 * kernel -> kernel   lazy + transfer active
	 *   user -> kernel   lazy + mmgrab() active
	 *
	 * kernel ->   user   switch + mmdrop() active
	 *   user ->   user   switch
     *
	 * 上面的注释说明了四种情况。switch 表示需要切换内存映射，lazy 表示不需要
	 * 切换内存映射。由于内核线程没有自己的内存空间，它将直接沿用用户空间进程的
     * 内存映射；mmgrab 和 mmdrop 用于引用计数，防止内存映射在其属主进程退出
     * 后被释放。
	 */
	if (!next->mm) {  // 下一个任务为内核线程
		// 切换到内核线程。在一些架构上这意味着什么也不做，在 x86 上需要更新 TLB。
		// 具体可见该函数的注释。
		enter_lazy_tlb(prev->active_mm, next);

		next->active_mm = prev->active_mm;
		if (prev->mm)  // 上一个任务是用户进程
			// 递增 prev->active_mm 的引用计数器
			mmgrab(prev->active_mm);
		else  // 上一个任务是内核线程
			prev->active_mm = NULL;
	} else {  // 下一个任务为用户进程
		// 退出内核线程
		switch_mm_irqs_off(prev->active_mm, next->mm, next);

		if (!prev->mm) {   // 上一个任务是内核线程
			// 从对称性的角度，应该递减一次 prev->active_mm 的引用计数器；
			// 但是这个工作实际上是由 finish_task_switch 来完成
			rq->prev_mm = prev->active_mm;
			prev->active_mm = NULL;
		}
	}

	/* 更新寄存器和栈。每个结构体系都提供自己的实现。 */
	switch_to(prev, next, prev);

	// 善后工作，包括清理掉状态为 dead 的任务
	return finish_task_switch(prev);
}

思考题

进程调度非常复杂。上面的介绍实际上略过了很多问题，包括但不限于：

  1. vruntime 如何更新？
  2. 如何计算每个实体的运行时间？
  3. 队列红黑树如何建立？