本文结构
前面4节先展开讲讲linux内核2.6.24版本的调度器实现，其中包括CFS调度器。
然后对linux历史上出现过的O(1)和O(n)调度器做一个比较，看看它们的优缺点。
优先级和调度策略
linux中进程优先级在用户试图和内核视图两个方面有着不同表达。
在用户层面，对普通进程优先级的描述通常由nice值给出， nice值的范围为[-20,19]，nice值越高表示进程优先级越高（“nice的进程，竞争不过不nice的进程 ” ：））。而对实时进程，它的nice值实际上没有太多参考价值，普通进程是永远不可能竞争地过实时进程的。
在内核层面，进程的优先级的范围在[0,139], 其中的[100,129]留给普通进程，且一一映射进程的nice值范围，而[0, 99]这个范围的优先级是分配给实时进程的。
在taks_struct结构中，存在着四个关于优先级的属性：
struct task_struct {
// ...
int prio, static_prio, normal_prio;
unsigned int rt_priority;
- static_prio : 静态优先级，进程启动的时候就被分配
- normal_prio: 普通优先级，通过静态优先级和调度策略计算得来的优先级
- prio : 动态优先级，这才是调度器进行调度的参照。由于可能优先级继承而暂时提高进程优先级，所以在normal_prio之外还有prio这个动态优先级
- rt_priority: 实时进程的优先级
Linux2.6.24内核中有五个调度策略
#define SCHED_NORMAL 0 // 普通进程
#define SCHED_BATCH 3 // 批处理进程，那些计算密集型的进程，对交互性要求不高的进程可以使用这个调度策略
#define SCHED_IDLE 5 // 没有其他进程可以调度时，调度这个
#define SCHED_FIFO 1
#define SCHED_RR 2
其中使用前三个策略的进程由CFS调度器进行调度，后两个策略属于实时进程的策略，由RT调度器调度。而且实时进程的调用优先级一定高于普通进程，具体怎么做的，见下文的pick_next_task函数。
数据结构
调度实体
在2.6.24内核中，task_struc结构中内嵌了一个struct sched_entity结构，字面意思就是“可调度实体”，
struct sched_entity {
struct load_weight load; /* for load-balancing */
struct rb_node run_node; // 红黑树节点，由cfs调度器链入一个红黑数运行队列
struct list_head group_node; // 队列节点，由rt sched类链入一个运行队列
unsigned int on_rq; // 该调度实体是否在运行队列中
u64 exec_start;
u64 sum_exec_runtime; // 该调度实体总共的物理运行时间
u64 vruntime; // 虚拟运行时间， 由cfs计算和使用
u64 prev_sum_exec_runtime; // sum_exec_runtime - prev_sum_exec_runtime得到此次的运行时间
// ...其他的一些统计参数
};
调度队列
调度队列由struct rq这个数据结构标识，且每一个CPU都有自己的一个调度队列
struct rq {
/* runqueue lock: */
spinlock_t lock;
unsigned long nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
/* capture load from *all* tasks on this cpu: */
struct load_weight load;
unsigned long nr_load_updates;
u64 nr_switches;
u64 nr_migrations_in;
struct cfs_rq cfs;
struct rt_rq rt;
unsigned long nr_uninterruptible;
struct task_struct *curr, *idle;
unsigned long next_balance;
struct mm_struct *prev_mm;
u64 clock;
atomic_t nr_iowait;
};
rq就是对可调度队列的一个抽象，其中
struct cfs_rq cfs;
struct rt_rq rt;
这两个成员变量，就是真正存放调度队列的，可以看到一个可调度队列可有cfs队列和rt队列共同组成，其中cfs队列管理一个红黑树每个红黑树节点表示一个普通进程（看看之前的sched_entity.run_node, 每个可调度实体通过这个属性挂载到红黑树上），而rt队列则管理一个链表，每个节点都是表示一个实时进程。
调度类
2.6.24内核的具体调度工作（也就是选择下一个要执行的进程）是由各个不同的具体调度类完成的，为了代码的可维护和可扩展性，内核首先定义了一个抽象的调度器类型：
struct sched_class {
const struct sched_class *next; // 指向下一个具体的调度类
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
void (*yield_task) (struct rq *rq);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
struct task_struct * (*pick_next_task) (struct rq *rq);
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
void (*set_curr_task) (struct rq *rq);
// 每次由时钟调度器调用，可能会将task_struct中的need_reched字段置1
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
void (*task_new) (struct rq *rq, struct task_struct *p);
void (*switched_from) (struct rq *this_rq, struct task_struct *task,
int running);
void (*switched_to) (struct rq *this_rq, struct task_struct *task,
int running);
void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
int oldprio, int running);
unsigned int (*get_rr_interval) (struct task_struct *task);
};
所有的具体调度器类都是该类的一个对象，且分别有它们自己的函数指针。
比如fair_sched_class类，它就是linux中的CFS调度器，
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_new = task_new_fair,
.prio_changed = prio_changed_fair,
.switched_to = switched_to_fair,
.get_rr_interval = get_rr_interval_fair,
};
再比如rt_sched_class类，它是linux中的实时进程的调度器，是所有调度器（之上在2.6.24核中，是这样的）中优先级最高的具体调度类对象。
static const struct sched_class rt_sched_class = {
.next = &fair_sched_class, // rt_sched_class的下一个调度类是cfs调度类
.enqueue_task = enqueue_task_rt,
.dequeue_task = dequeue_task_rt,
.yield_task = yield_task_rt,
.check_preempt_curr = check_preempt_curr_rt,
.pick_next_task = pick_next_task_rt,
.put_prev_task = put_prev_task_rt,
.set_curr_task = set_curr_task_rt,
.task_tick = task_tick_rt,
.get_rr_interval = get_rr_interval_rt,
.prio_changed = prio_changed_rt,
.switched_to = switched_to_rt,
};
调度类的优先级通过宏sched_class_highest，以及sched_class中的next指针实现
#define sched_class_highest (&rt_sched_class)
这个宏的字面意思就是取得优先级最高的调度类，如上所示，最高优先级的调度类是实时调度类。
而sched_class的next指针指向比自己低一级优先级的调度类，就如上面的rt_sched_class.next = &fair_sched_class一样。
2.6.24内核中有三个调度类，按照优先级排序依次为：
rt_sched_class -> fair_sched_class -> idle_sched_class -> NULL
进程的调度类是在fork创建进程时就设置好了的：
p->prio = current->normal_prio; // 子进程的动态优先级初始为父进程的的普通优先级
if (!rt_prio(p->prio)) // 如果优先级不在实时进程的范围内，则该为cfs调度器
p->sched_class = &fair_sched_class;
注意， 子进程的动态优先级初始为父进程的的普通优先级，因为有可能父进程的动态优先级被暂时提高了（如果使用了rt_mutex可能会发生优先级继承，以缓解优先级反转现象）。
schedule函数
schedule函数是linux中进程调度的核心函数，只要涉及到进程调度，就需要调用它，它是操作系统进行调度的入口函数。shedule函数其实不是这里的重点，而是它调用的pick_next_task，这个函数将选择下一个优先级最高的进程来执行。
pick_next_task的代码如下所示：
pick_next_task(struct rq *rq)
{
const struct sched_class *class;
struct task_struct *p;
// 这是一个优化措施
// 如果运行队列中的可调度实体的数量等于cfs队列的调度实体数量，
// 表示该队列中只有普通进程，没有实时进程
// 因此直接使用fair_sched_class来选择下一个要调用的进程
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);
if (p)
return p;
/*
* Will never be NULL as the idle class always
* returns a non-NULL p:
*/
class = class->next; // 按照优先级遍历调度类
}
}
还是比较简单的，因为它把所有繁重的代码都交给了具体的调度类去处理。
总体思想就是，按优先级的高低遍历调度器类，使用具体调度类的pick_next_task选出下一个要运行的进程。
函数的最上方还有一个针对cfs调度器的优化措施。
CFS调度类
首先明确，完全公平调度是对普通进程来讲的“完全公平”调度，实时进程的调度优先级始终比普通进程的优先级高。所以CFS调度类调度的都是普通进程，不涉及实时进程。
CFS（Completely Fair Scheduler）自如其名，即为完全公平调度器，旨在对每个进程一视同仁。但是，即时是普通进程，他们的优先级有高也有低，同时调度器应该多照顾IO密集型任务，那么这里说的公平是指什么公平？指的是虚拟时间vruntime的相同：
vruntime = 实际运行时间 * 1024 / 进程权重
其中进程权重由nice值转换而来，nice值越低，权重值越高：
如果忽略系数，那么CFS的目标就使得进程的实际运行时间与进程权重的比值相同。
在具体实现上，linux使用红黑树维护每个进程的vruntime，红黑树O(logn)复杂度的插入、查找、删除操作是CFS的基础。位于红黑树左侧的节点vruntime相对较低，调度器选择vruntime值小的的进程运行一段时间后，随着实际运行时间的增加，vruntime也会增加，红黑树节点将慢慢向右移动。
从直觉上理解一下CFS，对于那些优先级高的进程，虽然它们的实际运行时间可能一直在增加，但是由于分母较大，所以它们向右移动的趋势比优先级低的进程小。对于那些IO密集型的进程，它们的实际运行时间就很少，所以也倾向于一直待在红黑树的左侧。所以CFS比较均衡地同时考虑了优先级和IO密集型进程。
O(n) 、O(1)调度器及它们的优缺点
linux在有过三种不同的调度策略：O(n)、O(1)、CFS。其中O(n)、O(1)并不仅仅调度普通进程，它们还关注着实时进程，而CFS则专注于普通进程的调度。关于O(n)、O(1)、CFS出现的先后顺序，看这篇文章
O(n)调度器
O(n)调度器是linux内核2.4引入的，它维护一个链表头runqueue_head，将所有可运行进程串联起来。调度器在选择下一个要执行的进程时，则遍历runqueue_head链表，使用goodness()计算其中每个进程的权重，挑选权重值最大的那一个运行。
那么goodness到底怎样计算权重呢？linux 2.4版本的源码如下：
/*linux 2.4内核源码 sched.c*/
// p ： 候选task_struct
// this_mm: 当前在此CPU上运行的进程的struct mm 结构，它表示了一个进程的地址空间(相当于JOS的PGDIR)
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{
int weight;
weight = -1;
// 1. 如果是yield的进程，权重为-1
if (p->policy & SCHED_YIELD)
goto out;
// 2. 针对普通进程
if (p->policy == SCHED_OTHER) {
// 如果下一个进程进程的时间片还没有用完，则奖励一些权重
weight = p->counter;
if (!weight)
goto out;
// 如果候选task_struct使用的struct mm 与当前进程相同，表示它与当前执行流逻辑上属于同一个进程。加一些权重
if (p->mm == this_mm || !p->mm)
weight += 1;
// 最后通过nice值计算
weight += 20 - p->nice;
goto out;
}
// 3.实时调度进程， RT进程表示自己有特权，权重直接加上1000，不更普通进程比，更其他实时进程比
weight = 1000 + p->rt_priority;
out:
return weight;
}
可以看到，对于实时进程，它根本不需要和普通进程比较，实时进程的权重永远比普通进程高，它只需要和其他实时进程比较rt_priority这个属性。
至于普通进程的权重，则是通过conter和nice值综合结算的结果， counter值越高(也就是时间片剩余越多，也就是喜欢IO的进程)、nice值越低的进程，其权重越高。其中nice的取值范围为[-20 - 19]，可以简单理解“越nice的进程，越得不到CPU的关注”。
O(n)调度器的缺点：
- 很明显它的时间复杂度为O(n)，虽然它实现简单，但是扩展性不高
- 并发度不高， 因为runqueue_head全局共享，这在多核系统的调度中是致命的缺点。
O(1)调度器
使用了2个优先级数组，一个为active，另一个为expired，每个数组使用140位的bitmap表示，bitmap的每一位(如果它有效)都对应了一个队列，该队列中的进程优先级相同。bitmap的1-100的优先级分配给实时进程用，其余的优先级给普通进程，与O(n)相同，这里的实时进程同样拥有较高的优先级。调度器在选择下一个执行的进程时，只要找到优先级最高的队列选择一个进程执行即可。这个过程的时间复杂度是O(1),为什么呢？因为找到bitmap中的第一个有效位这个操作可以由一条CPU指令完成，时间复杂度为O(1)（即使依次遍历这个bitmap数组，那也是O(140) = O(1))。此外每个CPU拥有的两个优先级数组，并发度有所提高。
当一个进程用完了它的时间片后，调度器重新计算并重置它的时间片，然后放入expired数组中。当active数组的每一位都无效时，交换active、expierd两个bitmap即可，这个交换操作只需要交换指针指向即可，时间复杂度还是O(1)。
此外，除了上述的静态优先级，O(1)调度器也会计算每个进程的动态优先级，目标也和O(n)调度器一样，对交互式进程的进程有利。
O(1)调度器假设经常陷入睡眠的进程是交互式进程，因此它将统计进程的平均睡眠时间，平均睡眠时间长的进程，调度器就认为它是交互式进程，因此对这些进程的动态优先级计算会有额外的奖励机制。
与O(1)调度器相比，O(n)的优势
- 时间复杂度低，扩展性强，即使任务适量很多，也能保证性能
- 每个CPU都有两个自己的两个优先级数组，因此并发度提高
- 采用新的算法计算进程的交互性，提高用户的交互体验
O(1)调度器的问题
- “该算法的主要问题是用于将任务标记为交互式或非交互式的复杂启发式算法”，该算法非常复杂，可能需要消耗很多CPU资源
O(1)与CFS的对比
CFS能够取代O(1)的最主要原因是，CFS能够更加公平地对待每个进程（即公平性更强），但与此同时CFS并没有太大的降低用户的交互体验。
可以参考下面两篇论文，它们都对O(1)与CFS做了对比，得出的结论总体上相同：
- Fairness and interactive performance of O(1) and CFS Linux kernel schedulers (researchgate.net)：该论文对比了O(n)和O(1)调度器的公平性和交互性，结果是：CFS能够在不牺牲用户交互的体验下，能够更好地保证公平性。
- A Comparison of Two Linux Schedulers
参考资料
- 《深入理解linux内核架构》第二章
- 《Linux内核源代码情景分析》相关章节
- Process Scheduling in Linux | Scaler Topics 总结了linux调度器的出现历史
- （五）Linux进程调度-CFS调度器 (qq.com) 图不错
- (36条消息) Interview: Ingo Molnar_zhoupengTrim的博客-CSDN博客(O(1)调度器编写者的采访)
- O(1) scheduler - Wikipedia ： “The main issue with this algorithm is the complex heuristics used to mark a task as interactive or non-interactive.”
- CFS调度器与O(1)调度器的比较-garfield_trump-ChinaUnix博客
- 从几个问题开始理解CFS调度器 - Yungyu - 博客园 (cnblogs.com)[CFS group scheduling LWN.net] (archive.org) ： CFS对比O(1)的优势
- Fairness and interactive performance of O(1) and CFS Linux kernel schedulers (researchgate.net)：该论文对比了O(n)和O(1)调度器的公平性和交互性，结果是：CFS能够在不牺牲用户交互的体验下，能够更好地保证公平性。
- A Comparison of Two Linux Schedulers ： CFS与O(1)的对比，大致上能够得出上面论文相同的结论
- linux2.6.24 以及 linux2.4内核源码