linux中的周期调度器

2017-06-27

上篇文章简要介绍了Linux进程调度，以及结合源代码窥探了下CFS的调度实例。但是没有深入内部区分析调度下面的操作，比如就绪队列的维护以及进程时间的更新等。本节就这些问题做深入讨论。

回想进程调度，在thread_info中有一个重调度位，标识当前进程是否需要被调度，如果该位被设置表明当前进程需要被调度，在那么就调用调度器，执行下一个进程。但是该位是如何被设置的呢？换句话说，什么时候会设置该值，主要有以下几个地方

1、时钟中断
2、主动礼让
3、唤醒进程，检查优先级
4、更改进程的调度策略
5、fork进程

今天我们重点说说时钟中断的情况，即进程的周期调度器。周期调度器正式通过时钟中断触发的。时钟中断的内容请参考前面关于时间管理部分，这里仅仅是从时钟中断引入周期调度器。为了简便，我们以普通的周期时钟为例，这种情况下中断处理程序为timer_interrupt,每次时钟中断都是调用update_process_times来更新进程的运行时间，之后会调用一个函数scheduler_tick，这个就是扮演的周期调度器的角色。之前讲进程调度的时候也有提到，进程调度依赖于具体的调度类，目前普通进程一般采用CFS做为调度算法，所以这里我们以CFS调度类为例做介绍。

CFS调度类的周期调度函数为task_tick_fair，看下代码

 1 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 2 {
 3     struct cfs_rq *cfs_rq;
 4     struct sched_entity *se = &curr->se;
 5 
 6     for_each_sched_entity(se) {
 7         cfs_rq = cfs_rq_of(se);
 8         entity_tick(cfs_rq, se, queued);
 9     }
10 
11     if (sched_feat_numa(NUMA))
12         task_tick_numa(rq, curr);
13 
14     update_rq_runnable_avg(rq, 1);
15 }

这里操作的是调度实体sched_entity，这样就把具体的调度对象抽象化，借助于调度实体可以调度进程、也可以调度进程组。所以这里是for_each……我们按照调度单个进程来讲，里面调用了entity_tick，该函数主要实现两个功能1、通过update_curr更新当前进程的运行时间，注意这里是主要更新vruntime和调度实体的时间字段,然后调用check_preempt_tick检查抢占。

1、vruntime的更新

update_curr()->__update_curr,在此之前我们还是回顾下调度实体中的几个关于时间的字段

struct sched_entity {
　　……

    /*每次周期调度器执行，当前时间和exec_start之差被计算，然后更新exec_start到当前时间，差值被加到sum_exec_runtime*/

    u64            exec_start;
    /*记录进程在CPU 上运行的总时间，在update_curr更新*/
    u64            sum_exec_runtime;
    /*进程的虚拟时间*/
    u64            vruntime;
    /*当进程从CPU 挪下，当前的sum_exec_runtime移动到prev_sum_exec_runtime 在进程抢占的时候会用到，但是并不会清除sum_exec_runtime，该值仍然是持续增长的 */
    u64            prev_sum_exec_runtime;
　　……
}

现在看下函数代码：

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock_task;
    unsigned long delta_exec;

    if (unlikely(!curr))
        return;

    /*
     * Get the amount of time the current task was running
     * since the last time we changed load (this cannot
     * overflow on 32 bits):
     */
     /*上次更新到现在的时间差*/
    delta_exec = (unsigned long)(now - curr->exec_start);
    if (!delta_exec)
        return;
    
    __update_curr(cfs_rq, curr, delta_exec);
    /*更新exec_start*/
    curr->exec_start = now;

    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);

        trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
        cpuacct_charge(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }

    account_cfs_rq_runtime(cfs_rq, delta_exec);
}

可以看到这里操作的实际上是当前队列的正在运行的调度实体，如果该实体为空，则返回。然后获取上次更新到现在的时间差，如果没有更新那么就没必要接下来的更新。否则调用__update_curr，该函数更新了vruntime；接下来更新exec_start到当前时间。如果当前实体是进程的话，还有接下来的统计操作，最后更新队列总的运行时间。

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

    schedstat_set(curr->statistics.exec_max,
              max((u64)delta_exec, curr->statistics.exec_max));
    /*增加进程的总的运行时间*/
    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);
}

这里增加了进程实际运行的总时间，然后调用calc_delta_fair计算vruntime，vruntime大致是delta*NICE_0_LOAD/curr->load.weight,可以看到vruntime是跟实际运行时间成正比，跟自身权重成反比的，权重越大在运行相同时间的情况下其vruntime增长的越慢，得到调度的机会就越多。得到的结果会加到当前进程的vruntime上，故随着进程的运行，其vruntime会一直增加。潜在的优先级也就越来越低。最后调用update_min_vruntime对队列的min_vrntime进行更新，更新条件是当前进程的vruntime 和下一个要被调度的进程的vruntime做对比，取小的值。如果该值大于cfs_rq的vruntime，则更新，否则不更新。

2、check_preempt_tick检查抢占

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;

    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);
        /*
         * The current task ran long enough, ensure it doesn't get
         * re-elected due to buddy favours.
         */
        clear_buddies(cfs_rq, curr);
        return;
    }

    /*
     * Ensure that a task that missed wakeup preemption by a
     * narrow margin doesn't have to wait for a full slice.
     * This also mitigates buddy induced latencies under load.
     */
    if (delta_exec < sysctl_sched_min_granularity)
        return;

    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;

    if (delta < 0)
        return;

    if (delta > ideal_runtime)
        resched_task(rq_of(cfs_rq)->curr);
}

该函数主要判断当前进程是不是运行的时间已经足够长了，是的话就设置重调度位（仅仅是设置重调度位，在调度器检查调度的时候才会真正执行调度）。分为一下三种情况

当前进程运行时间大于ideal_runtime，就设置重调度位。
当前进程运行时间小于sysctl_sched_min_granularity，就返回继续运行。
当前进程的vruntime大于下一个即将调度进程的vruntime，且差值大于ideal_runtime，设置重调度位。

说到这里需要介绍下几个变量，内核中有个ideal_runtime的概念，保证每个进程运行都至少运行一个固定的时间，默认情况该值为sysctl_sched_latency，同时又一个就绪进程的数目sched_nr_latency，当当前可运行进程数目大于该值时，运行时间sysctl_sched_latency也要相应扩展。同时内核中还有规定一个进程运行的最短时间sysctl_sched_min_granularity，当进程数目超过sched_nr_latency，就是根据sysctl_sched_min_granularity得到的ideal_runtime，ideal_runtime=sysctl_sched_min_granularity*nr_running

总结：根据以上的介绍可以发现，vruntime所影响的仅仅是得到调度的机会，一个优先级高的进程比优先级低的进程更可能得到调度，但是随着优先级高的进程运行时间的增加，其vruntime会逐渐增大，而随着优先级低的进程总有机会得到调度。就进程每次运行的时间而言，高优先级和低优先级的进程每次分到的时间是一样的。CFS的公平体现在减少了高优先级和低优先级进程在调度时带来的待遇的不平等，让低优先级的进程始终有机会得到调度。

参考资料：

linux3.10.1内核源码

深入linux内核架构