Linux 进程调度-基于 ARM64

进程

在 Linux 内核中，进程一般称为任务(task), 进程的虚拟地址空间在内存管理模块中被分为用户虚拟地址空间和内核虚拟地址空间，所有的进程共享内核虚拟地址空间, 每一个进程有独立的用户虚拟地址空间. 在内核中，进程有两种特殊形式，没有使用用户虚拟地址空间的进程称为内核线程，共享用户虚拟地址空间的进程称为用户线程.

我们通常开发过程中提及的进程与线程在 Linux 内核中并没有明确的区别，它们都拥有数据结构 task_struct 作为描述符，我们通常所讲的进程与线程的主要区别即是否共享用户虚拟空间.

本文着重介绍了 CFS 公平调度算法，它的公平性主要体现在按照优先级将一个完整的调度周期分配给不同的进程, 尽管每个进程因为优先级分得的时间片不同，但保证在一个调度周期内所有的进程都会被运行一次.

进程描述符task_struct

(task_struct 数据成员较多，仅列出重要的数据成员)

struct task_struct {
	/* ... */
	/* -1 unrunnable, 0 runnable, >0 stopped: */
	volatile long			state;		/* 进程状态位 */

	/* ... */

	void				*stack;		/* 指向内核栈 */

	/* ... */

	/* 优先级 */
	int				prio;
	int				static_prio;	/* 普通进程的静态优先级 */
	int				normal_prio;
	unsigned int			rt_priority;

  struct sched_entity   se;  /* 记录进程的调度信息, 用来插入 rb-tree 供调度使用 */

	/* ... */

	/* 调度策略 */
	unsigned int			policy;

	cpumask_t			cpus_mask;	/* 允许进程在哪些CPU执行, cpuset相关 */

	struct sched_info		sched_info;	/* 调度信息 */

	struct mm_struct		*mm;		/* 内存描述符 */

	struct vmacache			vmacache;	/* 虚拟内存管理 */

	/* 进程退出相关 */
	int				exit_state;
	int				exit_code;
	int				exit_signal;
	/* The signal sent when the parent dies: */
	int				pdeath_signal;

	/* ... */

	pid_t				pid;   /* 进程号 */
	pid_t				tgid;  /* 线程组标识符 */

	/* Real parent process: */
	struct task_struct __rcu	*real_parent;		/* 指向真实父进程 */

	/* ... */
	char				comm[TASK_COMM_LEN];	/* 进程名 */

	/* Filesystem information: */
	struct fs_struct		*fs;		/* 文件系统描述符 */

	/* Open file information: */
	struct files_struct		*files;		/* 打开的文件信息 */

	/* 信号处理相关 */
	struct signal_struct		*signal;
	struct sighand_struct		*sighand;
	sigset_t			blocked;
	sigset_t			real_blocked;

	/* ... */
	struct thread_struct		thread;  /* CPU的部分状态(寄存器)保存在thread中 */

	/* ... */
};

进程优先级

限期进程的优先级比实时进程高，实时进程比普通用户进程优先级高
限期进程的优先级是-1
实时进程的优先级是1~99, 优先级数值越大，优先级越高
普通进程的优先级是100~139, 优先级数值越小，优先级越高

调度策略

Linux 内核支持以下调度策略:

停机进程使用停机调度策略:

停机进程是优先级最高的进程，停机就是我们通常理解的使处理器停下来，做更紧急的任务.

限期进程使用限期调度策略:

限期进程使用最早期限优先算法，使用红黑书把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程.

实时进程支持两种调度策略: 先进先出调度和轮流调度
普通进程支持两种调度策略, 标准轮流分时和空闲调度
处理器上的空闲进程使用空闲调度策略:

每个处理器上有一个空闲进程，即0号进程. 空闲进程的优先级最低，只有当没有其他进程可以调度的时候，才会调度空闲进程.

完全公平调度算法CFS

我们这里介绍相对重要的普通用户进程的调度策略: 完全公平调度策略 CFS(Completely Fair Scheduler):

普通进程使用完全公平调度(CFS)算法. 为了保证在一个周期内所有的进程都能被调度, 完全公平调度算法引入了虚拟运行时间 vruntime 的概念:

  虚拟运行时间 = 实际运行时间 * nice0 对应的权重 / 进程的权重( nice 值对应的权重)

实际运行时间

实际运行时间就是字面意思，进程在 CPU 上运行的实际时间. 每一个进程(task_struct)的调度信息结构体 sched_entity 都记录了进程调度开始时间点(exec_start), 实际运行时间(sum_exec_runtime), 虚拟运行时间(vruntime), 上一次时间运行时间(prev_sum_exec_runtime).

调度进程的时候，选中 next 进程, 并开始记录 next 进程的开始运行时间点，运行结束后计算时间差即为进程的实际运行时间.

nice0 对应的权重

在 kernel/sched/core.c 中定义了 nice 值与权重的对应关系，nice0 的值为1024.

进程的权重

普通进程的 nice 值的取值范围是-20~19, 以下是 nice 值与权重的对应关系如下:

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

nice 值越小，进程的权重也就越大.

完全公平调度算法利用 rb-tree 将进程按虚拟运行时间从小到大的排序，每次调度选择虚拟运行时间最小的进程. nice0 对应的权重为常量，即可以理解在实际运行时间相同的情况下，进程的权重( nice 值对应的权重值)越大，被调度的机会就越大.

调度最小粒度

内核设置了调度最小粒度，默认为 0.75 毫秒，可以通过文件 /proc/sys/kernel/sched_min_granularity_ns 调整. 调度最小粒度表示进程在 CPU 至少运行的时间长度.

调度周期

在某个时间长度可以保证运行队列的每个进程都至少运行一次, 这个时间长度称为调度周期，如果运行队列的进程数量大于 8, 那么调度周期等于调度最小粒度 * 进程数量，否则调度周期为6ms

进程的时间片

进程的时间片公式如下:

进程的时间片(实际运行时间) = (调度周期 * 进程权重 / 运行队列中所有进程的权重总和)

介绍了CFS的基本概念, 我们来举例来分析为什么 CFS 算法是一个公平调度算法:

假如有两个进程A和B, 进程的 nice 值0和1, 即 A 进程的权重为1024, B 进程的权重为820. 以6ms的调度周期来计算, 根据进程的时间片公式，两个进程分别的运行时间片为A进程 6 * 1024 / (1024+820) = 3.33ms, B进程 6 * 820 / (1024+820) = 2.66ms. 通过进程时间片公式计算我们可以看到不同的优先级的进程运行时间片不同，但为了保证在 CPU 选择进程调度时，尽可能保证每个进程被选择的可能性是相同的，这里就要反推我们上面提到的虚拟运行时间. A 进程的虚拟运行时间为 3.33 * 1024(nice 0) / 1024 = 3.33, B 进程的虚拟运行时间为 2.6 * 1024(nice 0) / 820 = 3.33. 通过虚拟运行时间的公式我们得出A 进程和B 进程尽管优先级不同，但是在 rb-tree 的位置是接近的, 即被调度的优先级是相同的.

CFS调度算法的公平性体现在哪里?

我们可以先通过公式推导发现:

进程的时间片(实际运行时间) = (调度周期 * 进程权重 / 运行队列中所有进程的权重总和)

虚拟运行时间 = 实际运行时间 * nice0 对应的权重 / 进程的权重( nice 值对应的权重)

                调度周期 * 进程权重 * nice0 权重     调度周期 * nice0 权重
虚拟运行时间=  ---------------------------------  = ----------------------------
                 所有进程的权重总和 * 进程权重        所有进程的权重总和

CFS 调度算法利用虚拟运行时间保证在一个调度周期每个进程被调度的优先级尽可能的一样.

新进程的vruntime的初始值

对于新创建的进程我们如何设置虚拟运行时间, 假如设为0, 则调度器会因为 vruntime 较小频繁的调度新建的进程直到它的虚拟运行时间追上就绪队列里其他的进程. 这个现象则违背了 CFS 调度算法的公平性. 所以在有一个数据字段 min_vruntime, 当新进程创建时，我们将其 vruntime 初始化为就绪队列里的 min_vruntime, 则确保新进程与大部分的进程之间的虚拟运行时间的 GAP 不会过大, 从而避免被频繁调度.

进程调度源码分析

运行队列

每一个处理器都有一个运行队列，定义如下:

/* kernel/sched/sched.h */

struct rq {
	/* runqueue lock: */
	raw_spinlock_t		lock;     /* 运行队列的锁 */

	unsigned int    nr_running; /* 运行队列的进程数量 */

	/* ... */
	struct cfs_rq		cfs;  /* 公平运行进程队列 */
	struct rt_rq		rt;   /* 实时运行进程队列 */
	struct dl_rq		dl;   /* 限期运行进程队列 */

	/* ... */
	struct task_struct	*curr;  /* 正在运行的进程 */
	struct task_struct	*idle;  /* 空闲进程 */
	struct task_struct	*stop;  /* 迁移进程 */

	/* ... */
};

调度进程

调度进程的核心函数是 __schedule, 函数 __schedule() 的处理流程如下:

调用 pick_next_task() 以选择下一个进程
调用 context_switch() 以切换进程

`pick_next_task()`

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	/* sched_class是Linux抽象的调度类，类别和优先级分别如下:
	 * 停机调度类，限期调度类，实时调度类，公平调度类和空闲调度类. */
	const struct sched_class *class;
	struct task_struct *p;

	/* 假如所有进程属于公平调度类,
	 * 我们可以直接调用公平调度类的pick_next_task函数. */
	if (likely((prev->sched_class == &idle_sched_class ||
		    prev->sched_class == &fair_sched_class) &&
		   rq->nr_running == rq->cfs.h_nr_running)) {

		p = fair_sched_class.pick_next_task(rq, prev, rf);
		/* 假如没有可调度的进程，跳转again, 选择其他优先级的调度类. */
		if (unlikely(p == RETRY_TASK))
			goto again;

		/* 假如公平调度类选择的下一个进程属于空闲调度类，直接调用
		 * 空闲调度类的pikc_next_task(). */
		if (unlikely(!p))
			p = idle_sched_class.pick_next_task(rq, prev, rf);

		return p;
	}

again:
	/* 迭代调度类，从优先级最高的调度类开始，调用对应的pick_next_task
	 * 选择下一个进程，假如没有可以调度的进程，就选择一个优先级的调度类. */
	for_each_class(class) {
		p = class->pick_next_task(rq, prev, rf);
		if (p) {
			if (unlikely(p == RETRY_TASK))
				goto again;
			return p;
		}
	}

	/* 正常的情况下，不会走到这里，因为空闲调度类总会有可以调度的进程. */
	BUG();
}

用户进程属于公平调度类，即调用 pick_next_task_fair() 选择下一个运行的进程, 公平调度类会从当前 cfs_rq 即公平调度运行队列中选择虚拟运行时间最小的调度进程，所有的调度进程都由 rb-tree (红黑树)维护.

`context_switch()`

/* linux/kernel/sched/core.c */

static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next, struct rq_flags *rf)
{
	struct mm_struct *mm, *oldmm;

	/* 执行进程切换的准备工作，ARM64架构为默认定义: 一个空的宏. */
	prepare_task_switch(rq, prev, next);

	/* mm为下一个选择的进程的内存描述符,
	 * old_mm为上一个进程的内存描述符. */
	mm = next->mm;
	oldmm = prev->active_mm;
	/* 开始执行上下文切换，ARM64架构依旧使用默认定义，是一个空的宏. */
	arch_start_context_switch(prev); 

	if (!mm) {
		/* 假如mm为空, 即下一个选择的进程为内核线程,
		 * 内核线程没有用户虚拟地址空间， 所以需要借用上一个进程的mm_struct,
		 * 调用enter_lazy_tlb()通知处理器架构不需要切换用户虚拟地址空间. */
		next->active_mm = oldmm;
		mmgrab(oldmm);
		enter_lazy_tlb(oldmm, next);
	} else
		/* 否则需要进行切换进程的地址空间. */
		switch_mm_irqs_off(oldmm, mm, next);

	/* ... */

	/* 切换寄存器和堆栈. */
	switch_to(prev, next, prev);
	barrier();  /* 内存屏障 */

	/* finish_task_switch负责进程切换后执行的清理工作. */
	return finish_task_switch(prev);
}

用户虚拟地址空间切换

/* switch_mm_irqs_off() -> switch_mm() -> __switch_mm() */

/* arch/arm64/include/asm/mmu_context.h */

static inline void __switch_mm(struct mm_struct *next)
{
	unsigned int cpu = smp_processor_id();

	/*
	 * init_mm.pgd does not contain any user mappings and it is always
	 * active for kernel addresses in TTBR1. Just set the reserved TTBR0.
	 */
	if (next == &init_mm) {
		cpu_set_reserved_ttbr0();
		return;
	}

	check_and_switch_context(next, cpu);
}

static inline void
switch_mm(struct mm_struct *prev, struct mm_struct *next,
	  struct task_struct *tsk)
{
	if (prev != next)
		/* 假如切换的两个进程不共享虚拟地址空间,
		 * 调用__switch_mm()进行切换. */
		__switch_mm(next);

	/* 更新TTBR0寄存器 */
	update_saved_ttbr0(tsk, next);
}

寄存器和堆栈切换

/* switch_to() -> __switch_to() */

/* arch/arm64/kernel/process.c */

__notrace_funcgraph struct task_struct *__switch_to(struct task_struct *prev,
				struct task_struct *next)
{
	struct task_struct *last;

	fpsimd_thread_switch(next);         /* 切换浮点寄存器 */
	tls_thread_switch(next);            /* 切换线程本地存储相关的寄存器 */
	hw_breakpoint_thread_switch(next);  /* 切换调试寄存器 */
	contextidr_thread_switch(next);     /* 切换上下文标识符寄存器 */
	entry_task_switch(next);            /* 将下一个进程的task_struct存入CPU的__entry_task */
	uao_thread_switch(next);            /* 用户访问覆盖相关切换 */
	ptrauth_thread_switch(next);        /* 指针验证相关切换 */
	ssbs_thread_switch(next);           /* 推测性执行侧通道相关切换 */

	/* 数据同步屏障 */
	dsb(ish);

	/* 切换通用寄存器 */
	last = cpu_switch_to(prev, next);

	return last;
}

进程切换与线程切换

通过上面的系统的分析，我们可以发现在Linux内核中并没有区分进程和线程，对于线程和进程，我们可以这么理解:

当进程只有一个线程时，可以认为进程就等于线程.
当进程拥有多个线程时，这些线程会共享相同的虚拟地址空间, 虚拟地址空间在上下文切换时是不需要切换的。另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要切换保存的.

查看进程上下文切换

我们通常所说的上下文切换分为CPU上下文切换和进程上下文切换, 例如C/C++中的系统调用即会执行CPU上下文切换，而系统性能分析工具 vmstat 所显示的也是 CPU 上下文切换和中断的次数. 关于进程上下文切换我们可以利用工具 pidstat:

每隔5秒输出1组数据

pidstat

这个结果中有两列内容是我们的重点关注对象。一个是 cswch ，表示每秒自愿上下文切换（voluntary context switches）的次数，另一个则是 nvcswch ，表示每秒非自愿上下文切换（non voluntary context switches）的次数. 所谓自愿上下文切换，是指进程无法获取所需资源，导致的上下文切换。比如说， I/O、内存等系统资源不足时，就会发生自愿上下文切换。而非自愿上下文切换，则是指进程由于时间片已到等原因，被系统强制调度，进而发生的上下文切换。比如说，大量进程都在争抢 CPU 时，就容易发生非自愿上下文.

调度时机

调度进程的时机如下:

进程主动调用schedule()函数.
周期性调度，抢占当前进程，强迫当前进程让出处理器.
唤醒进程的时候，被唤醒的进程可能会抢占当前进程.
创建新进程的时候, 新进程可能抢占当前进程.

主动调度

进程在用户模式下运行的时候，无法直接调用 schedule() 函数, 只能通过系统调用进入内核模式，假如系统调用需要等待某个资源，例如互斥锁(mutex)或者信号量，会将进程的状态设为睡眠状态，然后调用 schedule() 来调度进程.

进程也可以通过系统调用 sched_yield() 让出处理器，这种情况下进程不会进入睡眠.

周期性调度

Linux内核依靠周期性的时钟中断抢夺处理器的控制权，时钟中断处理程序检查当前进程的执行时间有没有超过限额，如果超过了限额，设置需要重新调度的标志.

在CFS算法中，如果当前调度实体的运行时间超过了前面介绍的进程的时间片，那么会设置重新调度的标志位.

修改进程优先级

Linux系统可以通过 renice 设置进程优先级，具体使用方法可以通过 man renice.
C/C++编程可以使用以下方法:

#include <sys/time.h>
#include <sys/resource.h>

int getpriority(int which, int who);
int setpriority(int which, int who, int prio);

参考

« Linux 内核深度解析»