阅读材料cfs调度算法介绍

1、CFS 算法介绍一、 概述首先简单介绍一下基本的设计思路。CFS 思路很简单，就是根据各个进程的权重分配运行时间。进程的运行时间计算公式为：分配给进程的运行时间 = 调度周期 * 进程权重 / 所有进程权重之和(公式 1)调度周期，就是将所有处于 TASK_RUNNING 态进程都调度一遍的时间，差不多相当于 O(1)调度算法中运行队列和过期队列切换一次的时间。举个例子，比如只有两个进程 A、B，权重分别为 1 和 2，调度周期设为 30ms，那么分配给A 的CPU 时间为 30ms * (1/(1+2) = 10ms 而B 的CPU 时间为 30ms * (2/(1+2) = 20ms 那么

2、在这 30ms 中 A 将运行 10ms，B 将运行 20ms。调度的公平并不体现在实际运行时间上，而是体现在另外一个量上面：虚拟运行时间（vruntime）。实际运行时间到 vruntime 的换算公式：vruntime = 实际运行时间 * 1024 / 进程权重(公式 2)这里直接写 1024， 实际上它等于 nice 为 0 的进程的权重，代码中是 NICE_0_LOAD。也就是说，所有进程都以 nice 为 0 的进程的权重 1024 作为基准，计算自己的 vruntime 增加速度。还以上面 AB 两个进程为例，B 的权重是 A的 2 倍，那么 B 的 vruntime 增加速度只

3、有 A 的一半。现在把公式 2 中的实际运行时间用公式 1 来替换，可以得到如下结果：vruntime = (调度周期 * 进程权重 / 所有进程总权重) * 1024 / 进程权重= 调度周期 * 1024 / 所有进程总权重(公式 3)所有进程 vruntime 增长速度是一样的，这就是“公平”。CFS 算法利用 vruntime 来选择运行的进程，谁的 vruntime 值较小就说明它以前占用 cpu 的时间较短，受到了“”对待，因此下一个运行进程就是它。这样既能公平选择进程，又能保证高优先级进程获得较多的运行时间。这就是 CFS 的主要。补充一下权重的来源，权重跟进程 nice 值之间

4、有一一对应的关系，可以通过全局数组 prio_to_weight 来转换，nice 值越大，权重越低。另外，与之前的 Linux 调度器不同，CFS 没有将任务在运行队列中，树 是一个树，CFS了一个以 vruntime 为顺序的树（参见图 1 ）。具有很多有趣、有用的属性。首先，它是自平衡的，这意味着树上没有路径比任何其他路径长两倍以上。 第二，树上的操作时间复杂度为 O(log n) （ n 是树点的数量）。这意味着可以快速高效地或删除任务。1图 1任务在以时间为顺序的树中（由 sched_entity 对象表示），对处理器需求最多的任务 （vruntime 最低）在树的左侧，处理器需求最

5、少的任务（vruntime 最高）在树的右侧。 调度器选取树最左端的节点调度为下一个以便保持公平性。被调度下 CPU 的任务，将其运行时间添加到其 vruntime，然后如果任务可运行，再插回到树中。树的内容从右侧迁移到左侧以保持公平。因此，每个可运行的任务都会追赶其他任务以维持整个可运行任务集合的执行平衡。2二、 重要数据结构三个与调度相关的重要数据结构：task_struct：任务描述符（进程描述符） sched_entity：调度实体 sched_class：调度策略Linux 内的所有任务都由称为 task_struct 的任务结构表示。该结构（以及其他相关内容）完整地描述了任务并包括

6、了任务的当前状态、其堆栈、进程标识、优先级（静态和动态）等等。可以在 ./linux/include/linux/sched.h 中找到这些内容。但是因为不是所有任务都是可运行的，在 task_struct 中不会发现任何与 CFS相关的字段。相反，会有一个名为 sched_entity 的新结构来图 2）。调度信息（参见图 2CFS去掉了 struct prio_array，并引入调度实体（scheduling entity）和调度类（scheduling classes），分别由 struct sched_entity 和 struct sched_class 定义。因此，task_str

7、uct 包含关于 sched_entity 和 sched_class 这两种结构的信息：1. task_struct 结构3struct task_struct /* Defined in 2.6.23:/usr/include/linux/sched.h */.-struct prio_array *array;struct sched_entity 该结构包含了完整的信息，用于实现对单个任务或任务组的调度。它可用于实现组调度。调度实体可能与进程没有关联。2. sched_entity 结构struct sched_class 该调度类类似于一个模块链，协助内核调度程序工作。每个调度程序模

8、块需要实现 struct sched_class建议的一组函数。3. sched_class结构4struct sched_class /* Defined in 2.6.23:/usr/include/linux/sched.h */ struct sched_class *next;void (*enqueue_task) (struct rq *rq， struct task_struct *p，wakeup);void (*dequeue_task) (struct rq *rq， struct task_struct *p，sleep); void (*yield_task) (st

9、ruct rq *rq， struct task_struct *p);void (*check_preempt_curr) (struct rq *rq， struct task_struct *p);struct task_struct * (*pick_next_task) (struct rq *rq);void (*put_prev_task) (struct rq *rq， struct task_struct *p);unsigned long (*load_balance) (struct rq *this_rq，this_cpu， struct rq *busiest，uns

10、igned long max_nr_move， unsigned long max_load_move， struct sched_*sd， enum cpu_idle_type idle，*all_pinned，*this_best_prio);void (*set_curr_task) (struct rq *rq);void (*task_tick) (struct rq *rq， struct task_struct *p); void (*task_new) (struct rq *rq， struct task_struct *p);struct sched_entity /* D

11、efined in 2.6.23:/usr/include/linux/sched.h */long wait_runtime; /* Amount of time the entity must run toe compley */* fair and balanced.*/s64 fair_key;struct load_weight load;/* for load-balancing */struct rb_node run_node;/* To be part of Red-black tree data structure */ unsignedon_rq;.;+ struct s

12、ched_entity se;+ struct sched_class *sched_class;.;3 中的函数：enqueue_task：当某个任务进入可运行状态时，该函数将得到调用。它将树中，并对 nr_running 变量加 1。调度实体（进程）放入dequeue_task：当某个任务退出可运行状态时调用该函数，它将从中去掉对应的调度实体，并从 nr_running 变量中减 1。树yield_task：在 compat_yield sysctl 关闭的情况下，该函数实际上执行先出队队；在这种情况下，它将调度实体放在树的最右端。check_preempt_curr：该函数将检查当前运行

13、的任务是否被抢占。在实际抢占正在运行的任务之前，CFS 调度程序模块将执行公平性测试。这将驱动唤醒式（wakeup）抢占。pick_next_task：该函数选择接下来要运行的最合适的进程。 load_balance：每个调度程序模块实现两个函数，load_balance_start() 和 load_balance_next() ，使用这两个函数实现一个迭代器，在模块的 load_balance 例程中调用。内核调度程序使用这种方法实现由调度模块管理的进程的负载平衡。set_curr_task：当任务修改其调度类或修改其任务组时，将调用这个函数。 task_tick：该函数通常调用自 tim

14、e tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占。task_new：内核调度程序为调度模块提供了管理新任务启动的机会。CFS调度模块使用它进行组调度，而用于实时任务的调度模块则不会使用这个函数。运行队列中与 CFS 有关的字段对于每个运行队列，都提供了一种结构来保存相关树的信息。4. cfs_rq结构5struct cfs_rq /* Defined in 2.6.23:kernel/sched.c */ struct load_weight load;unsigned long nr_running;s64 fair_clock; /* runqueue wide

15、 global clock */ u64 exec_clock;s64 wait_runtime; u64 sleeper_bonus;unsigned long wait_runtime_overruns， wait_runtime_underruns;struct rb_root tasks_timeline; /* Pos to the root of the rb-tree*/struct rb_node *rb_leftmost; /* Pos to mosigible task to give the CPU */ struct rb_node *rb_load_balance_c

16、urr;#ifdef CONFIG_FAIR_GROUP_SCHEDstruct sched_entity *curr; /* Currently running entity */struct rq *rq;/* cpu runqueue to which this cfs_rq is attached */.;6.#endif;三、 具体调度过程（代码）3.1 进程创建主要流程：Linux 创建进程使用 fork 或者 clone 或者 vfork 等系统调用，最终都会到do_fork。如果没有设置 CLONE_STOPPED，则会进入 wake_up_new_task 函数。wake_u

17、p_new_tasktask_new_fairplace_entitycheck_preempt_currwakeup_preempt_entitytask_new_fairplace_entity 是更新新进程的 vruntime 值，以便把它树。它以 cfs 队列的 min_vruntime 为基准，再加上进程在一次调度周期中所增长的虚拟运行时（sched_vslice）。这里把进程的已经运行时间设为一个较大的值，这样做的原因是：假设新进程都能获得最小的 vruntime(min_vruntime)，那么新进程会第一个被调度运行，这样程序员就能通过不断的 fork 新进程来让自己的程序一直

18、占据 CPU，这显然是不合理的。min_vruntime这是每个 cfs 队列一个的变量，它一般小于等于所有就绪态进程的最小vruntime，也有例外，比如对睡眠进程进行时间补偿会导致 vruntime小于 min_vruntime。至于 sched_vslice 计算细节暂且不细看，大体上说就是把概述中给出的两个公式结合起来如下：sched_vslice = (调度周期 * 进程权重 / 所有进程总权重) * NICE_0_LOAD /进程权重也就是算出进程应分配的实际 cpu 时间，再把它转化为 vruntime。把这个 vruntime 加在进程上之后，就相当于认为新进程在这一轮调度中已

19、经运行过了。新进程的 vruntime 确定之后有一个判断，同时满足以下几个条件时，交换父子进程的 vruntime：1.2.3.4.sysctl 设置了子进程优先运行fork 出的子进程与父进程在同一个 cpu 上父进程不为空父进程的 vruntime 小于子进程的 vruntime最后，调用 enqueue_task_fair 将新进程CFS树中。check_preempt_curr这个函数就直接调用了 check_preempt_wakeup。首先是有两个指针与进程调度策略有很大关系，last 和 next。如果这两个指针不为 NULL，那么 last 指向最近被调度出去的进程，next

20、 指向被调度上 cpu 的进程。例如 A 正在运行，被 B 抢占，那么 last 指向 A，next 指向 B。当 CFS 在调度点选择下一个运行进程时，会优先照顾这两个进程。这两个指使用一次，就是在上面这个函数退出后，返回用户空间时会触发 schedule，7在那里选择下一个调度进程时会优先选择 next，次优先选择 last，选择完后，就会清空这两个指针。这样设计的原因是，在上面的函数中检测结果是可以抢占并不代表已经抢占，而只是设置了调度标志，在最后触发 schedule 时抢占进程 B 并不一定是最终被调度的进程。因为判断能否抢占的根据是 vruntime 小，但树中可能有比抢占进程 B

21、 的 vruntime 更小的进程 C，这样在调度时就会选中 C 而不是 B。但是当然希望优先调度 B，因为就是为了运行 B 才设置了调度标志，所以用 next 指针指向 B，以便给 B 一定优待，如果 B 的 vruntime 太大，那还是继续运行被抢占进程 A 比较合理，因此 last 指向被抢占进程，因此这里对 A 也是有一点优待，如果被抢占进程 A 的 vruntime 也太大，只好从树中挑一个vruntime 最小的了。不管 next 和 last 指向的进程是否被成功调度，一旦选出下一个进程，就立刻清空这两个指针。然后调用 wakeup_preempt_entity 检测是否满足抢

22、占条件，如果满足（返回值为 1）则对当前进程设置 TIF_NEED_RESCHED 标志，在退出系统调用时会触发 schedule 函数进行进程切换。wakeup_preempt_entity(se， pse)，如何判断后者是否能够抢占前者？这个函数返回-1 表示新进程 vruntime 大于当前进程，当然不能抢占；返回 0表示虽然新进程 vruntime 比当前进程小，但是没有小到超过调度粒度，一般也不能抢占；返回 1 表示新进程 vruntime 比当前进程小的超过了调度粒度，可以抢占。调度粒度假设进程A 和B 的vruntime 很接近，那么 A 先运行了一个tick， vruntime

23、 比 B 大了，B 又运行一个 tick，vruntime 又比 A 大了，又切换到 A，这样就会在 AB 间频繁切换，对性能影响很大，因此如果当前进程的时间没有用完，就只有当有进程的 vruntime 比当前进程小超过调度粒度时，才能进行进程切换。3.2 进程被唤醒主要看函数 try_to_wake_up。该函数会调用相关函数计算进程的 vruntime 并将其树。需要注意的是 try_to_wake_up 也会调用 place_entity 来计算 vruntime，但是与新建进程走不同的条件分支。设想一个任务睡眠了很长时间，它的 vruntime 就一直不会更新，这样当它醒来时 vrun

24、time 会远远小于运行队列上的任何一个任务，于是它会长期占用 CPU，这显然是不合理的。所以这要对唤醒任务的 vruntime 进行一些调整，可以看到，这里是用min_vruntime 减去一个thresh，这个 thresh 的计算过程就是将sysctl_sched_latency换算成进程的 vruntime，而这个 sysctl_sched_latency 就是默认的调度周期，单核 CPU 上一般为 20ms。之所以要减去一个值是为了对睡眠进程做一个补偿，能让它醒来时可以快速得到 CPU。这个设计非常聪明，以前 O(1)调度器有一个复杂的公式，用来区分交互式进CPU 密集型进程，参考

25、ULK 等书，而现在 CFS 无须再使用那个复杂的公式了，只要是常睡眠的进程，它被唤醒时一定会有很小的 vruntime，可以立刻运行，省却了很多特殊情况的处理。同时还要注意代码中提到 ensure we never gain time by being placed8backwards，本来这里是给因为长时间睡眠而 vruntime 远远小于 min_vruntime 的进程补偿的，但是有些进程只睡眠很短时间，这样在它醒来后 vruntime 还是大于 min_vruntime，不能让进程通过睡眠获得额外的运行时间，所以最后选择计算出的补偿时间与进程原本 vruntime 中的较大者。3.3

26、 主动调度进程调度函数 schedule。下面这两个语句是调度算法的重点： prev-sched_class-put_prev_task(rq, prev);next = pick_next_task(rq, prev);首先看 put_prev_task，它等于 put_prev_task_fair，后者基本上就是直接调用 put_prev_entity。再回到 schedule pick_next_task_fair。中看看 pick_next_task 函数， 基本上也就是直接调用91. sic struct task_struct *pick_next_task_fair(struct

27、 rq *rq) 2. 3.struct task_struct *p;1. sic void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev) 2. 3./* If still on the runqueue then deactivate_task()* was not called and update_curr() has to be done:6.*/记得这里的 on_rq 吗？在 schedule 函数中如果进程状态不是 TASK_RUNNING，/那么会调用 deactivate_task 将 pr

28、ev 移出运行队列，on_rq 清零。因此这里也是只有当/prev 进程仍然在运行态的时候才需要更新 vruntime 等信息。/如果 prev 进程因为被抢占或者因为时间到了而被调度出去则 on_rq 仍然为 1if (prev-on_rq)update_curr(cfs_rq);check_spread(cfs_rq, prev);/这里也一样，只有当 prev 进程仍在运行状态的时候才需要更新 vruntime 信息/实际上正在 cpu 上运行的进程是不在树中的，只有在等待 CPU 的进程才在树/因此这里将调度出的进程重新加入树。on_rq 并不代表在树中，而代表在运行状态if (pre

29、v-on_rq) update_ss_wait_start(cfs_rq, prev);/* Put current backo the tree. */这个函数就是把进程以(vruntime-min_vruntime)为 key 加入到树中 enqueue_entity(cfs_rq, prev);22./没有当前进程了，这个当前进程将在 pick_next_task 中更新cfs_rq-curr = NULL;25. 主要看下 pick_next_entity 和 set_next_entity。101. sic struct sched_entity *pick_next_entity(

30、struct cfs_rq *cfs_rq) 2. / pick_next_entity 就是直接选择树缓存的最左结点，也就是 vruntime 最小的结点struct sched_entity *se = pick_next_entity(cfs_rq);/下面的 wakeup_preempt_entity 已经讲过，忘记的同学可以到上面看下/这里就是前面所说优先照顾 next 和 last 进程，只有当 pick_next_entity 选出来的进程/的 vruntime 比 next 和 last 都小超过调度粒度时才轮到它运行，否则就是 next 或者 lastif (cfs_rq-n

31、ext & wakeup_preempt_entity(cfs_rq-next, se) next;if (cfs_rq-last & wakeup_preempt_entity(cfs_rq-last, se) last;return se;13. sic voidset_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)16. /* current is not kept withhe tree. */if (se-on_rq) * Any task has to be enqueued before it get to

32、execute on* a CPU. So account for the time it spent waiting on the* runqueue.22.*/update_ss_wait_end(cfs_rq, se);/就是把结点从树上取下来。前面，占用 CPU 的进程不在树上 dequeue_entity(cfs_rq, se);26.update_ss_curr_start(cfs_rq, se);cfs_rq-curr = se; /OK，在 put_prev_entity 中清空的 curr 在这里被更新struct cfs_rq *cfs_rq = &rq-cfs;struc

33、t sched_entity *se;if (unlikely(!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;17. 3.4 时钟中断主要函数是 entity_tick，entity_tick 函数就是更新状态信息，然后检测是否满足抢占

34、条件。更新信息是通过调用 update_curr(cfs_rq)来完成的。111. sic void update_curr(struct cfs_rq *cfs_rq) 2. struct sched_entity *curr = cfs_rq-curr;u64 now = rq_of(cfs_rq)-clock; /这个 clock 刚刚在 scheduler_tick 中更新过unsigned long delta_exec;6./* Get the amount of time the current task was running* since the last time we c

35、hanged load (this cannot* overflow on 32 bits):10.*/exec_start的是上一次调用update_curr 的时间用当前时间减去exec_start/就得到了从上次计算 vruntime 到现在进程又运行的时间，用这个时间换算成 vruntime/然后加到 vruntime 上，这一切是在 update_curr 中完成的delta_exec = (unsigned long)(now - curr-exec_start); update_curr(cfs_rq, curr, delta_exec);curr-exec_start = no

36、w;if (entity_is_task(curr) struct task_struct *curtask = task_of(curr);ccct_charge(curtask, delta_exec);account_group_exec_runtime(curtask, delta_exec);21.22. 23. /* Update the current tasks runtime sistics. Skip current taskst* are not in our scheduling class.26. */sic inline void update_curr(struc

37、t cfs_rq *cfs_rq, struct sched_entity *curr,unsigned long delta_exec)30. unsigned long delta_exec_weighted;/前面说的 sum_exec_runtime 就是在这里计算的，它等于进程从创建开始占用 CPU 的总时间/将进程运行总时间保存到 prev_.中，这样进程本次调度的运行时间可以用下面公式计算：/进程本次运行已占用 CPU 时间 = sum_exec_runtime - prev_sum_exec_runtime/这里 sum_exec_runtime 会在每次时钟 tick 中更新se-prev_sum_exec_runtime = se-sum_exec_runtime;33. 更新完 CFS 状态之后回到 entity_tick 中，这时需要检