Linux Kernel - Process Scheduler

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

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

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

调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。

调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。通常做法是（其并未被 Linux 系统完全采用）优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。

Linux 采用了两种不同的优先级范围。第一种范围是用 nice 值，它的范围是从 -20 到 +19，默认值为 0；越大的 nice 值意味着更低的优先级——nice 似乎意味着你对系统中的其他进程更“友好”。nice 值是所有 Unix 系统中的标准化的概念——但不同的 Unix 系统由于调度算法不同，因此 nice 值的运用方式有所差异。比如一些基于 Unix 的操作系统，如 Mac OS，进程的 nice 值代表分配给进程的时间片的绝对值；而 Linu 系统中，nice 值则代表时间片的比例。

第二种范围是实时优先级，它的变化范围是从 0 到 99（包括 0 和 99）。与 nice 值意义相反，越高的实时优先级数值意味着进程优先级越高。 任何实时进程的优先级都高于普通的进程，也就是说实时优先级和 nice 优先级处于互不相交的两个范畴。 Linux 实时优先级的实现参考了 Unix 相关标准特别是 POSIX.1b。大部分现代的 Unix 操作系统也都提供类似的机制。

Linux 下可以通过命令：

$ ps -eo state,uid,pid,nice,rtprio,time,comm
S   UID   PID  NI RTPRIO     TIME COMMAND
S     0     1   0      - 00:13:47 systemd
S     0     2   0      - 00:00:01 kthreadd
I     0     4 -20      - 00:00:00 kworker/0:0H
I     0     6 -20      - 00:00:00 mm_percpu_wq
S     0     7   0      - 00:18:36 ksoftirqd/0
I     0     8   0      - 00:46:07 rcu_sched
I     0     9   0      - 00:00:00 rcu_bh
S     0    10   -     99 00:00:35 migration/0
S     0    11   -     99 00:00:39 watchdog/0
S     0    12   0      - 00:00:00 cpuhp/0
......

查看到你系统中的进程列表，以及它们对应的 nice 值（位于 NI 列下）和实时优先级（位于 RTPRIO 列下）。如果进程的 RTPRIO 那列显示“-”，说明改进程是个普通进程，不是实时进程。

Linux 中的完全公平调度（CFS）是一个针对普通进程的调度器，也就说它不调度实时进程。

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。 调度策略必须规定一个默认的时间片，但这并不是件简单的事。时间片过长会导致系统对交互的响应表现欠佳，让人觉得系统无法并发执行应用程序；时间片太短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。此外，I/O 消耗型和处理器消耗型的进程之间的矛盾在这里也再次显露出来：I/O 消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好（比如这样可以让它们的高速缓存命中率更高）。

从上面的争论中可以看出，任何长时间片都将导致系统交互表现欠佳。很多操作系统中都特别重视这一点，所以默认的时间片很短如 10ms。但是 Linux 的 CFS 调度器并没有直接分配时间片到进程，它是将“处理器的使用比”划分给了进程。这样一来，进程所获得的处理器时间其实是和系统负载密切相关的。这个比例进一步还会受进程 nice 值的影响（nice 值越高，优先权越低，处理器的使用比越小）。

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

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

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

“所有进程能公平分享处理器”是 CFS 的基本思想，也是其名称的由来。

Linux 调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类（scheduler classes），它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础的调度器代码定义在 kernel/sched.c 文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。

完全公平调度（CFS）是一个针对普通进程的调度类，也就说它不调度实时进程。在 Linux 中称为 SCHED_NORMAL（在 POSIX 中称为 SCHED_OTHER），CFS 算法实现定义在文件 kernel/sched_fair.c 中。

在讨论公平调度算法前，我们必须首先认识一下传统 Unix 系统的调度过程。正如前面所述，现代进程调度器有两个通用的概念：进程优先级和时间片。时间片是指进程运行多少时间，进程一旦启动就会有一个默认时间片。具有更高优先级的进程将运行得更频繁，而且（在多数系统上）也会被赋予更多的时间片。在 Unix 系统上，优先级以 nice 值形式输出给用户空间。这点听起来简单，但是在现实中，却会导致许多反常的问题，我们下面具体讨论。

第一个问题，若要将 nice 值映射到时间片，就必然需要 将 nice 单位值对应到处理器的“绝对时间”。但这样做将导致进程切换无法最优化进行。 举例说明，假定我们将默认 nice 值（0）分配给一个进程对应的是一个 100ms 的时间片；同时再分配一个最高 nice 值（+20，最低的优先级）给另一个进程对应的时间片是 5ms。我们接着假定上述两个进程都处于可运行状态。那么默认优先级的进程将获得 20/21（105ms 中的 100ms）的处理器时间，而低优先级的进程会获得 1/21（105ms 中的 5ms）的处理器时间。现在我们看看如果运行两个同等低优先级的进程情况将如何。我们是希望它们能各自获得一半的处理器时间，事实上也确实如此。但是任何一个进程每次仅仅只能获得 5ms 的处理器时间（10ms 中各占一半）。也就是说，相比刚才例子中 105ms 内进行一次上下文切换，现在则需要在 10ms 内继续进行两次上下文切换。类推，如果是两个具有普通优先级的进程，它们同样会每个获得 50% 处理器时间，但是是在 100ms 内各获得一半。显然，我们看到这些时间片的分配方式并不很理想：它们是给定 nice 值到时间片映射与进程运行优先级混合的共同作用结果。事实上，给定高 nice 值（低优先级）的进程往往是后台进程，且多是计算密集型；而普通优先级的进程则更多是前台用户任务。所以这种时间片分配方式显然是和初衷背道而驰的。

第二个问题涉及相对 nice 值，同时和前面的 nice 值到时间片映射关系也脱不了干系。假设我们有两个进程，分别具有不同的优先级。第一个假设 nice 值只是 0，第二个假设是 1。它们将被分别映射到时间片 100ms 和 95ms（O(1) 调度算法确实这么干了）。它们的时间片几乎一样，其差别微乎其微。但是如果我们的进程分别赋予 18 和 19 的 nice 值，那么它们则分别被映射为 10ms 和 5ms 的时间片。如果这样，前者相比后者获得了两倍的处理器时间！不过 nice 值通常都使用相对值（nice 系统调用是在原值上增加或减少，而不是在绝对值上操作），也就是说：“把进程的 nice 值减小 1”所带来的效果极大地取决于其 nice 的初始值。

第三个问题，如果执行 nice 值到时间片的映射，我们需要能分配一个绝对时间片，而且这个绝对时间片必须能在内核的测试范围内。在多数操作系统中，上述要求意味着时间片必须是定时器节拍的整数倍。但这么做必然会引发了几个问题。首先，最小时间片必然是定时器节拍的整数倍，也就是 10ms 或者 1ms 的倍数。其次，系统定时器限制了两个时间片的差异：连续的 nice 值映射到时间片，其差别范围多至 10ms 或者少则 1ms。最后，时间片还会随着定时器节拍改变。

第四个问题，你可能为了进程（如交互相关任务）能更快地投入运行，而去对它进行优先级提升。虽然上述方法确实能提升不少交互性能，但很多进程都这么干就不公平了，损害系统中其他进程的利益。

上述问题中的绝大多数都可以通过对传统 Unix 调度器进行改造解决，虽然这种改造修改不小，但也并非是结构性调整。比如，将 nice 值呈几何增加而非算数增加的方式解决第二个问题：采用一个新的度量机制将从 nice 值到时间片的映射与定时器节拍分离开来，以此解决第三个问题。但是这些解决方案都回避了实质问题即分配绝对的时间片引发的固定的切换频率，给公平性造成了很大变数。 CFS 采用的方法是对时间片分配方式进行根本性的重新设计（就进程调度器而言）：完全摒弃时间片，而是分配给进程一个“处理器使用比重”。 通过这种方式，CFS 确保了进程调度中能有恒定的公平性，而将切换频率置于不断变动中。

CFS 的出发点基于一个简单的理念： 进程调度的效果应如同系统具备一个“理想中的完美多任务处理器”。在这种系统中，每个进程将能获得 1/n 的处理器时间——n 是指可运行进程的数量。 同时，我们可以调度给它们无限小的时间周期，所以在任何可测量周期内，我们给予 n 个进程中每个进程同样多的运行时间。举例来说，假如我们有两个运行进程，在标准 Uinx 调度模型中，我们先运行其中一个 5ms，然后再运行另一个 5ms。但它们任何一个运行时都将占有 100% 的处理器。而在理想情况下，完美的多任务处理器模型应该是这样的：我们能在 10ms 内同时运行两个进程，它们各自使用处理器一半的能力。

当然，上述理想模型并非现实，因为我们无法在一个处理器上真的同时运行多个进程。而且如果每个进程运行无限小的时间周期也是不高效的——因为调度时进程抢占会带来一定的代价：将一个进程换出，另一个换入本身有消耗，同时还会影响到缓存的效率。因此虽然我们希望所有进程能只运行一个非常短的周期，但是 CFS 充分考虑了这将带来的额外消耗，实现中首先要确保系统性能不受损失。CFS 的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠 nice 值来计算时间片。nice 值在 CFS 中被作为进程获得的处理器运行比的权重：越高的 nice 值（越低的优先级）进程获得更低的处理器使用权重，这是相对默认 nice 值进程的进程而言的；相反，更低的 nice 值（越高的优先级）的进程获得更高的处理器使用权重。

每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行， 为了计算准确的时间片，CFS 为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标称作“目标延迟”， 越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但是你必须承受更高的切换代价和更差的系统总吞吐能力。让我们假定目标延迟值是 20ms，我们有两个同样优先级的可运行任务（无论这些任务的优先级是多少）。每个任务在被其他任务抢占前运行 10ms，如果我们有 4 个这样的任务，则每个只能运行 5ms。进一步设想，如果有 20 个这样的任务，那么每个仅仅只能获得 1ms 的运行时间。

你一定注意到了，当可运行任务数量趋于无限时，它们各自所获得的处理器使用比和时间片都将趋于 0 这样无疑造成了不可接受的切换消耗。 CFS 为此引入每个进程获得的时间片底线，这个底线称为“最小粒度”。默认情况下这个值是 1ms。 如此一来，即便是可运行进程数量趋于无穷，每个最少也能获得 1ms 的运行时间，确保切换消耗被限制在一定范围内。（敏锐的读者会注意到假如在进程数量变得非常多的情况下 CFS 并非一个完美的公平调度，因为这时处理器时间片再小也无法突破最小粒度。的确如此，尽管修改过的公平队列方法确实能提高这方面的公平性，但是 CFS 的算法本身其实已经决定在这方面做出折中了。但还好，因为通常情况下系统中只会有几百个可运行进程，无疑，这时 CFS 是相当公平的。）

现在，让我们再来看看具有不同 nice 值的两个可运行进程的运行情况比如一个具有默认 nice 值（0），另一个具有的 nice 值是 5。这些不同的 nice 值对应不同的权重，所以上述两个进程将获得不同的处理器使用比。在这个例子中，nice 值是 5 的进程的权重将是默认 nice 进程的 1/3。如果我们的目标延迟是 20ms，那么这两个进程将分别获得 15ms 和 5ms 的处理器时间。再比如我们的两个可运行进程的 nice 值分别是 10 和 15，它们分配的时间片将是多少呢？还是 15 和 5ms！可见，绝对的 nice 值不再影响调度决策：只有相对值才会影响处理器时间的分配比例。

总结一下，任何进程所获得的处理器时间是由它自己和其他所有可运行进程 nice 值的相对差值决定的。nice 值对时间片的作用不再是算数加权，而是几何加权。任何 nice 值对应的绝对时间不再是一个绝对值，而是处理器的使用比。CFS 称为公平调度器是因为它确保给每个进程公平的处理器使用比。正如我们知道的，CFS 不是完美的公平，它只是近乎完美的多任务。但是它确实在多进程环境下，降低了调度延迟带来的不公平性。

所有的调度器都必须对进程运行时间做记账。 多数 Unix 系统，正如我们前面所说，分配一个时间片给每一个进程。那么当每次系统时钟节拍发生时，时间片都会被减少一个节拍周期。当一个进程的时间片被减少到 0 时，它就会被另一个尚未减到 0 的时间片可运行进程抢占。 不过，Linux 的 CFS 不是这样的。

在前面内容中我们的讨论中谈到若存在一个完美的多任务处理器（参考节 5.3 ），所有可运行进程的 vruntime 值将一致。但事实上我们没有找到完美的多任务处理器，因此 CFS 试图利用一个简单的规则去均衡进程的虚拟运行时间：当 CFS 需要选择下一个运行进程时，它会挑一个具有最小 vruntime 的进程。 这其实就是 CFS 调度算法的核心：选择具有最小 vruntime 的任务。

CFS 使用红黑树（rbtree）来组织可运行进程队列，并利用其迅速找到最小 vruntime 值的进程。

我们先假设，有那么一个红黑树存储了系统中所有的可运行进程，其中节点的键值便是可运行进程的虚拟运行时间。CFS 调度器选取待运行的下一个进程，是所有进程中 vruntime 最小的那个，它对应的便是在树中最左侧的叶子节点。也就是说，你从树的根节点沿着左边的子节点向下找，一直找到叶子节点，你便找到了其 vruntime 值最小的那个进程。实现这一过程的函数是 __pick_next_entity ，它定义在文件 kernel/sched_fair.c 中：

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

注意： __pick_next_entity 函数本身并不会遍历树找到最左叶子节点，因为该值已经缓存在 rb_leftmost 字段中。虽然红黑树让我们可以很有效地找到最左叶子节点，但是更容易的做法是把最左叶子节点缓存起来。这个函数的返回值便是 CFS 调度选择的下一个运行进程。如果该函数返回值是 NULL，那么表示没有最左叶子节点，也就是说树中没有任何节点了。这种情况下，表示没有可运行进程，CFS 调度器便选择 idle 任务运行。

进程调度的主要入口点是函数 schedule() ，它定义在文件 kernel/sched.c 中。它正是内核其他部分用于调用进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。 schedule() 通常都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类——后者需要有自己的可运行队列，然后问后者谁才是下一个该运行的进程。知道了这个背景，就不会吃惊 schedule() 函数为何实现得如此简单该函数中唯一重要的事情是调用 pick_next_task() （也定义在文件 kernel/sched.c 中）。 pick_next_task() 会以优先级为序，从高到低依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程：

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;

    // ......

    class = sched_class_highest;
    for ( ; ; ) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
        /*
         * Will never be NULL as the idle class always
         * returns a non-NULL p:
         */
        class = class->next;
    }
}

该函数的核心是 for 循环，它以优先级为序，从最高的优先级类开始，遍历了每一个调度类。每一个调度类都实现了 pick_next_task() 函数，它会返回指向下一个可运行进程的指针，或者没有时返回 NULL。我们会从第一个返回非 NULL 值的类中选择下一个可运行进程。CFS 中 pick_next_task() 实现会调用 pick_next_entity ，而该函数会再来调用我们前面内容中讨论过的 __pick_next_entity 函数。

休眠（被阻塞）的进程处于一个特殊的不可执行状态。这点非常重要，如果没有这种特殊状态的话，调度程序就可能选出一个本不愿意被执行的进程，更槽糕的是，休眠就必须以轮询的方。式实现了进程休眠有多种原因，但肯定都是为了等待一些事件。事件可能是一段时间从文件 I/O 读更多数据，或者是某个硬件事件。一个进程还有可能在尝试获取一个已被占用的内核信号量时被迫进入休眠。休眠的一个常见原因就是文件如进程对一个文件执行了 read() 操作，而这需要从磁盘里读取。还有，进程在获取键盘输入的时候也需要等待。无论哪种情况，内核的操作都相同：进程把自己标记成休眠状态，从“可执行红黑树”中移出，放入“等待队列”，然后调用 schedule() 选择和执行一个其他进程。唤醒的过程刚好相反：进程被设置为可执行状态，然后再从“等待队列”中移到“可执行红黑树”中。

休眠有两种相关的进程状态：TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE。它们的唯一区别是处于 TASK_UNINTERRUPTIBLE 的进程会忽略信号，而处于 TASK_INTERRUPTIBLE 状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。两种状态的进程位于同一个等待队列上，等待某些事件，不能够运行。

内核至少在两种情况下会设置 TIF_NEED_RESCHED 标志，一个是在被唤醒进程的优先级比正在运行的进程的优先级高时（参考节 6.4.2）；另一个是在时钟中断进行周期性的检查时，调用路径为：

tick_periodic()->update_process_times()->scheduler_tick()

scheduler_tick() 函数中会设置 TIF_NEED_RESCHED 标志。

调度操作分为“触发”和“执行”两个部分，触发时仅仅设置一下当前进程的 TIF_NEED_RESCHED 标志，执行的时候则是通过 schedule() 函数来完成进程的选择和切换。这种方式被称为“延迟调度”。

为什么不在设置 TIF_NEED_RESCHED 标志的时候，直接执行调度呢？原因如下（参考 https://blog.csdn.net/pwl999/article/details/78817899 ）：

1. 唤醒操作经常在中断上下文中执行，在这个环境中直接调用 schedule() 进行调度是不行的；
   
2. 为了维护非抢占内核以来的一些传统，不要轻易中断进程的处理逻辑除非他主动放弃；
   
3. 在普通上下文中，唤醒后接着调用 schedule() 也是可以的，比如 smp_send_reschedule(), resched_curr() 函数就是这么实现。