操作系统的任务调度机制（三）调度器策略

2月 14, 2021

操作系统中的调度器有任务调度、I/O 调度（以后再说）、内存调度（之前提到的换页策略）等多种类型，本文主要关注任务调度。在单核多进程并发的环境里，进程之间并不是“并行”执行的，实际上在任何时刻都只有一个进程处于执行状态，背后是 CPU 在不停地进行上下文切换，让你看起来像是多个任务在并行执行。而任务调度器要做的就是决定选择哪个进程执行，什么时候执行，执行多久，下面开始详细介绍。

调度器（Scheduler） #

调度器分配处理器资源给进程，决定了如何选择进程、何时进行调度、每次调度执行多久等关键问题。从 Linux 内核源码角度看，scheduler 函数是理解调度操作的起点，该函数定义在 kernel/sched.c 中，是内核代码中最常调用的函数之一。在 Linux 中，调度器使用红黑树实现运行队列，跟踪进程的等待时间，对进程进行管理。

调度类型 #

进程调度可以分为长期、中期、短期调度，从而对 CPU、内存、I/O 资源的使用进行管理。

长期调度 #

长期调度，又称为作业调度或高级调度，这种调度将已进入系统并处于后备状态的作业按某种算法选择一个或一批，为其建立进程，并进入主机，当该作业执行完毕时，还负责回收系统资源，在批处理系统中，需要有作业调度的过程，以便将它们分批地装入内存，在分时系统和实时系统中，通常不需要长期调度。它的频率比较低，主要用来控制内存中进程的数量。

中期调度 #

中期调度，又称为交换调度，实际上也是内存调度（换页机制）。它的核心思想是能将进程从内存或从 CPU 竞争中移出，从而降低多道程序设计的程度，之后进程能被重新调入内存，并从中断处继续执行，这种交换的操作可以调整进程在内存中的存在数量和时机。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。

中期调度的主要目的是及时挂起短期调度管理的进程，避免操作系统中的进程过多而占用内存重量，并在适当的时机激活此前挂起的进程。

短期调度 #

短期调度，又称为进程调度、低级调度或微观调度。这也是通常所说的调度，一般情况下使用最多的就是短期调度。短期调度主要负责进程在就绪态、运行态、阻塞状态之间的转换，使用适当的调度策略，尽可能地满足系统的调度指标。

调度指标 #

从日常经验直观上说，肯定是能够公平地在最短时间内完成所有任务的调度策略，就是最优策略。公平显然非常重要，其次是任务的优先级，即重要程度，越重要的任务越要优先执行。公平和优先级这两点在哪个场景里几乎都很重要。

在此基础上，手机系统会格外注重能耗，个人 PC 操作系统会格外注重及时反馈（即响应时间），服务器操作系统会格外注重并发性以处理 I/O 密集任务，一些汽车、航天等专业领域还会格外注重实时性等等。

很明显，不同需求的调度场景应该有不同的评价指标，脱离场景只谈指标毫无意义。常用的性能指标有：CPU 利用率、吞吐量、响应时间、周转时间。非性能指标有：公平性、优先级。

调度场景 #

单核批处理 #

单处理器调度策略是批处理时代的一些经典的调度策略，这些策略假设系统只有一个可用的 CPU 核心，并且系统只会在任务完成后进行调度。常见的策略包括先到先得策略、最短任务优先策略、时间片轮转策略，看上去很简单，了解这些策略有助于后面了解更先进和复杂的策略。

交互式 #

后来随着操作系统的发展，计算机已经从批处理时期进入分时操作系统时期，交互式系统在个人计算机变得常见起来，这为系统调度带来了新的挑战：及时的响应时间。像之前长任务得不到处理的情况，就必须要解决了。

实时 #

实时操作系统是需要实时处理任务请求的操作系统，当外部时间到达系统后，系统需要尽可能在可控、确定的时间范围内将事件处理完。该类操作系统已经应用在生活中的许多地方，例如：车控系统、飞行管控系统、机器人控制系统、音响系统等等。在是是操作系统上运行的主要为实时任务，顾名思义，实时任务有非常高的时效性，必须对请求和事件立刻做出反应。

通用 #

真实场景中，批处理、交互式和实时任务的区分不会那么明显，一个系统可能同时在处理三种对应的任务，因此有些调度策略的目标是具有通用性，能够为不同的任务提供调度。

多处理器 #

在多处理系统调度中，任务会同时在多个 CPU 核心上并行地运行，相比单处理器调度策略，多处理器需要考虑的因素更加复杂。

不管选择哪种策略，理想情况都有可能会和实际情况会有一些差距，比如绝对公平（占用相同的 CPU 时间）的策略却可能达不到最快完成所有任务的目标，当多种目标叠加在一起的时候，也就没有一个策略适合所有场景，操作系统也需要根据不同的场景选择不同的调度策略。又比如，程序刚刚开始运行时，操作系统对一个任务的复杂程度没有判断依据，那么最终选择合适的策略的过程也一定动态的。

单处理器系统调度 #

先来先服务调度算法（FCFS） #

先到先得（First Come First Served，FCFS）策略是最简单直观的一种，开发者只需要维护一个队列就可以实现 FCFS 策略，所有新创建的任务排队一个一个执行，不需要预知任何信息。

很明显，FCFS 策略简单的同时，带来的就是短任务可能会等待长任务执行的问题，一个任务不管多短都需要等待前面的任务执行完成，任务的周转时间非常不稳定，如果是优先级很高的任务被前面的耗时任务长时间卡着肯定是不能接受的，这些不确定性都会给用户体验带来严重影响。

最短任务优先算法（SJF，SPN） #

为了改善 FCFS 的短任务等待问题，又出现一种策略，就是最短任务优先（Shortest Job First，SJF）策略，有的也叫最短进程优先（Shortest Process Next，PSN），该策略在调度时会选择运行时间最短的任务执行。也就是说，这个策略需要预知任务的时间。但是，系统一般很难预知一个任务所需要的确切运行时间，这和系统的运行状态、程序的执行性能都有关系。

同时还有另一个问题，SJF 策略严重依赖任务完成的时间点。SJF 需要在上一个任务完成的时间点之前选择下一个最短任务，但是实际情况很可能是一个长任务刚刚开始运行就产生了若干“迟到”的短任务，那这种情况是 SJF 根本无法解决的。

SJF 看上去可以通过简单的方式解决问题，但实际上却带来了新的待解决问题，所以此时我们还需要寻找其他的策略。

最短完成时间任务优先（STCF） #

为了让上面的“迟到”的短任务得到及时的执行，产生了 SJF 策略的抢占式版本：最短完成时间任务优先（Shortest Time-to-Completion First，STCF）策略。在 STCF 中，同样需要知道任务的运行时间，该策略会在任务到达系统时就进行调度，有可能会中断正在运行的任务，这种方式被称为抢占式调度。相对应的，FCFS 和 SJF 都是非抢占式调度，也叫协作式调度。

但是这个策略还是会存在一些问题：如果要执行的短任务过多，那么等待执行的长任务就会因为一直无法得到 CPU 资源而进入饥饿状态（Starvation），这时的不公平现象又回到了长任务身上。

交互式系统调度 #

时间片轮转算法（RR） #

最简单、也是最公平的策略就是时间片轮转策略（Round Robin，RR），该策略为任务设置了时间片，限定了任务每次执行的时间，这就解决了 SJF 和 STCF 策略中需要预知任务运行时间的问题，同时也不会出现长任务饥饿的问题。

对于 RR 策略，时间片的大小选择非常重要，既不能太高，也不能太低。太高的话，CPU 会有更多时间消耗在进程的上下文切换中，太低的话，对用户的响应速度就会降低，从而影响使用体验。通常来说 20ms 到 50ms 是比较常见的选择。

但是还要给 RR 策略找一个缺点，那就是如果都是类型场景的任务，耗时差不多都相同，RR 策略会延长每个任务的周转时间。这意味着，如果是 3 个相同的任务同时开始，最终可能是 3 个任务同时相继结束。这确实是个问题，问题在于本应该一个单位时间就能完成的任务，最终都花了三倍的时间才完成。

优先级调度算法（Priority） #

为了解决 RR 策略任务平均周转时间长的问题，又引入了优先级（Priority）的概念，我们给任务定一个优先级，比如交互型任务需要优先完成，不然会影响用户体验，别的任务则可以通过时间片轮转慢慢执行。

为了防止高优先级的任务无限运行下去，调度器可以定期降低任务的优先级，当优先级低于其他任务时，就进行切换。优先级还可以通过多级队列进行静态赋予，也可以通过多级反馈队列进行动态赋予。

多级队列策略（MLQ） #

多级队列（Multi-Level Queue，MLQ）策略根据任务类型会将每个任务分配预先设置好的优先级，每个优先级对应一个队列，任务会被存储在对应的优先级队列中，如果优先级队列中的任务同时处于就绪状态，调度器会倾向于调度优先级高的队列的任务。

但是多级队列还引入了低优先级队列可能的饥饿问题，这需要 MLQ 策略周期性的提升其优先级。另外还有可能存在优先级反转（Priority Inversion）的问题：高优先级申请的锁可能已经被低优先级任务持有，于是申请失败进入阻塞状态等待低优先级任务的释放，这时优先级低的任务就会先执行，产生了优先级反转现象。

多级反馈队列（MLFQ） #

由于静态分配队列还是存在问题，加上任务调度的需求越来越复杂，于是最终在优先级策略的道路上，还是发展出了多级反馈队列（Multi-Level Feedback Queue，MLFQ）的设计。MLFQ 与 MLQ 策略类似，也会维护多个优先级队列，不同的是，MLFQ 实现了优先级的动态设置，具体如下：

1. 短任务拥有更高的优先级
2. MLFQ 会对任务的运行时间进行评估
3. 低优先级的任务采用更长的时间片
4. 定时地将所有任务的优先级提升至最高，保证不会有任务饥饿。
5. 动态优先级调整除了有定期提升机制也有定期“惩罚”机制。

公平共享调度（Fair-Share） #

如果用户 A 启动了 9 个进程，用户 B 启动了 1 个进程，使用时间片轮转算法或相同优先级的调度算法，那么用户 A 将得到 90% 的 CPU 时间，用户 B 只得到 10% 的 CPU 时间。

用户看重的是自己拥有的时间占总资源的比重，于是为了能够支持以用户为粒度进行系统资源分配，产生了公平共享调度（Fair-Share scheduling）。在上面的例子中，用户 A 和 B 将各自占有 50% 的使用份额，而 A 的每个任务的份额将会从 10% 变为 5.55%。

下面给出了三种以公平共享为目标的调度算法。

保证调度算法 #

为了实现所做的保证，系统必须跟踪各个进程自创建以来已使用了多少 CPU 时间，然后它计算各个进程应获得的 CPU 时间。由于各个进程实际获得的 CPU 时间是已知的，所以很容易计算出真正获得的 CPU 时间和应获得的 CPU 时间之比。比为 0.5 说明一个进程只获得了应得时间的一半，而比率为 2.0 则说明它获得了应得时间的 2 倍，于是该算法随后转向比率最低的进程，直到该进程的比率超过它的最接近竞争者为止。

给用户一个保证，然后兑现之，是一个好想法，不过很难实现，于是又有了一种既可以预测结果实现又非常简单的方法，就是彩票调度算法。

彩票调度算法 #

彩票调度（lottery scheduling）算法也是一种公平共享调度策略的实现方式，在彩票策略中，彩票的份数就是份额，任务拥有的彩票越多，越有概率获得 CPU 调度，随着调度的次数增加，最终任务被调度的总次数的比例也就逐渐趋近于这个份额的比例。相比保证调度，彩票调度更容易实现一些。

彩票调度还可以用来解决其他方法很难解决的问题，一个例子是，有一个视频服务器，该服务器正在向若干个客户提供视频流，每个视频流的帧速率都不相同，假设是 10、20、25 帧每秒。那么可以给这些进程分配 10、20和 25 张彩票，它们就会自动地按照大致正确的比例（即 10:20:25）划分 CPU 的使用。

除了彩票调度的基本算法外，彩票调度还给出了一些基于彩票的优化方法，用与解决不同的问题。

• 彩票转让（ticket transfer）
• 彩票货币（ticket currency）
• 彩票通胀（ticket inflation）

步幅调度算法 #

步幅调度（stride scheduling）也是一种公平共享调度，相比彩票调度，它是以一种确定性的方式进行任务调度，核心概念就是步幅。

实时系统调度（RT） #

实时系统根据任务的完成度、周期性和决策阶段可以从不同的维度描述。

实时系统按照对截止时间的完成度可以分为硬实时（head real-time task）和软实时（soft real-time task），硬实时的含义是必须在截止时间前完成，否则系统无法承担任务超时的后果，比如车辆上的传感器信息必须在截止时间前完成，否则会有严重的安全隐患。软实时是可以偶尔超过截止时间，其结果是可以接受的，比如视频播放软件，偶尔的卡顿并不会有严重的后果。

实时系统中的事件可以按照响应方式进一步分为周期性事件或非周期事件，一个系统可能要响应多个周期性事件。而非周期任务指的就是随机任务，系统同一时刻可以处理多个相同的非周期事件，并且非周期任务通常都是软实时任务，比如用户的输入。

实时系统的调度算法可以是静态或动态的，前者在系统开始运行之前做出调度决策，后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时，静态调度才可以工作，而动态算法不需要这些限制。下面介绍属于静态优先级实时调度的速率单调策略和属于动态优先级实时调度的最早截止时间优先策略。

速率单调（RM） #

速率单调（Rate-Monotonic，RM）是一个用于调度周期任务的静态优先级实时调度策略。速率指的是任务到达率，它是任务周期的倒数，即 1/T 。该策略需要预知任务的周期 T，并且根据周期静态地为每个任务分配一个优先级，任务的周期越短，意味着其截止时间要求越迫切，则优先级越高。RM 还支持抢占调度，高优先级的任务可以抢占低优先级的任务执行。

最早截止时间优先（EDF） #

最早截止时间优先（Earliest Deadline First，EDF）会根据任务的截止时间动态分配任务优先级，任务的截止时间越近则优先级越高。在 EDF 策略中，调度器只需要知道任务的截止时间这一种信息，因此 EDF 策略的通用性较强。

通用调度策略 #

借用虚拟时间（BVT） #

多处理器系统调度 #

负载分担 #

负载分担（load sharing）会假设有一个全局共享的运行队列，当有 CPU 核心空闲时，就会从全局队列分担出一个任务进行执行。

负载分担虽然模型简单，但是它会带来多核心共同更新一个全局队列的同步问题，还有就是任务的切换可能导致下次运行时不在上次核心从而带来高速缓存失效问题。

协同调度 #

协同调度（coscheduling）策略尽可能让一组任务并行执行，避免处理器同时调度有依赖关系的两组任务，从而被动增加同步成本。协同调度比较适合并行计算（parallel computing）场景，即将任务切分为多个子任务并行执行的场景。

两级调度 #

由于负载分担的问题，两级调度（two-level scheduling）为每个 CPU 核心引入了一个本地调度器，并用它管理对应核心上执行的任务，这样有了全局调度器和本地调度器，形成了层级结构。全局调度器会在任务开始时根据系统当前情况分配给指定 CPU 核心，此后任务就会被 CPU 的本地调度器所管理，不会迁移到其他 CPU 核心上执行。

以 Linux 为代表的操作系统为每个CPU 核心分配一个本地运行队列，即可以理解为每个 CPU 核心有一个本地调度器。

负载均衡 #

由于两级调度在一开始就被绑定到特定的 CPU 核心上进行调度执行，避免了任务在多核间切换，不过也有可能会导致多核间的负载不平衡。于是两级调度又引入了负载均衡策略。

负载均衡的思想是，通过追踪每个 CPU 核心当前的负载情况，将处于高负债的 CPU 核心管理的任务迁移到低负载的 CPU 核心上，尽可能地保证每个核心的负载大致相同。

能耗感知调度（EAS） #

以 Linux 为例，Linux 的能耗感知策略（Energy Aware Scheduling，EAS）在 CFS 基础上进行了扩展。当一个任务从阻塞或睡眠状态被唤醒时，需要放入某一 CPU 核心的运行队列。在混合处理器架构中，任务被放在不同的 CPU 核心上带来的能耗开销是不同的，为了保证性能的同时达到最低的系统整体能耗，调度器通过 EAS 决定任务在哪个 CPU 核心上执行。

Linux 调度器 #

$O(n)$ 调度器 #

$O(n)$ 调度器是在内核 2.4 以及更早期版本采用的算法，$O(n)$ 代表的是寻找一个合适的任务的时间复杂度。调度器定义了一个 runqueue 的运行队列，将进程的状态变为 Running 的都会添加到此运行队列中，但是不管是实时进程，还是普通进程都会添加到这个运行队列中。当需要从运行队列中选择一个合适的任务时，就需要从队列的头遍历到尾部，这个时间复杂度是 $O(n)$，运行队列中的任务数目越大，调度器的效率就越低。

$O(1)$ 调度器 #

内核 2.6 采用了 $O(1)$ 调度器，让每个 CPU 维护一个自己的 runqueue，从而减少了锁的竞争。每一个runqueue 运行队列维护两个链表，一个是 active 链表，表示运行的进程都挂载 active 链表中；一个是 expired 链表，表示所有时间片用完的进程都挂载 expired 链表中。当 acitve 中无进程可运行时，说明系统中所有进程的时间片都已经耗光，这时候则只需要调整 active 和 expired 的指针即可。每个优先级数组包含 140 个优先级队列，也就是每个优先级对应一个队列，其中前 100 个对应实时进程，后 40 个对应普通进程。

完全公平调度器（CFS） #

完全公平调度器（Completely Fair Scheduler，CFS）调度器和前两种调度器不同之处在于没有固定时间片的概念，而是公平分配 CPU 使用的时间。调度器使用红黑树实现运行队列，跟踪进程的等待时间，对进程进行管理，算法效率为 $O(log(n))$。

处理器亲和性 #

当一个进程在一个多处理器系统上被重新调度时，如果原来运行的 CPU 处于忙碌状态，可以进行切换 CPU。进程切换 CPU 会对性能有一定影响，存在原来的 CPU 的 MMU 的 TLB 下的缓存数据就需要被删除（避免多核之间数据不一致）。Linux 系统提供了处理器亲和性（Processor affinity）的机制，在条件允许的情况下进程可以重新调度到原来的 CPU 上运行。

调度策略设置 #

有经验的开发者对自己程序属于哪一类任务会有清晰的认识，Linux 系统支持多种调度策略和调度器，支持开发者可以通过系统调用选择对应的任务策略。

在上面三种调度器中，Linux 会优先调度 DL 调度器管理的任务，其次是 RT 调度器管理的任务，只有当这前两种调度器的任务被执行完后，才会调度 CFS 调度器管理的任务。

GCD 调度器 #

苹果公司的 macOS 和 iOS 系统使用一种面向用户体验的调度器：GCD（Grand Central Dispatch）。GCD 使用了基于实时优先的调度策略以满足应用程序对时延的需求，同时调度的对象不再是内核中的线程，而是更轻量级的单元：纤程。

参考 #

https://mp.weixin.qq.com/s/pKdQu74Sl3PIaKyDlIEExg

https://www.scaler.com/topics/operating-system/scheduling-algorithms-in-os/

The Linux Kernel documentation

https://www.kernel.org/doc/html/latest/scheduler/index.html

https://blog.csdn.net/lianhunqianr1/article/details/119067477

深入 Linux 内核架构