process scheduler(简称 scheduler) 决定运行哪个 Process，什么时候运行以运行多长时间。其主要 idea 就是最大化地利用 processor time

多任务(Multitasking) OS 有两种：

  • cooperative multitasking，除非进程主动放弃，不然会一直运行。调度器无法决定一个进程能够运行多长时间，因此进程可以独占处理器
  • preemptive multitasking，一个运行中的进程可以被抢占。Linux 采用这种方式

Scheduler 将 CPU 时间划分为时间片(timeslice)，scheduler 的工作就是管理这些时间片。在现代 OS 中，时间片通常是根据进程的行为和系统配置动态计算的。

O(1) scheduler 可以轻松支持数十甚至上百个处理器，但是对调度 latency-sensitive applications 有些问题，这些 applications 被称为 interactive processes(包括所有与用户交互的应用)

Rotaing Staircase Deadline scheduler 引入 fair scheduling 的概念，–> Completely Fair Scheduler(CFS)

Schedule class

有两种方法可以激活调度，一种是直接的，比如进程打算睡眠或因为其他原因放弃 CPU；另一种是周期性检查。这两种组件称为通用调度器(generic scheduler)或核心调度器(core scheduler)

schedule class 提供了通用调度器和各个调度方法之间的关联，用于判断接下来运行哪个进程，kernel 支持不同的调度策略（完全公平调度、实时调度等），schedule class 能够以模块化的方式实现这些策略。每个进程都只属于一个调度类，进程调度时，由所属的调度类来调度。

所有的 schedule class 通过链表的形式连接起来，这个结构在 /kernel/sched/sched.h 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct sched_class { 
    const struct sched_class *next;

    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
    void (*yield_task) (struct rq *rq); // 进程资源放弃对处理器 控制权时调用
    // 用新唤醒的进程抢占当前进程。wake_up_new_task() 唤醒新进程时会调用
    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p);

    struct task_struct * (*pick_next_task) (struct rq *rq);
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);
    // 进程调度策略发生变化时调用
    void (*set_curr_task) (struct rq *rq);
    // 每次激活周期性调度器时有周期性调度器调用
    void (*task_tick) (struct rq *rq, struct task_struct *p);
    // 建立 fork 系统调用和调度器之间的关联。每次创建新进程后，使用 new_task 通知调度器
    void (*task_new) (struct rq *rq, struct task_struct *p);
};

每个 CPU 都有自身的就绪队列，就绪队列通过 struct rq 来表示，每个就绪队列中有两个队列，分别代表两个 schedule class (完全公平调度, 实时调度) 管理的队列。各个活动进程都只会出现在一个 CPU 的一个就绪队列中

1
2
3
4
5
6
7
8
9
10
11
struct rq {
    unsigned long nr_running; // 指定队列上可运行的进程的数目
    #define CPU_LOAD_IDX_MAX 5
    unsigned long cpu_load[CPU_LOAD_IDX_MAX]; // 就绪队列负荷的度量(与队列上当前活动进程数目成正比，与权重也有关)
    
    struct load_weight load; // 用于跟踪此前的负荷状态
    struct cfs_rq cfs; // 完全公平调度 子就绪队列
    struct rt_rq rt; // 实时调度器 子就绪队列
    struct task_struct *curr, *idle;
    u64 clock; // 就绪队列时钟，每次调用周期性调度器时更新
};

Priority

进程大致可以分为两类

  • I/O-Bound，更多的时间花在 I/O 上，即大部分时间都在等待 I/O
  • Processor-Bound，更加关注在执行 code 上

目标：快速响应（低延迟）、最大化地利用系统（高吞吐）

Unix 更加关注在 I/O 密集型进程

基于优先级的调度：给进程排优先级，优先级高的先执行（有些系统可能会有更多的时间片），优先级低的后执行。相同优先级可以采用 RR。

Linux 实现了两种 priority ranges:

  • nice value, 从 -20 到 19，默认为 0。nice value 越大，优先级越小，能够使用的 CPU 时间的比例越少。可以使用 ps -el 查看 nice value(NI 列)。nice value 设置的优先级也是 static priority，可以通过 nice 和 sched_setscheduler 进行修改
  • real-time priority，这个值是可配置的，默认范围为 [0,99]。real-time priority 越大，优先级越高。实时进程的优先级比普通进程的优先级要高。可以使用 ps -eo rtprio 查看

在 Linux 中，使用一个简单的数值范围 [0, 139] 来表示 nice value 和 real-time priority，其中 0~99 分配给 real-time priority，100~139 映射到 nice value。Linux 中，这个数值越大，优先级越小。(对于实时进程的优先级，会采用 99 - rt_priority 的形式计算，因此 rt_priority 越大，这个数值越小，优先级就越大。而对于普通进程，会使用 (120 + nice) 进行计算)

在 task_struct 中有三个字段表示优先级

  • static_prio，静态优先级，进程启动时分配的优先级，可以用 nice, sched_setscheduler 系统调用修改
  • normal_prio，基于静态优先级和调度策略计算出的优先级。实时进程的优先级为 MAX_RT_PRIO - 1 - rt_prio，普通进程的优先级根据 nice 值计算(nice + DEFAULT_PRIO)。具体的可以看这里
  • prio，动态优先级。如果一个普通进程临时提高优先级，那么就会使用这个字段的值作为优先级，否则使用 normal_prio 作为优先级。具体可以看这里
  • rt_priority，表示实时进程的优先级，实时进程的优先级总是高于普通进程。如果一个普通进程临时提高优先级，会使用进程
进程类型/优先级 static_prio normal_prio prio
非实时进程 static_prio static_prio static_prio
优先级提高的非实时进程 static_prio static_prio prio 不变
实时进程 static_prio MAX_RT_PRIO - 1 - rt_prio prio 不变

时间片的选取既不能太长，也不能太短。太长会导致交互性变差，太短又会在上下文切换上消耗过多。

同时，将 nice value 映射到固定的时间片也不是一个好方法。比如

  • nice value 分别为 0 和 20 的时间片分别为 100 和 5ms。但是如果只有两个 nice value 为 0 的进程会导致每隔 100ms 切换一次，这个时间片太长了；如果只有两个 nice value 为 20 的进程，就会每隔 5ms 切换一次，这个时间片太短了。
  • 而且 nice value 为 0 和 1 时间片的差距（比如 100, 95)与 nice value 为 18 和 19 的差距（比如 10，5）会很不一样，这样很不合理。

CFS 调度器解决这些问题通过：

  • nice value geometric instead of additive
  • 将 nice value 映射为 比例而非固定的值，比如 nice 每减少 1，获得的时间片增加 10%

Context Switch

  • switch_mm 切换 task_struct->mm 描述的内存管理上下文，包括 page table，TLB等，细节取决于处理器
  • switch_to 切换处理器寄存器内容和内核栈(包括用户状态下的栈)

Fair Scheduling

理想中完美的调度模型是 n 个进程，每个进程都使用 frac1nfrac{1}{n} 的 CPU 时间，并在无限小的时间内调度它们，让他们都运行相同的时间。但是调度会进行上下文切换，所以这种模型是不可能实现的。

CFS 就是基于这种模型实现的。CFS 会尽量让每个进程运行相同多的时间，并使用 RR 等调度算法将运行时间最少得进程选座下一个运行的进程。

CFS 会记录从上次执行开始到现在的时间，并会根据当前 runnable 的进程数量对其进行调整，得到一个加权后的 vruntime(virtual runtime) 作为其运行的总时间，并利用 vruntime 来估算这个进程应该获取多少时间片。

原文:

The vruntime variable stores the virtual runtime of a process, which is the actual runtime(the amount of time spent running) normalized(or weighted) by the number of runnable processes.

update_curr() calculates the execution time of the current process and stores that value in delta_exec. It then pass that runtime to __update_curr(), which weights the time by the number of runnable processes. The current process’s vruntime is then increment by the weighted value

不是很理解这里说的 “weights the time by the number of runnable processes”。应该是根据进程的 nice value 来分配权重，nice value 越小，权重越大。计算 vruntime时权重越大，其 vruntime 加得越慢。

vruntime 增加的速度依赖于等待调度器挑选的进程的数目，比如有 N 个进程，那么 vruntime 将以实际时钟 1/4 的速度运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static void update_curr(struct cfs_rq *cfs_rq) { 
    struct sched_entity *curr = cfs_rq->curr; 
    u64 now = rq_of(cfs_rq)->clock; 
    unsigned long delta_exec; 

    //Get the amount of time the current task was running * since the last time we changed load
    // 获取上次 改变这个时间以来过去的时间
    delta_exec = (unsigned long)(now - curr->exec_start); 
    if (!delta_exec) return;

    // 对时间进行加权。计算物理时间和虚拟时间
    __update_curr(cfs_rq, curr, delta_exec); 
    curr->exec_start = now; 
}

static inline 
void __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr, unsigned long delta_exec) { 

    // 计算总的运行时间，以及加权时间
    curr->sum_exec_runtime += delta_exec; 
    schedstat_add(cfs_rq, exec_clock, delta_exec); 
    delta_exec_weighted = calc_delta_fair(delta_exec, curr); 

    // 将加权后的时间增加到 vruntime 上
    curr->vruntime += delta_exec_weighted; 
    update_min_vruntime(cfs_rq); 
}

update_curr() 有两种调用时机：

  • 周期性地被系统定时器调用
  • 当进程变为 runnable 或 blocks 或 unrunnable 时调用

delta_exec_weighted=delta_exec⋅NICE_0_LOADcurr→load.weightdelta\_exec\_weighted = delta\_exec \cdot \frac{NICE\_0\_LOAD}{curr \to load.weight}

选择下一个运行的进程

CFS 的核心思想就是选择 vruntime 最小的进程调度。

CFS 使用红黑树来管理 runnable 进程，当需要调度时，从红黑树中取出 vruntime 最小的进程，并会将其缓存起来。当进程变为 runnable 或被创建时，也会想红黑树中新增一个节点。当进程变为 block 或 终止时，会从红黑树中移除。

实际红黑树中 key 的存储是 vruntime - min_vruntime。min_vruntime 跟踪 cfs 就绪队列上所有进程的最小 vruntime（可能比节点的 vruntime 还大）只有在树的节点的 vruntime 超过时 min_vruntime 时才会更新（确保 min_vruntime 单调递增）。vruntime 会随着时间增加，这可以减缓不公平状态

  • 进程运行时，vruntiem 增加得越慢，节点向右移动的速度也越慢，即高优先级的进程更有可能被调度
  • 当进程进入 sleep 状态时，vruntime 会保持不变，但是队列中的 min_runtime 可能会增加，那么当进程唤醒后，节点会往左移，即更有可能被调度。实际上当进程被环境后会补偿一定的 vruntime
  • 新创建进程时，子进程会继承父进程的 vruntime（之前的版本可能会在父进程的 vruntime 的基础之上增加或减少一定的 vruntime）

Real-time Schedule

实时进程的优先级总是比普通进程高。如果系统各种有一个实时进程，并且可以运行，那么调度器总是会选中它运行。

有两种实时调度类：

  • 循环进程(SCHED_RR) 有时间片，采用 RR 来执行
  • 先进先出进程(SCHED_FIFI)，没有时间片，可以运行任意长时间

实时调度类的就绪队列采用链表实现，具有相同优先级的所有实时进程都保存在一个链表中。在 SCHED_RR 中，如果一个进程时间片用完，会重新放入到链表的末尾

1
2
3
4
5
6
7
struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* 包含1比特用于间隔符 */
    struct list_head queue[MAX_RT_PRIO]; 
};
struct rt_rq {
    struct rt_prio_array active;
};

Enhance

多核处理器上必须考虑几个问题

  • CPU 负载必须尽可能公平地在所有处理器上共享
    • 周期调度器函数 scheduler_tick 完成任务后会调用 trigger_load_balance 引发 SCHEDULE_SOFTIRQ 软中断，该中断会在适当时机执行 run_rebalance_domains，最终对当前 CPU 调用 rebalance_domains 实现负载均衡
  • 进程与系统中某些处理器的亲和性(affinity) 必须可以设置
  • 内核必须能够将进程从一个 CPU 迁移到另一个 CPU
    • 内核为每个就绪队列提供了一个迁移线程，可以接受迁移请求，这些请求保存在 migration_queue 链表中。通常发源于调度器自身。
    • 可以优先在物理上临近或共享高速缓存的 CPU之间迁移