进程调度器决定了接下来运行哪一个进程，什么时候，多长时间。进程调度器分配了处理器上面有限的时间给可运行的进程；调度器是多任务操作系统的基础，比如说Linux。通过决策下一个运行的进程，调度器负责utilize系统并给用户一种多个进程在同事运行的印象。
调度器背后的考虑是很简单的；优化处理器时间，假设说有可运行的进程的话，总有一个进程应该是处于运行态的。如果说系统中可运行的进程的数量多于处理器的数量，一部分进程只能运行一段时间，其他的进程等待运行。决策下一个运行的进程，给出一系列可运行的进程，是调度器应该做的最基本工作。
Multitasking
一个多任务的操作系统是可以同时运行多个进程的。在单一处理器的系统上，会给出一种假象：多个进程在同时运行；在多处理器的系统上，这一特性可以真正实现，让多个进程在不同处理器上面并行执行。在上述两种机器模型上，它会是能多个进程block和sleep，而不是一直运行指导工作就绪。虽然在内存中的那些进程是不可运行的状态。Instead，这些进程使内核等待一定特定的实践发生。因此，现在Linux系统可以在内存中存在多个进程，但是仅仅有一个处于可运行的状态。
多任务操作系统存在两种形式：cooperative多任务和可抢占的多任务状态；Linux像UNIX和大多数现代操作系统一样实现的是可抢占的多任务形式。在可抢占的多任务系统中，调度器决定什么时候停止进程和什么时候运行一个新的进程。这种involuntarily的暂停一个进程叫做抢占。进程被抢占之前运行的时间通常来说是预设好的，它叫做进程的时间片。时间片实际来说是给出了每一个可运行的进程一部分处理器的时间。管理这些时间片让调度器可以为系统做一个全局全局的调度决策。他也可以阻止任意的进程不会独占处理器。在一些现代的操作系统当中，时间片是根据处理器行为和系统的配置策略而动态计算的。
相反的，在cooperative多任务系统中，如果进程本身不自愿放弃运行，进程是不会停止运行的。进程本身自愿停止运行的行为叫做yielding。最理想的情况是，进程可以时常的停止执行，给其他可运行的进程让出一部分处理器的运行时间，但是操作系统不会强制执行这一行为。这一策略的缺点是很明显的：不管进程运行多久，调度器也不能做出全局的决策；进程可能独占处理器的时间比用户设置的要长；而且一个从来不会停止的hung进程是有可能bring down整个系统的。Thankfully，最近20年设计的操作系统都采用了可抢占的多任务模式，但是MAC 0S9、windows 3.1除外。Of course,Unix自从他诞生以来就采用了可抢占的多任务模式。
Linux Process Scheduler
从Linux第一个版本到kernel 2.4，Linux调度器在设计上都是相当简单的。它是易于理解的，但是再多进程和多多处理器的调度上面的表现是糟糕的。
作为解决措施，Linux kernel2.5开始，Linux引入了新的调度器策略。由于他的算法表现，新的调度器叫做O(1)调度器，它解决了一部分之前调度器的一些缺点并引入了一些新的poweful的特性，提升了性能。通过引入在时间片和每个处理器runqueue方面constant-time算法机制，它更正了早期调度器的诸多限制。
O(1)调度器表现很理想并且可以轻松扩展，因为Linux支持大的“铁”处理器，有几十个甚至几百个。Over time,O(1)调度器在latency-sensitive应用上面表现出了一定的缺陷。这些应用（叫做intercative进程）包括任意任意人机交互的应用。因此，虽然O(1)调度器对于大负载的服务器是理想的（ps:大型服务器是很少有人机交互的），但是它在桌面系统表现的差强人意，桌面系统存在着大量的需要人机交互的应用。 在2.6内核之前，开发者引入了新的进程调度器旨在提升O(1)调度器的交互性能。其中最著名的就是Rotating Staircase Deadline scheduler，它从queue理论中引入了公平调度的理念到进程调度器中。这种理念就是在内核2.6.23中完全替换掉O(1)调度器的CFS调度器（Complete Fair Scheduler）。
Policy
Policy是调度器的行为，决定什么时候运行什么。调度器的policy通常决定一个系统的整体感觉，也负责合理分配处理器时间。因此它是很重要的。
I/O-Bound Versus Processor-Bound Processes
进程被分类为I/O bound或者processor bound。前者可以这样总结that进程花费大量的时间在提交和等待I/O请求。Therefore，由于它最终在等待更多的IO，这样的进程仅仅在很短的时间内是可运行的状态。比如说，大多数的用户交互的应用都是I/O-bound，即使他们从来不向磁盘写入或者读取内容，因为他们花费了大量的时间在等待用户在键盘或者鼠标的交互动作。
相反地，processor-bound进程花费了大多数时间在执行代码。直到他们被抢占之前，他们都倾向于run,因为他们不经常block I/O请求。但是，由于他们不是I/O driven的，系统响应并不要求调度程序经常运行它们。因此，processor-bound进程的调度器策略倾向于更低的频率运行，但通常会运行更长的时间。The ultimate的processor-bound的例子就是执行无限循环的程序。更好一点的例子包括一些程序that执行大量的数学计算，比如说MATLAB。
当然，这些分类并不是互相冲突的。进程也可能同时存在这两种形式。比如说X-Windows就即使I/O bound也是processor bound。系统调度器的策略必须满足两个冲突的目标：进程快速响应（低延时）和系统的最大利用率（高吞吐）。为了满足这种满是冲突的要求，调度器需要使用复杂的调度算法去抉择最有价值的进程去运行，但是又不失对于其他低优先级进程的公平性。Unix系统中调度器策略倾向于I/O-bound进程，英雌可以提供良好的进程响应时间。旨在提供良好的交互响应和桌面性能的Linux优化了进程响应时间（低延时），因此相比于processor-bound而言更倾向于I/O-bound进程策略。As we will see,这是一个富有创造性的manner，又不失processor-bound的策略。
Process priority
调度算法的通用类型就是基于优先级的调度策略。这样做的目标是基于他们的价值和对于处理器需要的时间对这些进程进行排名。通常的idea是更高优先级的进程比低优先级的进程优先运行，相同优先级的进程通过round-robin的方式进程调度，但是这一idea并没有在Linux中实现。在有些系统中，更高优先级的进程甚至拥有更长的时间片。拥有时间片的进程和最高优先级的进程是总是运行的。用户和系统都能够设置进程的优先级来影响系统调度的行为。
Linux kernel完成了两种不同的优先级范围。第一个是nice值，范围值是-20到+19，默认值是0.相较于低nice值的进程，nice值越大意味着对系统中的其他进程越”nice”。相比于拥有高nice值（低优先级）的进程，有着低nice值（高优先级）的进程占用更多的处理器时间。虽然取决于他们各自的调度算法，不同的Unix系统以不同的方式实现nice值的标准范围，但是Nice值在所有的Unix系统中是一个标准的优先级范围。在其他的基于Unix的系统中，比如说MAC OS X，nice值也是分配进程绝对时间片的控制方式；在Linux总，nice值通过时间片的占比来控制。使用命令ps –el，你可以在你的系统中看到一系列进程和他们各自的nice值。
第二个范围是real-time优先级。这项参数是可以配置的，但是默认参数区间是0-99.和nice参数不同的是，更高的实时优先级对应着更高的优先级。所有的实时进程都比普通进程的优先级要高。也就是说实时的优先级和nice值优先级是互不相关的两个域。Linux根据Unix的POSIX.1b来完成实时的优先级设置。所有的现代Unix系统都是完成相似的机制。使用命令ps –eo state,uid,pid,ppid,rtprio,time,comm，你可以看到在你的系统中的一系列进程和各自进程的实时优先级。如果有的参数为negative的话，那么这个进程是非实时的。
Timeslice
时间片是一个数字参数，代表着一个进程能够运行的时间，until it is completed。调度器的策略需要指明一个默认的时间片参数，这是相当重要的。太长的时间片可能会导致系统在交互上面的很差劲；系统会感觉到好像没有程序在同时并行执行。太短的时间片会导致系统在进程切换的过程中浪费的时间跟运行时间片相当。Futhermore,I/O-bound和processor-bound进程的冲突又进一步的显现出来了：I/O-bound进程不需要更长的时间片（虽然他们喜欢经常运行），但是processor-bound进程需要更长的时间片（保持他们的caches hot）。
如果按照上一段中的论述的话，任意长度的时间片都有可能导致糟糕的交互性能。在很多的操作系统中，大家都注意到了这个问题，因此默认的时间片参数相当低，举个例子，10毫秒。但是Linux CFS调度器并没有直接分配时间片给进程。相反的，以一种更有艺术性的方式来实现，CFS分配给进程一定处理器的占比。因此在Linux中，进程接收到的处理器时间是系统加载的函数。这种分配到的占比进一步影响了每个进程的nice值。Nice值作为权重，改变了每个进程接收到的处理器时间的占比。拥有更高nice值（低优先级）的进程接收到了更大的权重，使他们获得更小的处理器占有比例；拥有更低nice值（高优先级）的进程接收到了更小的权重，使他们获得了更大的处理器占有比例。
如上文所述的，Linux操作系统是可以抢占的。当一个进程进入可运行的状态的时候，他变得很渴望去运行。在大多数操作系统中，无论进程是否立即运行，抢占当前运行的进程需要基于进程优先级和可用时间片。在Linux中，基于新的CFS调度器，决策需要基于新进程所占处理器的占比来指定。如果他比当前进程消耗了较小的处理器比例，他会立即抢占当前进程。
The Scheduling Policy in Action
假如说一个系统有两个任务：一个是文本编辑器，另一个是视频编码器。文本编辑器是I/O-bound，因为他几乎花费了所有的时间在等待用户按下键盘输入文本。除此之外，当文本编辑器接收到了按键按下后，用户期待编辑器立即响应给他。相反地，视频编码器是processor-bound类型的。除了从磁盘读取数据流之外，而且还写入resulting视频，视频解码器花费了几乎所有的时间都在给视频处理上，轻松的消耗了处理器100%的时间。视频编码器也没有很强力的时间限制在什么时候返回上。当然，完成的越快越好，但是延迟不是主要的担心之处。
在这种情境下，调度器会很理想的给出文本编辑器更大的处理器占比相比于视频编码器而言，因为文本编辑器是需要更加的交互的。对于文本编辑器，我们有两个目标，第一个是我们需要更多的可用的处理器时间；不是因为它需要更多的处理器而是因为我们总是想要它有可用的处理器时间，当他需要的时候。第二点，我们想要文本编辑器唤醒的时候，抢占视频编码器。这样能保证文本编辑器有一个良好的交互体验，对于用户的输入有良好的相应。在大多数操作系统中，通过给文本编辑器更高的优先级和更大的时间片来满足这一要求。更高级的操作系统甚至可以检测到文本编辑器是交互性的应用而自动分配对应的优先级和时间片。Linux也实现了这个目标，但是使用了不同的办法。不是分配不同的优先级和时间片，他保证了文本编辑器占据了特定的处理器比例。如果视频编码器和文本编辑器是唯一在运行的进程并拥有相同的nice值，这一占比将会是50%—双方都保证了拥有一半儿的处理器时间。因为文本处理器花费了大多数的时间在在阻塞、等待用户按下按键，它不使用接近50%的处理器。相反地，视频编码器可以使用超过分配的50%处理器，可以让他完成视频编码更快些。
重要的部分是文本编辑器唤醒的时候，发生什么。我们的主要目标是当用户输入之后尽快的响应用户。这种情况下，当文本编辑器唤醒了，CFS注意到他分配到了50%的处理器占比但是使用的还相对较少。明确的说，CFS调度器决定了文本编辑器比视频编码器运行的时间要少。为了给所有进程公平的共享处理器，它抢占了视频编码器并使文本编辑器去运行。文本编辑器开始运行，快速处理了用户按键事件，然后又睡眠了，等待更多的用户输入。因为文本编辑器消耗的比例小于分配的50%，我们继续这种策略，当文本编辑器想要运行的时候，CFS调度器会让它运行，视频编码器运行剩下的时间。
The Linux Scheduling Algorithm
在前一章节中，我们主要讨论了进程调度。随着调度部分的建立，我们可以进入Linux进程调度器。
Scheduler Classes
Linux调度器是模块化的涉及到不同的调度算法去调度不同类型的进程。这个模块化叫做schedule classes。Scheduler classes使用了不同的、可拆卸的算法，不同的模块调度各自类型的进程。每一个调度器都有一个优先级。基本调度器代码（定义在kernel/sched.c）按优先级顺序遍历了每一个调度器类。最高优先级的类（有可运行的进程的调度器类）获胜，选择下一个运行的哪个。
CFS调度器在Linux中作为NORMAL调度器注册进来的，called SCHED_NORMAL。
Process Scheduling in Unix System
为了讨论公平调度类，我们需要首先描述传统的Unix系统是如何调度进程的。如前面章节提到过的，现代的进程调度器有两个通用的概念：进程优先级和时间片。时间片指的是进程运行的时间；进程以默认的时间片开始运行。有更高优先级的进程运行的频率更高并且接受更多的时间片。在Unix系统中，优先级是以nice值的方式导出到用户空间的。
Fair Scheduling
CFS基于一个简单的概念：进程调度模型是基于系统拥有理想、完美的多任务处理器。在这样的系统中，每个进程都会接收到1/n的处理器时间，n代表着可运行的进程数量，并且我们可以以无限小的间隔调度这些进程，目的是在任意的周期内，我们都可以将每个进程运行相同短的时间间隔。比如说，我们有两个相同的进程。在标准的Unix系统模型中，我们可能运行一个线程5毫秒，运行另一个线程5毫秒。在运行的时候吗，每一个进程都会占用百分之百的CPU。在理想、多任务的处理器中，我们可以把每个进程同时运行10毫秒，每个50% power。后者的模型叫做完美多任务模型。
当然这种模型是不存在的，因为你不可能在单一处理器上同事运行多个进程。Moreover，以无限小的间隔运行进程也是相当低效的。因为进程切换还存在着切换消耗。因此，虽然我们倾向于以较小的间隔运行多个线程，CFS对部分的进程切换的消耗还是不满意的。Instead，CFS会运行每一个进程一段时间，round-robin,选择运行的最少进程作为下一个运行的进程。CFS不会分配给每一个进程运行的时间片，CFS会根据可运行的进程的数量的函数来计算一个进程需要运行多久的时间。不使用nice值去计算时间片，CFS使用nice值去衡量一个进程应该接收到的处理器占比：nice值越高的进程接收到了越少的权重，相比较默认的nice值，但是值越低的进程接收到了更大的权重。
每个进程都会运行一段时间片的占比（这些是根据全部可运行的线程的权重分配而来的）；为了计算实际的时间片，在完美的多任务系统中，CFS设置了一个无限小的时间间隔目标。这个目标间隔叫做目标延迟。越小的目标获得更好的交互性，越接近完美的多任务系统，但如果进程切换的消耗越高的话，导致的结果可能越差。假设目标延时是20毫秒、我们有两个相同优先级、可以运行的进程，忽略其他进程的优先级的，在抢占之前，每一个进程会运行10毫秒。如果我们有四个相同优先级的进程的话，每个运行5毫秒。如果我们有20个相同优先级的进程的话，每一个运行1毫秒。
假如说可运行的任务的数量达到了无限大的情况下，分配的处理器占比和分配的时间片就几乎为0了。这可能就会导致不可接受的进程切换代价，CFS给每个线程引入了一个最低限制。这个最低限制叫做最小细粒度。默认是1毫秒。因此即使可运行的进程的数量达到了无限大，每一个进程都可以至少运行1毫秒，这样就可以保证对进程切换的消耗进行上限控制了。
假设说还有两个可运行的进程，但是有着不同的nice值（一个是默认参数0，另外一个的参数是5）。他们的nice参数有着不同的权重，因此两者对这处理器时间的分配有着不同的占比。如果说我们的目标延迟是20毫秒的话，我们的两个进程将分别接收到15毫秒和5毫秒的处理器运行时间。绝对的nice值不再影响调度决策；只有相对的nice参数才会影响处理器时间的占比。
通常来讲，任意进程接收到的处理器时间的占比是由各个可运行进程之间的nice值的比例决定的。分配nice值的绝对时间片不会是一个绝对的数值，而是处理器的占比。由于给每一个进程都分配了公平的处理器时间，所以调度器叫做完全公平调度器。但是，CFS也不是完全公平的，因为他只能做到近似的完美多任务系统，但对于n个可运行进程的不公平性，它给n个可运行进程的延迟设置了一个下限。
The Linux Scheduling Implementation
我们来探究下CFS调度器的底层实现机制，defined in kernel/sched_fair.c。我们会讨论CFS调度器的如下机制：
Time Accounting
Process Selection
The scheduler Entry Point
Sleeping and Waking up
Time Accounting
所有的进程调度器必须记录进程运行的时间。大多数的Unix系统都是这样做的，如前所述，通过给每个进程分配一个时间片。在系统时钟每个tick后，这个时间片会根据tick周期递减。当时间片减到0的时候，进程就会被另一个时间片不为0的可运行的进程抢占。
The Scheduler Entity Structure
CFS没有时间片提醒，但是它必须保持每个进程的时间片计数，因为它需要确认每个进程仅仅会运行一定时间，基于公平共享处理器的策略。CFS调度器使用scheduler entity structure, struct sched_entity,defined in <linux/sched.h>，跟踪进程的accounting的情况：
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;
/* many stat variables elided, enabled only if CONFIG_SCHEDSTATS is set */
};
上述结构体是被嵌入到进程描述符结构体struct task_struct当中的，as a member variable named as se;
The Virtual Runtime
Vruntime变量存储了进程虚拟的运行时间，这是可运行的进程的实际运行时间（可能被weighed）。Vruntime时间的单位是纳秒，因此Vruntime时间是从定时器tick中去耦合而来的；虚拟运行时间被用来帮助我们估计CFS正在model的理想多任务处理器。在这种理想处理器的情况下，我们不需要vruntime，因为所有可运行的进程都会完美的实现多进程。也就是说在理想的处理器上，所有拥有相同优先级的进程的vruntime都是一致的-所有的任务都能够公平的占有处理器。因为处理器不能完美的执行多任务的动作，并且我们必须成功的运行每一个进程。CFS使用vruntime来计算进程已经运行多久以及还需要运行多久。
函数update_curr()，定义在kernel/sched_fair.c，管理这项计数：
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_of(cfs_rq)->clock;
unsigned long delta_exec;
if (unlikely(!curr))
return;
/*
* Get the amount of time the current task was running
* since the last time we changed load (this cannot
* overflow on 32 bits):
*/
delta_exec = (unsigned long)(now - curr->exec_start);
if (!delta_exec)
return;
__update_curr(cfs_rq, curr, delta_exec);
curr->exec_start = now;
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);
}
}
Update_curr()函数计算了当前进程的执行时间并储存这项参数在delta_exec中。紧接着它把runtime传递给_update_curr(),_update_curr()会根据可运行的进程数量加权这个时间。当前可运行进程的vruntime再根据加权后的值增加：
/*
* Update the current task’s runtime statistics. Skip current tasks that
* are not in our scheduling class.
*/
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
unsigned long delta_exec)
{
unsigned long delta_exec_weighted;
schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq, exec_clock, delta_exec);
delta_exec_weighted = calc_delta_fair(delta_exec, curr);
curr->vruntime += delta_exec_weighted;
update_min_vruntime(cfs_rq);
}
Update_curr()会由系统定时器周期性的调用或者当任意进程变为可运行状态或者阻塞，变为不可运行状态的时候，也会调用update_curr()。在这种机制下，vruntime是给定进程运行时间的一种精确的测量手段，并指出下一个运行的进程是哪一个。
Process Selection
在最后一节，我们会讨论在理想完美的多任务处理器上面，vruntime是如何在所有的可运行的进程中做到一致的。现实的情况是，我们不能实现完美的多任务处理，所以CFS试图去平衡进程的虚拟运行时间，以下面的准则作为参考：当CFS决策什么进程去下一个运行的时候，他会选取vruntime参数最小的参数的进程。也就是说CFS调度的核心调度算法是：选取vrumtime最小的task.这张如下的部分会描述，最小vruntime的参数会如何完成选择的。
CFS使用rb-tree去管理可运行的进程列表，并能高效地选出最小vruntime进程。
Picking the Next Task
我们假设在系统中，rb-tree已经populated所有的可运行进程。假如说rb-tree使用到的话，CFS想要调度的进程、最小vruntime的进程都是这个tree的最左边节点。也就是说，从根节点开始向下向左查找，持续向左直到你到达一个叶子节点，你会发现这个进程就是vruntime最小的进程。CFS调度器进程调度选择算法的核心可以总结为：运行那些rb-tree最左边节点的进程。以下是个实例：
__pick_next_entity(), defined in kernel/sched_fair.c:
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
struct rb_node *left = cfs_rq->rb_leftmost;
if (!left)
return NULL;
return rb_entry(left, struct sched_entity, run_node);
}
Note that _pick_next_entity()实际上没有遍历tree去找最左边的节点，因为这个值是被cache在rb_leftmost中的。这个函数的返回值的CFS选择的下一个运行的进程。如果函数返回值是NULL的话，这就没有最左边的节点。在这种情况下，就是没有可运行的进程，并CFS调用idle_task。
Adding Processes to the Tree
现在我们来看CFS是如何把进程添加到rb-tree并cache最左边的节点。当进程变得可运行的时候或者它第一次通过fork创建的时候，都会涉及到adding the processes to the tree.添加进程到tree是通过enqueue_entity()实现的：
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
/*
* Update the normalized vruntime before updating min_vruntime
* through callig update_curr().
*/
if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
se->vruntime += cfs_rq->min_vruntime;
/*
* Update run-time statistics of the ‘current’.
*/
update_curr(cfs_rq);
account_entity_enqueue(cfs_rq, se);
if (flags & ENQUEUE_WAKEUP) {
place_entity(cfs_rq, se, 0);
enqueue_sleeper(cfs_rq, se);
}
update_stats_enqueue(cfs_rq, se);
check_spread(cfs_rq, se);
if (se != cfs_rq->curr)
__enqueue_entity(cfs_rq, se);
}
这项函数更新了runtime和其他静态参数，并调用_enqueue_entity()去执行把entry插入rb-tree的实际工作：
/*
* 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;
s64 key = entity_key(cfs_rq, se);
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 (key < entity_key(cfs_rq, 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);
}
让我们来解析下这个函数。While()循环本身实在遍历这个tree，目的在于查找matching key，这个key就是vruntime。每一个平衡的tree的规则是如果当前节点的参数比右节点大，比左节点小的话，就把这个节点向左移动。如果有一次向右移的情况发生的话，最新插入的进程就不可能是新的最左边的节点，并且他会设置leftmost为0。如果仅向左移动，leftmost会保持为1，并且我们有有一个最左边的节点，更新cache，设置rb_leftmost为新插入的进程。当我们比较自己到一个没有子节点的节点的时候，这个循环就会结束了。当跳出循环后，函数会在父节点调用rb_link_node()，设置新插入的进程为新的child。函数rb_insert_color()更新tree的自平衡属性，我们会在第六章讨论color。
Removing Processes from the tree
最终，我们来讨论CFS是如何从rb-tree中移除进程的。如果说进程被阻塞（变得不可运行状态）或者结束运行（停止并退出）的时候，removing would occur。
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
{
/*
* Update run-time statistics of the ‘current’.
*/
update_curr(cfs_rq);
update_stats_dequeue(cfs_rq, se);
clear_buddies(cfs_rq, se);
if (se != cfs_rq->curr)
__dequeue_entity(cfs_rq, se);
account_entity_dequeue(cfs_rq, se);
update_min_vruntime(cfs_rq);
/*
* 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 (!sleep)
se->vruntime -= cfs_rq->min_vruntime;
}
跟添加进程到rb-tree的动作一样，这项工作的实际工作也是由函数_dequeue_entity()辅助执行的：
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);
}
从tree中移除进程的动作是相对简单的，因为rb-tree提供了rb_erase函数完成的所有的工作。这个函数的剩下部分是更新rb_leftmost cache。如果process-to-remove是leftmost节点，函数调用rb_next去查找遍历顺序下哪一个是下一个运行的进程。当当前leftmost节点被移除的时候，这就是下一个leftmost节点。
The Scheduler Entry Point
进程调度的主入口就是函数schedule(),定义在kernel/sched.c。kernel余下的工作调用这个函数去决策下一个运行的进程并执行它。也就是说with a runnable process找到最高优先级的调度器的类，并ask下一个运行的task。It should no surprise that schedule是如此简单。这个函数中唯一重要的部分是调用pick_next_task()，也定义在kernel/sched.c。函数pick_next_task() starting with最高优先级，遍历调度器类，并在最高优先级类里面选择最高优先级的进程。
/*
* 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);
if (p)
return p;
/*
* Will never be NULL as the idle class always
* returns a non-NULL p:
*/
class = class->next;
}
}
Note 在函数开始部分的optimization。因为CFS调度器是普通进程的调度器的类，并且大多数系统运行的是普通进程；如果可运行的进程数量等于CFS可运行的进程数量，这里有一个小技巧去选择下一个CFS提供的进程。
函数的核心就是for()循环，它会以优先级的顺序循环遍历每个类，starting with最高优先级的类。每个类完成pick_next_entity()函数（它会返回下一个可运行进程的指针，如果没有可运行进程的话，返回NULL）。第一个返回非NULL的类已经选择了下一个可运行的进程。CFS完成pick_next_task()调用pick_next_entity()（它会调用_pick_next_entity()函数）。
Sleeping and Waking up
处于睡眠（blocked）的任务是一种特殊的非可运行的状态。这很重要，因为没有这个状态的话，调度器会选择他们不想运行的进程，或者更糟糕的话，只能通过busy循环来实现sleep。一个任务睡眠的话，通常因为几种原因，但通常是为了等待某些事件。这些事件可能是一个具体的时间，或者文件I/O，也可能是硬件事件。如果在内核当中，任务试图获取已经contended的信号量的话，他也可能被强制进入睡眠状态。通常的睡眠原因是文件I/O，比如说一个任务执行read()请求文件，但是文件又需要从磁盘中读出的时候。另一个例子的话，任务可能在等待键盘输入。无论上述的例子是什么类型的，内核的行为总是一致的：任务mask自身为睡眠状态，put自己到等待队列，从rb-tree可运行队列中移除。
正如我们之前讨论的，状态TASK_UNINTERRUPTBLE和TASK_INTERRUPTBLE是和睡眠状态相关的；他们两个唯一的区别就是，TASK_UNINTERRUPTBLE是忽略信号量的，但是TASK_INTERRUPTBLE的话，如果信号量is issued话，会被很快唤醒并相应信号。这两种睡眠状态的任务都会在等待队列中，等待事件发生，并且处于不可运行状态。
Wait Queues
睡眠is handled via等待队列。等待队列是一个简单的进程列表，等待着特定的事件发生。等待队列在内核中的形式是wake_queue_head_t。等待队列可以通过DECLARE_WAITQUEUE()静态撞见或者init_waitqueue_head()创建。进程把自身放入等待队列并mark自己为不可运行的。当相关的事件发生的时候，处在队列中的进程就会被唤醒。正确地完成睡眠和唤醒动作，避免race conditions，是非常重要的。
一些简单的睡眠接口被广泛的使用中。但是那些接口是存在race conditions的：当条件变为真后，可能会进入睡眠。如果说这种情况的话，这个任务可能会永远的进入睡眠状态。因此，在内核中推荐的睡眠方法是有点儿复杂的：
/* ‘q’ is the wait queue we wish to sleep on */
DEFINE_WAIT(wait);
add_wait_queue(q, &wait);
while (!condition) { /* condition is the event that we are waiting for */
prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
if (signal_pending(current))
/* handle signal */
schedule();
}
finish_wait(&q, &wait);
任务会执行如下步骤把自己添加到等待队列中：
a) 通过宏DEFINE_WAIT()创建一个等待队列
b) 通过函数add_wait_queue()把自己添加到等待队列中。当任务等待的条件满足的时候，该等待队列会唤醒该进程。
c) 调用prepare_to_wait()函数改变进程状态为TASK_UNINTERRUPTBLE或者TASK_INTERRUPTBLE。这个函数在有需要的时候还会把任务添加到等待队列的后面，which is needed on subsequent of iterations of the loop.
d) 如果状态被设置为TASK_INTERRUPTBLE，一个信号会唤醒这个进程。这叫做苏醒（a wake up不是由于事件发生而导致的）。So check and handle signals。
e) 当任务被唤醒后，它会再次检查条件是否为真。如果是的话，它会退出循环。否则的话，它会再次调用schedule()并重复。
f) 现在条件为真了，任务自己本身把自己设置为TASK_RUNNING并通过finish_wait()从等待队列中移除自己。
如果在任务睡眠之前，条件发生了，循环就会终止，任务不会错误的进入睡眠状态。Note that:内核代码经常不得不在loop循环体中执行各种任务。比如说，在调用schedule()之前，可能要释放lock，或者调用schedule()之后，重新获取lock；或者重新react其他事件。函数inotify_read()在fs/notify/inotify/inotify_user.c就是一个使用等待队列的最直接例子。
static ssize_t inotify_read(struct file *file, char __user *buf,
size_t count, loff_t *pos)
{
struct fsnotify_group *group;
struct fsnotify_event *kevent;
char __user *start;
int ret;
DEFINE_WAIT(wait);
start = buf;
group = file->private_data;
while (1) {
prepare_to_wait(&group->notification_waitq,
&wait,
TASK_INTERRUPTIBLE);
mutex_lock(&group->notification_mutex);
kevent = get_one_event(group, count);
mutex_unlock(&group->notification_mutex);
if (kevent) {
ret = PTR_ERR(kevent);
if (IS_ERR(kevent))
break;
ret = copy_event_to_user(group, kevent, buf);
fsnotify_put_event(kevent);
if (ret < 0)
break;
buf += ret;
count -= ret;
continue;
}
ret = -EAGAIN;
if (file->f_flags & O_NONBLOCK)
break;
ret = -EINTR;
if (signal_pending(current))
break;
if (start != buf)
break;
schedule();
}
finish_wait(&group->notification_waitq, &wait);
if (start != buf && ret != -EFAULT)
ret = buf - start;
return ret;
}
这个函数很好的诠释了我们的例子。主要的区别在于它在while()循环本身去检查condition，但是我们是在while()这里检查。这是因为检查conditions是相当复杂的并要求获取lock.循环通过break结束。
Waking up
唤醒是通过wake_up()来实现的，它会唤醒所有处于等待队列中的任务。它调用try_to_wake_up()，which设置任务的状态为TASK_RUNNING，调用enqueue_task()去添加任务到rb-tree中，并且如果唤醒任务的优先级高于当前运行的任务的话，需要设置need_resched。The code that causes the event to occur typically calls wake_up() itself.比如说，当数据从磁盘到达后，VFS calls wake_up()。
关于睡眠的话，特别需要注意的就是spurious wake up。因为任务被唤醒不意味着他等待的事件已经发生了；睡眠应该总是被handled in loop,在循环中来确保他已经等待的条件发生了。Figure 4-1显示了每一个调度器之间的关系；
Preemption and Context Switching
上下文切换是通过定义在kernel/sched.c中的context_switch()函数处理的。当一个新的进程被选择运行的时候，调用schedule()再调用到context_switch()。他会做出如下两种工作：
a) 调用context_mm()去切换虚拟内存映射，从原来的进程切换到新的进程。
b) 调用switch_to()区切换处理器状态，从原来的进程切换到新的进程。这就涉及到保存和恢复stack信息、处理器寄存器、任意架构相关的状态（这些都必须被管理到和还原基于每个进程的信息）
但是，内核必须知道什么时候调用schdule()。如果仅仅在code explicitly调用到schedule()，用户空间的程序可能会无限期的运行下去。相反的，内核会提供flag need_resched去指示出reschedule是否需要重新执行（see Table4.1）。当进程需要重新被调度的时候，flag是通过scheduler_tick()设置；当唤醒的进程比当前进程的优先级高的时候，flag是通过try_to_wake_up()设置。内核代码会检查flag，查看flags是否被设置，调用schedule()去切换到新的进程。这个flag对于内核来说是一个msg，调度器需要尽快的调用到，因为其他的进程是渴望运行的。
返回到用户空间后或者从中断返回后，the need_resched flag需要检查。如果被设置了，在continue之前，调度器就需要被调用进来了。
The flag是对于每一个进程的而不是全局的，因为在进程描述符中访问一个参数比全局变量要快（因为being cache hot的话，current的快速和他的high probability）。历史原因，在2.2内核之前，the flag是全局变量的。在2.2和2.4中，the flag是task_struct中的int变量。在2.6内核中，他被移动到thread_info结构体中的一个特殊的single bit flag。
User Preemption
当内核将要返回到用户空间、need_resched被设置的时候，用户抢占发生了；紧接着调度器开始涉及到。如果内核正在返回到用户空间，他知道他是出于一种暂时安静的状态。换句话说，如果继续执行当前进程是安全的话，选择一个新的进程去执行也是安全的。因此，无论什么情况下，当内核准备返回到用户空间、从中断中返回或者从系统调用中返回，参数need_resched都需要被检查。如果被设置了，调度器就会介入选择一个新的进程去执行。从中断中返回的paths和系统调用返回的paths都是硬件架构相关的，通常来说是在entry.s（它除了包含kernel入口的代码还包含kernel退出的代码）中完成的。
简而言之，用户抢占发生的情形：
a) 当从系统调用返回到用户空间的时候
b) 当从中断handler返回到用户空间的时候
Kernel Preemption
Linux内核不像大多数Unix操作系统一样，它是完全可抢占的内核。在非抢占的内核当中，内核代码会一直运行直到完成。也就是说，当代码处于在内核态中的时候，调度器是不能重新调度任务的；内核代码是合作的而不是抢占的。内核代码会一直运行指导它完成或者被阻塞。但是在2.6内核中，Linux内核变得是可抢占了：只要内核代码处于安全的可以抢占的状态，Linux内核代码都是可以抢占的。
所以什么时候内核才是安全可以抢占的呢？只要内核代码没有持有锁的时候，都是可以抢占的。也就是活，locks已经变成了marker of nonpreemptibility。由于内核是SMP-safe的，如果没有持有锁，当前代码都是可重入和能抢占的。
支持内核抢占的第一项改变就是增加抢占计数器,preempt_counter到每一个进程的thread_info。这个计数器从0开始，每次每个lock被require的时候都会加一，每次每个lock被release的时候都会减一。当counter为0的时候，内核就是可以抢占的。从中断返回之后，如果返回到内核空间，内核会检查参数need_resched和preempt_count。如果need_resched被设置和preempt_count为0的话，more important任务是可运行的，他可以安全的抢占。因此调度器就会被调用到了。如果preempt_count是非0的，a lock是被持有的，这时候抢占是不安全的。在这种情况下，中断返回到当前执行的任务。当当前任务持有的所有的锁都被released的时候，preempt_count计数为0.在那时候,the unlock code检查need_resched是否被设置。如果被设置到了，调度器会被调用到。
当任务在内核中阻塞或者调用schedule()，内核抢占可以明确的执行。这种形式的内核抢占是总是被支持的，因为你不需要做额外的工作去确保内核处于安全抢占的状态。也就是说当调用schedule()的时候，代码是知道内核处于安全抢占的状态的。
内核抢占可能发生的情形：
a) 当中断handler退出，返回到内核空间之前
b) 当内核代码变得再次可抢占的状态的时候
c) 如果内核任务确定的调用schedule()时候
d) 如果内核任务阻塞的时候（which results in a call to schedule()）
Real-time Scheduling Policies
Linux提供两种实时调度器策略，SCHED_FIFO和SCHED_RR。通常的，非实时的调度器策略是SCHED_NORMAL。通过调度器策略的frame_work，这些实时调度器策略是不受CFS调度器管理的，但是需要被一个特殊的实时调度器管理，defined in kernel/sched_rt.c。本章的余下部分我们会讨论调度器策略和算法；
SCHED_FIFO完成了一个简单的first-in,first-out的调度算法，没有时间片。一个可运行的SCHED_FIFO任务总是调度在SCHED_NORMAL任务之上。当SCHED_FIFO任务变得可运行的时候，他可以一直运行指导它阻塞或者它放弃处理器；它没有时间片，能够无限的运行下去。只有更高优先级的SCHED_FIFO或者SCHED_RR任务能够抢占SCHED_FIFO任务。两个或者多个SCHED_FIFO同一优先级的任务以round-robin的方式运行；但是仅仅他们决定放弃处理器的时候，才会放弃处理器。如果一个SCHED_FIFO任务是可运行的，所有的低优先级的任务在高优先级任务变得不可运行之前都是不能够运行的。
SCHED_RR更SCHED_RR是一样的，except that每个进程仅能运行预设的时间片的时间长度；也就是说SCHED_RR是SCHED_FIFO的带时间片的版本—它是实时的、round-robin的调度算法。当SCHED_RR任务消耗完他的时间片后，任意其他的同优先级的实时进程都会被调度round robin。时间片是用来仅允许同优先级进程的重新调度的。至于SCHED_FIFIO的话，一个高优先级的进程总是立刻抢占低优先级的进程，并且低优先级的进程是用来从来不能抢占SCHED_RR进程，即使他的时间片已经耗尽了。
两种实时的调度策略都完成了static的属性。内核不会计算实时任务的动态优先级。这保证了一个高优先级的实时的进程总能够抢占低优先级的进程。
Linux提供的是一种软实时的实时调度策略。软实时的策略的含义是：Linux尽可能的在deadline内调度应用，但是内核没有保证总是达到这个目标。相反地，硬实时的系统保证保证在一定的限制内满足调度要求。Linux没有保证去满足实时任务的调度。尽管没有去保证具备硬实时调度的能力，但是Linux的实时调度室相当的优秀的。2.6内核是具备能力去满足一定严格时间的要求的。实时任务的优先级的范围是0-(MAX_RT_PRIO-1)。默认来说，MAX_RT_PRIO是100，因此，默认的实时任务的优先级范围是0-99.这个优先级范围是和nice value的SCHED_NORMAL共享的。默认情况下，它是-20到+19 nice范围直接映射到优先级空间为100-139.
Scheduler-Related System calls
Linux提供了一系列调度器参数管理相关的系统调用。这些系统调用允许操作进程的优先级、调度策略和处理器亲和力，还提供一种机制可以放弃处理器给其他任务。
各种不同的书以及man pages都提供了这些系统调用的参考。Table 4.2 list简要的介绍了这些系统调用。
Processor Affinity System calls
Linux调度器enforces hard 处理器亲和力。也就是说，虽然软亲和力或者自然亲和力在努力保进程在同一个处理器上面运行，调度器也告诉用户：这个任务必须保持在统一处理器上面，无论什么原因。This hard处理器亲和力的话，是在任务的task_struct存储了bitmask,as cpus_allowed.这个bitmask的per bit指明了系统中可能的处理器。默认情况下是，all is set。因此，一个进程潜在的情况下，是可能在所有的处理器上面运行的。但是用户通过sched_setaffinity()可以提供不同的bitmast，包含一个或者多个bits。相似的，也可以利用sched_getaffinity()去获取当前cpus_allowed的bitmask。
内核强制hard处理器亲和力是一个简单的manner。首先，当一个进程首先被创建的时候，它会继承他的父进程的亲和力Mask。因为父进程运行在允许的处理器上面，子进程因此也运行在这个处理器上面。第二、当处理器亲和力改变了的时候，内核使用migration threads把当前任务Pull到合法的处理器。最终，负载均衡器把任务pull到唯一允许的处理器。因此，一个进程仅仅能够运行在他的进程描述符中cpus_allowed允许的处理器上面。
Yielding Processor Time
Linux给进程提供了sched_yield()系统调用去放弃处理器给其他等待的进程。他的工作方式是把进程从active array中移除，插入到expired array。 这不仅仅抢占进程和put it在优先级列表的末尾，还put it在expired list（一段时间内保证他不会运行）。因为实时任务从来不会expire，这是一个特殊的情况。因此，他们仅仅移动到优先级列表的末尾（不插入到expired array）。在早期的Linux的版本中，sched_yield()调用时相当的不同的；他们仅把任务移至优先级列表的末尾。这种放弃的时间通常来说没有多久。今天来说，应用甚至是内核代码，在他们调用sched_yield()之前，都应该确定自己是真的要放弃处理器了。
As a convenience,内核代码可以调用yield()，这样确保任务是TASK_RUNNING,再调用sched_yield()。用户空间的应用使用系统调用sched_yield()。
