linux内核笔记（四）CFS 完全公平调度器类

完全公平调度器类 Completely Fair Scheduler

数据结构

CFS的就绪队列

struct cfs_rq {
    struct load_weight load;
    unsigned long nr_running;       //可运行进程数量
    u64 exec_clock;                 //运行时间
    u64 min_vruntime;               //队列上所有进程的最小虚拟运行时间
    struct rb_root tasks_timeline;  //在按时间排序的红黑树中管理所有进程
    struct rb_node *rb_leftmost;    //指向树最左边的结点，即最需要被调度的进程
    struct list_head tasks;         //存储当前在运行队列中的所有任务
    struct list_head *balance_iterator;//用于遍历调度器的运行队列，以便进行负载均衡的决策
    struct sched_entity *curr, *next, *last, *skip;//分别指向当前在运行的调度实体、下一个即将被调度的调度实体、最后调度的调度实体（刚运行完成的）、跳过调度的调度实体
    unsigned int nr_spread_over;    //在负载均衡操作中，如果一个CPU核心的任务数超过了一定阈值，调度器可能会将一些任务移动到其他CPU核心中去。nr_spread_over字段则表示了需要移动的任务数量。
}

调度算法-虚拟时钟的计算

CFS算法依赖于虚拟时钟，用以度量等待进程在完全公平系统中所能得到的CPU时间。虚拟时钟根据现存的实际时钟和与每个进程相关的负荷权重推算出来。相关的计算在update_curr中执行，该函数在系统中各个不同地方调用，包括周期性调度器之内。

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;
    
    delta_exec = (unsigned long)(now - curr->exec_start);
    if (!delta_exec)
        return;
    //将其余的工作委托给__update_curr 。
    __update_curr(cfs_rq, curr, delta_exec);
    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);
    }
}

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);
    //计算虚拟时间，并统计至当前进程的vruntime
    delta_exec_weighted = calc_delta_fair(delta_exec, curr);
    curr->vruntime += delta_exec_weighted;
    update_min_vruntime(cfs_rq);
}

static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
    //如果nice为0  虚拟时间与实时时间相同，直接返回
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);

    return delta;
}
//计算虚拟时间的算法，delta *= weight / lw
static unsigned long
calc_delta_mine(unsigned long delta_exec, unsigned long weight,
        struct load_weight *lw)
/* 跟踪树中最左边的结点的vruntime，维护cfs_rq->min_vruntime的单调递增性 */
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
    u64 vruntime = cfs_rq->min_vruntime;
    if (cfs_rq->curr)
        vruntime = cfs_rq->curr->vruntime;
    if (cfs_rq->rb_leftmost) {
        //树上最左边的结点（优先级最高的）的vruntime值。
        struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
                            struct sched_entity,
                            run_node);
        if (!cfs_rq->curr)
            vruntime = se->vruntime;
        else
            vruntime = min_vruntime(vruntime, se->vruntime);
    }
    //保证每个队列的min_vruntime是单调递增的，内核将其设置为二者中的较大者。
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

calc_delta_mine函数是CFS算法的核心，它根据进程的运行时间、调度优先级和调度权重计算出进程的虚拟运行时间，其实现逻辑为：

\[calc\_delta\_mine(delta\_exec,weight,lw)=\begin{cases}=SRR((delta\_exec \times weight) \times lw.inv\_weight) \\ \approx delta\_exec \times weight \div lw.weight \end{cases}\]

为了提高性能，对权重的除法换成了以load.inv_weight做SRR（Shift right and round 即右移并进行舍入）运算以提供近似除法的效果，但由于是通过右移和舍入实现的，因此可能会引入一定的误差。

不同优先级的进程的现实时间与虚拟时间的关系（当nice值为0时，虚拟时间与现实时间相等）

良好的调度延迟

为避免进程饥饿（某些进程无法得到足够的CPU时间，导致它们无法正常执行或者执行效率低下）和检测调度的健康度，内核设置了一个调度延迟的概念，它是指从一个进程被唤醒到它实际被调度执行之间的时间延迟。

//此宏意义在于se指向的结构将在指令块中被访问，然后不再允许被访问（se设置为NULL）
#define for_each_sched_entity(se) \
        for (; se; se = NULL)

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    //根据当前队列和可运行进程数量确定延迟周期的长度
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
    //计算se的调度延迟
    for_each_sched_entity(se) {
        struct load_weight *load;
        struct load_weight lw;
        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load;

        if (unlikely(!se->on_rq)) {
            //调度体不在队列中 将调度体的权重叠加到就绪队列的权重中
            lw = cfs_rq->load;
            update_load_add(&lw, se->load.weight);
            load = &lw;
        }
        //与计算虚拟时间相同的算法，计算出调度延迟
        slice = calc_delta_mine(slice, se->load.weight, load);
    }
    return slice;
}

static u64 __sched_period(unsigned long nr_running)

延期周期的长度以系统中的sysctl_sched_latency（系统内置的调度延迟长度）确定，但如果有更多进程在运行，周期就要线性扩展。扩展中也必须考虑到每个进程切换调度的最小时间间隔，在内核中以sysctl_sched_min_granularity表示

\[period = (nr\_running \le \frac{sysctl\_sched\_latency}{sysctl\_sched\_min\_granularity})?sysctl\_sched\_latency: sysctl\_sched\_min\_granularity \times nr\_running\]

翻译过来即是：

\[period = (就绪队列中的进程数量 \le \frac{默认调度延迟长度}{任务间的最小调度间隔})?默认调度延迟长度: 任务间的最小调度间隔 \times 就绪队列中的进程数量\]

就绪队列的入队和出队

CFS中用来管理就绪队列的增删函数分别是enqueue_task_fair和dequeue_task_fair

enqueue_task_fair逻辑栈

static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;

    for_each_sched_entity(se) {
        if (se->on_rq)
            break;
        //调度体不在队列中，将加入队列逻辑委托给enqueue_entity
        cfs_rq = cfs_rq_of(se);
        enqueue_entity(cfs_rq, se, flags);
        flags = ENQUEUE_WAKEUP;
    }

    for_each_sched_entity(se) {
        //如果调度体已经在队列中，维护队列的负载和权重
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        update_cfs_load(cfs_rq, 0);
        update_cfs_shares(cfs_rq);
    }

    hrtick_update(rq);
}

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    /* 进程正在唤醒中，先将调度体的虚拟时间加上队列中的最小虚拟运行时间 */
    if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
        se->vruntime += cfs_rq->min_vruntime;

    /* 更新维护当前进程的虚拟时间、负载、权重*/
    update_curr(cfs_rq);
    update_cfs_load(cfs_rq, 0);
    account_entity_enqueue(cfs_rq, se);
    update_cfs_shares(cfs_rq);

    if (flags & ENQUEUE_WAKEUP) {
        //进程已经被唤醒，在place_entity调整进程的虚拟运行时间
        place_entity(cfs_rq, se, 0);
        enqueue_sleeper(cfs_rq, se);
    }

    update_stats_enqueue(cfs_rq, se);
    check_spread(cfs_rq, se);
    //将se加入到红黑树中
    if (se != cfs_rq->curr)
        __enqueue_entity(cfs_rq, se);
    se->on_rq = 1;

    if (cfs_rq->nr_running == 1)
        list_add_leaf_cfs_rq(cfs_rq);
}
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;

    //新进程的引入会拖慢队列里的存量进程，因此给于给其sched_vslice的虚拟时间作为惩罚
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);

    if (!initial) { 
        //睡眠一段时间的进程的虚拟时间要减去一轮调度延迟长度（如果配置了温和的睡眠进程算法则减50%）以确保它在调度延迟周期内得到调度
        unsigned long thresh = sysctl_sched_latency;
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;
        vruntime -= thresh;
    }

    /* 确定给睡眠进程带来的奖励时间不超出它的睡眠时间 */
    vruntime = max_vruntime(se->vruntime, vruntime);

    se->vruntime = vruntime;
}

选择下一个进程

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct task_struct *p;
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    //没有进程可运行
    if (!cfs_rq->nr_running)
        return NULL;

    do {
        //获取树中最左边结点，并检查是否设置了跳过是否可以抢占
        se = pick_next_entity(cfs_rq);
        //从树中退出并设置为当前进程
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se);
    hrtick_start_fair(rq, p);

    return p;
}