完全公平调度算法

用户7244416

发布于 2021-10-26 13:46:09

9080

发布于 2021-10-26 13:46:09

1.算法介绍

针对没有实时需求的普通进程，Linux内核使用完全公平调度器（Completely Fair Scheduler，CFS）。普通进程的nice值（相对优先级，基准值是120）的取值范围是-20~19，值越小表示优先级越高，不同优先级的进程应该享受不同的待遇，优先级高的进程应该获得更多的处理器时间。为了兼顾进程优先级和公平性，完全公平调度算法引入了虚拟运行时间，如下。

虚拟运行时间 = 实际运行时间 × nice 0对应的权重 / 进程的权重

进程的权重是根据nice值转换得到的，nice值和权重的对应关系如下。

kernel/sched/core.c
const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

nice 0对应的权重是1024，nice n-1的权重是nice n的权重的1.25倍，取1.25倍的依据是：假设系统只有两个进程，nice值相同，如果一个进程的nice值减一，优先级提升一级，那么在长度为T的时间段它获得的CPU时间是（T×55%），比另一个进程多（T×10%）；如果一个进程的nice值加一，优先级降低一级，那么在长度为T的时间段它获得的CPU时间是（T×45%），比另一个进程少（T×10%）。举个例子，假设进程A和B的nice值都是0，两个进程的CPU份额都是50%，如果进程B的nice值加一，优先级降低一级，那么进程A的权重是1024，进程B的权重是1024/1.25≈820，进程A的CPU份额是1024/(1024+820)≈55%，进程B的CPU份额是820/(1024+820)≈45%，在长度为T的时间段进程B获得的CPU时间比进程A少（T×10%）。

完全公平调度算法使用红黑树（一种平衡的二叉树）把进程按虚拟运行时间从小到大排序，每次调度时选择虚拟运行时间最小的进程。

调度器选中进程以后分配的时间片是多少呢？

调度周期：在某个时间长度可以保证运行队列中的每个进程至少运行一次，我们把这个时间长度称为调度周期。也称为调度延迟，因为一个进程等待被调度的延迟时间是一个调度周期。

调度最小粒度：为了防止进程切换太频繁，进程被调度后应该至少运行一小段时间，我们把这个时间长度称为调度最小粒度。

调度周期的默认值是6毫秒，调度最小粒度的默认值是0.75毫秒，如下所示，两者的单位都是纳秒。

kernel/sched/fair.c
unsigned int sysctl_sched_latency      = 6000000ULL;
unsigned int sysctl_sched_min_granularity    = 750000ULL;

如果运行队列中的进程数量太多，导致把调度周期sysctl_sched_latency平分给进程时的时间片小于调度最小粒度，那么调度周期取“调度最小粒度 × 进程数量”。

进程的时间片的计算公式如下。

进程的时间片 = 调度周期 × 进程的权重 / 运行队列中所有进程的权重总和

按照这个公式计算出来的时间片称为理想的运行时间。可以看出，优先级高的进程的权重大，所以获得的时间片长。

进程调度器周期性地检查当前进程的运行时间是否到达理想的运行时间，如果是，那么重新选择进程。

在一个调度周期中，进程的虚拟运行时间 = 进程的时间片 × nice 0对应的权重 / 进程的权重

= （调度周期 × 进程的权重 / 运行队列中所有进程的权重总和）× nice 0对应的权重 / 进程的权重

= 调度周期 / 运行队列中所有进程的权重总和 × nice 0对应的权重

= 调度周期 × nice 0对应的权重 / 运行队列中所有进程的权重总和

可以看出，在每个调度周期中，优先级高的进程的实际运行时间多，但是每个进程的虚拟运行时间是相同的，所以完全公平调度算法的公平性体现在每个调度周期中给每个进程分配相同的虚拟运行时间。

2.计算虚拟运行时间

当进程调度器选中进程p的时候，使用p->se.exec_start记录开始运行时间，如下。

__schedule() -> pick_next_task() -> class->pick_next_task() 
-> pick_next_task_fair() -> set_next_entity() 
-> update_stats_curr_start()

kernel/sched/fair.c
static inline void
update_stats_curr_start(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
  se->exec_start = rq_clock_task(rq_of(cfs_rq));
}

从进程p切换到其他进程的时候，获取当前时间，减去进程p的开始运行时间，得到进程p的运行时间，然后把运行时间转换为虚拟运行时间，接着把虚拟运行时间累加到p->se.vruntime，如下。

__schedule() -> pick_next_task() -> class->pick_next_task() 
-> pick_next_task_fair() -> put_prev_task() 
-> prev->sched_class->put_prev_task() -> put_prev_task_fair() 
-> put_prev_entity() -> update_curr()

kernel/sched/fair.c
static void update_curr(struct cfs_rq *cfs_rq)
{
  struct sched_entity *curr = cfs_rq->curr;
  u64 now = rq_clock_task(rq_of(cfs_rq));
  u64 delta_exec;

  ...
  delta_exec = now - curr->exec_start;
  ...
  curr->vruntime += calc_delta_fair(delta_exec, curr);
  ...
}

正常情况下进程的虚拟运行时间是一步一个脚印走出来的，但是有3种情况进程的虚拟运行时间是伪造的，以公平运行队列的最小虚拟运行时间为基础进行篡改。

2.1.公平运行队列的最小虚拟运行时间

每个处理器的公平运行队列维护一个min_vruntime字段，用来记录公平运行队列的最小虚拟运行时间，即公平运行队列中的所有进程的虚拟运行时间的最小值。这个字段的值是单调递增的。假设min_vruntime是公平运行队列中的所有进程的虚拟运行时间的最小值，那么cfs_rq.min_vruntime的计算方法如下，即取自己和min_vruntime的较大值。

cfs_rq.min_vruntime = max(cfs_rq.min_vruntime, min_vruntime)

在创建新进程、睡眠进程被唤醒和进程从一个处理器迁移到另一个处理器这些情况，会以公平运行队列的最小虚拟运行时间为基础设置进程的虚拟运行时间，使进程的虚拟运行时间和其他进程保持在合理的差距范围内。

2.2.新进程的虚拟运行时间的初始值

创建新进程，新进程的虚拟运行时间的初始值是多少？假如初始值是0，比老进程小很多，将会导致进程调度器在很长一段时间内总是选中它，老进程得不到调度，显然不合理。

新进程的虚拟运行时间的初始值以它所在的公平运行队列的最小虚拟运行时间为基础设置，与老进程保持在合理的差距范围内。

新进程的虚拟运行时间的初始值有两个控制参数，如下。

（1）调度特性START_DEBIT：新进程的虚拟运行时间的初始值在公平运行队列的最小虚拟运行时间的基础上增加延迟时间，延迟时间是新进程自己的时间片，假装新进程在当前调度周期被调度过一次，因为当前调度周期已经承诺给公平运行队列中的所有进程，所以新进程应该不参加当前调度周期的调度。默认开启。这个调度特性是针对“某个进程持续调用fork()创建新进程”这种情况设计的，假设某个进程持续调用fork()创建了很多新进程，如果把新进程的虚拟运行时间的初始值设置为公平运行队列的最小虚拟运行时间，会导致已经在公平运行队列中的进程得不到调度。

（2）sysctl_sched_child_runs_first：在调用fork()创建子进程以后，子进程先运行，父进程后运行。默认禁止，可以执行命令“echo 1 > /proc/sys/kernel/sched_child_runs_first”开启。

新进程的虚拟运行时间的初始值的计算方法如下。

（1）如果父进程属于公平调度类，那么把新进程的虚拟运行时间的初始值设置为父进程的虚拟运行时间。父进程是指调用函数fork()的进程，注意，父进程可能不属于公平调度类，可能是限期进程或者实时进程，如果父进程调用函数sched_setscheduler()设置调度策略时设置了标志SCHED_RESET_ON_FORK，那么创建的子进程使用默认的调度策略SCHED_NORMAL。

（2）取公平运行队列的最小虚拟运行时间，如果开启了调度特性START_DEBIT，那么在这个基础上加上延迟时间。新进程的虚拟运行时间的初始值取第1步和第2步的较大值。

（3）如果开启子进程先运行的特性，父进程属于公平调度类，并且父进程的虚拟运行时间小，那么交换父进程和子进程的虚拟运行时间。

2.3.睡眠进程的虚拟运行时间

进程睡眠一段时间，它的虚拟运行时间保持不变，其他进程在运行，它们的虚拟运行时间一直增加，当睡眠进程被唤醒的时候，它的虚拟运行时间和其他进程相比，可能有很大的差距，导致进程调度器在一段时间内总是选中它，其他进程得不到调度。

当睡眠进程被唤醒的时候，重新设置它的虚拟运行时间，取下面两个时间的较大值。

（1）进程开始睡眠时的虚拟运行时间。

（2）以公平运行队列的最小虚拟运行时间为基础，给一定的补偿，补偿值是半个调度周期，即vruntime = cfs_rq.min_vruntime – (sysctl_sched_latency / 2)。调度特性GENTLE_FAIR_SLEEPERS用来控制睡眠进程的补偿值，默认开启，如果禁止，那么补偿值是一个调度周期，即vruntime = cfs_rq.min_vruntime - sysctl_sched_latency。

根据上面的计算方法，可以得出下面的结论。

（1）如果进程只是短暂睡眠，它的虚拟运行时间大于“cfs_rq.min_vruntime - 补偿值”，那么它的虚拟运行时间保持原样。

（2）如果进程长时间睡眠，它的虚拟运行时间小于“cfs_rq.min_vruntime - 补偿值”，那么把它的虚拟运行时间修改为“cfs_rq.min_vruntime - 补偿值”。

2.4.进程迁移

在多处理器系统中，不同处理器的负载不同，负载重的处理器上进程多，每个进程的虚拟运行时间增加得慢，负载轻的处理器上进程少，每个进程的虚拟运行时间增加得快，假设处理器1有10个普通进程，处理器2只有1个普通进程，处理器1上每个进程的虚拟运行时间是处理器2上进程的虚拟运行时间的1/10。当从负载重的处理器迁移进程到负载轻的处理器的时候，迁移过来的进程的虚拟运行时间小很多，导致进程调度器在一段时间内总是选中它，对其他进程不公平。

完全公平调度算法的解决方法如下。

（1）当进程p退出一个处理器的公平运行队列的时候，把它的虚拟运行时间减去公平运行队列的最小虚拟运行时间，即p->se.vruntime = p->se.vruntime - cfs_rq.min_vruntime。

（2）当进程p加入一个处理器的公平运行队列的时候，把它的虚拟运行时间加上公平运行队列的最小虚拟运行时间，即p->se.vruntime = p->se.vruntime + cfs_rq.min_vruntime。

注意：当进程因为要睡眠而退出公平运行队列的时候，不会把它的虚拟运行时间减去公平运行队列的最小虚拟运行时间；当进程因为唤醒而加入公平运行队列的时候，不会把它的虚拟运行时间加上公平运行队列的最小虚拟运行时间。

3.选择进程的算法

完全公平调度算法通常选择虚拟运行时间最小的进程，但是选择算法还需要考虑下面的特殊情况。

（1）刚唤醒或刚创建的进程抢占处理器，抢占的进程运行完以后把处理器归还给被抢占的进程，这样做的好处是利用缓存局部性原理，被抢占的进程的指令和数据可能还在处理器的缓存中。

（2）某个处理器密集型的进程长时间占用处理器，良心发现，调用函数sched_yield()表示自愿让出处理器，调度器选择进程的时候应该跳过它。

在公平运行队列的结构体中增加了下面这些成员。

kernel/sched/sched.h
struct cfs_rq {
  ...
  struct sched_entity *curr, *next, *last, *skip;
  ...
};

成员curr指向当前正在运行的调度实体。成员next指向要抢占处理器的调度实体，成员last指向被抢占的调度实体。成员skip指向自愿让出处理器的调度实体。

综合所有情况，选择进程的算法如下（把虚拟运行时间最小的进程记为min）。

（1）如果有进程要抢占处理器（即cfs_rq.next指向某个进程），并且它的虚拟运行时间和进程min的差值小于或等于限定值，那么选择要抢占处理器的进程。

（2）在第1条规则不成立的情况下，如果存在被抢占的进程（即cfs_rq.last指向某个进程），并且它的虚拟运行时间和进程min的差值小于或等于限定值，那么选择被抢占的进程。

（3）在前2条规则不成立的情况下，如果进程min自愿让出处理器（即cfs_rq.skip指向进程min），并且虚拟运行时间第二小的进程和它的差值小于或等于限定值，那么选择虚拟运行时间第二小的进程。

（4）在前3条规则不成立的情况下，选择虚拟运行时间最小的进程min。

前3条规则使用的限定值是“唤醒粒度 × nice 0对应的权重 / 进程min的权重”，即使用进程min的权重把唤醒粒度转换成的虚拟时间。

唤醒粒度参数sysctl_sched_wakeup_granularity限定了刚唤醒的进程要抢占当前进程必须满足的条件：只有当刚唤醒进程的虚拟运行时间比当前进程小，并且差距大于“唤醒粒度× nice 0对应的权重 / 刚唤醒进程的权重”，才可以抢占。这个参数越大，发生唤醒抢占就越困难。唤醒粒度参数的默认值是1毫秒。