CFS调度器
1. 概述
CFS代表“完全公平调度器”，是由Ingo Molnar实现并合并到Linux 2.6.23中的新“桌面”进程调度器。它是替代先前普通调度器SCHED_OTHER交互代码的调度器。
CFS设计的80%可以用一句话概括：CFS基本上在真实硬件上模拟了一个“理想、精确的多任务CPU”。
“理想的多任务CPU”是一个（不存在的 ?) CPU，具有100%的物理能力，可以以精确相等的速度并行运行每个任务，每个任务以1/nr_running的速度运行。例如：如果有2个任务在运行，那么它们每个都以50%的物理能力运行---即实际上是并行运行的。
在真实硬件上，我们一次只能运行一个任务，因此我们必须引入“虚拟运行时间”的概念。任务的虚拟运行时间指定了在上述理想多任务CPU上其下一个时间片段将开始执行的时间。在实践中，任务的虚拟运行时间是其实际运行时间标准化到运行任务总数的结果。
2. 一些实现细节
在CFS中，虚拟运行时间通过每个任务的p->se.vruntime（纳秒单位）值来表示和跟踪。通过这种方式，可以准确地时间戳和测量任务应该获得的“预期CPU时间”。
小细节：在“理想”硬件上，任何时候所有任务都会有相同的p->se.vruntime值---即任务将同时执行，没有任务会从“理想”的CPU时间份额中“失衡”。
CFS的任务选择逻辑基于p->se.vruntime值，因此非常简单：它总是尝试运行具有最小p->se.vruntime值的任务（即到目前为止执行最少的任务）。CFS始终尝试在可运行任务之间尽可能接近“理想多任务硬件”分配CPU时间。
CFS的大部分设计都是基于这个非常简单的概念，还有一些额外的装饰，如优先级、多处理和各种算法变体来识别休眠任务。
3. 红黑树
CFS的设计相当激进：它不使用旧的运行队列数据结构，而是使用一个时间排序的红黑树来构建未来任务执行的“时间线”，因此没有“数组切换”副作用（这是先前的普通调度器和RSDL/SD所受到的）。
CFS还维护rq->cfs.min_vruntime值，这是一个单调递增的值，跟踪运行队列中所有任务中最小的vruntime。系统完成的总工作量通过min_vruntime进行跟踪；该值用于尽可能将新激活的实体放在树的左侧。
运行队列中运行任务的总数通过rq->cfs.load值进行统计，该值是排队在运行队列上的任务权重的总和。
CFS维护一个时间排序的红黑树，其中所有可运行的任务都按照p->se.vruntime键进行排序。CFS选择这棵树中的“最左边”任务并坚持执行。随着系统的前进，执行的任务会被放入树的右侧---慢慢地给每个任务一个机会成为“最左边的任务”，从而在确定的时间内获得CPU。
总之，CFS的工作方式如下：它运行一个任务一点，当任务调度（或调度器发生滴答）时，任务的CPU使用情况被“记录”：它刚刚在物理CPU上使用的（少量）时间被添加到p->se.vruntime中。一旦p->se.vruntime变得足够高，以至于另一个任务成为维护的时间排序红黑树的“最左边的任务”（再加上与最左边任务的“粒度”距离，以便我们不会过度调度任务和破坏缓存），那么新的最左边的任务将被选择，当前任务将被抢占。
4. CFS的一些特性
CFS使用纳秒粒度的计算，不依赖于任何jiffies或其他HZ细节。因此，CFS调度器不像先前的调度器那样具有“时间片”的概念，也没有任何启发式。只有一个中央可调节项（您必须打开CONFIG_SCHED_DEBUG）：
/sys/kernel/debug/sched/base_slice_ns
它可以用于调整调度器从“桌面”（即低延迟）到“服务器”（即良好的批处理）工作负载。它默认设置适用于桌面工作负载。SCHED_BATCH也由CFS调度器模块处理。
由于其设计，CFS调度器不容易受到针对股票调度器启发式的任何“攻击”：fiftyp.c、thud.c、chew.c、ring-test.c、massive_intr.c都可以正常工作，不会影响交互性，并产生预期的行为。
CFS调度器对nice级别和SCHED_BATCH的处理比先前的普通调度器更加强大：这两种工作负载都得到了更积极的隔离。
SMP负载平衡已经重新设计/清理：负载平衡代码中的运行队列遍历假设现在已经消失，调度模块的迭代器被使用。结果，平衡代码变得更简单了。
5. 调度策略
CFS实现了三种调度策略：
-
SCHED_NORMAL（传统上称为SCHED_OTHER）：用于常规任务的调度策略。
-
SCHED_BATCH：不像常规任务那样频繁地抢占，从而允许任务运行更长时间并更好地利用缓存，但代价是交互性较差。这非常适合批处理作业。
-
SCHED_IDLE：这甚至比nice 19还要弱，但它不是一个真正的空闲定时器调度器，以避免陷入优先级倒置问题，这会导致机器死锁。
SCHED_FIFO/_RR是在sched/rt.c中实现的，并且与POSIX规定的一样。
来自util-linux-ng 2.13.1.1的chrt命令可以设置所有这些调度策略，除了SCHED_IDLE。
6. 调度类
新的CFS调度器已经被设计成引入“调度类”，这是一个可扩展的调度器模块层次结构。这些模块封装了调度策略的细节，并由调度器核心处理，而核心代码对它们的假设不多。
sched/fair.c实现了上述的CFS调度器。
sched/rt.c实现了SCHED_FIFO和SCHED_RR的语义，比先前的普通调度器更简单。它使用100个运行队列（用于所有100个RT优先级级别，而不是先前调度器中的140个），并且不需要过期数组。
调度类是通过sched_class结构来实现的，其中包含必须在发生有趣事件时调用的函数的钩子。
这是（部分）钩子的列表：
-
enqueue_task(...)
当任务进入可运行状态时调用。它将调度实体（任务）放入红黑树中，并增加nr_running变量。 -
dequeue_task(...)
当任务不再可运行时，调用此函数以使相应的调度实体不在红黑树中。它减少nr_running变量。 -
yield_task(...)
这个函数基本上只是一个出队，然后是一个入队，除非打开了compat_yield sysctl；在这种情况下，它将调度实体放在红黑树的最右端。 -
check_preempt_curr(...)
此函数检查进入可运行状态的任务是否应该抢占当前正在运行的任务。 -
pick_next_task(...)
此函数选择下一个最合适的任务来运行。 -
set_curr_task(...)
当任务改变其调度类或改变其任务组时，调用此函数。 -
task_tick(...)
此函数大多数情况下是从时间滴答函数调用的；它可能导致进程切换。这驱动了运行的抢占。
7. CFS的组调度器扩展
通常，调度器操作在个别任务上，并努力为每个任务提供公平的CPU时间。有时，将任务分组并为每个任务组提供公平的CPU时间可能是可取的。例如，可能希望首先为系统上的每个用户提供公平的CPU时间，然后再为属于用户的每个任务提供。
CONFIG_CGROUP_SCHED正是为了实现这一点。它允许任务被分组，并在这样的组之间公平地分配CPU时间。
CONFIG_RT_GROUP_SCHED允许对实时（即SCHED_FIFO和SCHED_RR）任务进行分组。
CONFIG_FAIR_GROUP_SCHED允许对CFS（即SCHED_NORMAL和SCHED_BATCH）任务进行分组。
这些选项需要定义CONFIG_CGROUPS，并允许管理员使用“cgroup”伪文件系统创建任意的任务组。有关此文件系统的更多信息，请参阅控制组。
当定义CONFIG_FAIR_GROUP_SCHED时，将为使用伪文件系统创建的每个组创建一个“cpu.shares”文件。请参阅下面的示例步骤，以创建任务组并使用“cgroups”伪文件系统修改它们的CPU份额。
# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu
# mkdir multimedia # create "multimedia" group of tasks
# mkdir browser # create "browser" group of tasks
# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group
# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares
# firefox & # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks
# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks