• 本文是对进程调度的总体概述，下面是几篇详细介绍：

• Linux调度算法，见文章：https://www.daimajiaoliu.com/series/linux_kernel/479799196100404

  • Linux调度的实现，见文章：https://www.daimajiaoliu.com/series/linux_kernel/47981925e9003fe
  • 上下文切换、用户/内核抢占，见文章：https://www.daimajiaoliu.com/series/linux_kernel/48711012a90041c
  • 实时调度策略，见文章：https://www.daimajiaoliu.com/series/linux_kernel/485c4989f1003e8
  • 与调度相关的系统调用，见文章：https://www.daimajiaoliu.com/series/linux_kernel/4797a27e59003f8

一、进程调度概述

• 前面几篇文章讨论了进程，它在操作系统看来是程序的运行态表现形式。本文及后面几篇文章将讨论进程调度程序，它是

确保进程能有效工作的一个内核子系统

• 调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序（常常简称调度程序）可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。调度程序是像Linux这样的多任务操作系统的基础。只有通过调度程序的合理调度，系统资源才能最大限度地发挥作用，多进程才会有并发执行的效果
• 调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是，

只要有可以执行的进程，那么就总会有进程正在执行。但是只要系统中可运行的进程的数目比处理器的个数多，就注定某一给定时刻会有一些进程不能执行。这些进程在等待运行。在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作

二、多任务系统

• 多任务操作系统就是

能同时并发地交互执行多个进程的操作系统：

• **在单处理器机器上：**这会产生多个进程在同时运行的幻觉
  • **在多处理器机器上：**这会使多个进程在不同的处理机上真正用时、并行地运行
  • 无论在单处理器或者多处理器机器上，

多任务操作系统都能使多个进程处于堵塞或者睡眠状态，也就是说，实际上不被投入执行，直到工作确实就绪。这些任务尽管位于内存，但并不处于可运行状态。相反，这些进程利用内核阻塞自己，直到某一事件（键盘输入、网络数据、过一段时间等）发生。因此，现代Linux系统也许100进程在内存，但是只有一个处于可运行状态

• 多任务系统分类：

• 非抢占式多任务（cooperative multitasking）

  • 抢占式多任务（preemptive multitasking）。

非抢占式多任务

• 在非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。

• 进程主动挂起自己的操作称为让步（yielding)。理想情况下，进程通常做出让步，以便让每个可运行进 程享有足够的处理器时间

• 这种机制有很多缺点：

• 调度程序无法对每个进程该执行多长时间做出统一规定，所以进程独占的处理器时间可能超出用户的预料

  • 更糟的是，一个决不做出让步的悬挂进程就能使系统崩溃

• 幸运的是，近20年以来，绝大部分的操作系统的设计都采用了抢占式多任务——除了Mac OS 9（以及其前身）、还有Windows 3.1（以及其前身）这些出名且麻烦的异端以外。毫无疑问，Unix从一开始就采用的是抢先式的多任务

抢占式多任务

• 像所有Unix的变体和许多其他现代操作系统一样，

Linux提供了抢占式的多任务模式

• 在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程 能够得到执行机会。这个

强制的挂起动作就叫做抢占（preemption)

• 进程在被抢占之前能够运行的时间是预先设置好的，而且有一个专门的名字，

叫进程的时间片（timeslice)：

• 时间片实际上就是分配给每个可运行进程的处理器时间段
  • 有效管理时间片能使调度程序从系统全局的角度做出调度决定，这样做还可以避免个別进程独占系统资源
  • 当今众多现代操作系统对程序运行都采用了动态时间片计算的方式，并且引入了可配置的计算策略。 不过我们将看到，Linux独一无二的 “公平”调度程度本身并没有采取时间片来达到公平调度

三、Linux的进程调度

• 从1991年Linux的第1版到后来2.4内核系列，Linux调度程序都相当简陋，设计近乎原始。当然它很容易理解，但是它在众多可运行进程或者多处理器的环境下都难以胜任

O(1)调度程序

• 因为上面的原因，在Linux 2.5开发系列的内核中，调度程序做了大手术。开始采用了一种

叫做O(1)调度程序的新调度程序——它是因为其算法的行为而得名的

• O(1)：用的是大O表示法。简而言之，它是指不管输入有多大，调度程序都可以在恒定时间内完成工作
• 它解决了先前版本Linux调度程序的许多不足，

引入了许多强大的新特性和性能特征。这里主要要感谢
静态时间片算法和针对每一处理器的运行队列，它们帮助我们摆脱了先前调度程序设计上的限制

• O(1)调度器虽然在拥有数以十计（不是数以百计）的多处理器的环境下尚能表现出近乎完美的性能和可扩展性，但是时间证明该调度算法对于调度那些响应时间敏感的程序却有一些先天不足。这些程序我们称为交互进程——它无疑包括了所有需要用户交互的程序。正因为如此，

O(1)调度程序虽然对于大服务器的工作负载很理想，但是在有很多交互程序要运行的桌面系统上则表现不佳，因为其缺少交互进程

RSDL算法、CFS算法

• 因为O(1)在很多交互程序要运行的桌面系统上表现不佳。自2.6内核系统开发初期，开发人员为了提髙对交互程序的调度性能引入了新的进程调度算法。其中

最为著名的是“反转楼梯最后期限调度算法 (Rotating Staircase Deadline scheduler)”（RSDL)，该算法吸取了队列理论，将公平调度的概念引入了Linux调度程序

• 并且最终在2.6.23内核版本中替代了O(1)调度算法，它此刻

被称为“完全公平调度算法”，或者简称CFS

四、策略

• **策略决定调度程序在何时让什么进程运行。**调度器的策略往往就决定系统的整体印象，并且，好药负责优化使用处理器时间。无论从哪个方面来看，它都是至关重要的

I/O消耗型进程、处理器消耗型进程

• 进程可以被分为

I/O消耗型和处理器消耗型

• I/O消耗型：

• I/O消耗型指进程的大部分时间用来提交I/O请求或是等待I/O请求

  • 因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，因为它在等待更多的I/O请求时最后总会阻塞（这里所说的I/O是指任何类型的可阻塞资源，比如键盘输入，或者是网络I/O)
  • 举例来说，多数用户图形界面程序（GUI）都属于I/O密集型，即便它们从不读取或者写入磁盘，它们也会在多数时间里都在等待来自鼠标或者键盘的用户交互操作

• 处理器消耗型：

• 处理器耗费型进程把时间大多用在执行代码上

  • 除非被抢占，否则它们通常都一直不停地运行，因为它们没有太多的I/O需求。但是，因为它们不属于I/O驱动类型，所以从系统响应速度考虑，调度器不应该经常让它们运行。对于这类处理器消耗型的进程，调度策略往往是尽量降低它们的调度频率，而延长其运行时间
  • 处理器消耗型进程的极端例子就是无限循环地执行。更具代表性的例子是那些执行大量数学计算的程序，如sshkeygen或者MATLAB

• **当然，上面这种划分方法并非是绝对的。进程可以同时展示这两种行为：**比如，X Window服务器既是I/O 消耗型，也是处理器消耗型。还有些进程可以是I/O消耗型，但属于处理器消耗型活动的范围。其典型的例子就是字处理器，其通常坐以等待键盘输入，但在任一时刻可能又粘住处理器疯狂地进行拚写检査或者宏计算

• 调度策略通常要在两个矛盾的目标中间寻找平衡：

**进程响应迅速（ 应时间短）和最大系统利用率（高吞吐量）。**为了满足上述需求，调度程序通常采用一套非常复杂的算法来决定最值得运行的进程投入运行，但它往往并不保证低优先级进程会被公平对待：

• Unix系统的调度程序更倾向于I/O消耗型程序，以提供更好的程序响应速度

  • Linux为了保证交互式应用和桌面系统的性能，所以对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程。虽然如此，但在下面你会看到，调度程序也并未忽略处理器消耗型的进程

进程优先级

• 调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法：

• 通常做法是（其并未被Linux系统完全采用）优先级高的进程先运行，低的后运行

  • 相同优先级的进程按轮转方式进行调度（一个接一个，重复进行)
  • 在某些系统中，优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度

• Linux采用了两种不同的优先级范围：nice值、实时优先级

• nice值：

• 它的范围是从-20到+19，默认值为0

  • 越大的nice值意味着更低的优先级nice似乎意味着你对系统中的其他进程更“优待 ”。相比高的nice值（低优先级）的进程，低的nice值（高优先级） 进程可以获得更多的处理器时间
  • nice值是所有Unix系统中的标准化的概念——但不同的Unix系统由于调度算法不同，因为nice值的运用方式有所差异：

• 比如一些基于Unix的操作系统，如Mac OS X，进程的nice值代表分配给进程的时间片的绝对值
  * 而Linux系统中，nice值则代表时间片的比例。你可以通过ps -el命令查看系统中的进程列表，结果中标记N1的一列就是进程对应的nice值

• 实时优先级：

• 其值是可配置的，默认情况下它的变化范围是从0到99（包括0和99）

  • 与nice值意义相反，越高的实时优先级数值意味着进程优先级越高
  • 任何实时进程的优先级都高于普通的进程，也就是说

实时优先级和nice优先级处于互不相交的两个范畴。Linux实时优先级的实现参考了Unix相关标准——特别是POSIX.1b。大部分现代的Unix操作系统也都提供类似的机制。你可以通过下面的命令查看到你系统中的进程列表，以及它们对应的实时优先级（位于RTPRIO列下），其中如果有进程对应列显示“-”则说明它不是实时进程：

1
2
1ps -eo state,uid,pid,ppid,trprio,time,comm

2

时间片

• 时间片是一个数值，它

表明进程在被抢占前所能持续运行的时间（在其他系统中，时间片有时也称为量子（quantum）或处理器片（processor slice））

• 调度策略必须规定一个默认的时间片，但这并不是件简单的事：

• 时间片过长会导致系统对交互的响应表现欠佳，让人觉得系统无法并发执行应用程序

  • 时间片太短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短
  • 此外，**I/O消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来：**I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好（比如这样可以让它们的高速缓存命中率更高）

• 从上面的争论中可以看出，任何长时间片都将导致系统交互表现欠佳：

• ​​​​​​​很多操作系统中都特別重视这一点，所以默认的时间片很短，如10ms

  • 但是Linux的CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。这样一来，进程所获得的处理器时间其实是和系统负载密切相关的。这个比例进一步还会受进程nice值的影响，nice值作为权重将调整进程所使用的处理器时间使用比。具有更高nice值（更低优先权）的进程将予予低权重，从而丧失一小部分的处理器使用比：而具有更小nice值（更高优先级）的进程则会被赋予高权重，从而抢得更多的处理器使用比

• 总结：

• ​​​​​​​像前面所说的，

Linux系统是抢占式的。当一个进程进入可运行态，它就被准许投入运行
* 在多数操作系统中，是否要将一个进程立刻投入运行（也就是抢占当前进程），是完全由进程优先级和是否有时间片决定的。
而在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。否则，将推迟其运行

调度策略的活动

• 想象下面这样一个系统，它拥有两个可运行的进程：

一个文字编辑程序和一个视频编码程序

• **文字编辑程序显然是I/O消耗型的，**因为它大部分时间都在等待用户的键盘输入（无论用户的输入速度有多快，都不可能赶上处理的速度）。用户总是希望按下键系统就能马上响应
  • 相反，视频编码程序是处理器消耗型的。除了最开始从磁盘上读出原始数据流和最后把处理好的视频输出外，程序所有的时间都用来对原始数据进行视频编码，处理器很轻易地被100%使用。它对什么时候开始运行没有太严格的要求——用户几乎分辨不出也并不关心它到底是立刻就运行还是半秒钟以后才开始的。当然，它完成得越早越好，至于所花时间并不是我们关注的主要问题
• 在这样的场景中，理想情况是调度器应该给予文本编辑程序相比视频编码程序更多的处理器时间，

因为它属于交互式应用。对文本编辑器而言，我们有两个目标：

• **第一是我们希望系统给它更多的处理器时间，**这并非因为它需要更多的处理器时间（其实它不需要），是因为我们希望在它需要时总是能得到处理器
  • 第二是我们希望文本编辑器能在其被唤醒时（也就是当用户打字时）抢占视频解码程序。这样才能确保文本编辑器具有很好的交互性能，以便能响应用户输入
  • 在多数操作系统中，上述目标的达成是要依靠系统分配给文本编辑器比视频解码程序更高的优先级和更多的时间片。先进的操作系统可以自动发现文本编辑器是交互性程序，从而自动地完成上述分配动作。Linux操作系统同样需要追求上述目标，但是它采用不同方法。它不再通过给文本编辑器分配给定的优先级和时间片，而是分配一个给定的处理器使用比。假如文本编辑器和视频解码程序是仅有的两个运行进程，并且又具有同样的nice值，那么处理器的使用比将都是50%——它们平分了处理器时间。但因为文本编辑器将更多的时间用于等待用户输入，因此它肯定不会用到处理器的50%。同时，视频解码程序无疑将能有机会用到超过50%的处理器时间，以便它能更快速地完成解码任务
• 这里关键的问题是，当文本编辑器程序被唤醒时将发生什么。

**我们首要目标是确保其能在用户输入发生时立刻运行。**在上述场景中，一旦文本编辑器被唤醒，CFS注意到给它的处理器使用比是50%，但是其实它却用得少之又少。特别是，CFS发现文本编辑器比视频解码器运行的时间短得多。这种情况下，为了兑现让所有进程能公平分享处理器的承诺，它会立刻抢占视频解码程 序，让文本编辑器投入运行。文本编辑器运行后，立即处理了用户的击键输入后，又一次进入睡眠等待用户下一次输入。因为文本编辑器并没有消费掉承诺给它的50%处理器使用比，因此情况依旧，CFS总是会毫不犹豫地让文本编辑器在需要时被投入运行，而让视频处理程序只能在剩 下的时刻运行