跳到主要内容

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, Deadline 和 Period 三个参数，以 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

最后于 更新