Chapter 4

http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/

schedule()采用面向对象思想，通过sched_class结构允许多种scheduler classes。POSIX将非实时调度policy称为SCHED_OTHER，也就是Linux中的SCHED_NORMAL，指的就是CFS，在sched_fair.c中实现。POSIX定义了一系列sched_XXX()系统调用用于读取和设置一个进程如何被调度。Linux提供chrt命令to manipulate real-time attributes of a process，taskset命令to retrieve or set a process's CPU affinity。

每个调度类有一个优先级，实时调度的优先级最高，idle class最低。Linux对实时进程的调度方法是，采用round robin调度最高优先级进程，而不理会其余进程。schedule()通过pick_next_task()，从高到低调用各scheduler class自己的pick_next_task()函数，直到某一class返回一个runnable process。

CFS的核心思想：不使用复杂的算法来调整进程的优先级，而是尽量保证所有进程公平的分得CPU的使用权。这样一个I/O bound process自然不会用满它的配额，当它可调度时，就会抢占其它CPU bound processes。可参考Documentation/scheduler/sched-design-CFS.txt。

理想情况下，每个进程同时使用CPU，各分得1/n的计算能力。他们的运行时间是相等的，因为是理想情况，称为virtual runtime，实际的计算方法为its actual runtime normalized to the total number of running tasks，由task_struct的se->vruntime记录。为了模拟理想情况，CFS总是调度vruntime最小的任务，通过RB tree维护。通过__pick_first_entity()的代码看出，最小的节点由cfs_rq->rb_leftmost缓存，从O(logN)的时间减少为O(1)。

每个进程获得的时间片，由一个总时间片（称为target lantency）除以总进程数再根据nice值加权决定，但至少长为minimum granularity。这些值在打开CONFIG_SCHED_DEBUG时，允许我们通过sysctl修改。

update_curr() is invoked periodically by the system timer and also whenever a process becomes runnable or unrunnable. 首先根据rq_of(cfs_rq)->clock_task算出当前时间，减去curr->exec_start得到delta_exec，然后调用calc_delta_fair()算出delta_exec_weighted（nice值为0时它就等于delta_exec），加到curr->vruntime。

CFS的还维护一个cfs_rq->min_vruntime，a monotonic increasing value tracking the smallest vruntime among all tasks in the runqueue，这样新创建的进程的vruntime加上这个min_vruntime才能保证时间的正确性。

进程通过__wake_up()唤醒，而try_to_wake_up()会调用enqueue_task()最终到enqueue_task_fair()再到enqueue_entity()。移除的操作则由dequeue_entity()完成。

在进程时间片用完，或内核在唤醒某进程时发现其优先级高于当前进程时，会设置need_resched标志。内核在返回用户态前可以返回到当前进程或调度其它进程，这在内核看来没什么区别，因此它会检查need_resched标志来判断是否需要调用schedule()来调度另一进程。内核本身也通过一个计数器preempt_count来记录获得了多少个锁，当计数器归0时，内核也是可以被抢占的，发生的时机在从中断处理返回到内核态时，以及释放所有锁时。

内核为每个CPU起了一个migration内核线程，当系统调用sched_setaffinity()发生时，它会负责将进程迁移到合法的CPU上。