Linux内核学习（三）—— 进程调度（基于Linux 2.6内核）

所有的调度器必须堆进程运行时间做记账，CFS虽然不再有时间片的概念，但是它也必须维护每个进程的运行时间记账，每次系统时钟节拍发生时，时间片都会被减少一个节拍周期，当一个进程的时间片被减少到 0 时，它就会被另一个尚未减到 0 的时间片可运行进程抢占。因此这种进程所需要占用处理器运行的时间很短，因为他们在等待I/O时最后总会自己阻塞（这里说的I/O指任何类型的可阻塞资源，如键盘输入，或网络I/O，实

Patarw20

1221人浏览 · 2023-03-22 16:19:09

Patarw20 · 2023-03-22 16:19:09 发布

一、进程调度程序

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序可以看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作。

二、多任务系统

多任务操作系统就是能同时并发地交互执行多个进程的操作系统。在单处理器系统上，可以实现并发执行。在多处理器系统上，可以实现并行执行。

多任务系统可以分为两类：协作式多任务（cooperative multitasking）和抢占式多任务（preemptive multitasking）。Linux提供了抢占式的多任务模式，在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会，这个强制挂起的动作就叫抢占（preemption）。进程在被抢占之前能运行的时间是预先设置好的，这段时间叫做进程的时间片（timeslice）。相反，在非抢占式多任务模式下，除非进程自己主动停止，否则会一直运行，进程主动挂起自己的操作叫做让步（yielding）。

三、Linux的进程调度

从1991年 Linux 的第一版到后来的 2.4 内核系列，Linux 的调度程序都相当简陋。

在 2.5 开发系列的内核中，开始采用一种叫做 O(1) 调度程序（无论输入多大，调度程序都可以在恒定时间内完成工作），但此算法对于交互进程较多的 os 表现不佳。

在 2.6 内核系统开发初期，开发人员为了提高对交互程序的调度性能而引入了“反转楼梯最后期限调度算法（Rotating Staircase Deadline scheduler）”（RSDL），最终在 2.6.23 内核版本中替代了 O(1) 调度算法，现在称其为“完全公平调度算法”（CFS）。

3.1 调度策略

进程可以被分为I/O消耗型和处理器消耗型。

I/O消耗型进程大部分时间用来提交I/O请求或是等待I/O请求。因此这种进程所需要占用处理器运行的时间很短，因为他们在等待I/O时最后总会自己阻塞（这里说的I/O指任何类型的可阻塞资源，如键盘输入，或网络I/O，实际处理输入的时间很少，大部分时间都在等待输入的到来）。

相反，处理器消耗型进程把大部分时间用在执行代码上。除非被抢占，否则他们通常一直不停地运行，所以从系统响应速度来考虑，调度器应该尽量降低他们的调度频率，延长他们的运行时间。

所以调度策略通常要在两个矛盾的目标中寻找平衡：进程相应迅速（响应时间短）和最大系统利用率（高吞吐量）。Linux为了保证交互式应用的性能，所以对进程的响应时间进行了优化，更倾向于优先调度I/O消耗型进程，但也并未忽略处理器消耗型进程。

3.2 进程优先级

Linux采用了两种不同的优先级范围。第一种是nice值，范围为-20到+19，默认值为0，越大的nice值优先级越低（nice值越高人越好，好人更懂得礼让）。第二种是实时优先级（real-time priority）,可以配置，默认变化范围为0到99，与nice值相反，任何实时进程的实时优先级都高于普通进程，越高的实时优先级意味着进程优先级越高。在 Linux 系统中，nice 值代表时间片的比例。

3.3 时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。时间片大小的选择要考虑到很多因素。比如时间片过长会让系统对交互的响应表现欠佳（并发度下降），时间片太短会明显增大进程切换带来的处理器耗时；I/O消耗型不需要太长的时间片，而处理器消耗型的进程则希望时间片越长越好。

但是 Linux 的 CFS（完全公平调度算法）并没有直接分配时间片到进程，它是将处理器的使用比（proportion of the processor）划分给了进程，这个比例还会进一步受到 nice 值的影响。如果新的可运行进程消耗的使用比比当前进程小，则新进程立即投入运行，抢占当前进程，否则将推迟运行。这样一来，进程所获得的处理器时间其实是和系统负载密切相关的。

举个例子，假如有一个获取用户输入字符的程序（I/O消耗型）和一个视频编码程序（处理器消耗型），他们在当前系统中的处理器使用比初始都是50%，由于获取输入字符程序大部分时间在等待用户输入，使用的处理器时间很少，因此它肯定不会用到处理器的50%；而视频编码程序大部分时间在计算，使用的时间很长，所以视频编码程序肯定有机会用到超过50%；因为获取用户输入的程序并没有消费掉承诺给他的50%处理器使用比，为了公平，在获取输入字符程序想要运行时，CFS 总是会毫不犹豫地让它运行，而视频编码程序只能在剩下的时间运行。这样既保证了在用户有字符输入时能够即使获取，也保证了视频编码程序利用大部分的剩余时间去计算。

四、Linux的调度算法

4.1 调度器类

Linux 调度器是以模块的方式提供的，目的是为了允许不同类型的进程可以有针对性地选择调度算法。这种模块化的结构称为调度器类（scheduler classes），它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器有一个优先级，基础的调度器代码定义在 kernel/sched.c 文件中，他会按照优先级的顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的程序。

完全公平调度（CFS）是一个针对普通进程的调度类，在 Linux 中称为 SCHED_NORMAL，CFS 算法实现定义在 kernel/sched_fair.c 中。CFS 分配给进程一个处理器使用比重而不是时间片。

CFS 的调度方法是允许每个进程运行一段时间，循环轮转，并且选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠 nice 值来计算时间片。nice 值在 CFS 中被作为进程获得处理器运行比的权重：越高的 nice 值（越低的优先级）进程获得更低的处理器使用权重，这是相对默认 nice 值的进程而言的；反之则获得更高的处理器使用权重。

例如，假定 CFS 的目标延迟值为 20ms（20ms 内让所有进程都能执行一次），假如有两个优先级相同的任务，则每个任务运行 10ms，4个任务则每个只能运行 5ms，20个则每个只能运行 1ms。

在上述情况下，当可运行任务数量趋于无限的时候，每个任务所获得的处理器时间则无限趋于0，这无疑造成了不可接收的切换开销。CFS 为此引入每个进程获得的时间片底线，这个底线称为最小粒度。默认情况下这个值为 1ms（但在进程数量变得非常多的时候，CFS 的实时性会开始下降）。

绝对的 nice 值不再影响调度决策：只有相对值才会影响处理器时间的分配比例。如，nice 值为 0 和 5 的进程和 nice 值为 10 和 15 的进程获得的处理器使用比是相同的。

4.2 Linux调度的实现

CFS的组成分为四个部分，相关代码位于 kernel/sched_fair.c ：

时间记账（Time Accounting）
进程选择（Process Selection）
调度器入口（The Scheduler Entry Point）
睡眠和唤醒（Sleeping and Waking Up）

4.2.1 时间记账

所有的调度器必须堆进程运行时间做记账，CFS虽然不再有时间片的概念，但是它也必须维护每个进程的运行时间记账，每次系统时钟节拍发生时，时间片都会被减少一个节拍周期，当一个进程的时间片被减少到 0 时，它就会被另一个尚未减到 0 的时间片可运行进程抢占。CFS使用调度器实体结构（定义在<linux/sched,h>的struct_sched_entity中）来追踪进程运行时间记账：

调度器实体结构作为一个名为 se 的成员变量，嵌入在进程描述符 struct task_struct 内。

其中，上图中的 vruntime 变量存放进程的虚拟运行时间，该运行时间的计算是经过了所有可运行进程总数的标准化（或者说是被加权的）。虚拟时间是以 ns 为单位的，所以 vruntime 和定时器节拍不再相关。CFS 使用 vruntime 变量来记录一个程序到底运行了多长时间以及它还应该运行多久。

4.2.2 进程选择

CFS需要选择下一个进程时，它会挑一个具有最小vruntime的进程，这就是CFS算法调度的核心。CFS使用红黑树（rbtree）来组织可运行队列，在该红黑树中，节点的键值为 vruntime 值，由于红黑树是一种自平衡二叉搜索树，所以最小 vruntime 值的进程一定是树的最左侧叶子节点。所以，为了快速找到最小 vruntime 值节点，linux一般会把最左侧叶子节点给缓存起来（rb_leftmost字段中）。rb_leftmost 字段在每次插入或删除节点的时候都会更新。

4.2.3 调度器入口

进程调度的主要入口点是函数 schedule()，它定义在 kernel/sched.c 中。schedule()函数会找到一个最高优先级的调度类，并且函数会询问这个调度类谁才是下一个该运行的进程。该函数中唯一重要的事情是它会调用 pick_next_task()，这个函数会以优先级为序，从高到底，依次检查每个调度类，并且从最高优先级的调度类中选择最高优先级的进程。

4.2.4 休眠与唤醒

休眠（被阻塞）的进程处于一个特殊的不可执行的状态。进程休眠有很多原因，但肯定都是为了等待一些事件。一个进程还有可能在尝试获取一个已被占用的内核信号量时被迫进入休眠。进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程（因为一般进程是自我阻塞）。唤醒的过程刚好相反，进程被设置成可执行状态，然后再从等待队列中移到可执行红黑树中。

休眠通过等待队列进行处理，等待队列是由等待某些事件发生的进程组成的简单链表。唤醒操作通过函数 wake_up() 进行，它会唤醒指定等待队列上的所有进程。

4.3 抢占和上下文切换

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在 kernel/sched.c 中的 context_switch() 函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule() 就会调用该函数。它完成了两项基本工作：

调用声明在 <asm/mmu_context> 中的 switch_mm() ，该函数负责把虚拟内存从上一个进程映射切换到i新进程中。

调用声明在 <asm/system.h> 中的 switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，其实就是进程上下文。

内核即将返回用户空间的时候，如果 need_resched 标志被设置，会导致 schedule() 被调用，此时就会发生用户抢占，在如下情况会发生用户抢占：

在系统调用返回用户空间时。
从中断处理程序返回用户空间时。

Linux 也支持内核抢占，在不支持内核抢占的内核中，内核代码可以一直运行，直到它完成为止。在支持内核抢占的内核中，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。内核抢占发生在：

中断处理程序正在执行，且返回内核空间之前。
内核代码再一次具有可抢占性的时候。
如果内核中的任务显式地调用 schedule()。
如果内核中的任务阻塞（会导致调用 schedule()）。

4.4 实时调度策略

Linux 提供了两种实时调度策略，SCHED_FIFO 和 SCHED_RR。而普通的、非实时的调度策略是 SCHED_NORMAL。这些实时策略被一个特殊的实时调度器管理，具体的定义在 kernel/sched_rt.c 种。

SCHED_FIFO 实现了一种简单的、先入先出的调度算法，它不使用时间片。处于可运行状态的 SCHED_FIFO 级的进程会比任何 SCHED_NORMAL 级的进程都先得到调度。一旦一个SCHED_FIFO 级进程处于可执行状态，就会一直执行，直到它自己阻塞或显示地释放处理器为止。只有更高优先级的 SCHED_FIFO 或者 SCHED_RR 任务才能抢占 SCHED_FIFO 任务。

SCHED_RR 与 SCHED_FIFO 大体相同，只是 SCHED_RR 级的进程在耗尽事先分配给它的时间后就不能再继续执行了，也就是说 SCHED_RR 是带有时间片的 SCHED_FIFO，这是一种实时轮流调度算法。当 SCHED_RR 任务耗尽时间片时，在同一优先级的其他实时进程被轮流调度。时间片只用来重新调度同一优先级的进程。

对于 SCHED_FIFO 进程，高优先级总是立即抢占低优先级，但低优先级绝不能抢占 SCHED_RR 任务，即使它的时间片耗尽。