一、完全公平调度算法
完全公平调度 CFS 的出发点基于一个简单的理念：进程调度的效果应该如同系统具备一个理想中的完美多任务处理器。在这种系统中，每个进程能够获得 1/n 的处理器时间（n 为可运行进程数）。同时，我们可以调度给它们无限小的时间周期，所以，在任何可测量周期内，我们给予 n 个进程中每个进程同样多的运行时间。
但是，上述模型并不现实，因为我们无法再一个处理器上真的同时运行多个进程。而且，如果每个进程运行无限小的时间周期也并不高效（调度时的进程抢占会带来一定的代价）。因此，虽然我们希望所有的进程能只运行一个非常短的周期（这样会带来较好的交互性），但是 CFS 充分考虑了这样将带来的额外消耗，实现中首先要确保系统性能不受损失。 CFS 的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配时间片的方式。 CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠 nice 值来计算时间片。 nice 值在 CFS 中被作为进程获得的处理器运行比的权重，越高的 nice 值将获得更低的处理器使用比。
接下来，我们将在上述思想下，讨论 CFS 是如何实现的。
二、时间记账
所有的调度器都必须对进程运行时间做记账。多数 Unix 系统通过给进程分配时间片的方式来进行时间记账，每当系统时钟发生变化时，时间片都会被减少一个节拍周期。当一个进程的时间片被减到 0 时，它就会被另一个时间片尚未减到 0 的可运行进程抢占。
我们已经知道，CFS不再有时间片的概念。尽管如此，我们依然需要对每个进程运行的时间记账，以保证每个进程只在公平分配给它的处理器时间内运行。CFS 使用调度器实体结构（sched_entity）来追踪进程运行记账，其定义在 include/linux/sched.h 中：
/* * CFS stats for a schedulable entity (task, task-group etc) * * Current field usage histogram: * * 4 se->block_start * 4 se->run_node * 4 se->sleep_start * 6 se->load.weight */ struct sched_entity { struct load_weight load; // 权重，与优先级有关 struct rb_node run_node; // 红黑树的结点 struct list_head group_node; // 所在进程组 unsigned int on_rq; // 标记是否处于红黑树运行队列中 u64 exec_start; // 进程开始执行的时间 u64 sum_exec_runtime; // 进程运行总时间 u64 vruntime; // 虚拟运行时间 u64 prev_sum_exec_runtime; // 上个调度周期中进程运行的总时间 u64 last_wakeup; u64 avg_overlap; u64 nr_migrations; u64 start_runtime; u64 avg_wakeup; ... ... #ifdef CONFIG_FAIR_GROUP_SCHED struct sched_entity *parent; /* rq on which this entity is (to be) queued: */ struct cfs_rq *cfs_rq; /* rq "owned" by this entity/group: */ struct cfs_rq *my_q; #endif };
调度器实体结构作为一个名为 se 的成员变量，嵌入在进程描述符 task_struct 内。实际上，在 task_struct 结构中，还定义了一个调度器实体结构 sched_rt_entity，这是实时调度的调度器实体。如下：
struct task_struct{ ...... struct sched_entity se; struct sched_rt_entity rt; ...... }
回到 sched_entity 结构。注意到该结构里面有一个元素 vruntime（虚拟运行时间），调度器实体结构就是用这个来对进程运行时间进行记账的。使用 vruntime 进行时间记账的步骤如下：
1）调用 update_curr() 函数，计算当前进程的执行时间，并将结果存放在变量 delta_exec 中；
2）将 delta_exec 作为参数传递给 _update_curr() 函数，该函数将根据当前可运行的进程总数对运行时间进行加权运算；
3）将权值与当前运行进程的 vruntime 相加得到新的 vruntime 值。
update_curr() 函数是由系统定时器周期性调用的，无论进程是处于可运行状态，还是被堵塞处于不可运行状态。根据这种方式，vruntime 可以准确地测量给定进程的运行时间，而且可知道谁应该是下一个被运行的进程。
三、进程选择
当 CFS 需要选择下一个运行进程时，它会挑一个具有最小 vruntime 的进程。CFS 算法的核心就是选择具有最小 vruntime 的任务。CFS 使用红黑树来组织可运行进程队列，并利用其迅速找到最小 vruntime 值（红黑树最左叶子结点）的进程。
CFS 通过调用 _pick_next_entity() 函数来寻找红黑树最左叶子结点，即最小 vruntime 值，如下：
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = cfs_rq->rb_leftmost; // rb_leftmost 字段中缓存着红黑树最左叶子结点的值 if (!left) return NULL; return rb_entry(left, struct sched_entity, run_node); }
_pick_next_entity() 函数本身并不会遍历整个红黑树来寻找最左叶子结点，最左叶子结点的值已经缓存到了 rb_leftmost 字段中，直接调用就行，这样可以节省时间。当没有最左叶子结点（也即没有任何结点）的时候，函数返回值为 NULL，表明没有可运行的进程，此时 CFS 调度器将选择 idle 任务运行。
四、调度器入口
进程调度的主要入口点是函数 schedule()，其定义在 kernel/sched.c 中。它正式内核其他部分用于调度进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。 schedule() 通常都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类（这个调度类需要有自己的可运行队列），然后向这个调度类询问下一个该运行的进程是哪个。
系统通过 schedule() 函数进入进程调度器，然后schedule() 函数调用 pick_next_task() 函数来选择下一个将要执行的进程：
/* * Pick up the highest-prio task: */ static inline struct task_struct * pick_next_task(struct rq *rq) { const struct sched_class *class; struct task_struct *p; /* * Optimization: we know that if all tasks are in * the fair class we can call that function directly: */ if (likely(rq->nr_running == rq->cfs.nr_running)) { p = fair_sched_class.pick_next_task(rq); if (likely(p)) return p; } class = sched_class_highest; for ( ; ; ) { p = class->pick_next_task(rq); // 每个调度类都实现了 pick_next_task()函数，它会返回指向下一个可运行进程的指针，若没有，则返回 NULL
// 从第一个返回非 NULL 值的类中选择下一个可运行进程
if (p) return p; /* * Will never be NULL as the idle class always * returns a non-NULL p: */ class = class->next; } }
picke_next_task() 函数会以优先级为顺序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程。
五、睡眠和唤醒
休眠（被阻塞）的进程处于一个特殊的不可执行状态。如果没有这种状态的话，调度程序就可能选出一个本不愿意被执行的进程，因此，休眠状态是很重要的。进程休眠有多种原因，但肯定都是为了等待一些事件。进程有两种休眠相关的状态：TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE。其中，TASK_INTERRUPTIBLE 在接收到一个信号时，可以被提前唤醒并响应该信号，而后者则会忽略该信号。
当进程把自己标记成休眠状态时，从可执行红黑树中移除，放入等待队列，然后调用 schedule() 选择和执行一个其他进程；唤醒过程刚好相反，进程被设置为执行状态，然后再从等待队列中移到可执行红黑树中。
5.1、等待队列
休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用 wake_queue_head_t 来代表等待队列。等待队列可以通过 DECLARE_WAITQUEUE() 静态创建，也可以由 init_waitqueue_head() 动态创建。进程把自己放入等待队列中并设置为不可执行状态。当与等待队列相关的事件发生时，队列上的进程会被唤醒。进程通过以下几个步骤将自己加入到一个等待队列中：
1）调用宏 DEFINE_WAIT() 创建一个等待队列的项；
2）调用 add_wait_queue() 把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它，通过在事件发生时对等待队列执行 wake_up() 操作；
3）调用 prepare_to_wait() 方法将进程的状态变更为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 。如果有必要的话，会将进程加入到等待队列；
4）若进程被设置为 TASK_INTERRUPTIBLE ，则信号唤醒进程。这就是所谓的伪唤醒（唤醒并不是因为事件的发生），因此检查并处理信号；
5）当进程被唤醒时，它会再次检查条件是否为真。如果为真，则退出循环；否则，再次调用 schedule() 并重复这一步；
6）当条件满足后，进程将自己设置为 TASK_RUNNING 并调用 finish_wait() 方法把自己移除等待队列。
5.2 唤醒
唤醒操作通过函数 wake_up() 进行，它会唤醒指定的等待队列上的所有进程。它调用函数 try_to_wake_up() ，该函数负责将进程设置为 TASK_RUNNING 状态，然后调用 enqueue_task() 将此进程放入红黑树中，如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置 need_resched 标志。另外，关于休眠，存在虚假的唤醒。有时候进程被唤醒并不是因为他所等待的条件达成了，因此需要用一个循环处理来保证等待的条件真正达成（上文中的第5步）。
参考书籍：Linux内核设计与实现（第三版）