时间记账
CFS不再有时间片的概念，为了确保每个进程只在公平分配给他的处理器时间内运行，必须为每个进程维护时间记账。调度器实体结构为：
结构体中的vruntime存放的是进程的虚拟运行时间，该值是经过了所有可运行进程综述的标准化计算。以ns为单位，和定时器的节拍不再相关，从而可以实现优先级相同的所有进程的虚拟运行时间是相同的，所有任务都将收到相等的处理器份额。
kernel/sched_fair.c中的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;//当前调度器时间
unsigned long delta_exec;
if(unlikely(!curr))
return;
//获得最后一次修改负载后当前任务所占用的运行总时间并存入delta_exec
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_start_runtime(curtask,delta_exec,curr->vruntime);
cpuacct_charge(curtask,delta_exec);
account_group_exec_runtime(curtask,delta_exec);
}
}
更新运行时间的具体代码为
进程选择
进程调度的最终目的是为了让所有进程的vruntime一致，所以CFS试图利用一个简单的规则来均衡进程的虚拟运行时间，即每次选择最小vruntime的进程运行。所以需要讨论如何选择最小的vruntime进程。
CFS使用红黑树(rbtree)来组织可运行进程队列，具体的红黑树策略在此不进行讨论。
挑选下一个任务
CFS调度器一直寻找红黑树的最左侧的叶子节点，即为vruntime最小的节点。代码比较简单： 
向树中加入进程
进程被唤醒或通过fork()第一次创建进程时将调用enqueue_entity实现向树中插入进程的功能。
static void enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se,int flags){
if(!(flags&ENQUEUE_WAKEUP)||(flags&ENQUEUE_MIGRATE))
se->vruntime += cfs_rq->min_vruntime;//更新min_vruntime之前先更新vruntime
update_curr(cfs_rq);//更新当前任务的运行统计数据
account_entity_enqueue(cfs_rq,se);
if(flags&ENQUEUE_WAKEUP){//进程是被唤醒
place_entity(cfs_rq,se,0);
enqueue_sleeper(cfs_rq,se);
}
update_state_enqueue(cfs_rq,se);
check_spread(cfs_rq,se);
if(se!=cfs_rq->curr)
__enqueue_entity(cfs_rq,se);//正式的插入操作
}
__enqueue_entity函数的具体代码不再贴出，主要就是红黑树的插入算法，如果插入过程中，一直执行的是向左移动，也就是说leftmost标志位保持为1，那么最后插入成功后更新缓存rb_leftmost为当前新插入的进程。在后续的进程选择过程中无需再遍历树。
从树中删除进程
删除进程的操作发生着进程阻塞（不可运行）或终止时（结束运行）
如果删除的是leftmost节点，则通过顺序遍历找到谁是下一个节点
调度器入口
入口点是函数schedule() 定义与kernel/sched.c
是贝博betball网页其他部分用于调用进程调度器的入口：选择哪个进程可以运行，何时投入运行。通常需要和一个具体的调度类相关联，也就是说它会找到一个有自己的可运行队列的最高优先级的调度类，通过队列获取下一个该运行的进程。
schedule()函数唯一重要的事情为调用pick_next_task()函数以优先级为序，依次检查每一个调度类，并从最高优先级的调度类中选择最高优先级的进程。
睡眠和唤醒
休眠（被阻塞）的进程处于一个特殊的不可执行状态，休眠必须以轮询的方式实现。休眠大多是因为需要等待一些事件（如从I/O读取数据，硬件事件，尝试获取一个已被占用的贝博betball网页信号而被迫休眠）
等待队列
是由某些等待事件发生的进程组成的简单链表，贝博betball网页用wake_queue_head_t来表示。可通过DECLARE_WAITQUEUE()静态创建也可以由init_waitqueue_head()动态创建
针对休眠，之前的简单的接口可能会带来竞争条件，可能导致在判断条件变为真以后，进程却开始了休眠。下面的代码段为等待队列的伪代码。等待队列的具体应用实例可见《Linux贝博betball网页设计与实现第三版》P50的fs/notify/inotify/inotify_user.c文件中的inotify_read函数。
DEFINE_WAIT(wait);//创建一个等待进程
add_wait_queue(q,&wait);//将等待进程加入等待队列
while(!condition){//condition为正在等待的事件
prepare_to_wait(&q,&wait,TASK_INTERRUPTIBLES);//将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，若被设置为INTERRUPTILBE，则进程需要去检测并处理信号，不是完全的唤醒，所以被称为是伪唤醒
if(signal_pending(current))
schedule();
}
finish_wait(&q,&wait);//将进程设置为TASK_RUNNING并将自己移除等待队列。
进程被唤醒或通过fork()第一次创建进程时将调用enqueue_entity实现向树中插入进程的功能。
static void enqueue_entity(struct cfs_rq *cfs_rq,struct sched_entity *se,int flags){
if(!(flags&ENQUEUE_WAKEUP)||(flags&ENQUEUE_MIGRATE))
se->vruntime += cfs_rq->min_vruntime;//更新min_vruntime之前先更新vruntime
update_curr(cfs_rq);//更新当前任务的运行统计数据
account_entity_enqueue(cfs_rq,se);
if(flags&ENQUEUE_WAKEUP){//进程是被唤醒
place_entity(cfs_rq,se,0);
enqueue_sleeper(cfs_rq,se);
}
update_state_enqueue(cfs_rq,se);
check_spread(cfs_rq,se);
if(se!=cfs_rq->curr)
__enqueue_entity(cfs_rq,se);//正式的插入操作
}
__enqueue_entity函数的具体代码不再贴出，主要就是红黑树的插入算法，如果插入过程中，一直执行的是向左移动，也就是说leftmost标志位保持为1，那么最后插入成功后更新缓存rb_leftmost为当前新插入的进程。在后续的进程选择过程中无需再遍历树。
从树中删除进程
删除进程的操作发生着进程阻塞（不可运行）或终止时（结束运行）
如果删除的是leftmost节点，则通过顺序遍历找到谁是下一个节点
调度器入口
入口点是函数schedule() 定义与kernel/sched.c
是贝博betball网页其他部分用于调用进程调度器的入口：选择哪个进程可以运行，何时投入运行。通常需要和一个具体的调度类相关联，也就是说它会找到一个有自己的可运行队列的最高优先级的调度类，通过队列获取下一个该运行的进程。
schedule()函数唯一重要的事情为调用pick_next_task()函数以优先级为序，依次检查每一个调度类，并从最高优先级的调度类中选择最高优先级的进程。
睡眠和唤醒
休眠（被阻塞）的进程处于一个特殊的不可执行状态，休眠必须以轮询的方式实现。休眠大多是因为需要等待一些事件（如从I/O读取数据，硬件事件，尝试获取一个已被占用的贝博betball网页信号而被迫休眠）
等待队列
是由某些等待事件发生的进程组成的简单链表，贝博betball网页用wake_queue_head_t来表示。可通过DECLARE_WAITQUEUE()静态创建也可以由init_waitqueue_head()动态创建
针对休眠，之前的简单的接口可能会带来竞争条件，可能导致在判断条件变为真以后，进程却开始了休眠。下面的代码段为等待队列的伪代码。等待队列的具体应用实例可见《Linux贝博betball网页设计与实现第三版》P50的fs/notify/inotify/inotify_user.c文件中的inotify_read函数。
DEFINE_WAIT(wait);//创建一个等待进程
add_wait_queue(q,&wait);//将等待进程加入等待队列
while(!condition){//condition为正在等待的事件
prepare_to_wait(&q,&wait,TASK_INTERRUPTIBLES);//将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，若被设置为INTERRUPTILBE，则进程需要去检测并处理信号，不是完全的唤醒，所以被称为是伪唤醒
if(signal_pending(current))
schedule();
}
finish_wait(&q,&wait);//将进程设置为TASK_RUNNING并将自己移除等待队列。
是由某些等待事件发生的进程组成的简单链表，贝博betball网页用wake_queue_head_t来表示。可通过DECLARE_WAITQUEUE()静态创建也可以由init_waitqueue_head()动态创建
针对休眠，之前的简单的接口可能会带来竞争条件，可能导致在判断条件变为真以后，进程却开始了休眠。下面的代码段为等待队列的伪代码。等待队列的具体应用实例可见《Linux贝博betball网页设计与实现第三版》P50的fs/notify/inotify/inotify_user.c文件中的inotify_read函数。
DEFINE_WAIT(wait);//创建一个等待进程
add_wait_queue(q,&wait);//将等待进程加入等待队列
while(!condition){//condition为正在等待的事件
prepare_to_wait(&q,&wait,TASK_INTERRUPTIBLES);//将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，若被设置为INTERRUPTILBE，则进程需要去检测并处理信号，不是完全的唤醒，所以被称为是伪唤醒
if(signal_pending(current))
schedule();
}
finish_wait(&q,&wait);//将进程设置为TASK_RUNNING并将自己移除等待队列。