Linux Process Scheduling, 进程调度

进程调度概述

操作系统要实现多进程，进程调度必不可少。进程调度是对 TASK_RUNNING 状态的进程进行调度（进程状态详见 Linux Process State, 进程状态）。如果进程不可执行（正在睡眠或其他），那么它跟进程调度没多大关系。

所以，如果系统负载非常低，盼星星盼月亮才出现一个可执行状态的进程，那么进程调度也就不会太重要，哪个进程可执行就让它执行去，没有什么需要多考虑的。

反之，如果系统负载非常高，时时刻刻都有 N 多个进程处于可执行状态，等待被调度运行，那么进程调度程序为了协调这 N 个进程的执行，必定得做很多工作。协调得不好，系统的性能就会大打折扣，这个时候，进程调度就是非常重要的。

尽管我们平常接触的很多计算机（如桌面系统、网络服务器等）负载都比较低，但是 Linux 作为一个通用操作系统，不能假设系统负载低，必须为应付高负载下的进程调度做精心的设计。

当然，这些设计对于低负载（且没有什么实时性要求）的环境没多大用。极端情况下，如果 CPU 的负载始终保持 0 或 1（永远都只有一个进程或没有进程需要在 CPU 上运行），那么这些设计基本上都是徒劳的。

优先级

现在的操作系统为了协调多个进程的"同时"运行，最基本的手段就是给进程定义优先级。定义了进程的优先级，如果有多个进程同时处于可执行状态，那么谁优先级高谁就去执行，没有什么好纠结的了。

进程的优先级该如何确定呢？有两种方式：由用户程序指定、由内核的调度程序动态调整。Linux 内核将进程分成两个级别：普通进程和实时进程。实时进程的优先级都高于普通进程，除此之外，它们的调度策略也有所不同。

实时进程的调度

实时，原本的涵义是"给定的操作一定要在确定的时间内完成"。重点并不在于操作一定要处理得多快，而是时间要可控（在最坏情况下也不能突破给定的时间）。

这样的"实时"称为"硬实时"，多用于很精密的系统之中（比如火箭、导弹之类的）。一般来说，硬实时的系统是相对比较专用的。

像 Linux 这样的通用操作系统显然没法满足这样的要求，中断处理、虚拟内存等机制的存在给处理时间带来了很大的不确定性，硬件的 cache、磁盘寻道、总线争用也会带来不确定性。

比如考虑 i++; 这么一句 C 代码，绝大多数情况下它执行得很快，但是极端情况下还是有这样的可能：

1. i 的内存空间未分配，CPU 触发缺页异常，而 Linux 在缺页异常的处理代码中试图分配内存时，又可能由于系统内存紧缺而分配失败，导致进程进入睡眠；
2. 代码执行过程中硬件产生中断，Linux 进入中断处理程序而搁置当前进程，而中断处理程序的处理过程中又可能发生新的硬件中断，中断永远嵌套不止……

而像 Linux 这样号称实现了"实时"的通用操作系统，其实只是实现了"软实时"，即尽可能地满足进程的实时需求。

如果一个进程有实时需求（它是一个实时进程），则只要它是可执行状态的，内核就一直让它执行，以尽可能地满足它对 CPU 的需要，直到它完成所需要做的事情，然后睡眠或退出（变为非可执行状态）。

而如果有多个实时进程都处于可执行状态，则内核会先满足优先级最高的实时进程对 CPU 的需要，直到它变为非可执行状态。于是，只要高优先级的实时进程一直处于可执行状态，低优先级的实时进程就一直不能得到 CPU；只要一直有实时进程处于可执行状态，普通进程就一直不能得到 CPU。

后来，内核添加了 /proc/sys/kernel/sched_rt_runtime_us 和 /proc/sys/kernel/sched_rt_period_us 两个参数，限定了在以 sched_rt_period_us 为周期的时间内，实时进程最多只能运行 sched_rt_runtime_us 这么多时间，这样就在一直有实时进程处于可执行状态的情况下，给普通进程留了一点点能够得到执行的机会。

那么，如果多个相同优先级的实时进程都处于可执行状态呢？这时就有两种调度策略可供选择：

1. SCHED_FIFO：先进先出，直到先被执行的进程变为非可执行状态，后来的进程才被调度执行。在这种策略下，先来的进程可以调用 sched_yield 系统调用，自愿放弃 CPU，以让权给后来的进程；
2. SCHED_RR：轮转调度，内核为实时进程分配时间片，在时间片用完时，让下一个进程使用 CPU；

强调一下，这两种调度策略仅仅针对于相同优先级的多个实时进程同时处于可执行状态的情况。

在 Linux 下，用户程序可以通过 sched_setscheduler 系统调用来设置进程的调度策略以及相关调度参数，sched_setparam 系统调用则只用于设置调度参数。这两个系统调用要求用户进程具有设置进程优先级的能力（CAP_SYS_NICE，一般来说需要 root 权限）。

通过将进程的策略设为 SCHED_FIFO 或 SCHED_RR，使得进程变为实时进程，而进程的优先级则是通过以上两个系统调用在设置调度参数时指定的。

对于实时进程，内核不会试图调整其优先级，因为进程实时与否、有多实时，这些问题都是跟用户程序的应用场景相关，只有用户能够回答，内核不能臆断。

综上所述，实时进程的调度是非常简单的：进程的优先级和调度策略都由用户定死了，内核只需要总是选择优先级最高的实时进程来调度执行即可，唯一稍微麻烦一点的只是在选择具有相同优先级的实时进程时，要考虑两种调度策略。

普通进程的调度

实时进程调度的中心思想是，让处于可执行状态的最高优先级的实时进程尽可能地占有 CPU，因为它有实时需求；而普通进程则被认为是没有实时需求的进程，于是调度程序力图让各个处于可执行状态的普通进程和平共处地分享 CPU，从而让用户觉得这些进程是同时运行的。

与实时进程相比，普通进程的调度要复杂得多。内核需要考虑两件麻烦事：

动态调整进程的优先级

按进程的行为特征，可以将进程分为"交互式进程"和"批处理进程"：

• 交互式进程（如桌面程序、服务器等）主要的任务是与外界交互，这样的进程应该具有较高的优先级，它们总是睡眠等待外界的输入，而在输入到来、内核将其唤醒时，它们又应该很快被调度执行，以做出响应。比如一个桌面程序，如果鼠标点击后半秒钟还没反应，用户就会感觉系统"卡"了；
• 批处理进程（如编译程序）主要的任务是做持续的运算，因而它们会持续处于可执行状态，这样的进程一般不需要高优先级，比如编译程序多运行了几秒钟，用户多半不会太在意；

如果用户能够明确知道进程应该有怎样的优先级，可以通过 nice、setpriority（非实时进程优先级的设置）系统调用来对优先级进行设置（如果要提高进程的优先级，要求用户进程具有 CAP_SYS_NICE 能力）。

然而应用程序未必就像桌面程序、编译程序这样典型，程序的行为可能五花八门，可能一会儿像交互式进程，一会儿又像批处理进程，以致于用户难以给它设置一个合适的优先级。再者，即使用户明确知道一个进程是交互式还是批处理，也多半碍于权限或因为偷懒而不去设置进程的优先级。

于是，最终，区分交互式进程和批处理进程的重任就落到了内核的调度程序上。调度程序关注进程近一段时间内的表现（主要是检查其睡眠时间和运行时间），根据一些经验性的公式，判断它现在是交互式的还是批处理的、程度如何，最后决定给它的优先级做一定的调整。

进程的优先级被动态调整后，就出现了两个优先级：

1. 用户程序设置的优先级（如果未设置，则使用默认值），称为静态优先级，这是进程优先级的基准，在进程执行的过程中往往是不改变的；
2. 优先级动态调整后，实际生效的优先级，这个值是可能时时刻刻都在变化的；

调度的公平性

在支持多进程的系统中，理想情况下，各个进程应该是根据其优先级公平地占有 CPU，而不会出现"谁运气好谁占得多"这样的不可控的情况。

Linux 实现公平调度基本上是两种思路：

1. 给处于可执行状态的进程分配时间片（按照优先级），用完时间片的进程被放到"过期队列"中，等可执行状态的进程都过期了，再重新分配时间片；
2. 动态调整进程的优先级，随着进程在 CPU 上运行，其优先级被不断调低，以便其他优先级较低的进程得到运行机会；

后一种方式有更小的调度粒度，并且将"公平性"与"动态调整优先级"两件事情合而为一，大大简化了内核调度程序的代码，因此这种方式也成为内核调度程序的新宠。

强调一下，以上两点都是仅针对普通进程的，而对于实时进程，内核既不能自作多情地去动态调整优先级，也没有什么公平性可言。

调度程序的效率

“优先级"明确了哪个进程应该被调度执行，而调度程序还必须要关心效率问题。调度程序跟内核中的很多过程一样会频繁被执行，如果效率不济就会浪费很多 CPU 时间，导致系统性能下降。

调度程序选择下一个执行进程的算法，随内核版本演进经历了几个阶段：

• Linux 2.4：可执行状态的进程被挂在一个链表中，每次调度需要扫描整个链表以找出最优的那个进程来运行，复杂度为 O(n)；
• Linux 2.6 早期：可执行状态的进程按优先级分别挂在 140 个链表中，每次调度只需要从第一个不为空的链表中取出位于链表头的进程即可，复杂度为 O(1)；
• Linux 2.6 近期版本：可执行状态的进程按照优先级顺序被挂在一棵红黑树中，每次调度需要从树中找出优先级最高（即虚拟运行时最小）的进程，复杂度为 O(log n)。

演进的详细过程（O(1) 调度器的实现细节、楼梯算法 SD、RSDL）以及最终取代 O(1) 调度器的完全公平调度器（CFS）的实现原理，见独立文章 CFS 完全公平调度器。

调度触发的时机

调度的触发主要有如下几种情况：

1. 当前进程（正在 CPU 上运行的进程）状态变为非可执行状态：
   • 进程执行系统调用主动变为非可执行状态，比如执行 nanosleep 进入睡眠、执行 exit 退出等；
   • 进程请求的资源得不到满足而被迫进入睡眠状态，比如执行 read 系统调用时，磁盘高速缓存里没有所需要的数据，从而睡眠等待磁盘 IO；
   • 进程响应信号而变为非可执行状态，比如响应 SIGSTOP 进入暂停状态、响应 SIGKILL 退出等；
2. 抢占：进程运行时，非预期地被剥夺 CPU 的使用权，这又分两种情况：进程用完了时间片、或出现了优先级更高的进程：
   • 优先级更高的进程受正在 CPU 上运行的进程的影响而被唤醒，如发送信号主动唤醒，或因为释放互斥对象（如释放锁）而被唤醒；
   • 内核在响应时钟中断的过程中，发现当前进程的时间片用完；
   • 内核在响应中断的过程中，发现优先级更高的进程所等待的外部资源变为可用，从而将其唤醒。比如 CPU 收到网卡中断，内核处理该中断，发现某个 socket 可读，于是唤醒正在等待读这个 socket 的进程；再比如内核在处理时钟中断的过程中触发了定时器，从而唤醒对应的正在 nanosleep 系统调用中睡眠的进程；

其他问题

内核抢占

理想情况下，只要满足"出现了优先级更高的进程"这个条件，当前进程就应该被立刻抢占。但是，就像多线程程序需要用锁来保护临界区资源一样，内核中也存在很多这样的临界区，不大可能随时随地都能接收抢占。

Linux 2.4 时的设计就非常简单，内核不支持抢占，进程运行在内核态时（比如正在执行系统调用、正处于异常处理函数中）是不允许抢占的，必须等到返回用户态时才会触发调度。

Linux 2.6 则实现了内核抢占，但是在很多地方还是为了保护临界区资源而需要临时性地禁用内核抢占。

也有一些地方是出于效率考虑而禁用抢占，比较典型的是 spin_lock。spin_lock 是这样一种锁：如果请求加锁得不到满足（锁已被别的进程占有），则当前进程在一个死循环中不断检测锁的状态，直到锁被释放。

为什么要这样忙等待呢？因为临界区很小，比如只保护 i += j++; 这么一句。如果因为加锁失败而形成"睡眠-唤醒"这么个过程，就有些得不偿失了。那么既然当前进程忙等待（不睡眠），谁又来释放锁呢？其实已得到锁的进程是运行在另一个 CPU 上的，并且是禁用了内核抢占的，这个进程不会被其他进程抢占，所以等待锁的进程只有可能运行在别的 CPU 上（如果只有一个 CPU，那么就不可能存在等待锁的进程了）。

而如果不禁用内核抢占呢？那么得到锁的进程将可能被抢占，于是可能很久都不会释放锁，等待锁的进程可能就不知何年何月得偿所望了。

对于一些实时性要求更高的系统，则不能容忍 spin_lock 这样的东西，宁可改用更费劲的"睡眠-唤醒"过程，也不能因为禁用抢占而让更高优先级的进程等待，比如嵌入式实时 Linux MontaVista 就是这么干的。由此可见，实时并不代表高效，很多时候为了实现"实时”，还是需要对性能做一定让步的。

多处理器下的负载均衡

如果系统中只有一个可执行队列，哪个 CPU 空闲了就去队列中找一个最合适的进程来执行，这样看起来很均衡，但是多处理器共用一个可执行队列会有一些问题：每个 CPU 在执行调度程序时都需要把队列锁起来，这会使得调度程序难以并行，可能导致系统性能下降；而如果每个 CPU 对应一个可执行队列则不存在这样的问题。

另外，多个可执行队列还有一个好处：这使得一个进程在一段时间内总是在同一个 CPU 上执行，那么很可能这个 CPU 的各级 cache 中都缓存着这个进程的数据，很有利于系统性能的提升。

所以，在 Linux 下，每个 CPU 都有着对应的可执行队列，而一个可执行状态的进程在同一时刻只能处于一个可执行队列中。

于是，“多处理器负载均衡"这个麻烦事情就来了。内核需要关注各个 CPU 可执行队列中的进程数目，在数目不均衡时做出适当调整。什么时候需要调整，以多大力度进行调整，这些都是内核需要关心的，当然，尽量不要调整最好，毕竟调整起来又要耗 CPU、又要锁可执行队列，代价还是不小的。

另外，内核还得关心各个 CPU 的关系，两个 CPU 之间可能是相互独立的、可能是共享 cache 的、甚至可能是由同一个物理 CPU 通过超线程技术虚拟出来的，CPU 之间的关系也是实现负载均衡的重要依据，关系越紧密，进程在它们之间迁移的代价就越小。

优先级继承

由于互斥，一个进程（设为 A）可能因为等待进入临界区而睡眠，直到正在占有相应资源的进程（设为 B）退出临界区，进程 A 才被唤醒。

可能存在这样的情况：A 的优先级非常高，B 的优先级非常低，B 进入了临界区，但是却被其他优先级较高的进程（设为 C）抢占了，而得不到运行，也就无法退出临界区，于是 A 也就无法被唤醒。

A 有着很高的优先级，但是现在却沦落到跟 B 一起，被优先级并不太高的 C 抢占，导致执行被推迟，这种现象就叫做优先级反转。

出现这种现象是很不合理的，较好的应对措施是：当 A 开始等待 B 退出临界区时，B 临时得到 A 的优先级（还是假设 A 的优先级高于 B），以便顺利完成处理过程，退出临界区，之后 B 的优先级恢复，这就是优先级继承的方法。

中断处理线程化

在 Linux 下，中断处理程序运行于一个不可调度的上下文中，从 CPU 响应硬件中断自动跳转到内核设定的中断处理程序去执行，到中断处理程序退出，整个过程是不能被抢占的。

一个进程如果被抢占了，可以通过保存在它的进程控制块（task_struct）中的信息，在之后的某个时间恢复它的运行，而中断上下文则没有 task_struct，被抢占了就没法恢复了。

中断处理程序不能被抢占，也就意味着中断处理程序的"优先级"比任何进程都高（必须等中断处理程序完成了，进程才能被执行）。但是在实际的应用场景中，可能某些实时进程应该得到比中断处理程序更高的优先级。

于是，一些实时性要求更高的系统就给中断处理程序赋予了 task_struct 以及优先级，使得它们在必要的时候能够被高优先级的进程抢占。但是显然，做这些工作是会给系统造成一定开销的，这也是为了实现"实时"而对性能做出的一种让步。

sched_class 调度器体系

所谓调度，就是按照某种调度的算法，从进程的就绪队列中选取进程分配 CPU，主要是协调对 CPU 等资源的使用，进程调度的目标是最大限度利用 CPU 时间。

内核默认提供了 5 个调度器，Linux 内核使用 struct sched_class 来对调度器进行抽象：

• Stop 调度器（stop_sched_class）：优先级最高的调度类，可以抢占其他所有进程，不能被其他进程抢占；
• Deadline 调度器（dl_sched_class）：使用红黑树，把进程按照绝对截止期限进行排序，选择最小进程进行调度运行；
• RT 调度器（rt_sched_class）：实时调度器，为每个优先级维护一个队列；
• CFS 调度器（cfs_sched_class）：完全公平调度器，采用完全公平调度算法，引入虚拟运行时间概念（Completely Fair Scheduler，详见 CFS 完全公平调度器）；
• IDLE-Task 调度器（idle_sched_class）：空闲调度器，每个 CPU 都会有一个 idle 线程，当没有其他进程可以调度时，调度运行 idle 线程；

Linux 内核提供了一些调度策略供用户程序来选择调度器，其中 Stop 调度器和 IDLE-Task 调度器仅由内核使用，用户无法进行选择：

• SCHED_DEADLINE：限期进程调度策略，使 task 选择 Deadline 调度器来调度运行；
• SCHED_RR：实时进程调度策略，时间片轮转，进程用完时间片后加入优先级对应运行队列的尾部，把 CPU 让给同优先级的其他进程；
• SCHED_FIFO：实时进程调度策略，先进先出调度没有时间片，没有更高优先级的情况下，只能等待主动让出 CPU；
• SCHED_NORMAL：普通进程调度策略，使 task 选择 CFS 调度器来调度运行；
• SCHED_BATCH：普通进程调度策略，批量处理，使 task 选择 CFS 调度器来调度运行；
• SCHED_IDLE：普通进程调度策略，使 task 以最低优先级选择 CFS 调度器来调度运行；

runqueue 运行队列

每个 CPU 都有一个运行队列，每个调度器都作用于运行队列；分配给 CPU 的 task，作为调度实体加入到运行队列中；task 首次运行时，如果可能，尽量将它加入到父 task 所在的运行队列中（分配给相同的 CPU，缓存 affinity 会更高，性能会有改善）。

Linux 内核使用 struct rq 结构来描述运行队列，关键字段如下：

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq {
    /* runqueue lock: */
    raw_spinlock_t lock;

    /*
     * nr_running and cpu_load should be in the same cacheline because
     * remote CPUs use both these fields when doing load calculation.
     */
    unsigned int nr_running;

    /* three scheduling queues: CFS, RT, DL */
    struct cfs_rq cfs;
    struct rt_rq rt;
    struct dl_rq dl;

    /* stop points to the migration kernel thread, idle to the idle kernel thread */
    struct task_struct *curr, *idle, *stop;
    /* ... */
};

task_group 任务分组

利用任务分组的机制，可以设置或限制任务组对 CPU 的利用率，比如将某些任务限制在某个区间内，从而不去影响其他任务的执行效率。

引入 task_group 后，调度器的调度对象不仅仅是进程了，Linux 内核抽象出了 sched_entity/sched_rt_entity/sched_dl_entity 描述调度实体，调度实体可以是进程或 task_group。

Linux 内核使用 struct task_group 来描述任务组，任务组在每个 CPU 上都会维护一个 CFS 调度实体、CFS 运行队列，RT 调度实体、RT 运行队列。

调度程序核心函数

schedule() 函数是进程调度的核心函数，核心的逻辑是选择另外一个进程来替换掉当前运行的进程。进程的选择是通过进程所使用的调度器中的 pick_next_task 函数来实现的，不同的调度器实现的方法不一样；进程的替换是通过 context_switch() 来完成切换的（详见 上下文切换）。

周期调度：schedule_tick()

时钟中断处理程序中，调用 schedule_tick() 函数；时钟中断是调度器的脉搏，内核依靠周期性的时钟来控制器 CPU 的控制权；时钟中断处理程序检查当前进程的执行时间是否超额，如果超额则设置重新调度标志（_TIF_NEED_RESCHED）；时钟中断处理函数返回时，被中断的进程如果在用户模式下运行，需要检查是否有重新调度标志，设置了则调用 schedule() 调度。

高精度时钟调度：hrtick()

高精度时钟调度与周期性调度类似，不同点在于周期调度的精度为 ms 级别，而高精度调度的精度为 ns 级别；高精度时钟调度需要有对应的硬件支持。

进程唤醒时调度：wake_up_process()

唤醒进程时调用 wake_up_process() 函数，被唤醒的进程可能抢占当前的进程。

参考

• Linux Kernel调度器的过去，现在和未来
• scheduler 调度器（cnblogs，LoyenWang）
• 伯乐在线：Linux 调度器
• 知乎：Linux 调度器
• CSDN：Linux 调度器

维护记录