汀的知识碎片

3.1 Linux调度发展简史

21 min read

3.1 Linux调度发展简史

本文将从以下四个维度深入剖析 Linux 进程调度器：

  1. 调度器的发展简史
  2. 调度器是如何定义的，运行队列到底长什么样？
  3. 新进程和老进程是如何确定自己该加入哪个运行队列的？
  4. 调度器是何时触发选择下一个待运行进程的？

在对调度器有了基本了解后，你也会对以下几个实践中息息相关的问题有更加深入的理解：

  1. 进程不主动释放 CPU 的话，每次调度最少能运行多久？
  2. 现在的进程调度还是按时间片来执行的吗？
  3. 进程的 nice 值的含义是什么？
  4. 用户进程中，高优先级是否能抢占低优先级的 CPU？
  5. 业界流行的在离线混部有啥副作用没？
  6. 为什么进程执行会在 CPU 各个核之间飘来飘去？
  7. taskset 命令是如何让一个进程钉在某个核上的？

3.1 Linux 进程调度发展简史

进程调度是一步步地发展起来的。在操作系统的教科书中，介绍了一些经典的进程调度算法，比如先来先服务、短作业优先、时间片轮转调度、优先级调度等等。不管是什么调度算法，其实都是在围绕调度中的两个核心问题在做文章：

  • 第一个核心问题：CPU 如何选择下面让哪一个任务运行？
  • 第二个核心问题：允许选中的进程运行多长的时间？

接下来我们要讨论的 Linux 各个版本的调度算法的迭代，也都是在围绕着这两个问题不断地演进。

3.1.1 O(n) 调度发展过程

在调度历史上，2.4 版本也是一个比较经典的版本。我们来看下 Linux 是如何演进到这个实现的。

先来先服务是最简单的进程调度算法。这种算法的思想就是搞一个就绪进程的队列。每当有新任务到达的时候，就添加到任务队列的尾部。当 CPU 处理完手头的任务选择下一个的时候，就直接从队列头中取一个出来。这其实就是我们日常生活中随处可见的排队的思路。比如你到银行、车管所、派出所等地方办事的时候，这些地方都是去了先让你领号排个队。当窗口可以处理下一位的时候，就直接喊下一个号。

这种算法的优点是实现起来非常的简单。但是缺点也非常的多。假如对头排第一位的任务处理起来非常的消耗时间，比如说要花 1 分钟。这时候队尾来的新任务可能只需要 1 秒就能处理完。显然让这个新任务为了获得 1 秒钟的 CPU 而等一分钟以上是非常不合适的。系统整体的响应能力会非常的差。

短作业优先是上面的一个改进。假如说在某种场景下提前可以大概估算处理所需要的耗时。比如车管所业务中包含新车上牌和处理交通违章两种业务，显然交通违章处理起来要比新车上牌要快的多。在这种情况下最短作业优先的思路就是让处理快的业务先处理。这样从整体上来看，大家在排队这件事情上所花的时间要低一些。因为短的任务很快就会被处理完，只剩下了大任务慢慢处理就好了。

短作业虽然整体上排队时间是短了，但是对于长作业来说却不公平。如果一直都有短作业到达的话，长作业将一直得不到 CPU 处理，一直排队排下去。

时间片轮转调度算法开始考虑公平性。它在调度的时候，会将一个进程分配一个时间片，这是本次调度分配给该进程的最长时间。如果时间片用尽后进程还没运行完，将被剥夺 CPU 并分配给下一个进程执行。当前进程重新进入运行队列排队，等待下一轮的调度。

时间片轮转是一个比较简单的公平算法。它能够保证所有进程都能得到一些处理时间，保证没有进程被饿死。然而系统中并不是所有的进程的诉求都是一样的。有的进程可能需要的 CPU 时间并不多，但对及时性更急迫。这类任务应该更优先一点处理，而不是和所有进程一样慢慢分时间片排队。

简单的时间片轮转没有考虑到优先级。系统中有些任务是需要尽快被处理的。另一方面是时间片大小。系统中所有进程并没有优先级的概念，所有的进程一视同仁，一个时间片一个时间片地调度。等调度到紧急任务的时候，可能很长时间都过去了。所以还必须得把优先级考虑进来，高优先级的任务应该位于队列的头部。这样调度的时候可以优先处理。

但是，一旦把优先级考虑进来后，很有可能会对低优先级的进程不友好。假如高优先级的任务足够多，低优先级的任务处理延时大大增加，甚至可能都无法获取 CPU 进行运行。

动态优先级方案做了一些改进。它将调度时使用的优先级会考虑两个方面的影响。一方面是和上面一样的静态优先级。另一方面是根据是否获得了时间片来给其一个优先级调整。静态优先级只是一个基础优先级，真正调度的时候根据动态优先级来执行调度。

如果一个进程用光了它的时间片，那么它计算后的最终动态优先级就会低一些。如果没有获得过时间片，或者时间片没有用光，相应的计算后的动态优先级就会高一些。

当然了，动态优先级的计算还是在静态优先级的基础上进行的。静态优先级高的进程仍然有较大的概率获得 CPU。静态优先级低的优先权会随着等待而逐步上升，也有机会获得 CPU。不会造成 CPU 被高静态优先级进程独霸的事情。

以上就是 Linux 进程调度器发展到 2.4 时代演进过程。最终在 2.4 的实现上，整个系统中有一个调度队列。当有新任务到达的时候，先设置一个静态优先级。调度器选择进程执行的时候，选择的办法是遍历整个任务队列，选择优先级最高的。但是优先级是在静态优先级的基础上动态变化的，如果获得了 CPU，那动态优先级就会变低。如果一直未获得，动态优先级就会变高。这样既照顾了对实时性要求高的高优先级进程，也避免了把低优先级的进程饿死。

O(n) 调度的核心特点

  • 单一全局运行队列。
  • 每次调度需要遍历整个队列寻找最高优先级进程。
  • 时间复杂度为 O(n)，n 为进程数。

3.1.2 Linux 2.5 O(1) 调度器

Linux 2.4 版本是在 2001 年的时候发布的，在当时的那个年代里运行的还算不错。但后面 CPU 硬件在单核主频上受到物理极限的限制，CPU 朝着多核的方向发展了。随着系统中核数的变多，单任务队列的矛盾就暴露出来了。所有的 CPU 都需要访问同一个任务队列，锁竞争的开销越来越高。另外就是后面服务器上跑的进程越来越多，O(n) 遍历方式也显得有那么一点低效了。所以接下来调度器发展中要考虑的重点就是如何在多核状态下尽可能提高调度器的运转性能。

在 Linux 2.5 中，调度器进行了脱胎换骨的改造，完美解决了前面小节提到的多核锁竞争和 O(n) 遍历问题。针对锁竞争问题，2.6 版本采取的手段是为每个 CPU 逻辑核都准备一个独立的 runqueue，这样就大大地减少了锁的开销。针对 O(n) 低性能遍历问题，2.6 采取的解决方法是采用多优先级任务队列。每一个优先级都有一个链表。在查找的时候，引入 bitmap 辅助数据结构实现 O(1) 查找。2.6 版本的调度器的实现逻辑图大概是如下图所示。

每个核上都有一个 runqueue 数据结构。这样每当需要调度执行新进程的时候，再也不需要到公共的队列中访问了。在 runqueue 中有 active、expired 两个任务队列。其中 active 是当前周期要调度的进程列表。当一个进程在当前周期的时间片用完后，就会被转到 expired 队列，而且会重新计算它的优先级。

当 active 中任务全部执行完毕后，active 和 expire 交换一下，开始下一个周期的调度，如此循环运行。

另外就是为了进一步提高调度效率。引入了多优先级任务队列。每一个优先级都拥有一个独立的链表。全局优先级，范围为 0~139，数值越低，优先级越高。借助了一个 bitmap 辅助数据结构来加速查询，通过每一个 bit 位来表示相对应的优先级上是否有任务存在。

在查找待调度进程的时候，直接根据 bitmap 上的比特位就可以快速定位到指定优先级上对应的任务链表。然后再从链表上找到进程调度即可。例如下图中第 0、第 3 bit 位不为 0，表示的是第 0 号、第 3 号优先级上的任务链表不为空。

在 2.4 时代，每次调度都需要遍历任务链表。所以算法复杂度是 O(n) 的。而到了 2.5 时代，通过 bitmap + 多优先级任务队列的方式达到了 O(1) 的算法复杂度。所以 2.5 时代的调度器又被称为 O(1) 调度器。

在优先级方面，定义了 140 个优先级。这些优先级被分成了两部分：

  • 第 0 ~ 99 的 100 个优先级是作为实时进程优先级来使用的。
  • 剩下的从 100 ~ 139 号 40 个优先级是给普通进程准备的。

我们开发的绝大多数的应用程序都是普通进程，也就是说使用的是 100 ~ 139 这部分优先级。

在调度优先级上，对于实时进程和普通进程的完全是不一样的。实时进程调度中，优先级是一个静态优先级。优先级高的进程具有绝对的优先权，肯定会被优先调度，而且还支持抢占低优先级进程的 CPU 时间。对于同优先级的实时进程采用先入先出或者是时间片轮转算法来分配 CPU。

但在普通进程中使用的是我们在上面的小节介绍的动态优先级的方法。静态优先级不发生变化，而动态优先级会随着是否使用过 CPU 时间片，使用多少来动态地计算。保证每个进程都能够被调度到，不至于被饿死。

说完了如何选择进程运行，再说说选择一个进程后该允许其运行多长的时间。在 O(1) 调度器中，时间片和优先级绑定的。通过 task_timeslice 函数来计算指定优先级的进程可以分配多长的时间片。我在 linux-2.5.68 的源码中找到了它的定义。

系统规定了最小时间片是 10 * HZ / 1000，最大时间片是 200 * HZ / 1000。其中 HZ 代表的是时钟中断的次数，还不是实际的时间单位。要想转化为具体的时间单位，是通过内核中的 jiffies_to_time 开头的几个函数来完成的。例如 jiffies_to_timeval 函数把时钟中断次数转换为秒和微秒两部分具体的时长。

最小时间片长度 MIN_TIMESLICE (10 * HZ / 1000) 在经过该函数处理后，结果是 10,000 usec（微秒），等于 10 ms。最大时间片长度 MAX_TIMESLICE (200 * HZ / 1000) 经过处理后结果是 200,000 usec（微秒），为 200 ms。也就是说 2.5 版本中，一个进程的运行时间片长度是 10 ms ~ 200 ms 之间。优先级越高的进程获得的时间片就越多。

O(1) 调度的关键改进

  • 每 CPU 独立运行队列：减少锁竞争。
  • bitmap + 多优先级链表：实现 O(1) 查找。
  • active/expired 双队列：支持时间片轮转与优先级重算。
  • 时间片与优先级绑定：高优先级获得更长的时间片。

相关代码片段

// file:kernel/sched.c
#define MIN_TIMESLICE   ( 10 * HZ / 1000)
#define MAX_TIMESLICE   (200 * HZ / 1000)
 
static inline unsigned int task_timeslice(task_t *p)
{
  return BASE_TIMESLICE(p);
}
 
#define BASE_TIMESLICE(p) (MIN_TIMESLICE + \
  ((MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1-(p)->static_prio)/(MAX_USER_PRIO - 1)))
 
//file:include/linux/time.h
static __inline__ void
jiffies_to_timeval(unsigned long jiffies, struct timeval *value)
{
    value->tv_usec = (jiffies % HZ) * (1000000L / HZ);
    value->tv_sec = jiffies / HZ;
}

3.1.3 完全公平调度器诞生

Linux 2.5 的调度器已经进化的非常不错了，但还是存在一点瑕疵 ，那就是优先级和时间片挂钩。优先级高的进程被分配了比较多的时间片，优先级低的进程被分配的时间片较少，通过这种方式来提供公平性。这会存在什么样的问题呢？

最大的问题就是调度延迟不可控。 传统的 O(1) 调度器在服务器负载高的时候，调度延迟会出现非常大的劣化。O(1) 调度器中当前周期内的每个进程的时间片是根据优先级计算出来的。那么一个调度周期就是当前周期内需要执行的所有任务的时间片之和。新来一个任务或者本轮时间片用完的话，就需要在下一个周期内才能调度的到。

举个实际的例子，假如某台服务器上每个核上都有 10 个进程在等待运行，他们的时间片都是 100ms。那么当再有优先级较低的新进程加入的时候，需要等待 10*100ms，整整 1 秒后才能被执行。秒级别在计算中是一个非常夸张的延迟了。

在实际应用中，有一些交互性的进程对延迟非常的敏感，例如带 UI 界面的程序，用户对延迟会非常敏感。不光是 UI 界面程序，即使是运算类的后台程序，延迟不可控也是非常严重的问题。如果这种算法用在今天的互联网后端服务器上，用户们估计早就拔腿闪人了。

Linux 内核在 2.6.23 版 中对 O(1) 调度器中普通进程（优先级为 100-139 之间的进程）的调度方式进行了改造。引入了 CFS (Completely Fair Scheduler) 完全公平调度器 以取代 O(1) 调度器中原来的普通进程调度，然后一直沿用至今。

O(1) 的瑕疵：调度延迟不可控

  • 时间片与优先级绑定，导致高负载下低优先级进程等待时间不可预测。
  • 交互式进程（如 UI）可能遭遇长达秒级的延迟，用户体验差。

以上内容完整覆盖了 Linux 调度器从 O(n) 到 O(1) 再到 CFS 的发展历程，并包含了关键的数据结构、算法逻辑、代码片段以及实践中的问题。请继续阅读后续章节以深入了解 CFS 的工作原理。