「Learning Linux Kernel」- 进程调度(学习笔记)

  CREATED BY JENKINSBOT

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

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

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

多任务(Multitasking)

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

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

多任务操作系统分为两类:非抢占式多任务(cooperative multitasking);抢占式多任务(preemptive multitasking)。

	与其他现代操作系统一样,Linux 采用抢占式多任务。在抢占式多任务模式下,由调度程序决定什么时候停止一个进程的运行,以便其他进程可以执行。调度程序强制挂起进程的行为就叫做抢占(preemption)。进程在被抢占前能够运行的时间是预先设置好的,这个时间称为进程时间片(timeslice)。时间片是分配给每个可运行进程的处理器时间段。有效的管理时间片能使调度程序从系统全局的角度作出调度决定,还能避免进程独占系统资源。很多现代操作系统都采用动态时间片计算的方式,并且引入可配置的计算策略。但是,Linux 的公平调度程序没有采用时间片的方式来公平调度。
	在非抢占式多任务模式下,需要进程主动挂起自己(该操作称之为让步yielding)。缺点也比较明显:进程不受调度程序控制,所以独占处理器时间可能超过用户预料;如果进程挂起而不让步,系统则可能崩溃。不过,近年来的操作系统都是抢占式多任务。

Linux 的进程调度历史

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

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

	O(1) 调度程序在数以十计的多处理器环境下表现出完美的性能和可扩展性,但是对于响应时间敏感的程序却有些不足。这些响应时间敏感的程序我们称之为交互进程,这里面就包含需要用户交互的程序。正因为如此,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 采用两种不同的优先级范围:

	1)nice,-20 ~ +19,值越大,表示进程越“友好”,因此优先级越低,获得的处理器时间也越少。虽然在很多 Unix 系统中的常见概念,但是不同系统使用 nice 值的方式并不相同。比如,macOS 进程 nice 值表示分配给进程的时间片的绝对值;在 Linux 中,代表时间片的比例。命令 ps -el 的 NI 列显示的便是 nice 值。
	2)实时优先级(real-time priority),可配置,范围 0~99(包括两端)。值越高,优先级越高。任何“实时进程”(real-time process)的优先级,都高于普通进程。nice 与 实时优先级是两个不同的范畴。Linux 的实时优先级参考 Unix 相关标准(特别是 POSIX.1b),大部分现代的 Unix 操作系统都提供类似的机制。命令 ps -eo state,uid,pid,ppid,rtprio,time,comm 的 RTPRIO 列显示进程的实时优先级,如果显示为 - 表示它不是实时进程。
	什么是实时进程?:[[https://stackoverflow.com/questions/2717662/some-examples-for-common-real-time-processes-in-linux%20|scheduling - Some examples for common Real Time processes in Linux - Stack Overflow]]

时间片(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 值的形式暴露到用户空间;

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

	**(1)不理想的进程切换**:如果将 nice 值映射到时间片,那么必须有一个映射规律,即必须将单位的 nice 值对应到处理器的绝对时间。这里,我们假设 nice=0 为 100ms 时间片;nice=20 为 5ms 时间片,并且我们假设现在系统中有两个可运行的进程。(我们也可以假设其他值,但是效果是一样的)
		那么,默认优先级(nice=0)的进程将或者 20/21 的处理器时间(100ms/105ms),而最低优先级(nice=20)的进程将获得 1/21 的处理器时间(5ms/105ms)。也就是说,进程将在 105ms 内完成两次进程切换。如果,此时系统中的两个进程全部为最低优先级(nice=20),那么他们的各自为 5ms 时间片,也就是说 10ms 发生两次进程切换。 如果,此时系统中的两个进程全部为普通优先级(nice=0),那么它们各自为 100ms 时间片,也就说 200ms 发生两次进程切换。很显然,这种调度并不理想,nice 值与时间片的混合,导致不确定的调度频率。
		而且另外一个问题是,高优先级的进程,应该频繁运行,但是分配的时间片较长,导致调度周期长,进程无法频繁运行。而低优先级的进程,不应该频繁运行,但是由于时间片短,导致频繁调度,却经常运行。(反之亦然:如果给高优先级较低的时间片,导致频繁调度,依旧无法长时间运行)
	**(2)相对 nice 值导致的不同效果**:也就是说,将 nice 值减一所带来的效果是不同的,完全取决于 nice 的初始值。
		这里我们假设 nice=0 为 100ms 时间片,nice=1 为 95ms 时间片,此时差别不大。但是 nice 值达到 18 与 19 时,时间片分别为 10ms 与 5ms,也就是说前者则运行时间,是后者的两倍(这里不能说“它们都相差 5ms 所以效果是类似的”,这是因为进程是交替运行的,很显然在后面的情况中,一个进程的运行时间是另一个进程的两倍)。
	**(3)时间片的绝对值不是固定的**:将 nice 值映射到时间片,需要分配绝对时间片。但是,这个时间片必须能测量,也就是说它必须是定时器节拍的整数倍。这带来一些问题:
		1)最小的时间片不能低于定时器节拍。2)系统的计时器限制了两个时间片的差别。3)时间片长度会随着计时器而发生改变(这是 CFS 背后的仅有动机)。
	**(4)优先级提升带来的损害**:在基于优先级的调度器中(该调度器想要优化交互程序),处理进程唤醒。在该系统中,为了进程能够快速运行,会去提升新唤醒进程的优先级,即使它们的时间片已经用完了。虽然这能够提升性能,但是在某些情况下却给了进程愚弄调度器的后门,导致进程打破公平原则,损害系统其他进程的利益。

当然,这些问题都可以进行解决。比如:解决第二个问题,可以通过使 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