调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作。
1.多任务
多任务系统分为两类：非抢占式多任务（cooperative multitasking）和抢占式多任务（preemptive multitasking）。
Linux提供了抢占式的多任务模式。
抢占式的意思是，调度器可以强制挂起一个进程。
而在非抢占式模式下，除非进程自己主动停止运行，否则它会一直执行。
2.策略
策略决定调度程序在何时让什么进程运行。
2.1 I/O消耗型和处理器消耗型的进程
I/O消耗型进程：大部分时间用来提交I/O请求或是等待I/O请求。这样的进程经常处于可运行状态，但是运行时间不长，因为它在等待I/O请求时会阻塞。
处理器消耗型进程：时间大多花在执行代码上。对于这类进程，调度策略往往是尽量降低它们的调度频率，而延长其运行时间。
当然，以上划分并不是绝对的。
调度策略通常要在两个矛盾的目标中寻找平衡：进程响应迅速和最大系统利用率。
为提供更好的响应速度，Linux更倾向于优先调度I/O消耗型进程。
2.2 进程优先级
Linux采用了两种不同的优先级范围。
第一种是用nice值，范围是-20到+19，默认值为0；越大的nice值意味着更低的优先级。
可以通过以下命令查看系统中进程列表，结果中标记NI的一列就是对于的nice值：
ps -el
第二种是实时优先级，其值是可配置的，默认情况下变化范围是0到99（包括0和99）。与nice相反，越高的实时优先级数值意味着越高的优先级。
任何实时进程的优先级都高于普通进程。即一个进程同时设置了实时优先级和nice值时，只认实时优先级。
可以通过以下命令：
ps -eo state,uid,pid,ppid,rtprio,time,comm
查看你系统中的进程列表，以及对应的实时优先级（trprio列下），其中如果显示的是“-”，说明它不是实时进程。
2.3 时间片
时间片是一个数值，表明进程在被抢占前能持续运行的时间。
I/O消耗型不需要长的时间片，而处理器消耗型的进程则希望越长越好（比如可以让它们的高速缓存命中率更高）。
时间片过长会导致系统对交互的响应表现欠佳，因此很多系统的默认时间片很短。
Linux的CFS调度器则并没有直接分配时间片到进程，而是将处理器的使用比划分给进程，这样进程获得的处理器时间与系统负载密切相关。这个比例还受nice值影响，nice作为权重将调整进程使用处理器的时间比。
Linux的CFS调度器，抢占时机取决于新的可运行程序消耗了多少处理器使用比，如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程，否则推迟运行。
2.4 调度策略的活动
有了以上的基础，我们来看一个具体的场景：
有两个可运行的进程：一个文字编辑程序和一个视频编码程序。
前者是I/O消耗型的，后者是处理器消耗型的。
对文本编辑器而言，我们有两个目标：
1.我们希望系统给它更多的处理器时间，着并非它需要更多的处理器时间，而是我们希望在它需要时总是能得到处理器。
2.我们希望文本编辑器能在其被唤醒时抢占视频解码程序。
这样才能保证文本编辑器有很有的交互性能。
假设文本编辑器和视频解码程序是仅有的两个进程，并且具有同样的nice值，那么处理器的使用比将都是50%——它们平分了处理器时间。
由于文本编辑器更多的时间用于等待用户输入，所以肯定不会用到处理器的50%，而视频解码器无疑将有机会用到超过50%的处理器时间。
在上述场景中，一旦文本编辑器被唤醒，CFS注意到给它的处理器使用比是50%，但是其实它却用的少之又少。这种情况下，为了兑现让所有进程能公平分享处理器的承诺，它会立刻抢占视频解码程序，让文本编辑器投入运行。
因为文本编辑器并没有消费掉承诺给它的50%处理器使用比，因此CFS总是会毫不犹豫地让文本编辑器在需要时被投入运行，而让视频解码器只能在剩下的时刻运行。
3.Linux调度算法
上面我们只是抽象地讨论了进程调度原理，下面我们进一步探讨具有Linux特色的进程调度程序。
3.1调度器类
Linux调度器以模块方式提供，它允许不同类型的进程有针对性地选择调度算法。
这种模块化结构被称为调度器类（scheduler classes）。每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。
3.2公平调度
完全公平调度（CFS）是一个针对普通进程的调度类，在linux中称为SCHED_NORMAL，CFS算法实现定义在文件kernel/sched_fair.c中。
假设有两个进程，nice值分别为0和5，nice值是5的进程的权重将是默认nice进程的1/3，如果我们的目标延迟是20ms，那么两个进程分别获得15ms和5ms的处理器时间。
假设两个进程的nice值分别为10和15，则处理器时间还是15ms和5ms。可见，绝对的nice值不会影响调度决策（在时间片和优先级调度中，将会影响很大），只有相对值才会影响处理器时间的分配比例。
4.Linux调度的实现
4.1时间记账
CFS调度器都必须对进程运行时间做记账，因为它需要确保每个进程只在公平分配给它的处理器时间内运行。
CFS使用调度器实体结构来追踪进程运行记账（定义在文件< linux/sched.h >的struct_sched_entity中）：
struct sched_entity {
struct load_weight load; /* for load-balancing */
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 nr_migrations;
/* 其他统计变量 */
};调度器实体结构作为一个名为se的成员变量，嵌入在进程描述符struct task_struct内。
vruntime变量存放进程的虚拟运行时间，vruntime并不是实际的运行时间，它是实际运行时间进行加权运算后的结果。
举个简单的例子，有3个进程，ProcessA(NI=1)，ProcessB(NI=3)，ProcessC(NI=6)，在CFS算法中，分别占用CPU的百分比为：ProcessA(10%)，ProcessB(30%)，ProcessC(60%)。
ProcessA(10%)只分配了CPU总的处理时间的10%，那么ProcessA运行10ms的话，它的vruntime会增加100ms。以此类推，ProcessB运行10ms的话，它的vruntime会增加(100/3)ms,ProcessC运行10ms的话，它的vruntime会增加(100/6)ms。
实际的运行时，由于ProcessC的vruntime增加的最慢，所以它会获得最多的CPU处理时间。
定义在kernel/sched_fair.c文件中的update_curr()函数实现了记账功能：
/* * Update the current task's runtime statistics. */
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
/* 获得从最后一次修改负载后当前任务所占用的运行总时间 */
delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;
schedstat_set(curr->statistics.exec_max,
max(delta_exec, curr->statistics.exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq, exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cpuacct_charge(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}
update_curr计算了当前进程的执行时间，并将其存放在变量delta_exec中。然后再调用calc_delta_fair()根据当前可运行进程总数对运行时间进行加权计算。最终将上述的权重值与当前运行进程的vruntime相加。
update_curr是由系统定时器周期性调用的，无论是在进程处于可运行态，还是被阻塞处于不可运行态。
4.2进程选择
CFS调度算法的核心：选择具有最小vruntime的任务。
CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。
挑选下一个任务
CFS使用一个红黑树存储了系统中所有的可运行进程，其中节点的键值便是可运行进程的虚拟运行时间。CFS调度器选取待运行的下一个进程，是所有进程中vruntime最小的那个，它对应的便是树中最左侧的叶子节点。
实现这一过程的函数是__pick_next_entity()：
static struct sched_entity *__pick_next_entity(struct sched_entity *se)
{
struct rb_node *next = rb_next(&se->run_node);
if (!next)
return NULL;
return rb_entry(next, struct sched_entity, run_node);
}实际上该函数并不会遍历树找到最左叶子节点，而是将其缓存在rb_leftmost字段中。
向树中加入进程
我们看看CFS如何将进程加入rbtree中，以及如何缓存最左叶子节点。
这一切发生在进程变为可运行态或者是通过fork()调用第一次创建进程时。
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
bool curr = cfs_rq->curr == se;
/* * If we're the current task, we must renormalise before calling * update_curr(). */
if (renorm && curr)
se->vruntime += cfs_rq->min_vruntime;
update_curr(cfs_rq);
/* * Otherwise, renormalise after, such that we're placed at the current * moment in time, instead of some random moment in the past. Being * placed in the past could significantly boost this task to the * fairness detriment of existing tasks. */
if (renorm && !curr)
se->vruntime += cfs_rq->min_vruntime;
enqueue_entity_load_avg(cfs_rq, se);
account_entity_enqueue(cfs_rq, se);
update_cfs_shares(cfs_rq);
if (flags & ENQUEUE_WAKEUP) {
place_entity(cfs_rq, se, 0);
if (schedstat_enabled())
enqueue_sleeper(cfs_rq, se);
}
check_schedstat_required();
if (schedstat_enabled()) {
update_stats_enqueue(cfs_rq, se);
check_spread(cfs_rq, se);
}
if (!curr)
__enqueue_entity(cfs_rq, se);
se->on_rq = 1;
if (cfs_rq->nr_running == 1) {
list_add_leaf_cfs_rq(cfs_rq);
check_enqueue_throttle(cfs_rq);
}
}该函数更新运行时间和其他一些统计数据，然后调用__enqueue_entity()进行繁重的插入操作：
/* * Enqueue an entity into the rb-tree: */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
struct rb_node *parent = NULL;
struct sched_entity *entry;
int leftmost = 1;
/* * Find the right place in the rbtree: */
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
/* * We dont care about collisions. Nodes with * the same key stay together. */
if (entity_before(se, entry)) {
link = &parent->rb_left;
} else {
link = &parent->rb_right;
leftmost = 0;
}
}
/* * Maintain a cache of leftmost tree entries (it is frequently * used): */
if (leftmost)
cfs_rq->rb_leftmost = &se->run_node;
rb_link_node(&se->run_node, parent, link);
rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}如果一旦走过右边分支，则说明插入的进程不会是新的最左节点，因此设置leftmost为0，如果一直向左移动，则leftmost维持为1，说明我们有一个新的最左节点，并且可以更新缓存——设置rb_leftmost指向被插入的进程。
rb_insert_color更新树的自平衡相关属性。
从树中删除进程
删除动作发生在进程阻塞（变为不可运行态）或者终止时（结束运行）。
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/* * Update run-time statistics of the 'current'. */
update_curr(cfs_rq);
dequeue_entity_load_avg(cfs_rq, se);
if (schedstat_enabled())
update_stats_dequeue(cfs_rq, se, flags);
clear_buddies(cfs_rq, se);
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
se->on_rq = 0;
account_entity_dequeue(cfs_rq, se);
/* * Normalize the entity after updating the min_vruntime because the * update can refer to the ->curr item and we need to reflect this * movement in our normalized position. */
if (!(flags & DEQUEUE_SLEEP))
se->vruntime -= cfs_rq->min_vruntime;
/* return excess runtime on last dequeue */
return_cfs_rq_runtime(cfs_rq);
update_min_vruntime(cfs_rq);
update_cfs_shares(cfs_rq);
}static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
if (cfs_rq->rb_leftmost == &se->run_node) {
struct rb_node *next_node;
next_node = rb_next(&se->run_node);
cfs_rq->rb_leftmost = next_node;
}
rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}如果要删除的是最左节点，则要调用rb_next()按顺序遍历，找到谁是下一个节点，并更新缓存。
4.3调度器入口
进程调度的主要入口点是函数schedule()，它定义在kernel/sched.c中。该函数唯一重要的是，调用pick_next_task()，它会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程：
/* * Pick up the highest-prio task: */
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct pin_cookie cookie)
{
const struct sched_class *class = &fair_sched_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(prev->sched_class == class &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = fair_sched_class.pick_next_task(rq, prev, cookie);
if (unlikely(p == RETRY_TASK))
goto again;
/* assumes fair_sched_class->next == idle_sched_class */
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq, prev, cookie);
return p;
}
again:
for_each_class(class) {
p = class->pick_next_task(rq, prev, cookie);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
}
}
BUG(); /* the idle class will always have a runnable task */
}函数一开始做了一个小优化，如果所有可运行进程都是CFS类的，则直接使用CFS来选择。否则，通过for循环来遍历。
4.4睡眠和唤醒
函数 schedule()是一个调度函数，它可以被一个进程主动调用，从而调度其它进程占用CPU。一旦这个主动放弃CPU的进程被重新调度占用 CPU，那么它将从上次停止执行的位置开始执行，也就是说它将从调用schedule()的下一行代码处开始执行。
有时候，进程需要等待直到某个特定的事件发生，例如设备初始化完成、I/O 操作完成或定时器到时等。在这种情况下，进程则必须从运行队列移出，加入到一个等待队列中，这个时候进程就进入了睡眠状态。
休眠有两种状态：TASK_INTERRUPTIBLE状态的进程如果收到信号，会被提前唤醒并响应该信号，TASK_UNINTERRUPTIBLE状态的进程则会忽略该信号。
休眠：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。
唤醒：进程被设为可执行状态，然后从等待队列中移到可执行红黑树中。
等待队列：由等待某些事件发生的进程组成的简单链表。内核用wake_queue_head_t来代表等待队列。等待队列可由DECLARE_WAITQUEUE()静态创建，也可以由init_waitqueue_head()动态创建。
进程休眠时把自己放入等待队列，当与等待队列相关的事件发生时，队列上的进程会被唤醒。
上面提到，进程是调用schedule()进入睡眠状态的：
sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* Rest of the code ... */在第一个语句中，程序存储了一份进程结构指向sleeping_task，current 是一个宏，它指向正在执行的进程结构。set_current_state()将该进程的状态从执行状态TASK_RUNNING 变成睡眠状态TASK_INTERRUPTIBLE。
如果schedule()是被一个状态为TASK_RUNNING 的进程调度，那么schedule()将调度另外一个进程占用CPU；如果schedule()是被一个状态为TASK_INTERRUPTIBLE 或TASK_UNINTERRUPTIBLE 的进程调度，那么还有一个附加的步骤将被执行：当前执行的进程在另外一个进程被调度之前会被从运行队列中移出，这将导致正在运行的那个进程进入睡眠，因为它已经不在运行队列中了。
我们可以使用下面的这个函数将刚才那个进入睡眠的进程唤醒。
wake_up(sleeping_task);在调用了wake_up()以后，这个睡眠进程的状态会被设置为TASK_RUNNING，而且调度器会把它加入到运行队列中去。当然，这个进程只有在下次被调度器调度到的时候才能真正地投入运行。
哪段代码促使等待条件达成，就要负责随后调用wake_up_process()函数。
无效唤醒
正常情况下，进程都会在检查了某些条件之后，发现条件不满足才进入睡眠。可是有的时候进程却会在判定条件满足后开始睡眠，如果这样的话进程就会无限期地休眠下去，这就是所谓的无效唤醒问题。无效唤醒是由于竞争条件导致的。
假设有两个进程A和B，A 进程正在处理一个链表，它需要检查这个链表是否为空，如果不空就对链表里面的数据进行一些操作，同时B进程也在往这个链表添加节点。当这个链表是空的时候，由于无数据可操作，这时A进程就进入睡眠，当B进程向链表里面添加了节点之后它就唤醒A 进程，其代码如下：
// A进程:
spin_lock(&list_lock);
if(list_empty(&list_head)) {
spin_unlock(&list_lock);
set_current_state(TASK_INTERRUPTIBLE);
schedule();
spin_lock(&list_lock);
}
/* Rest of the code ... */
spin_unlock(&list_lock);
// B进程:
spin_lock(&list_lock);
list_add_tail(&list_head, new_node);
spin_unlock(&list_lock);
wake_up(processa_task);这里会出现一个问题，假如当A进程执行到第4行后第5行前的时候，B进程被另外一个处理器调度投入运行。在这个时间片内，B进程执行完了它所有的指令，因此它试图唤醒A进程，而此时的A进程还没有进入睡眠，所以唤醒操作无效。在这之后，A 进程继续执行，它会错误地认为这个时候链表仍然是空的，于是将自己的状态设置为TASK_INTERRUPTIBLE然后调用schedule()进入睡眠。由于错过了B进程唤醒，它将会无限期的睡眠下去，这就是无效唤醒问题，因为即使链表中有数据需要处理，A 进程也还是睡眠着。
避免无效唤醒
我们发现无效唤醒主要发生在检查条件之后和进程状态被设置为睡眠状态之前，本来B进程的wake_up_process()提供了一次将A进程状态置为TASK_RUNNING 的机会，可惜这个时候A进程的状态仍然是TASK_RUNNING，所以wake_up_process()将A进程状态从睡眠状态转变为运行状态的努力没有起到预期的作用。
要解决这个问题，必须使用一种保障机制使得判断链表为空和设置进程状态为睡眠状态成为一个不可分割的步骤才行，也就是必须消除竞争条件产生的根源，这样在这之后出现的wake_up_process ()就可以起到唤醒状态是睡眠状态的进程的作用了。
找到了原因后，重新设计一下A进程的代码结构，就可以避免上面例子中的无效唤醒问题了。
// A进程:
set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if(list_empty(&list_head)) {
spin_unlock(&list_lock);
schedule();
spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* Rest of the code ... */
spin_unlock(&list_lock);可以看到，这段代码在测试条件之前就将当前执行进程状态转设置成TASK_INTERRUPTIBLE了，并且在链表不为空的情况下又将自己置为TASK_RUNNING状态。这样一来如果B进程在A进程进程检查了链表为空以后调用wake_up_process()，那么A进程的状态就会自动由原来TASK_INTERRUPTIBLE变成TASK_RUNNING，此后即使进程又调用了schedule()，由于它现在的状态是TASK_RUNNING，所以仍然不会被从运行队列中移出，因而不会错误的进入睡眠，当然也就避免了无效唤醒问题。
我们看下linux内核是如何处理休眠的：
DEFINE_WAIT(wait);
for (;;)
{
prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
if (signal_pending(current))
/* 处理信号 */
if (likely(condition))
break;
schedule();
}
finish_wait(&q, &wait);上面代码保证了在测试条件之前就将当前执行进程状态设置成TASK_INTERRUPTIBLE，避免了无效唤醒问题。
之所以使用循环，是因为如果进程是被信号唤醒的（称为伪唤醒，因为唤醒不是因为事件的发生），则处理完信号后应该重新把进程加入到等待队列中，然后再次检查条件是否满足，如果不满足，则继续休眠。
5.抢占和上下文切换
上下文切换，就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行时，schedule()就会调用该函数。
它完成了两项基本工作：
1.调用声明在< asm/mmu_context.h >中的switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。
2.调用声明在< asm/system.h >中的switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。
内核必须知道在什么时候调用schedule()。内核提供了一个need_resched标志来表明是否需要重新执行一次调度。当某个进程应该被抢占时，scheduler_tick()就会设置这个标志，内核检查该标志，确认其被设置，调用schedule()来切换到一个新的进程。该标志对内核来讲是一个信息，表示有其他进程应当被运行了，要尽快调用调度程序。在返回用户空间以及从中断返回的时候，内核也会检查该标志。
每个进程都包含一个need_resched标志，存在thread_info结构体内。
5.1用户抢占
用户抢占发生在从系统调用或者中断处理程序返回用户空间的时候，这时会检查need_resched标志，调用schedule()来选择一个合适的进程运行。
5.2内核抢占
在不支持内核抢占的内核中，内核代码可以一直执行，直到它完成为止。
在支持内核抢占的内核中，只要重新调度是安全的，内核可以在任何时间抢占正在执行的任务。
何时重新调度才是安全的——只要没有持有锁，内核就可以进行抢占。
每个进程的thread_info引入preempt_count计数器，初始值为0，每当使用锁数值就加1，释放锁数值就减1。当数值为0时，内核就可以抢占。
从中断返回内核空间的时候，会检查need_resched和preempt_count的值。
内核抢占发生的时机：
1.中断处理程序正在执行，且返回内核空间之前。
2.内核代码再一次具有可抢占性的时候（释放锁的时候preempt_count变回0，则会检查need_resched）。
3.内核中的任务显式调用schedule()。
4.内核中的任务阻塞（同样会调用schedule()）。
6.实时调度策略
普通、非实时的调度策略是SCHED_NORMAL，实时调度策略有SCHED_FIFO和SCHED_RR。
借助调度类的框架，这些实时策略并不被CFS管理，而是被一个特殊的实时调度器管理，具体实现定义在kernel/sched_rt.c中。
SCHED_FIFO是简单的、先入先出的调度算法，它不使用时间片。处于可运行状态的SCHED_FIFO级进程会比任何SCHED_NORMAL级的进程优先调度。一旦执行，就会一直执行下去，直到自己受阻塞或者显式地释放处理器为止。只有更高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。
SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再继续执行了，即这是一种待时间片的SCHED_FIFO（时间片只用来重新调度同一优先级的进程）。
