Gentoo 实现原理 — 进程调度与策略配置

dummy@example.com (batsom) — Mon, 25 Mar 2024 13:32:59 +0000

进程调度

进程调度，即 Linux Kernel Scheduler 如何将多个 User Process 调度给 CPU 执行，从而实现多任务执行环境的公平竞争以及合理分配 CPU 资源。

在古早的单核环境中，Linux Scheduler 的主要目的是通过 "时间片轮转算法" 和 “优先级调度算法“ 来实现调度。而在现代多核环境中，Linux Scheduler 则需要考虑更多的复杂因素，如：CPU 负载均衡、Cache 亲和性、多核互斥等。所以本文主要讨论的是多核环境中的进程调度。

为了应对不同应用场景中的进程调度需求，Linux Kernel 实现了多种 Scheduler 类型，常见的有：

CFS（Completely Fair Scheduler，完全公平调度器）
RT（Real-time Scheduler，实时调度器）
DS（Deadline Scheduler，最后期限调度器）

这些 Scheduler 会被作用于每个 CPU Cores 的 “就绪队列“ 中，且具有各自不同的调度算法和优先级策略。

在操作系统层面用户可以操作的只有用户进程实体，所以我们能够看见并使用的大多数调度配置都是针对 User Process 而言。

如下图，Kernel 将进程分为 2 大类型，对应各自的优先级区域以及不同的调度算法。

实时进程：具有实时性要求，共有 0～99 这 100 个优先级。
普通进程：没有实时性要求，共有 100～139 这 40 个级别。

但实际上，实时进程的优先级是初设后不可更改的。也就是说，从系统管理员的角度（Shell）只能配置普通进程的优先级。

针对普通进程的优先级配置，Linux 引入了 Nice level 的设计，Nice 值的范围是 -20～19 刚好对应到普通进程的 40 个优先级。其中，普通用户可以配置的范围是 0～19，而 Root 管理员则可以配置 -20～19。

CFS 完全公平调度器

Linux CFS（Completely Fair Scheduler，完全公平调度器）是 Kernel 默认使用的进程调度器，常用于通用计算场景。

CFS 的 “完全公平“ 并不是简单粗暴的按照 CPU 时间片大小来进行调度，而是会根据进程的运行时间来计算出优先级，运行时间较短的进程会拥有更高的优先级，从而保证了每个进程都能够获得公平的 CPU 时间。

具体而言，CFS 是一种基于红黑树的调度算法，它的目标是让所有进程都可以获得相同的 CPU 时间片。实现原理如下：

CFS 在每个 CPU 上都有一棵红黑树，每个节点对应一个普通进程的 PCB（task_struct）和一个 Key。这个 Key 是进程的一个 VRT（虚拟运行时间），反应了进程在 CPU 上的运行时间。运行时间越长，VRT 就越大，优先级就越小。
当一个新的普通进程被创建时，它会被加入到红黑树中，并且初始的 VRT 值为 0，表示拥有最高调度优先级。
当 CPU 空闲时，就查询红黑树，并将 VRT 最小的就绪进程调度执行，完毕后增加其 VRT，降低其下次调度的优先级。

可见，CFS 的优点让每个进程都获得了公平的 CPU 时间。然而，CFS 的缺点是由于红黑树的操作复杂度较高，对于高并发的场景可能会影响系统的性能。

SCHED_NORMAL（普通进程调度算法）

SCHED_NORMAL 是 CFS 的基本实现，采用了上文中提到的 “时间片轮转“ 和 “动态优先级“ 调度机制。

动态优先级：普通进程具有一个 nice 值来表示其优先级，nice 值越小，进程优先级越高。
时间片轮转：如果有多个普通进程的优先级相同，则采用轮流执行的方式。

SCHED_BATCH（批量调度算法）

SCHED_BATCH 是一种针对 CPU 密集型批处理作业的调度算法。它的主要目的是在系统空闲时间运行一些需要大量 CPU 时间的后台任务。

区别于 SCHED_NORMAL，它并不使用时间片轮转和动态优先级调度机制，而是采用了一种基于进程组的批量处理策略。该算法会将所有的后台任务进程加入到一个进程组中，该进程组会共享一个可调度时间片。

在 SCHED_BATCH 中，进程组会被赋予更高的优先级，以确保后台任务能够在系统空闲时间得到足够的 CPU 时间。
RTS 实时调度器

Linux RTS（Real-Time Scheduler，实时调度器）采用固定优先级调度算法，优先级高的进程会获得更多的 CPU 时间。RTS 是 RT-Kernel 的默认调度算法，常用于对实时性要求高的计算场景。

RTS 的主要目的是保证实时任务的响应性和可预测性。固定优先级调度算法，总是可以让高优先级任务先运行，同时还实现了基于抢占的调度策略，以保证实时任务能够在预定的时间内运行完成。实现原理如下：

RTS 优先级数值范围从 1（最高）～99（最低），其中 0 保留给 Kernel 使用。
RTS 还实现了基于抢占的调度策略。当一个高优先级的任务到来时，它可以抢占当前正在运行的任务，并且直到运行完毕。
RTS 使用了多队列的方法来管理实时进程。RTS 在每个 CPU 上维护 2 级就绪队列，一个是实时队列，一个是普通队列。并采用了不同的调度算法和优先级策略来进行调度。例如：实时进程采用 SCHED_FIFO 调度算法，普通进程采用 SCHED_RR。
调度器每次选择下一个要运行的进程时，会先从实时队列中选择进程，如果实时队列为空，则从普通队列中选择进程。这样可以保证实时进程的优先级高于普通进程，同时也避免了实时进程长时间等待的情况。

RTS 的优点是能够保证实时任务的响应性和可预测性，但缺点是对于普通任务来说可能会出现长时间等待的情况。

SCHED_FIFO（先到先服务调度算法）

SCHED_FIFO 调度算法会按照进程的提交顺序来分配 CPU 时间，当一个进程获得 CPU 时间后，它会一直运行直到完成或者被更高优先级的进程抢占。因此，该算法可能导致低优先级进程的饥饿情况，因为高优先级进程可能会一直占用 CPU 时间。
SCHED_RR（时间片轮转调度算法）

与 SCHED_FIFO 类似，SCHED_RR 调度算法也会按照进程的提交顺序来分配 CPU 时间。不同之处在于，每个进程都被赋予一个固定的时间片，当时间片用完后，该进程就会被放回就绪队列的尾部，等待下一次调度。该算法可以避免低优先级进程饥饿的问题，因为每个进程都能够获得一定数量的 CPU 时间，而且高优先级进程也不能一直占用 CPU 时间。
DS 最后期限调度器

Linux DS（Deadline Scheduling，最后期限调度器）是一种基于最后期限（Deadline）的调度器。实现原理如下：

DS 与 CFS 类似的采用了红黑树，但主要区别在于 DS 的树节点 Key 是 Deadline 值，而不是 VRT。
DS 为每个进程赋予一个 Deadline，DS 会按照进程的最后期限的顺序，安排进程的执行顺序。进程的最后期限越近，其优先级就越高。
当 CPU 空闲时，就查询红黑树，并将 Deadline 离与当前时间最近的就绪进程调度执行。

SCHED_DEADLINE（最后期限调度算法）

SCHED_DEADLINE 调度算法是 DS 调度器的默认调度算法，主要用于实时任务的调度。
进程调度策略的配置
ps 指令

我们在配置一个进程的调度策略之前，常常需要使用 ps 指令查看进程的状态信息。
查看进程资源使用信息

 $ ps aux

USER        PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root          1  0.1  0.0  78088  9188 ?        Ss   04:26   0:03 /sbin/init maybe-ubiquity
...
stack      2152  0.1  0.8 304004 138160 ?       S    04:27   0:04 nova-apiuWSGI worker 1
stack      2153  0.1  0.8 304004 138212 ?       S    04:27   0:04 nova-apiuWSGI worker 2
...

查看指定进程的 CPU 资源详细使用信息

$ pidstat -p 12285

02:53:02 PM   UID       PID    %usr %system  %guest    %CPU   CPU  Command
02:53:02 PM     0     12285    0.00    0.00    0.00    0.00     5  python

PID：进程 ID。
%usr：进程在用户态运行所占 CPU 的时间比率。
%system：进程在内核态运行所占 CPU 的时间比率。
%CPU：进程运行所占 CPU 的时间比率。
CPU：进程在哪个核上运行。
Command：创建进程对应的命令。

查看进程优先级信息

$ ps -le

F S   UID    PID   PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 S     0      1      0  0  80   0 - 19522 ep_pol ?        00:00:03 systemd
1 S     0      2      0  0  80   0 -     0 kthrea ?        00:00:00 kthreadd
1 I     0      4      2  0  60 -20 -     0 worker ?        00:00:00 kworker/0:0H
1 I     0      6      2  0  60 -20 -     0 rescue ?        00:00:00 mm_percpu_wq
...

UID：进程执行者 ID。
PID：进程 ID。
PPID：父进程 ID。
PRI：进程优先级，值越小优先级越高。
NI：进程的 nice 值。

查看系统中所有的实时进程

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm |awk '$4 !~ /-/{print $0}'

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN          COMMAND
    7     7 FF      99   - 139   0  0.0 FF  S    smpboot_thread migration/0
   10    10 FF      99   - 139   0  0.0 FF  S    smpboot_thread watchdog/0
   11    11 FF      99   - 139   1  0.0 FF  S    smpboot_thread watchdog/1
   12    12 FF      99   - 139   1  0.0 FF  S    smpboot_thread migration/1

查看 nice 不为 0 的普通进程

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm|awk '$4 ~ /-/ &&$5 !~/0/ {print $0}'

   63    63 TS       -   5  14   2  0.0 TS  SN   ksm_scan_threa ksmd
   64    64 TS       -  19   0   2  0.0 TS  SN   khugepaged     khugepaged
12995 12995 TS       -  -4  23   1  0.0 TS  S

查看进程运行状态及其内核函数名称

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:34,nwchan,pcpu,comm

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN                               WCHAN %CPU COMMAND
    1     1 TS       -   0  19   4  0.0 TS  Ssl  ep_poll                            ffffff  0.0 systemd
    2     2 TS       -   0  19   0  0.0 TS  S    kthreadd                            b1066  0.0 kthreadd
    3     3 TS       -   0  19   0  0.0 TS  S    smpboot_thread_fn                   b905d  0.0 ksoftirqd/0
...
   44    44 TS       -   0  19   7  0.0 TS  R    -                                       -  0.0 kworker/7:0

wchan：显示进程处于休眠状态的内核函数名称，如果进程正在运行则为 -，如果进程具有多线程且 ps 指令未显示，则为 *。 nwchan：显示进程处于休眠状态的内核函数地址，正在运行的任务将在此列中显示短划线 -。

nice 指令

nice 指令用于修改普通进程的 nice 值。设定即将启动的普通进程的 nice 值

nice -n -5 service httpd start

修改已经存在的普通进程的 nice 值

$ ps -le | grep nova-compute
4 S  1000  9301     1  2  80   0 - 530107 ep_pol ?       00:02:50 nova-compute

$ renice -10 9301
9301 (process ID) old priority 0, new priority -10

$ ps -le | grep nova-compute
4 S  1000  9301     1  2  70 -10 - 530107 ep_pol ?       00:02:54 nova-compute

chrt 指令

chrt 指令可用于修改进程的调度算法和优先级。

$ chrt --help
Show or change the real-time scheduling attributes of a process.

Set policy:
 chrt [options]   [...]
 chrt [options] --pid  

Get policy:
 chrt [options] -p 

Policy options:
 -b, --batch          set policy to SCHED_BATCH
 -d, --deadline       set policy to SCHED_DEADLINE
 -f, --fifo           set policy to SCHED_FIFO
 -i, --idle           set policy to SCHED_IDLE
 -o, --other          set policy to SCHED_OTHER
 -r, --rr             set policy to SCHED_RR (default)

修改进程的调度算法

$ chrt -r 10 bash

$ chrt -p $$
pid 13360's current scheduling policy: SCHED_RR
pid 13360's current scheduling priority: 10

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm |awk '$4 !~ /-/{print $0}'

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN          COMMAND
13360 13360 RR      10   -  50   7  0.0 RR  S    do_wait        bash

修改实时进程的优先级

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm |awk '$4 !~ /-/{print $0}'

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN          COMMAND
   27    27 FF      99   - 139   4  0.0 FF  S    smpboot_thread migration/4

$ chrt -p 31
pid 31's current scheduling policy: SCHED_FIFO
pid 31's current scheduling priority: 99

$ chrt -f -p 50 31

$ chrt -p 31
pid 31's current scheduling policy: SCHED_FIFO
pid 31's current scheduling priority: 50

Gentoo中文社区 / Gentoo 实现原理 — 进程调度与策略配置

Gentoo 实现原理 — 进程调度与策略配置