跳到主要内容

CPU 调度

参考Linux manual 从 Linux2.6.23 开始,默认调度器为 CFS(Completely Fair Scheduler),替代了早期的"0(1)"调度

Overview

  • 对每个线程,都会有相应的调度策略 (policy),和静态的优先级 (priority)
  • 调度器在每个优先级上都有一个队列,在决定下一个运行线程时,会获取优先级最高的非空队列的第一个
  • 线程的调度策略 (policy) 决定了它将如何插入同优先级的队列,以及它如何在队列中移动
  • 所有的调度策略都是抢占式的 (preemptive),当高优先级的线程可以运行时,当前运行的线程会被抢占,并被放回其优先级队列
  • 线程的调度策略只决定了其在同优先级队列中的的排序方式
  • 在 normal policies 中,Nice 值只会在线程所在的 cgroup 内与其他同组线程比较,而 cgroup 间也通过 Nice 值进行 CFS 分配时间片。

Normal policies

priority: 决策时不使用,必须设置为 0

OTHER

Linux 系统默认调度策略,在 Linux 源码中名称为SCHED_NORMAL

0 优先级队列内的优先级是动态调整的,基于线程的 Nice 值,且当线程可以运行时,单当前时间片内未得到运行时会增加

Nice value

  • 在 Linux 中,同一进程的不同线程可以有不同的 Nice

  • 影响 SCHED_OTHER 和 SCHED_BATCH

  • 现代 Linux 中,范围 -20(high) -> +19(low),其他系统可能不同

  • Nice 调整的效果在不同系统与内核版本中可能不同的。在当前版本,Nice 每相差 1,调度器就会 1.25 倍得偏向高优先级线程

  • 可用 RLIMIT_NICE 限制无特权进程的最高 Nice 值

IDLE

不受 Nice 值的影响,用于非常低优先级的线程,其优先级低于 Nice 设置为 +19(最低) 的 OTHER 与 BATCH 线程

BATCH

与 OTHER 相似,但调度器会认为改线程是 CPU 密集型,会对线程唤醒应用一个小的调度惩罚,因此该线程优先级会略微降低。主要用于非交互的,工作量大,但不希望降低 Nice 值的线程,与需要一个确定的交互策略,不希望受到交互额外抢占的线程

Real-time policies

实时线程优先级永远比普通线程高 priority: 1(low) to 99(high)

FIFO(First in-first out)

先进先出调度,在该调度下,线程可运行后会立即抢占 Normal 调度线程,且无时间片,若不主动释放则会一直占用

在队列中的顺序变化:

  • 被更高优先级抢占后,该策略的线程会被放到其优先级队列的头部,在更高优先级的线程都运行完后,会立即运行
  • 当被阻塞的 FIFO 线程可运行后,会被插入到其优先级队列的末尾
  • 当一个可运行或运行中的 FIFO 线程的优先级被更改时
    • 若优先级被提高,则会将其插入新优先级队列的末尾
    • 若优先级被降低,则会被放到新优先级队列的头部
    • 若优先级不变,则其位置不变
    • (根据 POSIX. 1-2008,任何除pthread_setschedprio()外的方法,改变优先级后,都应将其放到新优先级队列的末尾),具体情况可能需要测试
  • 调用yield后,会被放到其队列的末尾

FIFO 线程会持续运行直到被阻塞、被更高优先级线程抢占或主动调用yield

RR(Round-robin)

FIFO 的增强版,所有 FIFO 的规则都适用于 RR,除了每个线程有运行的最大时间,当线程运行时间超过最大时间后,会被方式其优先级队列的末端

  • 当 RR 线程被抢占后恢复运行时,可运行的最大时间为上次运行没用完的最大时间
  • 最大时间长度可通过sched_rr_get_interval()查询

DEADLINE

从 Linux 3.14 开始提供,采用 GEDF(Global Earliest Deadline First) 与 CBS(Constant Bandwidth Server) 相结合。若要使用该策略,需调用sched_setattr()sched_getattr()

Overview

         arrival/wakeup                    absolute deadline
| start time |
| | |
v v v
-----x--------xooooooooooooooooo--------x--------x---
|<- comp. time ->|
|<------- relative deadline ------>|
|<-------------- period ------------------->|
  • 适用于时断时续的任务,即在一个时期内只会被激活一次

  • arrival/wakeup: 任务被唤醒,或被放到等待队列中的时间

  • relative deadline: 在 arrival/wakeup 后,过多久必须被执行完毕

  • computation time: CPU 执行这个任务所需要的时间

  • absolute deadline: arrival time + relative deadline

Usage

         arrival/wakeup                    absolute deadline
| start time |
| | |
v v v
-----x--------xooooooooooooooooo--------x--------x---
|<-- Runtime ------->|
|<----------- Deadline ----------->|
|<-------------- Period ------------------->|
  • 使用sched_setattr(),有Runtime, DeadlinePeriod 三个参数,以 nanosecond 为单位

  • 实践中会把Runtime设置成一个比平均计算时间大,甚至最坏情况下的计算时间

  • Deadline 就是 relative deadline

  • Period 就是任务的周期,当设置为 0 时,其与Deadline 的值一致

  • 需满足Runtime < Deadline < Period,且三个都需大于 1024,即 1 微秒,是当前实践的分辨率,且小于 2^63,设定时,如果以上检查不满足,sched_setattr会以EINVAL失败

  • CBS 保证了任务直接不会干扰,当任务用完 Runtime 后,会被限制(throttle,放回队尾?)

  • 为保证效果,在设置/修改属性时会进行可行性检查,当设置不可行时,会以EBUSY失败

  • DEADLINE 线程有着用户可设置的最高优先级,会抢占其他任何 policies(包括 real-time)

  • 当 DEADLINE 线程调用fork,会以EAGAIN失败,除非其设置了 reset-on-fork

  • 当 DEADLINE 线程yield时,会等待到新的 Period 去运行

Practice

Reset policy for child processes

Privileges and resource limits

Limiting the real-time processes usage

当 real-time 的进程死循环后,可能会永远阻止其他进程访问 CPU

  • Linux 2.6.25 前,只可以通过设置一个更高优先级的进程控制这些进程

  • 可通过RLIMIT_RTTIME限制 real-time 线程的 CPU 时间

  • 可以编辑/proc/sys/kernel/sched_rt_period_us 和/proc/sys/kernel/sched_rt_runtime_us 给非实时线程保留一些 CPU 时间

Cgroup

Linux 2.6.38 后,提供了 autogrouping 特性来提升交互应用的体验

  • 通过/proc/sys/kernel/sched_autogroup_enabled 控制,0 为关闭,1 为打开,或通过启动参数noautogroup关闭。默认为打开

  • autogrouping 打开后,每次调用setsid时都会创建新的 cgroup,例如每新开一个终端

  • cgroup 的意义在于,当后台有 10 个线程在运行,而前台有一个交互线程,如果没有 cgroup,交互线程只能分得 1/11 的时间片,而若 10 个线程在同一个 cgroup,而交互线程在另一个 cgroup 时,交互线程就能分得 1/2 的时间片,10 个后台线程公用另 1/2

  • 通过 Nice 调整 cgroup 间的调度分配,可通过文件/proc/<pid>/autogroup 查看线程所在的 cgroup 和修改 cgroup 的 Nice 值

  • 可通过修改/proc/self/autogroup,修改整个终端所在的 autogroup 的 Nice

    echo 10 > /proc/self/autogroup