进程调度，由进程调度程序负责，它是确保内核能够有效工作的子系统，负责在可运行态进程之间分配有限的处理器时间资源。调度程序决定了哪个进程在哪个时间运行多少时间。调度程序是多任务操作系统的基础。只有通过调度程序的合理调度，系统资源才能最大限度的发挥作用，多进程才会出现并发执行的效果。

调度程序，需要最大限度的利用处理器资源，而原则是：只要有可以执行的进程，那么总会有进程在执行。但是只要系统中可运行进程数比处理器个数多，就注定会有进程不能运行（在等待运行）

调度程序，需要完成的基本工作就是：从在一组可运行状态的进程中选择一个来执行。

多任务（Multitasking）

多任务操作系统，即能同时并发地交互执行多个进程的操作系统。在单处理器上，这会产生多个进程在同时运行的幻觉。在多处理器上，这会使多个进程在不同的处理器上真正同时、并行地运行。

多任务操作系统可以使多个进程处于休眠或阻塞状态，也就是说，实际上进程不被投入运行。这些进程虽然存在于内存中，但并不处于可运行状态，他们被阻塞，直到某一事件发生（比如等待键盘输入、网络响应等等）。因此，在操作系统中，虽然存在很多进程，但不是没一个都处于运行或可运行状态。

多任务操作系统分为两类：非抢占式多任务（cooperative multitasking）；抢占式多任务（preemptive multitasking）。

Linux 的进程调度历史

在 Kernel 2.4 以前，Linux 的调度程序都相当简陋，很容易理解，但是在较多可运行进程或多处理环境下表现不佳。

在 Lernel 2.5 版本，开始采用称为 O(1) 调度程序的新调度程序，由算法的行为而得名。它解决了先前的问题，并引入许多强大的新特性与性能特征。这要感谢静态时间片算法和针对每一处理器的运行队列，使我们摆脱先前调度程序设计上的限制。

在 Kernle 2.6 版本，为了提高交互程序的调度性能，开始采用新的调度程序，最值得一提的是 Rotating Straircase Deadline Scheduler，它吸取队列理论，将公平调度的概念引入 Linux 调度程序。并在 Kernel 2.6.23 中替代 O(1) 调度算法，此时被称为“完全公平调度程序”（Completely Fair Scheduler, CFS）。

调度策略

策略决定调度程序在合适让什么进程运行，调度程序的策略往往决定了系统给用户的整体印象，并且还要负责优化处理器时间，因此十分重要。

IO 消耗型进程 与 处理器消耗型进程

I/O 消耗型进程，指进程的大部分时间用来提交 I/O 请求 或 等待 I/O 请求。这样的进程经常处于可运行状态，但通常都运行很短的时间，因为它们要等待 I/O 请求时最后总会阻塞。比如大多数 GUI 应用都属于 I/O 密集型，即使不读写磁盘，他们多数时间也在等待用户输入。

处理器消耗型进程，大多数时间都在执行运算，它们并没有太多 I/O 请求。所以对于处理器消耗型进程，调度策略往往是：尽量降低它们的调度频率，而延长其运行时间。

进程有又可能同时属于这两种类型，比如：文字处理程序，通常在等待用户输入，此时是 I/O消耗型；当用户输入结束之后，经常开始疯狂的拼写检查，此时又是处理器消耗型；

在系统中的调度策略，必须尝试满足这两个冲突的目标：快速的进程响应（低延迟）；最大化系统使用（高吞吐）；为什么说这两个目标是冲突的呢？如果想要最大化系统使用，就要保证进程长时间运行，因此不能频繁的调度与进程切换，否则只会将系统资源浪费，但是这降低进程的响应速度；如果想要进程快速响应，就要及时切换进程，但是这就无法最大化系统使用。

为了满足和两个需求，调度程序就会采用很多复杂的算法，以让最值得运行的进程投入运行，但是它并不能保证低优先级的进程呗公平对待。Unix 的系统调度程序倾向与 IO 消耗型程序，以提高相应速度。Linux 为了保证交互性程序和桌面系统的性能，所以对进程响应进行优化，更加倾向于 IO 消耗型进程（超过处理器消耗型），但是她又没有忽略处理器消耗型进程。

进程优先级

调度算法中最基本的一类就是 基于优先级的调度，该想法根据 进程的价值 和 其最处理器时间的需求 来对进程进行分级。通常是，优先级高的进程先运行，优先级低的进程后运行，优先级相同的进程按照论转的凡是调度。有些系统中，优先级高的进程，时间片也较长。调度程序总是选择优先级高且时间片为用完的进程运行。用户的系统都可以通过设置优先级来影响系统的调度。

Linux 采用两种不同的优先级范围：

时间片（Timeslice）

时间片是个数值，表示进程在被抢占前可以运行的时间。但是，时间片分配是个复杂的问题：如果分配的时间片过长，对交互进程的响应会下降；如果分配的时间片过短，频繁的进程切换，将消耗额外的资源。此外，I/O 消耗型进程 与 处理器消耗型进程 的矛盾再次凸显：前者无需过长的时间片；后者希望长时间运行（比如，这样会然他们的缓存命中效果较好）。

因此，不能分配过长的时间片，很多操作系统的默认时间片都很短，比如 10ms 时间。但是，Linux 的 CFS 调度程序，没有为进程直接分配时间片，而是将处理器的使用比例（proportion）划分给了进程。这样，进程获得的处理器时间是系统负载的函数。进一步，该比例还会受到 nice 值的影响，nice 作为权重值，将调整进程所使用的处理器时间比，高 nice（低权重）将损失一小部分处理器使用比，反之亦然。

在多数操作系统中，进程是否立刻投入运行（抢占），完全取决于优先级与时间片的有无。而在 Liunx 的 CFS 调度器中，抢占则取决于新的可运行进程消耗了多少处理器使用比。如果进程消耗的使用比小于当前进程，则抢占发生，运行进程。

调度策略的活动

加入这样一个系统，它拥有两个可运行的进程：一个文字编辑程序；一个视频编码程序。文字编辑程序必然是 IO 消耗型应用，大部分时间都在等待用户输入，用户希望按键时系统可以快速响应。视频编码程序则是处理器消耗型，大多数时间都在计算（忽略开始和结束时的视频数据读取与写入）。

我们希望调度程序分配给文本编辑器更多的处理器时间，当然这并不是因为它需要更多的处理时间，而是我们希望文本编辑程序大多数时间都在运行，以能够快速响应。

在多数操作系统中，要达成上述目标，依靠于系统分配给文本编辑程序更高的优先级与更多的时间片。先进的操作系统能够发现文本编辑器是交互性程序，从而自动完成上述分配工作。

但是 Linux 操作操作系统同样需要追求上述目标，但是采用了不同的做法，它不再通过给文本编辑器分配给定的优先级和时间片，而是分配一个给定的处理器使用比。假如，文本编辑器和视频编码程序是仅有的两个进程，并且又具有相同的 nice 值，那么处理器的使用比都是 50%（平分处理器时间）。但是文本编辑器将用更多的时间等待用户输入，所以处理器使用不会到达 50%，而视频编码程序必将能超过 50% 的处理器时间。

在这些条件下，当文本编辑器被唤醒，CFS 调度程序注意到文本编辑器的处理器使用比远小于 50%，而视频编码器用的时间却非常多。此时，CFS 程序会毫不犹豫的抢占视频编码程序，转而运行文本编辑程序。后续的情况依旧如此，CFS 调度程序会毫不犹豫的让文本编辑器程序投入运行，而视频处理程序只能在剩余的时间内运行。

Linux 的调度算法

调度器类

Linux 的调度器是以模块的形式提供的，这样可以允许不同类型的进程有针对性地选择调度算法，这种模块化的结构被称为调度器类（Scheduler Class），它允许多种不同的调度算法并存，调度属于自己范畴的进程。每个调度其类都有自己的优先级。基础的调度器代码（在 /include/kernel/sched.c 中）会按照优先级顺序遍历调度器类，优先级高的调度器类胜出，并调度它下面的进程。

CFS 是一个针对普通进程的调度类，在 Linux 中，称为 SCHED_NORMAL（SCHED_OTHER in POSIX），CFS 算法实现定义在 kernel/sched_fair.c 中。

# 02/24/2021 由于我们学得不多，因此在理解调度器类（Scheduler Class）这个术语有些困难，因此尝试寻找说明。但是这并不是个术语，而且这个词引用的频率比较低（而 Scheduling Class 出现的频率更高）。后来结合在 ps 命令的手册中的发现，我们认为它通常泛指调度算法（SCHED_OTHER, SCHED_FIFO, SCHED_RR, …）

Unix 系统中的进程调度

在讨论 CFS 前，先看看传统 Unix 的调度过程。现代进程调度器中，有两个通用的概念 —— 进程优先级；时间片：
1）时间片，指进程可以持续运行多长时间。在进程启动时，会分配默认时间片；
2）优先级，使其越高的进程，运行的越频繁，而且会获得更多的时间片。它以 nice 值的形式暴露到用户空间；

这个两个概念听起来简单，但是实现中却会出现各种问题：

当然，这些问题都可以进行解决。比如：解决第二个问题，可以通过使 nice 值呈现几何增加，以保证增量相同带来的效果也相同；对于第三个问题，采用新的度量机制，将 nice 值与定时器节拍分离。但是这些方案都没有解决本质问题，即：分配绝对时间片会产生一个恒定的切换频率，但公平性是无法确定。

而 CFS 的做法则是：完全摒弃时间片，而是为进程分配处理器使用比重。通过这种方式，CFS 确保了进程调度中，能有恒定的公平性，而将切换频率置于不断的变动中。

公平调度

CFS 允许没一个进程运行一段时间、循环论转、选择运行时间最短的进程运行。CFS 在所有可运行进程总数的基础上，算出每个进程应该运行的时间。

nice 至只作为权重出现，越高的 nice 值，获得更低的处理器使用权，而不是用来计算时间片。

Linux 调度的实现

时间记账

CFS 不再采用时间片的概念，但是依旧记录进程运行时间，使用 sched_entity 结构（linux/sched.h），来记录进程运行时间，该结构作为 task_struct 的 se 成员。

它的 vruntime 记录运行时间，以 ns 为单位，而 vruntime 的计算不是直接累加，而是经过所有可运行进程总数的标准化。

进程选择

CFS 使用红黑树来组织可运行进程队列，选择 vruntime 最小的任务。

调度器入口

调度器的入口为 schedule() 函数，该函数会遍历调度类（按照调度类的优先级），找到调度类中可运行的进程，并投入运行。

# 02/25/2021 进程是按照 CPU 使用时间进行调度的，那么为什么这里又说是按照调度类优先级进行调度的？

睡眠和唤醒

无论何种原因休眠，进程的操作都相同：进程把自己标为休眠状态，从可执行的红黑树中移出，放入等待队列，然后调用 schedule() 来选择和执行另外一个进程。

唤醒过程正好相反：进程被设置为可执行状态，然后从等待队列中移出，放入到红黑树中（并经内核里的红黑树就是用来组织可运行进程队列的）。

抢占与上下文切换

4

实时调度策略

4

与调度相关的系统调用

5

wait, wait_event

wait_event

在 wait_event 中：
1）定义 wait 结构，然后进入睡眠。
2）如果由其他进程唤醒该进程，则判断是否满足条件。如果已满足，则进行调度，并删除 wait 对象。如果未满足，则继续睡眠。

在内核中，还有很多其他的 wait_event 实现：
1）wait_event_timeout：
2）wait_event_interruputible：
3）wait_event_interruputible_timeout：
4）wait_event_interruputible_exclusive：