1. CFS如何选择最合适的进程

每个调度器类sched_class都必须提供一个pick_next_task函数用以在就绪队列中选择一个最优的进程来等待调度, 而我们的CFS调度器类中, 选择下一个将要运行的进程由pick_next_task_fair函数来完成

之前我们在将主调度器的时候, 主调度器schedule函数在进程调度抢占时, 会通过__schedule函数调用全局pick_next_task选择一个最优的进程, 在pick_next_task中我们就按照优先级依次调用不同调度器类提供的pick_next_task方法

今天就让我们窥探一下完全公平调度器类CFS的pick_next_task方法pick_next_fair

pick_next_task_fair

选择下一个将要运行的进程pick_next_task_fair执行. 其代码执行流程如下

对于pick_next_task_fair函数的讲解, 我们从simple标签开始, 这个是常规状态下pick_next的思路, 简单的来说pick_next_task_fair的函数框架如下

again:
    控制循环来读取最优进程

#ifdef CONFIG_FAIR_GROUP_SCHED
    完成组调度下的pick_next选择
    返回被选择的调度时实体的指针
#endif

simple:
    最基础的pick_next函数
   返回被选择的调度时实体的指针

idle :
    如果系统中没有可运行的进行, 则需要调度idle进程

可见我们会发现,

• simple标签是CFS中最基础的pick_next操作
• idle则使得在没有进程被调度时, 调度idle进程
• again标签用于循环的进行pick_next操作
• CONFIG_FAIR_GROUP_SCHED宏指定了组调度情况下的pick_next操作, 如果不支持组调度, 则pick_next_task_fair将直接从simple开始执行

2 simple无组调度最简单的pick_next_task_fair

在不支持组调度情况下(选项CONFIG_FAIR_GROUP_SCHED), CFS的pick_next_task_fair函数会直接执行simple标签, 优选下一个函数, 这个流程清晰而且简单, 但是已经足够我们理解cfs的pick_next了

2.1 simple的基本流程

pick_next_task_fair函数的simple标签定义在kernel/sched/fair.c, line 5526), 代码如下所示

simple:
    cfs_rq = &rq->cfs;
#endif
    /*  如果nr_running计数器为0,
     *  当前队列上没有可运行进程,
     *  则需要调度idle进程  */
    if (!cfs_rq->nr_running)
        goto idle;
    /*  将当前进程放入运行队列的合适位置  */
    put_prev_task(rq, prev);

    do
    {
        /*  选出下一个可执行调度实体(进程)  */
        se = pick_next_entity(cfs_rq, NULL);
        /*  把选中的进程从红黑树移除，更新红黑树  
         *  set_next_entity会调用__dequeue_entity完成此工作  */
        set_next_entity(cfs_rq, se);
        /*  group_cfs_rq return NULL when !CONFIG_FAIR_GROUP_SCHED
         *  在非组调度情况下, group_cfs_rq返回了NULL  */
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);  /*  在没有配置组调度选项(CONFIG_FAIR_GROUP_SCHED)的情况下.group_cfs_rq()返回NULL.因此,上函数中的循环只会循环一次  */


    /*  获取到调度实体指代的进程信息  */
    p = task_of(se);

    if (hrtick_enabled(rq))
        hrtick_start_fair(rq, p);

    return p;

其基本流程如下

流程	描述
!cfs_rq->nr_running -=> goto idle;	如果nr_running计数器为0, 当前队列上没有可运行进程, 则需要调度idle进程
put_prev_task(rq, prev);	将当前进程放入运行队列的合适位置, 每次当进程被调度后都会使用set_next_entity从红黑树中移除, 因此被抢占时需要重新加如红黑树中等待被调度
se = pick_next_entity(cfs_rq, NULL);	选出下一个可执行调度实体
set_next_entity(cfs_rq, se);	set_next_entity会调用__dequeue_entity把选中的进程从红黑树移除，并更新红黑树

2.2 put_prev_task

2.2.1 全局put_prev_task函数

put_prev_task用来将前一个进程prev放回到就绪队列中, 这是一个全局的函数, 而每个调度器类也必须实现一个自己的put_prev_task函数(比如CFS的put_prev_task_fair),

由于CFS调度的时候, prev进程不一定是一个CFS调度的进程, 因此必须调用全局的put_prev_task来调用prev进程所属调度器类sched_class的对应put_prev_task方法, 完成将进程放回到就绪队列中

全局的put_prev_task函数定义在kernel/sched/sched.h, line 1245, 代码如下所示

static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
{
    prev->sched_class->put_prev_task(rq, prev);
}

2.2.2 CFS的put_prev_task_fair函数

然后我们来分析一下CFS的put_prev_task_fair函数, 其定义在kernel/sched/fair.c, line 5572

在选中了下一个将被调度执行的进程之后，回到pick_next_task_fair中，执行set_next_entity

/*
 * Account for a descheduled task:
 */
static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
    struct sched_entity *se = &prev->se;
    struct cfs_rq *cfs_rq;

    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        put_prev_entity(cfs_rq, se);
    }
}

前面我们说到过函数在组策略情况下, 调度实体之间存在父子的层次, for_each_sched_entity会从当前调度实体开始,　然后循环向其父调度实体进行更新, 非组调度情况下则只执行一次

而put_prev_task_fair函数最终会调用put_prev_entity函