进程调度

进程调度程序是确保进程能有效工作的一个内核子系统，它负责决定：

哪个进程可以投入运行；
进程何时运行；
进程可以运行的时长；

可以将它看作在可运行态进程之间分配有限的处理器时间资源的内核子系统，这是多任务操作系统的基础。对进程的合理调度使得系统资源最大限度地发挥作用，多进程才会有并发执行的效果。

只要有可以执行的进程，那么就总会有进程在执行。但只要系统中可运行的进程数目比处理器个数多，就注定在某一时刻一部分进程不能执行。可以说，调度程序的基本工作就是：在一组处于可运行状态的进程中选择一个来执行。

多任务

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

多任务操作系统可以分为两类：

非抢占式多任务 cooperative multitasking：除非进程自己主动停止运行，否则它会一直执行。这个主动挂起自己的动作叫做让步(yielding)。当调度程序无法主导每个进程的运行时长时，麻烦就会增多。
抢占式多任务 preemptive multitasking：由调度程序决定何时停止一个进程的运行，以便其他进程能够得到执行的机会，这个强制将当前执行进程挂起的动作叫做抢占(preemption)。进程的时间片(timeslice)是进程在被抢占前能够运行的时间。有效合理地管理时间片使得调度程序从系统全局的角度做出调度决定。

Linux的进程调度

自 Linux 2.5 内核后，引入了一种叫做 O(1) 调度程序的新机制，从名字就知道这是一个效率很高的调度机制。其中使用了两个主要方法：

静态时间片算法
每一处理器新建单独的运行队列

该算法在调度那些对响应时间很敏感的程序有一些先天不足，例如对用户交互进程。在 2.6.23 中，引入了著名的“反转楼梯最后期限调度算法”(Rotaing Staircase Deadline scheduler, RSDL)，它汲取了队列理论，引入了公平调度的概念，所以也被称为“完全公平调度算法” (CFS)。

策略

策略决定调度程序在何时让何种程序运行，它是调度进程和优化使用处理器的核心。

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

从设备占用进程主要执行时间的角度看，进程可以分为：

I/O 消耗型进程

大部分时间用来提交 I/O 请求或是等待 I/O 请求，因而常处于可运行状态，但执行时间较短。比如，大多数用户图形界面程序(GUI)都属于 I/O 密集型程序，所以它们在执行时，属于 I/O 消耗型进程。
处理器消耗型进程

大部分时间用来执行代码上。从系统响应速度上考虑，不该让这样的进程常常运行，因此调度器会尽量减少调度这类程序的频率。例如，极端的有 while(true) 循死环，或者是 sshkeygen 和 MATLAB 这类需要执行大量数学计算的程序。

一个进程不是非A即B的，许多程序即是 I/O 消耗型程序，又是处理器消耗型程序。所以，调度策略通常需要在二者之间寻找平衡，即：在进程响应速度和最大系统利用率上寻找最优平衡解。

进程优先级

基于优先级的调度是调度策略中最基本的一类，它根据进程的价值和对处理器时间的需求对进程进行分级。通常做法是：

优先级高的进程先运行，优先级低的后运行；
相同优先级的进程按轮转方式运行；

Linux 采用了两种优先级范围：

nice 值：是默认为 0，范围在 -20~19 之间的数值。越低代表优先级越高，反之则反。低 nice 值的进程可以获得更多的处理器时间。可以通过 ps-el 来查看进程列表，其中 NI 列即为进程的 nice 值。基于 Unix 的不同的操作系统对 nice 值的运用方式不同，例如：
- Mac OS X 中的 nice 值表示分配给进程的时间片的绝对值；
- Linux 中的 nice 值表示分配给进程的时间片的比例；
可配置的实时优先级：默认变化范围为 0~99 ，数值越高代表优先级越高。任何实时进程的优先级都高于普通进程，实时优先级与 nice 值属于两个互不相交的范畴。使用 ps-eo state,uid,pid,ppid,rtprio,time,comm 来查看进程列表，实时优先级为 RTPRIO 列表，如果显示为 - ，则说明它不是实时进程。

时间片

时间片(timeslice) 是一个数值，表示进程被抢占前所能持续运行的时间。调度策略必须为时间片设置默认值，但这不是一个简单的事情，正如先前提到的 I/O 消耗型进程和处理器消耗型进程所涉及的矛盾。默认的时间片是 10 ms，Linux 的 CFS 调度器没有直接给进程分配时间片数值，而是将处理器的使用比例划分给进程，这个比例还影响进程的 nice 值因此，进程所获得的处理器使用时间与系统负载时密切相关的。

在一般的操作系统里，进程是否立刻投入运行取决于：

进程的优先级
是否有时间片

而在 Linux 的 CSF 调度器中，抢占时机取决于：

消耗的处理器使用比例（消耗使用比例更小，则立刻投入运行，否则推迟运行）

调度策略的活动

假设有两个可运行的进程：

文字编辑程序（I/O 消耗型）
视频编码程序（处理器消耗型）

理想情况下应当这样处理：

给予文本编辑程序更多处理器时间
希望文本编辑程序在被唤醒时能够抢占视频解码程序

这样用户才能得到使用交互式程序时带来的好的体验。这也意味着需要给文本编辑程序分配更高的优先级和时间片。

但 Linux 分配一个给定的处理器使用比。如果仅有这两个进程在运行，且它们具有相同的 nice 值，则处理器使用比都将分配为 50% 。但由于交互式程序需要更多时间等待输入，因此肯定不会用到处理器 50% 的使用时间，而类似于视频编码程序这类处理器消耗型进程就有机会使用超过 50% 的处理器使用时间，以便更快完成任务。

CFS 调度器能够发现，文本编辑程序并没有消费掉承诺给它的50%的处理器使用比，因此在文本编辑程序需要被投入运行时，让其进行抢占动作。

Linux调度算法

进一步深入了解Linux特色的进程调度。

调度器类

Linux调度器时以模块方式提供的，这种模块化结构被称为调度器类 (scheduler classes)，目的是允许不同类型的进程可以针对性地选择调度算法。

每个调度器都有一个优先级，基础的调度器代码定义在 kernel/sched.c 中，它按照优先级顺序遍历调度类，拥有可执行进程的最高优先级的调度类将胜出，去选择下面要执行的那一个程序。

完全公平调度 (CFS) 是针对普通进程的调度类，在 Linux 中被称为 SCHED_NORMAL ，CFS 算法的实现在 kernel/sched_fair.c 中。

Unix 系统中的进程调度

先前说到现代进程调度其通用的两个概念：1. 进程优先级；2. 时间片。由进程的优先级影响时间片的大小，即影响进程执行的时间长短。在 Unix 系统中以 nice 值来表示进程优先级。但是由 nice 值映射到时间片的简单方式会带来很多问题：

【问题一】nice 单位值对应到处理器绝对时间。在这里，假设默认时间片单位为 100ms。那么：
- 【情况一】当存在两个 nice 值分别为 0 （默认优先级）和 +19 （最低优先级）的两个进程，它们将分别占用处理器时间 100ms 和 5ms。假设理想条件下，系统中仅有这两个进程待运行时，那么它们分别占用 20/21 (100ms/105ms) 和 1/21 (5ms/105ms) 的处理器执行时间。内核将在 105ms 内进行两次上下文切换。
- 【情况二】当存在两个 nice 值都为 +19 （最低优先级）的进程，它们都占用处理器执行时间 5ms 。在理想条件下，系统中仅有这两个进程待运行时，它们每次仅能获得 5ms 的处理器执行时间，且在 10ms 内，处理器需要进行两次上下文切换。
- 【情况三】当存在两个 nice 值都为 0 （默认优先级）的普通进程，它们都占用处理器执行时间 100ms 。在理想条件下，系统中仅有这两个进程待运行时，它们每次各获得 100ms 的处理器执行时间，在 200ms 内，处理器进行两次上下文切换。
在事实上：
- 给定高 nice 值（低优先级）的进程多是计算密集型进程，它们可能需要较长的处理器执行时间；
- 给定默认 nice 值（默认优先级）的进程多是前台用户任务，它们往往要求抢占（响应速度）而不要求较长的处理器执行时间（系统利用率）。
【问题二】体现为相对 nice 值表现的处理器执行时间的不公平，以 O(1) 调度算法为例：
- 【情况一】当存在两个 nice 值分别为 0 和 +1 的两个进程，它们分别占用的处理器执行时间为 100ms 和 95ms，相差仅5ms`。
- 【情况二】当存在两个 nice 值分别为 +18 和 +19 的两个进程，它们分别占用的处理器执行时间为 10ms 和 5ms ，相差了整整一倍。
可以通过几何增加/减小而非算数增加/减小来解决这个问题。
【问题三】绝对时间片必须能在内核的测试范围内，这要求绝对时间片必须是定时器节拍的整数倍，也就是 10ms 或者 1ms 的倍数（关于定时器需要参考第11章）。引入 CFS 就是为了解决时间片跟随系统定时器变化而变化的问题。如果绝对时间片跟随定时器变化，那相邻优先级的进程所获得的处理器执行时间相隔可多至 10ms ，少至 1ms 。可以通过引入新的度量机制来解决这个问题。
【问题四】基于优先级的调度器为了优化交互任务而唤醒相关进程的手段导致的不公平。为了让交互进程能更快投入运行，系统可能会提升该进程的优先级，即使它们的时间片已经用尽。这个机制会给一些特殊的交互用例玩弄调度器的后门，导致对其他进程不公平。

即使上述问题能够通过一些非结构性的改动来解决，但是这样的调度算法没有看到根本问题：需要一个与处理器执行时间直接挂钩的调度机制。于是 CFS 应运而生：它摒弃时间片分配机制，而直接分配给进程一个处理器使用比重，从而确保了进程调度能由恒定的公平性。

CFS 公平调度

CFS 允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程。它不依靠 nice 值来计算运行时长，而是从总数进程上计算出一个进程应该运行多久。但 CFS 没有摒弃 nice 值，而是将它用作进程获得处理器运行比的权重。

每个进程按照其权重在全部可运行进程中所占的比例来运行。为了计算准确的运行时间，CFS 为完美多任务中的无限小的调度周期的近似值设立了一个目标，称为“目标延迟”。但是调度周期的减小带来的是更高的切换代价和更差的系统总吞吐能力。

【例子】假设目标延迟为 20ms 。

当存在两个优先级相同的可运行任务时：每个任务在被其他任务抢占前可运行 10ms 。
当存在四个这样的可运行任务时，每个任务只能运行 5ms 。
当存在二十个这样的任务时，每个任务只能运行 1ms 。
当存在非常多个这样的任务时，它们的可运行时间逐渐趋于 0 。

为了解决这样的切换消耗， CFS 引入了每个进程获得时间片的底线，称为时间片的最小粒度，默认为 1ms 。