CFS调度分析(内核版本：2.6.34)

1、时间记账

CFS不再有时间片的概念，他维护的是每个进程运行的时间记账

使用调度器实体结构来追踪进程运行记账：

<linux/sched.h>

 

 

 

无数统计变量… …，但是算法核心就是围绕vruntime设计。

 

调度器实体，作为进程的一个名为se的成员变量。

 

 

 

 

 

 

2、虚拟实时

CFS使用vruntime变量来记录一个程序到底运行了多长时间以及他要应该运行多久。

<kernel/sched_fair.c> 中，up_date_curr()实现这个功能。

 

 

update_curr()由系统定时器周期性调用，使得vruntime可以精准测量给定进程的运行时间。

 

 

delta_exec 执行时间，然后根据当前可运行进程总数队运行时间进行加权计算。

__update_curr()

 

3、进程选择

挑选一个最小的vruntime的进程。——红黑树。

 

rb_leftmost存储当前最小的vruntime。无需在红黑树上进行查询。

 

向树中插入进程

在进程变为可运行状态（被唤醒）或者fork()创建进程时，enqueue_entity()实现这个步骤。

 

 

 

先更新当前任务的运行时间和其他统计数据。

 

然后__enqueue_entity() 进行红黑树插入操作。

 

 

 

 

从树中删除进程

当进程阻塞，或者终止时:dequeuer_entity

 

 

同理先更新实时统计数据，然后在进程红黑树中删除。

 

 

 

4、调度器入口

调度器入口函数schedule()，<kernel/sched.c>

 

 

 

以优先级为序，从高到低，一次查看每一个调度类。其中，pick_next_task()，实现会调用pick_next_entity()。

 

 

5、睡眠和唤醒

当不愿意被执行的进程(进行文件I/0操作)进入睡眠状态。

添加睡眠等待队列。

 

 

 

 

 

唤醒：

<kernel/sched.c>

wake_up()调用try_to_wake_up()。

 

 

 

 

6、CFS完全公平调度算法分析

 

参考于

CFS主要由sched_entity 内含的 vruntime所决定，不再跟踪process的sleep time，并扬弃active/expire的概念, runqueue里面所有的进程都平等对待，CFS使用“虚拟运行时”（virtual running time）来表示某个任务的时间量。

CFS改使用算法，将执行时间越少的工作（即 sched_entity）排列在红黑树的左边，时间复杂度是O(log N)，节点（即rb_node）的安插工作则由dequeue_entity()和enqueue_entity（）来完成。当前执行的task通过呼叫 put_prev_task 返回红黑树，下一个待执行的task则由pick_next_task来呼叫。蒙内表示, CFS在百分之八十时间都在确实模拟处理器的处理时间。