CFS调度算法的思想和细节

今天在邮件列表里面有位朋友问了一个问题，问题表述如下：
在唤醒进程的时候,发现在check_preempt_wakeup()中.会将 cfs_rq->next设置为唤醒的进程,cfs_rq->last设置为当前的运行进程.然后将要唤醒的进程重新入列,即 enqueue_task().在pick_next_task_fair()中选择下一个调度进程的时候,有这样的选择 pick_next_task_fair() ---> pick_next_entity():
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
        struct sched_entity *se = __pick_next_entity(cfs_rq);
        if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)
                return cfs_rq->next;
        if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)
                return cfs_rq->last;
        return se;
}
其 中__pick_next_entity()用来选择rb_tree中最左端的se.然后,再调用wakeup_preempt_entity()来判断 选择出的se是否可以抢占cfs_rq->next和cfs_rq->last.现在我的疑问是: cfs_rq->next和cfs_rq->last是拿来做什么的呢? 它是为了保证唤醒时的当前进程和被唤醒的进程优先运行吗?但是,唤醒进程的时候已经调整了它的vruntime,并且调用enqueue_task()入 列,这样,它在选择下一个进程的时候,为什么直接按照vruntime值来调度呢?
<-问题描述结束
之所以有这样的疑问就是因为这位朋友没有从全局去考虑和理解cfs调度算法，而迷失在了局部的代码细节，这在读linux源代码的时候是一大 忌，linux的设计思想是很好很模块化很清晰的，但是具体到代码细节就不是这么美好了，这其实是一个编程习惯问题而不是什么设计问题。解决上述的问题很 容易，其实只要找一下check_preempt_wakeup的调用点就会发现，并不是仅仅在唤醒进程的时候才调用的，比如在更改进程优先级或者创建新 进程或者迁移进程的时候都要调用它。要点就是，如果入队的时候没有更新vruntime，那么就有必要将pick_up_next的结果也就是红黑树最左 下的结点和新入队的做一番比较，因为入队时的情况是不确定的，如果没有更新入队进程的vruntime但是其权值已经改变或者绑定的运行处理器已经改变的 话，比如迁移进一个新cpu的运行队列，那么就不能用它保留的原来的vruntime来竞争cpu了，但是又不想破坏代码的简洁而重新每次都在入队时计算 vruntime，那么只有先保留一个cfsq->next字段用来记录这个需要仲裁的新进程了，另外调度粒度也是一个很重要的参数，粒度过小的话 在cfs的平滑调度机制下就会发生频繁调度，系统的大部分时间都用到调度上了，对于调度器来说这样简直太精确了，但是对于整个系统来说调度仅仅是一个确保 公平的手段而已，仅是个服务，不能过多的占用处理器，相反调度粒度过大就又会回到时间片调度的那种低效状态，因此调度粒度是一个很重要的参数。判断入队时 是否更新vruntime的是enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)的waleup参数，比如在__migrate_task中就有调用activate_task(rq_dest, p, 0);check_preempt_curr(rq_dest, p);另外唤醒一个新进程的情况下入队时wakeup参数也可能为0，那么就不更新vruntime，这样就必须在pick_up_next的时候仲裁 了。
为何计算新入队的vruntime会破坏代码的简洁呢？linux内核由很多人编写，因此代码的模块化显得很重要，最好是只在一个地方修改一个变量而不是 到处都在修改，那么常规修改vruntime的地方就是update_curr了，当然唤醒睡眠进程或者新进程的时候也要修改，但是那不是常规修改，于是 要想修改调度实体的vruntime就必须使其成为curr，然后在更新curr时期更新其vruntime，于是就只有将未决进程，也就是cfsq的 next，和pick_up_next的结果进行比较，因为也只有pick_up_next的结果有资格参与比较，比较的另一方就是未决进程，它是确定 的，就是cfsq->next。首先看看这个神秘的wakeup_preempt_entity吧，待会儿再看看place_entity--另一 个设置vruntime的地方：
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
         s64 gran, vdiff = curr->vruntime - se->vruntime;  //vruntime的差值
         if (vdiff <= 0)    //cfsq的vruntime是单调递增的，也就是一个基准，各个进程的vruntime追赶竞争cfsq的vruntime，如果curr的 vruntime比较小，说明curr更加需要补偿，即se无法抢占curr
                 return -1;
         gran = wakeup_gran(curr);  //计算curr的最小抢占期限粒度
         if (vdiff > gran)          //当差值大于这个最小粒度的时候才抢占，这可以避免频繁抢占。
                 return 1;
         return 0;
}
static unsigned long wakeup_gran(struct sched_entity *se)
{
         unsigned long gran = sysctl_sched_wakeup_granularity;       //NICE_0_LOAD的基准最小运行期限
         if (!sched_feat(ASYM_GRAN) || se->load.weight > NICE_0_LOAD)     //非NICE_0_LOAD的进程要计算其自己的最小运行期限
                 gran = calc_delta_fair(sysctl_sched_wakeup_granularity, se); //计算进程运行的期限，即抢占的粒度。
         return gran;
}
看 完了上面两个函数后就可以说cfs的设计思想了，这里不再谈2.6.23的内核，仅以2.6.25以后的为准，本文讨论2.6.28的内核，这些新内核的 cfs算法和最开始的2.6.23的cfs的思想有些小不同。在cfs中，没有确定时间片的概念，不再像以前那样根据进程的优先值为进程分配一个确定的时 间片，在这个时间片过期后发生无条件进程切换，而未过期时则可以发生抢占。这个时间片的思想从早期的分时unix继承而来，已经不再适应现在抢占，特别是 内核抢占无处不在的新世界了，如今的处理器速度大大提高，时钟大大精确了，另外外设越来越智能，为cpu分担的工作越来越多，cpu仍然作为计算机的中心 就不能对外设为所欲为了，外设的中断更加频繁和有效，但是如果应用这些外设的运行于cpu的进程如果还是延迟响应的话，事情就会显得有些不和谐。这就要求 调度器必须改进，以前的时钟不精确，中断不频繁，外设少，总线带宽低，应用不丰富等原因使得内核非抢占是可以忍受的，后来虽然有了内核抢占但是还是和硬件 格格不入，应用程序总是看起来反映迟缓或者不公平，cfs调度器在这种情况下由运而生，cfs的总体思想就是尽量使进程公平的被调度，这种公平不是同等对 待所有进程，而是按照进程权值百分之百履行优先级承诺。cfs算法意味着cpu的调度和硬件行为的步调更加的一致，同时也免去了复杂的行为预测算法，这比 较符合这个世界的规则。按照以前的时间片方式硬件的时间片和操作系统调度的软件时间片差好几个数量级，而且软件已经不能做的更加精确了，因此必须抛弃这种 方式，cfs调度器看上去更像是一部无级变速器，既然跟不上硬件就别用时间片跟，到最后不但还是跟不上，而且还使得时间片调度行为丧失了世界原本的性质， 所以才有了那么多复杂的预测算法。cfs回归了世界的本质，就是公平的履行承诺。在2.6.25以后cfs中在每个队列设置了一个字段，就是 vruntime，这个字段在系统运行期间单调增长，各个进程自己也有一个vruntime，它们相互追赶向这个vruntime看齐，并且可以最终将自 己的vruntime设置为队列的vruntime，处理器总是挑选vruntime小的运行，这其实是一种对掉队者的补偿，这就是公平，每个进程的 vruntime相当于它自己的虚拟时钟，如果每个进程的虚拟时钟同步，各个进程就可以说是公平的，相互追赶vruntime并且向cfsq的 vruntime看齐就是保持虚拟时钟同步。对于不同权值的进程，它们的虚拟时钟快慢不同，这才是公平的真正含义，比方说权值大的进程的虚拟时钟10秒走 一个字，而权值小的进程虚拟时钟1秒就走一个字，虚拟时钟都走一个字就同步了，但是权值大的进程运行了10秒而小权值的进程才运行1秒，这就是实质。现在 看看place_entity：
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
         u64 vruntime = cfs_rq->min_vruntime;
         if (initial && sched_feat(START_DEBIT))  //如果是新进程第一次要入队，那么就要初始化它的vruntime，一般就把cfsq的vruntime给它就可以，但是如果当前运行的所有进程被承诺 了一个运行周期，那么则将新进程的vruntime后推一个他自己的slice，实际上新进程入队时要重新计算运行队列的总权值，总权值显然是增加了，但 是所有进程总的运行时期并不一定随之增加，则每个进程的承诺时间相当于减小了，就是减慢了进程们的虚拟时钟步伐。
                 vruntime += sched_vslice(cfs_rq, se);   //sched_vslice计算的结果就是这个新进程
         if (!initial) {
...//忽略一种情况
        vruntime = max_vruntime(se->vruntime, vruntime);  //如果是唤醒已经存在的进程，则单调附值
         }
         se->vruntime = vruntime;
}
sched_vslice很重要，它其实就是一个有意义的值，我们看一下：
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
         return calc_delta_fair(sched_slice(cfs_rq, se), se);
}
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)  //返回一个理想的运行时间
{
         unsigned long nr_running = cfs_rq->nr_running;
         if (unlikely(!se->on_rq))
                 nr_running++;
         return calc_delta_weight(__sched_period(nr_running), se); //返回一个进程se的应该运行的时间
}
static inline unsigned long calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
         if (unlikely(se->load.weight != NICE_0_LOAD))
                 delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);
         return delta;   //将delta除以总权值，得到一个值，该值的单位就是vruntime的单位。
}
static u64 __sched_period(unsigned long nr_running)  //返回一个值，该值是一个每个进程最少运行一趟的总时间
{
         u64 period = sysctl_sched_latency;
         unsigned long nr_latency = sched_nr_latency;
         if (unlikely(nr_running > nr_latency)) {
                 period = sysctl_sched_min_granularity;
                 period *= nr_running;
         }
         return period;
}
以 上几个函数很重要，很多cfs中所谓的“值”都是上述函数计算而来的，比如在时钟中断的tick节拍函数中，为了测试当前进程是否需要被抢占调用了 check_preempt_tick，该函数进一步调用了sched_slice获得了一个理想值，该理想值描述了这个当前进程实际上应该运行的时间， 如果这个进程实际运行的时间超过了这个理想值，那么就意味着该抢占了。
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
         unsigned long ideal_runtime, delta_exec;
         ideal_runtime = sched_slice(cfs_rq, curr);
         delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
         if (delta_exec > ideal_runtime)
                 resched_task(rq_of(cfs_rq)->curr);
}
今天在一个问题的激励下，我终于写了一篇描述cfs的文章，呵呵