调度算法

概述

调度类型

由于任务有优先级之分，Linux 系统为了保障高优先级的任务能够尽可能早的被执行，于是分为了这几种调度类型，如下图：

Deadline 和 Realtime 调度类型，应用于实时任务。这两个调度类型的调度策略合起来共有这三种，它们的作用如下：

  • SCHED_DEADLINE：是按照 deadline 进行调度的，距离当前时间点最近的 deadline 的任务会被优先调度；
  • SCHED_FIFO：对于相同优先级的任务，按先来先服务的原则，但是优先级更高的任务，可以抢占低优先级的任务，也就是优先级高的可以「插队」；
  • SCHED_RR：对于相同优先级的任务，轮流着运行，每个任务都有一定的时间片，当用完时间片的任务会被放到队列尾部，以保证相同优先级任务的公平性，但是高优先级的任务依然可以抢占低优先级的任务；

Fair 调度类型，应用于普通任务。都是由 CFS 调度器管理的，分为两种调度策略：

  • SCHED_NORMAL：普通任务使用的调度策略；
  • SCHED_BATCH：后台任务的调度策略，不和终端进行交互，因此在不影响其他需要交互的任务，可以适当降低它的优先级。

Deadline 调度器

RT 调度器

CFS 调度器

参考： 官方文档：https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt > https://blog.csdn.net/dog250/article/details/95729830 > https://blog.csdn.net/armlinuxww/article/details/97242063

https://www.jianshu.com/p/673c9e4817a8

https://zhuanlan.zhihu.com/p/83795639

https://blog.csdn.net/cloudvtech/article/details/107634785

CFS 调度器的前身是 O(1) 调度器 CFS 彻底抛弃了 时间片轮转 的策略，而是改之为 在任意的调度周期内公平分享 CPU 时间 的问题。 我们平日里遇到的基本都是普通任务，对于普通任务来说，公平性最重要，在 Linux 里面，实现了一个基于 CFS 的调度算法，也就是完全公平调度（Completely Fair Scheduling）。

Completely Fair Scheduler(完全公平的调度器，简称 CFS)。由 Ingo Molnar 实现并在 Linux Kernel 2.6.23 之后开始引入，并逐步替代老式的 (O)1 调度器。

CFS 使用 vruntime(虚拟运行时间) 的概念，来指定任务的下一个时间片何时开始在 CPU 上执行。

CFS 的做法就是在一个特定的调度周期内，保证所有待调度的进程都能被执行一遍，主要通过 vruntime 的值来决定本轮调度周期内所能占用的 CPU 时间，vruntime 越少，本轮能占用的 CPU 时间越多；总体而言，CFS 就是通过保证各个进程 vruntime 的大小尽量一致来达到公平调度的效果

CFS 的算法理念是想让分配给每个任务的 CPU 时间是一样，于是它为每个任务安排一个 vruntime(虚拟运行时间)，如果一个任务在运行，其运行的越久，该任务的 vruntime 自然就会越大，而没有被运行的任务，vruntime 是不会变化的。

那么，在 CFS 算法调度的时候，会优先选择 vruntime 少的任务，以保证每个任务的公平性。

这就好比，让你把一桶的奶茶平均分到 10 杯奶茶杯里，你看着哪杯奶茶少，就多倒一些；哪个多了，就先不倒，这样经过多轮操作，虽然不能保证每杯奶茶完全一样多，但至少是公平的。

进程的运行时间计算公式为(NICE_0_LOAD 默认为 1024)：
进程运行时间 = 调度周期 * 进程权重 / 所有进程权重之和
vruntime = 进程运行时间 * NICE_0_LOAD / 进程权重
         = (调度周期 * 进程权重 / 所有进程总权重) * NICE_0_LOAD / 进程权重
         = 调度周期 * NICE_0_LOAD / 所有进程总权重

通过上面两个公式，可以看到 vruntime 不是进程实际占用 CPU 的时间，而是剔除权重影响之后的 CPU 时间，这样所有进程在被调度决策的时候的依据是一致的，而实际占用 CPU 时间是经进程优先级权重放大的。这种方式使得系统的调度粒度更小来，更加适合高负载和多交互的场景。

实际上 vruntime 就是根据权重将实际运行时间标准化，标准化之后，各个进程对资源的消耗情况就可以直接通过比较 vruntime 来知道，比如某个进程的 vruntime 比较小，我们就可以知道这个进程消耗 CPU 资源比较少，反之消耗 CPU 资源就比较多。

CPU 运行队列

一个系统通常都会运行着很多任务，多任务的数量基本都是远超 CPU 核心数量，因此这时候就需要排队。

事实上，每个 CPU 都有自己的运行队列（Run Queue, rq），用于描述在此 CPU 上所运行的所有进程，其队列包含三个运行队列，Deadline 运行队列 dl_rq、实时任务运行队列 rt_rq 和 CFS 运行队列 csf_rq，其中 csf_rq 是用红黑树来描述的，按 vruntime 大小来排序的，最左侧的叶子节点，就是下次会被调度的任务。

这几种调度类是有优先级的，优先级如下：Deadline > Realtime > Fair，这意味着 Linux 选择下一个任务执行的时候，会按照此优先级顺序进行选择，也就是说先从 dl_rq 里选择任务，然后从 rt_rq 里选择任务，最后从 csf_rq 里选择任务。因此，实时任务总是会比普通任务优先被执行。

调整优先级

如果我们启动任务的时候，没有特意去指定优先级的话，默认情况下都是普通任务，普通任务的调度类是 Fail，由 CFS 调度器来进行管理。CFS 调度器的目的是实现任务运行的公平性，也就是保障每个任务的运行的时间是差不多的。

如果你想让某个普通任务有更多的执行时间，可以调整任务的 nice 值，从而让优先级高一些的任务执行更多时间。nice 的值能设置的范围是 -20 ～ 19， 值越低，表明优先级越高，因此 -20 是最高优先级，19 则是最低优先级，默认优先级是 0。

是不是觉得 nice 值的范围很诡异？事实上，nice 值并不是表示优先级，而是表示优先级的修正数值，它与优先级（priority）的关系是这样的：priority(new) = priority(old) + nice。内核中，priority 的范围是 0~139，值越低，优先级越高，其中前面的 0~99 范围是提供给实时任务使用的，而 nice 值是映射到 100~139，这个范围是提供给普通任务用的，因此 nice 值调整的是普通任务的优先级。

在前面我们提到了，权重值与 nice 值的关系的，nice 值越低，权重值就越大，计算出来的 vruntime 就会越少，由于 CFS 算法调度的时候，就会优先选择 vruntime 少的任务进行执行，所以 nice 值越低，任务的优先级就越高。

我们可以在启动任务的时候，可以指定 nice 的值，比如将 mysqld 以 -3 优先级：

~]# nice -n -3 /usr/sbin/mysqld

如果想修改已经运行中的任务的优先级，则可以使用 renice 来调整 nice 值：

~]# renice -10 -p 进程
PID

nice 调整的是普通任务的优先级，所以不管怎么缩小 nice 值，任务永远都是普通任务，如果某些任务要求实时性比较高，那么你可以考虑改变任务的优先级以及调度策略，使得它变成实时任务，比如：

# 修改调度策略为 SCHED_FIFO，并且优先级为 1
chrf -f 1 -p 1996

CFS 调度配置

参考：https://access.redhat.com/solutions/177953

在虚拟文件系统中，可以通过调整如下几个内核参数来改变 CFS 的行为: /proc/sys/kernel/sched_min_granularity_ns # 调度程序的最小粒度(单位：纳秒)。i.e.一个任务最少运行时间

增大该数值可以防止频繁的切换，最大值为 1000000000 纳秒，即 1 秒； 而对于交互系统（如桌面），该值可以设置得较小，这样可以保证交互得到更快的响应（见周期调度器的 check_preempt_tick 过程），最小值为 100000，即 0.1 毫秒

/proc/sys/kernel/sched_latency_ns # 调度延迟(单位：纳秒)。i.e.调度程序的调度 Period(周期，简写为 P)的初始值。也就是一个 CPU 的运行队列中，所有任务运行一次的时间长度

最大值为 1000000000 纳秒，即 1 秒；最小值为 100000，即 0.1 毫秒

  • 尽管 CFS 没有时间片的概念，但是可以将时间段视为初始时间块，然后将其平均划分为时间片，每个可运行的过程均使用一个时间片。
  • 请注意，此参数仅指定初始值。 当太多任务可运行时，调度程序将改为使用 kernel.sched_min_granularity_ns。
  • sched_nr_latency # 一个调度周期内的任务数。该值等于(sched_latency_ns/sched_min_granularity_ns)
  • 注意：这个参数是内核内部参数，无法直接设置，只能通过计算获得

在实际运行中，如果队列进程数 nr_running > sched_nr_latency，则调度周期就不是 sched_latency_ns，而是 P = sched_min_granularity_ns * nr_running，如果 nr_running <= sched_nr_latency，则 P = sched_latency_ns

/proc/sys/kernel/sched_nr_migrate # 在多 CPU 情况下进行负载均衡时，一次最多移动多少个进程到另一个 CPU 上

/proc/sys/kernel/sched_wakeup_granularity_ns # 表示进程被唤醒后至少应该运行的时间，这个数值越小，那么发生抢占的概率也就越高

sched_latency_ns 与 sched_min_granularity_ns 参数的白话示例

假如现在系统参数如下

~]# cat /proc/sys/kernel/sched_min_granularity_ns
10000000
~]# cat /proc/sys/kernel/sched_latency_ns
24000000

那么就表明系统默认情况下，一个任务最少运行 1000 万纳秒(10 毫秒)，而一个调度周期是 2400 万纳秒(24 毫秒)，那么就说明，在一个调度周期内，可以运行 2.4(24 除以 10) 个任务。

这时候，如果同时有 5 个任务正在运行，那么一共需要 50 毫秒，这已经超出了 24 毫秒的调度周期。

你想啊，一个任务默认情况下，可以在 24 毫秒后再次执行，但是如果任务过多，而每个任务最少又要运行 10 毫秒，那么就要等待 50 毫秒，才能再次执行。

所以这时候，系统的调度周期，就会变为 5000 万纳秒(50 毫秒)。虽然 sched_latency_ns 的值并没有变~因为每个任务最少运行 10 毫秒。


最后修改 May 22, 2024: memory mgmt, huge pages, numa (279776de)