Linux 完全公平算法 CFS 原理详解

      完全公平调度CFS是一个针对普通进程（linux还有其它类进程，例如实时进程）的调度类，CFS算法实现定义在文件kernel/sched_fair.c中，是在linux 2.6内核中提出的一类进程调度算法。
一、nice 值解析
       在linux中，nice值用来表示进程优先级，其取值范围是 -20～+19；越大的nice值意味着更低的优先级。
二、CFS 解析
       CFS的做法是每个进程运行一段时间、循环轮转、选择运行时间最少的进程作为下一个运行的进程，而不再采用分配给每个进程时间片的做法，CFS在所有可运行进程总数上基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得处理器使用比的权重，nice值越高(优先级更低)的进程获得更低的处理器使用权重；相反，nice值越低(更高的优先级)的进程获得更高的处理器使用权重。

       1> 运行时间片的计算

       进程运行的“时间片”是通过其权重在全部可运行进程中所占比例和“目标延迟”计算来的，这个“目标延迟”可以理解成调度周期。
       prio和weight之间的转换关系，这是个经验公式，如下图所示

      

        我们假设目标延迟是20ms，现在我们具体看看具有不同nice值的两个可运行进程的运行情况------一个具有默认nice值（0），另一个具有的nice值是5；不同的nice值对应不同的权重，由上图我们可以得知，nice值是5的进程的权重将是默认nice进程的1/3，所以nice值是5的进程和默认nice进程获得的处理器时间分别是15ms和5ms。如果两个可运行的进程的nice值分别是10和15，根据上图计算可得，两进程的权重比是仍然是3：1，故两进程获得的处理器时间分别是15ms和5ms。

       2> runtime 虚拟运行时间

       变量vruntime存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算经过了所有可运行进程总数的标准化（或者说是被加权的）。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。
       

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);
        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);
        }
}

     update_curr()计算了当前进程的执行时间，并且将其存放在变量delta_exec中。然后它又将运行时间传递给了__update_curr()，后者再根据当前可运行进程总数对运行时间进行加权计算。最终将上述的权重值与当前运行进程的vruntime相加。

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->exec_max, max((u64)delta_exec, curr->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);

        curr->vruntime += delta_exec_weighted;
        update_min_vruntime(cfs_rq);
}

        update_curr()是由系统定时器周期性调用，无论是在进程处于可运行状态，还是被堵塞处于不可运行状态。

        3> 进程的选择

        当CFS需要选择下一个运行进程时，它会挑选一个具有最小vruntime的进程，这其实就是CFS算法的核心。CFS算法采用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。

       知识点不断更新中，欢迎大家指正！
       附：我是一名刚开始学习linux_kernel的新手，从接触linux到现在已经四个月有余，再此期间，为了搞清楚某些知识点，通常会去反复的看书籍、问经验丰富的师兄、阅读文献、看博客等。经过这些努力，遗留的问题大部分通常都会得到解决。在阅读网上贴子的时候，大部分帖子都会使用相关内容的许多专业术语，这对阅读造成了一定抑制；还有有些内容只有被文字详述，缺乏相关的图标来生动解释。这是我决定写技术博客的第一个原因，我想在介绍相关内容的时候，会对相应的专业术语作一个通俗的解释，对晦涩的内容努力配上一个生动的图表。
       四个月虽然时间不长，可是通过上课、看书、实践，学了不少的内容。但随着不断学习新东西，之前已经被熟悉的内容或者工具，已经没有了清楚的知识框架和使用熟练技巧；换句话说，自己学过的东西已经不可追溯，只是能模糊记个大概，也就是以前的一部分努力白费了。这是我决定写技术博客的第二原因，我想让我的学习可追溯。
       当然，写技术博客可以可以扩展圈子，和相关领域的朋友们交流，共同提升，努力为开源贡献一份力量。
       开源万岁！