配套教材：
Operating Systems: Three Easy Pieces Remzi H. Arpaci-Dusseau Andrea C. Arpaci-Dusseau Peter Reiher
参考书目：
1、计算机操作系统（第4版） 汤小丹 梁红兵 哲凤屏 汤子瀛 编著 西安电子科技大学出版社

在线阅读：
http://pages.cs.wisc.edu/~remzi/OSTEP/
University of Wisconsin Madison 教授 Remzi Arpaci-Dusseau 认为课本应该是免费的。
————————————————————————————————————————
这是专业必修课《操作系统原理》的复习指引。
需要掌握的概念在文档中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
文档下载地址：
链接：https://pan.baidu.com/s/1yf4TPKPGvMfmQshWKLlG2g
提取码：0000

三 高级调度策略

虽然这些假设显得不真实，但是为了方便，在接下来的对高级调度策略（区别于定时器中断、上下文切换等底层机制）的讨论中，我们暂时假定所有进程（任务）都遵循完全可操作的调度规则，本指导简称“五个假设”：
（1）所有的任务都运行相同时间；
（2）所有的任务都同时分发下来；
（3）一旦开始运行，所有任务都一直运行到完成；
（4）所有任务只使用CPU（也就是说，没有IO）；
（5）所有任务需要的运行时间都是已知的。
在必要情形下，可能解除上面的一条或几条限制。
高级调度策略与底层调度机制是相对独立的：机制与策略分离的基本原理，是计算机科学与工程中的常用原理。

性能和公平性在调度中一般是矛盾的。如果一个调度器的调度规则偏向性能，那么可能会导致一些程序几乎分不到多少时间执行。如果优先保证每个程序都尽可能分到足够的时间执行，那么程序的性能有时并不能完全发挥出来。

FIFO（First in first out，先进先出）也称先来先服务（first come first serve，FCFS），是最基础的一种调度算法。这个算法简单且易于实现。在“五个假设”下，该方法的效果一般较好；但是在一些特殊情形下效果不佳。例如，如果每项任务的耗时不再是等时的，其中某项任务的耗时远大于其它任务，且比其它任务都早那么一点到达。那么，直到把这项最耗时的任务执行完毕以后，操作系统才会分配其它任务到这个处理器核。当任务的结束时间是影响效果或评价等指标的主要因素时，这种调度方式带来的结果就令人不满。
生活中有很多这样的情境。例如：如果一个末日生存狂为了应对核冬天而到超市大量扫货，那么假设因为他比别人先到一小会儿就开始忙于对他的结算，后面的许多个只需要买一点东西准备明天的早餐的顾客就会等待很久。再例如：你的计算机硬盘损坏，现从某网盘紧急下载备份文件。但由于网站技术故障，你无法开通它的会员，所以被限制一次只能下载一个文件。如果先下载最先添加的很大的文件（如：刚立项的为期两年的科研项目的神经网络训练模型），那么急用的小文件（如：即将到达提交截止期限的未完成的实验报告）也需要等到大文件下载完毕后才开始下载。这样做的后果可想而知。

SJF（Shortest Job First，最短作业优先）算法总是优先安排耗时最少的任务先行执行。在要求每个任务都尽早结束的情形下，如果任务都是同时到达的，那么SJF调度算法比FIFO调度算法能让更多任务尽快执行完毕。但是，还是套用刚才的例外：某项任务的耗时远大于其它任务，且比其它任务都早那么一点到达。在这个情形下，仍然需要等待耗时最长的任务完成后才能开始执行其它任务，对最终结果也是不利的。

非抢占（non-preemptive）调度一旦把CPU分配给某进程后，就一直让它运行下去，不会因为时钟中断或任何其它原因去抢占当前正在运行的进程占用的CPU，直至该进程完成。当该进程发生某事件而阻塞时，才把CPU分配给其它进程。而抢占（preemptive）调度允许调度程序根据某种原则，暂停正在执行的进程，将己分配给的CPU重新分配给另一进程。事实上所有的现代调度器都是抢占式的：这可以防止一个长进程长时间占用CPU，以确保CPU能为所有进程提供更为公平的服务。在分时系统中，只有采用抢占方式才有可能实现人机交互。在实时系统（Real-time System，见附录）中，抢占方式能满足实时任务的需求。但抢占方式比较复杂，所需开销也较大。
抢占不是任意的行为，必须遵循一定的原则。常用的原则有：
【1】优先权原则。有新进程到达时，如果它的优先级比当前进程的优先级高，则调度程序剥夺当前进程的运行，将CPU分配给新到的优先权高的进程。
【2】短进程优先原则。当新到达的进程比正在执行的进程（尚须运行的时间）明显短时，将CPU分配给新进程。
【3】时间片原则。即各进程按时间片（time slice）轮转运行，当前进程的一个时间片用完后，暂停该进程并调度其它进程。

STCF（Shortest Time-to-Completion First，最短距离完成时间优先）算法总是优先安排距离完成时间最少的任务先行执行。目前，底层机制总是会让CPU在很短的时间内通过上下文切换来迅速切换到另一个任务运行，所以在这里我们取消“五个假设”的第3条，即一个任务开始后不一定要一直运行到结束。于是，当耗时最长的任务到来并开始运行后不久，如果又有耗时较短的新任务到来，那么假如新来的任务距离其完成的时间比当前任务更短，操作系统就会令CPU开始运行新来的任务。这就解决了前两个调度策略不能解决的问题。也就是说，STCF是SJF的抢占式版本（PSJF）。
一个宏观层面的例子：在BOINC和Folding@home等分布式计算平台中，只有正确计算出结果并成功提交任务，才可以获得相应的点数。不正确的任务安排可能导致所有任务都不可以在截止期限之前成功提交。

但很多时候我们需要程序及时给出回应。如果CPU的所有核心都在执行任务，那么整台计算机就是无响应的状态。Round-Robin（RR，循环）调度法也称时间片轮转（time-slicing）算法，按照时间片来进行轮转调度，一个时间片结束就把当前的任务暂停，继续另一个任务。时间片的长度必须是定时器中断的间隔的整数倍。在切换任务的过程，计算机可以响应。但是切换任务是需要消耗时间的。进行上下文切换并不只是保存或恢复寄存器数据那么简单，各级缓存和TLB（见第5章）、分支预测器和其它片上硬件（on-chip hardware）都要进行相应的改动。过于频繁的任务切换，会导致大量的CPU时间消耗在任务调度本身，显然是不经济的。但如果任务切换频率较低，计算机就会在相当长的时间内无响应。不过RR调度策略是公平的，因为它总是平均分配CPU时间到各个任务。然而，对于只有完成任务才能获得收益的场景，RR算法甚至比FIFO的表现还要差得多。总之，哪个调度策略更优，需要结合具体情境具体分析。
因为切换一次任务的时间已经非常短，所以在讨论何种调度算法最优时，一般忽略上下文切换的时间。

事实上，大量程序需要频繁进行I / O，我们一般也无法得知程序需要运行多少时间。下面暂时取消“五个假设”的（4）和（5），然后继续分析讨论。
当程序请求IO时，调度器一般都要将其阻塞，然后等待I / O完成。举例来说，尝试从磁盘读取数据时，程序在等待磁盘将相应数据读取完毕并传回期间不应该继续执行，而应该暂停。此时，调度器一般选择其它任务去执行。
怎样选择调度策略呢？设有A、B两个任务，它们各需要50 ms 的CPU时间。但A每隔10 ms要进行一次10 ms的I / O，而B纯粹只需要在CPU上老老实实运行50 ms。若采用STCF调度方案，且调度器最终根据其调度策略选择先执行A，那么A一共要请求4次I / O，实际花费了90 ms的时间执行完毕，然后再用50 ms执行B，总耗时140 ms。而如果每10 ms 切换一次任务，那么在A请求IO时，调度器就安排B执行，于是由于CPU被更充分地利用，执行的总时间是100 ms。

“五个假设”的最后一条应该是最糟糕的假设了。通用目的的操作系统中，一个应用程序的运行时间几乎是无法提前得知的（某些嵌入式系统通常只运行为数不多的特定任务，它们的执行耗时较容易预测）。在没有先验信息的情形下，怎样进行尽可能优的调度呢？

Fernando J. Corbató等发明了最著名的调度算法之一：多级反馈队列（Multi-level Feedback Queue，MLFQ）算法。国际计算机协会（ACM）授予Corbató图灵奖（Turing Award）。除了任务调度，该算法还在分支预测、缓存算法等方面具有广泛应用。MLFQ算法是一种抢占式调度算法。目前有许多该算法的改进版本，但它们大致上相同。

MLFQ算法的两条基本规则是：对两个任务A、B，
（1）如果A的优先级更高，则运行A，暂停B。
（2）如果优先级相同，则A、B轮流运行。
MLFQ算法根据进程的行为来决定其优先级。对常常等待输入的I / O密集型程序，那么MLFQ保持其有一个较高的优先级。对CPU密集型程序，MLFQ降低其优先级。并且，只有当更高优先级的队列为空时，才选择更低优先级队列中的任务执行。

但如果只有这两条规则，那么如果有的任务的优先级远远低于其它任务，则意味着它们几乎不会被分配到运行时间。这种调度方案显然是不公平的。下面我们补充几条规则：
（3）当系统接到新的任务时，该任务总被赋予最高优先级。
（4a）如果一个任务耗尽了单个时间片，就降一级优先级。
（4b）如果一个任务在某个时间片到来时放弃使用CPU（如：等待输入），则保持优先级不变。
规则（3）说明了MLFQ是如何具体应用SJF规则的。我们一般不知道一个任务多久才结束，那么新来的任务总是按照比现有任务更短的任务处理。如果这个任务确实持续时间很短以至于不会掉到最低优先级的队列中去，那么它很快就会结束；如果它的优先级跌到了最低，那么就会与最低优先级的队列中已有的任务轮流运转。从这个角度来说，MLFQ接近SJF。
规则（4b）显示了MLFQ处理I / O密集型任务的方式。如果一个任务I / O频繁且需要大量与用户的交互，那么它总是会在用完时间片之前先放弃时间片，即放弃CPU，因此不应对其施加优先级的惩罚。

即便有了新添加的规则，这样的MLFQ算法还会存在很多漏洞。如果有大量的IO密集型任务运行在系统中，那么计算密集型任务几乎没有办法得到CPU时间。此外程序员们可以修改自己的程序，在时间片结束之前发起一次很短时间的IO，从而保持优先级不掉落。只要控制得当，单个进程可以垄断接近全部的CPU时间。一个任务几乎无法获得CPU时间继续执行，这种现象称为饥饿（starvation）。
此外，IO密集型任务也不是在所有时候都会请求大量IO的。当一个IO型任务开始了一段长期使用CPU的计算后，其优先级将会逐渐滑落。但当其优先级已经降到很低时，如果再需要发起大量IO，那么操作系统也许就无法让其获得与其它IO密集型程序相仿的优先级了。

无论是设计OS的调度器，还是设计其它类型的调度程序（例如分布式存储系统中的IO处理程序），都需要考虑恶意攻击。现代的大型数据中心（DC）中，世界各地的用户都会一同使用数据中心的资源，这时候就难免有恶意用户抢占其它用户的资源。

对MLFQ算法补充规则：
（5）经过一定时间，把所有任务的优先级都提到最高。
这条规则确保所有进程都不会饥饿。但这个间隔要设置合适。如果间隔太长，计算密集型任务就会饥饿；如果间隔太短，I / O密集型任务可能就无法获得足够的CPU时间。
把规则4a和4b改成一条：
（4）如果一个任务开始使用新的时间片（无论之前已经放弃了多少CPU时间），其优先级降一级。

这样处理可以防止某些任务通过请求不必要的IO来维持优先级。

MLFQ算法包含许多必要的参数。例如要设置多少队列（不同队列的优先级不同），时间片要多宽，经过多少时间要强制提升所有任务的优先级。
很多MLFQ算法的变体给不同优先级的任务分配不同的时间片长度：高优先级任务的时间片更短。Solaris系统的MLFQ改进算法默认有60个队列，时间片从20 ms到几百ms不等，每隔1 s强制提升全部任务到最高优先级。系统管理员可以更改调度器的参数。FreeBSD的调度器则根据进程已使用多少CPU，通过数学公式计算其优先级。此外，如果进程持续不占用或少占用CPU，由于（平均）使用率随时间流逝而衰减，FreeBSD的调度器会逐渐提升其优先级。

很多调度器还有额外的特性。例如，最高优先级总是分配给操作系统，用户进程一般不允许获得最高优先级；有的调度器还参考用户设置的值来调度任务。除调度器以外，内存管理器和文件系统都会参考用户设置。

Jean-Loup Waldspurger和William E. Weihl发明了彩票调度（lottery scheduling）算法。每个进程持有不同的票数。调度器生成一个随机序列，每隔一个时间片选择随机序列的下一个数字，持有这张票的进程获得CPU时间。通过票数多少决定得到资源的比例，这样的思想也可以应用于其它资源的分配。

在调度算法中使用随机数有诸多优点：一是能避免在最坏情况中获得与传统算法相仿的最坏结果；二是速度快、负载轻：传统的算法为了保障CPU时间分配的公平，需要追踪每个进程的各种信息；而随即决定得到下一个时间片的进程就可以免去这些工作。一般而言，如果要求随机算法很快，则随机数就越不接近真正意义上的随机性；不过，优秀的随机数算法的速率也可以非常快。

彩票调度还有很多机制。譬如说，彩票汇率机制允许用户将自己拥有的票数再分成更多的票或合并为更少的票，再分配给属于该用户的进程。当需要时，系统会将用户的总票数换算成全局的总票数。举例：用户A和B各有100张票，A把100张彩票细分为1000张，分给任务A1、A2各500张；B把10张票合并为1张，兑换的10张新票全部分给任务B1。
彩票转移机制则允许一个进程临时把票转让给另一个进程。这在客户端 / 服务器（Client-server，C-S）结构中很有用：客户端提交一定的票数给服务器，让服务器加快处理自己的请求。处理完毕后，服务器将收到的票给回客户端。
通胀机制有时也很有用。通胀机制允许进程临时增加或减少自己的票数。当一个进程需要更多CPU时间时，就通过增加自己的票数来影响系统对其分配的时间片数量。如果想防止一个进程过度抢占资源，那么系统就需要增加总票数，使单张票对获得CPU时间的影响减小。

Waldspurger还发明了步幅调度（stride scheduling）算法。每个任务都有一个步幅，但票数最多的步幅最少。例如，任务A、B、C分别有100、50、250票。用它们去除一个大数10000（可以是其它数），分别得到100、200、40。当每个进程运行了一个时间片，累计步幅（pass value）就增加相应的步幅。初始时，所有进程的累计步幅都是0。每次选一个累计步幅最小的进程运行。如果有多个进程的累计步幅相同，则任选一个进程分配时间片。

彩票调度有时候可能随机分配了多得多的时间片给票数偏少的某个进程，而步幅调度算法则不会出现此情况：在整数个调度周期后，所有进程都累计得到了相同数量的时间片。但如果新建了进程，这个进程的累计步幅应该是多少？0显然是不合适的，因为这会导致这个进程一直运行，从而霸占整个CPU直到其累计步幅不是最小。而运行一段时间后创建的新进程在彩票调度算法下可以一视同仁。

彩票调度和步幅调度虽然都比较容易实现公平调度，但是，因为这两种方式都无法出色的应对进程发起IO的情况，而且很难确定具体的进程（比如浏览器）应当获得多少票数，所以这两个调度策略并没有作为CPU调度策略广泛使用。MLFQ和Linux调度器等通用的调度程序在这些方面表现更好。
类似这样的按比例分配CPU时间的调度器更适合特定的领域。例如，在虚拟化的环境下，某台安装了Linux系统的计算机运行着Windows虚拟机。你可能会希望分配1/4的CPU周期给虚拟机，剩余的全部交给Linux系统。这种简单而直接的分配方式此时更加高效。

当前的Linux系统采用完全公平调度器（Completely Fair Scheduler，CFS）调度非实时任务，力求兼顾调度的公平性、高效性和缩放性（scalability）。对Google数据中心的一份研究表明，即便采用激进的优化策略，调度器消耗的CPU仍然占到整个数据中心的5 %。降低调度器本身的CPU占用率已经成为现代调度器的首要目标。这里只对CFS作简要介绍。

每个进程或线程（见第7章）运行时，虚拟运行时间（virtual runtime，vruntime）就各自累积起来。一般而言，所有进程的vruntime增量与物理意义上的时间流逝成比例。当决定切换任务时，CFS总是选择vruntime累积最少的任务。每个进程的vrumtime是由如下公式累计的：

v_i+=w_default/w_i r_i
v_i是进程i的vruntime值，w_default是默认权重，由nice值（见下文）决定，w_i为进程i的权重，而r_i是进程实际已经运行的时间。可见，对于默认优先级的任务，每次累积的虚拟运行时间与对应的实际运行时间是相同的。

CFS的一个参数——调度延迟（sched_latency）的典型值是48 ms，用于控制两次上下文切换的时间间隔。CFS通过这个值来动态决定时间片。当有多个进程运行时，这个值会被除以进程数，但一般不低于最细粒度min_granularity（通常为6 ms）。
CFS的正常运行依赖定时器中断。两个定时器中断的间隔（例如：1 ms）远小于两次上下文切换的间隔。
CFS也会根据进程优先级来调度。系统管理员有权更改进程优先级，用户也可以被授权更改。但按优先级调度的实现不是依赖票数，而是依赖UNIX的经典机制：nice值。其范围从–20到+19，默认为0。nice值越小，优先级越高。如果一个进程太nice了，意味着它不获得调度器的过多注意。也可以理解为：当一个任务增加了它的nice，说明它的优先级降低了，进而对其它任务变得nice。
nice值会被转换为权重。两者的关系定义在/kernel/sched/core.c中：

const int sched_prio_to_weight[40] = {
/* -20 / 88761, 71755, 56483, 46273, 36291,
/ -15 / 29154, 23254, 18705, 14949, 11916,
/ -10 / 9548, 7620, 6100, 4904, 3906,
/ -5 / 3121, 2501, 1991, 1586, 1277,
/ 0 / 1024, 820, 655, 526, 423,
/ 5 / 335, 272, 215, 172, 137,
/ 10 / 110, 87, 70, 56, 45,
/ 15 */ 36, 29, 23, 18, 15,
};
每个nice值都是后一个nice值的大约1.25倍。如果两个进程的nice值不同，但是比值相同，那么无论它们的nice值具体为多少，也不影响它们获得的CPU时间的相对关系。
进程k获得的时间片是按下述公式确定的：
t_k=w_k/(∑_(i=0)^(n-1)▒w_i ) l_s
t_k为进程k时间片长度，w_k为进程k按照sched_prio_to_weight[40]转换得到的等效权重，l_s为当前的调度延迟。
Linux从2.6.24版本的内核开始，引入了组调度的概念。同一个组的进程会同等对待，增强公平性。这个特性非常适用于会产生许多子任务的任务。
2.6.37版内核开始，实时进程不再像旧版本内核那样计算权重（旧版本内核设法保持其优先级较高）。实时任务和一般任务的优先级范围是不同的：-20 ~ +19的nice值映射到优先级100 ~ 139，值越小优先级越大；而实时任务的优先级范围为0 ~ 99，值越大优先级越大。与一般的任务相比，实时任务具有更高的优先级。实时调度主要采用FIFO或RR策略。

CFS采用红黑树（R-B Tree）来维护活动进程的相关信息。vruntime最少的进程排在红黑树的最左边。当进程休眠（阻塞）时，进程会被移出红黑树，用其它方式追踪。红黑树是常用的平衡树之一。用红黑树代替链表，其插入、删除、查找、修改的平均和最坏时间复杂度均为O(log⁡n )；相比之下，链表的的增删改查的平均和最坏时间复杂度都达到O(n)，普通二叉排序树的最坏时间复杂度也会达到O(n)。n较大时，对数和线性时间复杂度的效率差别就十分明显了。
相较AVL树而言，红黑树不是严格平衡的。但这个特性减少了树节点的旋转次数。因此当插入、删除操作非常频繁时，用红黑树来代替AVL树可以降低总体的时间复杂度（减小常数）。如果查找的次数远多于增删，则AVL树的时间复杂度具有更小的常数。
为了防止长时间休眠的进程在被唤醒后因为虚拟运行时间最少而霸占CPU，CFS会将每一个刚唤醒的进程的vruntime设为红黑树中最小的该值。这个办法避免了进程的饥饿，但并不是毫无代价的：频繁休眠并唤醒的进程会分到更少的CPU。
CFS还有很多启发式（heuristic）方法，能够很好地处理在多核CPU上调度的问题，而且可以改进缓存性能。此外，在进程数量非常庞大的时候，CFS也表现不错。

优先级倒置（priority inversion），指的是高优先级进程或线程被低优先级进程（或线程）延迟或阻塞的情况。当有程序进入临界区（见第7章）时，可能会发生此情形。很多时候，优先级倒置的持续时间是无法预计的。在实时系统中，这会产生非常严重的灾难。
一种能够减少优先级倒置的持续时间的办法是：一旦有进程进入临界区，就不允许其它进程再抢占CPU。这可以使得进入临界区的进程尽快退出临界区。当然，如果进程的临界区比较长，这个方法就不太管用了，因为高优先级进程仍然会等待很长时间。
一个比较实用的办法是动态优先级继承：假如有优先级较低的进程P进入了临界区，当优先级较高的进程Q也准备进入该临界区时，令优先级较低的进程P获得与Q相同的优先级。于是，其它优先级不高于Q的优先级的进程就无法再被优先调度，导致延迟退出临界区的时间。该方法已经在一些操作系统中应用。