综述
内核调度子系统负责进程调度，调度程序决定让哪个进程运行、什么时候运行、运行多久。调度程序的目标有两个：一个是最大化系统资源的利用率，一个是减少和用户的交互延迟，让用户觉得多个进程在同时运行。这两个目标是冲突的，需要做trade-off。
多任务操作系统
多任务操作系统指的是指可以多个进程同时交错执行的操作系统。在单处理器机器上，用户会产生有多个进程同时在不同的处理器上在同时执行的错觉。多任务系统可以分成两种：协作式（cooperative）和抢占式（preemptive）多任务系统。包括Linux、Windows在内的大部分操作系统都属于抢占式多任务系统。
抢占式多任务操作系统中，调度程序决定一个进程什么时候停止执行。调度程序终止一个进程的执行（并不是这个进程自愿的）并让另一个进程执行的行为被称为抢占，进程在被抢占之前可以运行的时间一般由调度程序预先确定，被称为时间片（timeslice）。时间片一般是动态计算的，Linux没有直接使用时间片，而是使用了处理器比例（processor proportion）来规定进程运行时间。
协作式多任务操作系统中，调度程序无法决定进程可以运行多久，一个进程除非自己主动地暂停并放弃CPU，否则可以一直执行下去，独占CPU，不会出现抢占的情况。进程通常会主动暂停执行，否则系统可能就会宕机了。
I/O-Bound进程和Processor-Bound进程
进程可以分为I/O-Bound和Processor-Bound，前者代表进程花费大量时间提交和等待I/O请求，这种类型的进程通常执行一段很短的时间，然后阻塞等待新的I/O，大部分GUI应用属于I/O bound，虽然GUI应用很少读写磁盘，但是他们花费大量时间等待用户通过键盘和鼠标进行交互。Processor-Bound进程是花费大量时间执行代码的进程，通常只有被抢占的时候才会停止执行，因为他们不会因为I/O请求被阻塞。对于Processor-Bound进程，调度策略倾向于让进程以较少的运行次数执行较长的时间，即每次运行时间较长。
这两种类别并不是互斥的，进程可以同时具有这两类行为，X Windows Server既是I/O-Bound也是Processor-Bound。文字处理软件大部分时间在等待用户输入（I/O-Bound），但是某些时刻会进行拼写检查或者宏计算等（Processor-Bound）。
调度程序必须尝试同时满足两个互相冲突的目标：快速响应（低延时）和最大化系统利用率（高吞吐量）。为了选择“最有价值的”的进程执行并同时照顾其他低优先级的进程，调度器通常需要采用非常复杂的调度策略。Unix系统的调度策略通常优先考虑低延时目标，Linux为了确保优秀的交互响应和桌面系统性能也优先考虑低延时目标，但是Linux采用的调度策略并不会忽视Processor-Bound进程（稍后会说）。
进程优先级
基于优先级的调度算法是一种典型的调度算法，根据进程的价值和需求给进程一个合适的优先级，通常（Linux中不是这样做的），优先级高的进程先于优先级低的进程运行，优先级相同的进程使用循环(round-roubin)方式运行。此外，优先级高的进程还会获得更长的时间片。
Linux内核中进程可以分为互斥的两种：普通进程（normal process） 和 实时进程（read-time process）。后者的优先级永远高于前者，两者分别使用独立的优先级范围，只有当没有实时进程需要运行时，普通进程才能够获得调度。前者使用nice值，是一个-20到19之间的数值，nice值越大，优先级越低（对其他进程来说你很nice），nice值越小优先级越大（这个进程对其他进程来说不nice）。不同的Unix系统对nice值的处理是不一样的，Mac OS X中使用nice值确定时间片的绝对长度，Linux中，nice值控制时间片的分配比例（timeslice proportion），nice值越小，获得的比例越大（这里的比例可以理解度时间片的相对长度）。Linux中使用ps -el命令可以查看进程的nice值（NI列），值为“-”的进程是read-time process，没有nice值。
read-time process使用read-time priority，默认范围为0~99（包括0和99）。Read-time priority值越大，优先级越高。可以使用ps -eo state,uid,pid,ppid,rtprio,time,comm 查看real-time优先级（RTPRIO列），值为“-”的进程是normal process。
时间片
时间片表示进程在被抢占之前可以运行的时间，调度策略必须指定一个缺省的时间片，这是一个艰巨的任务。时间片太长会导致系统的交互性能下降，时间片太低又会导致大量的CPU时间被浪费在了进程切换上面。同时还要考虑I/O bound进程不需要很长的时间片（但是需要较高的执行频率），processor-bound需要较长的时间片（保持cache hot）。Linux使用的CFS调度程序并不会直接给进程分配一个绝对大小的时间片，而是给进程分配处理器比例（processor propotion）。所以在Linux中进程获得的处理器时间是系统负载的函数，系统负载越大，每个进程获得的处理器时间越短。而处理器比例又会受到nice值的影响，nice值表现为分配处理器比例时的权重，nice值越大，权重越小，nice值越小，权重越大。
举个例子-文本编辑器和视频编码器
假设系统中有两个正在运行的进程：一个文本编辑器和一个视频编码器，文件编辑器是I/O-Bound（因为几乎所有时间都是在等待用户输入，不管用户打字多快，对于CPU来说都是慢到奶奶家去了），视频编码器是Processor-Bound。用户希望在自己按下键盘时，文本编辑器可以快速响应。视频编码器，除了读入数据和写出视频外，所有时间都花费在了编码上，很容易消耗100%的CPU。视频编码器的的编码速度肯定是越快越好，但是运行时间并不是非常重要，早一秒晚一秒差别不大。
对文本编辑器，我们有两个目标，首先，我们希望它有大量的处理器时间可用，不是因为它需要大量处理器时间（并不需要），是因为我们希望在需要时，文本编辑器总是拥有足够的处理器时间。其次，我们希望文本编辑器被唤醒的的时候可以抢占视频编码器。在大部分操作系统中，上述目标通过给文本处理器更高的优先级和更大的时间片来完成。Linux也实现了上述目标，但是采用了不同的方式，Linux使用的调度程序CFS（Completely Fair Scheduler，详细介绍在后面）确保给文本编辑器分配足够的处理器比例（processor propotion），假设系统中只有这两个进程，并且两个进程的nice值是相同的，那么每个进程将获得50%的处理器比例。因为文本处理器大部分时间都阻塞等待用户输入，所以文本编辑器使用的处理器比例实际远远低于50%，而视频编码器会使用远超过50%的处理器比例。关键在于文本编辑器wake up时，此时调度程序CFS注意到文本编辑器进程拥有50%的处理器比例，但是只使用了很小的一部分，即CFS发现文本编辑器比视频编码器运行了”更短的时间”，所以为了确保公平，CFS会暂停视频编码器进程（抢占），让文本编辑器立刻执行。文本编辑器快速地处理完用户输入之后，又会进入睡眠状态，等待下次被用户输入唤醒。不断重复这个过程，最终的结果是CFS总会保证文本编辑器在需要执行的时候能够立刻执行，其他的时间则全部分配给视频编码器。
CFS调度程序（Complitely Fair Scheduler）
Linux中的调度程序是在不断发展完善的，2.6.23内核开始采用CFS调度程序，调度程序的发展历史可以参见这篇文章Linux 调度器发展简述。传统的调度程序为进程直接分配时间片造成了固定的进程切换频率和分配的不公平。CFS对时间片分配方式进行了彻底的重新思考，并抛弃了时间片分配而是转而给每个进程分配处理器比例（processor proportion）。这样做的结果是实现了可变的进程切换频率并保证了公平性。
CFS是基于下面的理念的：假设一个有着n个进程的系统中有一个理想的、完美的多任务处理器，每个进程都将获得1/n的处理器时间。即确保任何可测量周期内，每个进程都运行相同多的时间，假设有两个进程，在10毫秒周期内，每个总的运行时间都是5ms，那么理想情况下，我们可以视作每个进程都运行了10ms，每个使用了50%的CPU性能，这种模型被称为完美的多任务处理系统。但是实际上这种模型是不实际的，因为没有考虑到进程切换的代价：一方面是切换操作的成本，另一方面是会对cache命中率造成影响。CFS会让每个进程运行一段时间，调度时选择当前执行时间（使用的是virtual runtime，后面有介绍）最少的进程作为下一个运行的进程。CPU使用nice值来计算每个进程获得的处理器比例（processor proportion），nice值越大（优先级越低）获得的处理器比例越低。同时系统中的进程越多，每个进程获得的处理器比例也越低。
CFS会设定一个目标周期（target latency），根据每个进程的处理器比例分配一个目标周期总的“时间片”。目标周期设定得越小，每个进程获得的时间片就越小，系统的交互响应速度就越快，但同时进程切换的开销也越大。假设目标周期设定为20ms，每个进程的优先级相同，即处理器比例相同，那么如果有2个进程，每个进程的时间片为10ms，如果有4个进程，每个进程的时间片为5ms，如果有20个进程，时间片将为1ms。如果进程数无限增加，那么每个进程的时间片将趋近于0。很明显，这将导致不可接受的进程切换开销。所以CFS为时间片设定了一个最小粒度（minimum granularity），默认为1ms。这是为了保证系统性能做的trade-off，这种情况下并不是完全公平（completely fair）。但是时间片没有超过最小粒度之前，CFS仍然是完全公平的。
Linux进程调度的实现
CFS由四个组件组成：
- 运行时间记录（Time Counting）
- 进程选择（Process Selection）
- 调度程序入口（The Scheduler Entry Point）
- 睡眠和唤醒（Sleeping and Waking Up）
运行时间记录（Time Counting）
调度程序需要记录进程运行的时间，CFS使用调度程序实体结构（scheduler entity structure）来记录进程运行时间，该结构使用struct sched_entity来存储，进程描述符task_struct结构中的se保存每个进程的sched_entity。 sched_entity中的vruntime保存进程的虚拟运行时间（即实际运行时间经过加权计算后的时间），vruntime的单位是纳秒，所以不受系统的timer tick的粒度限制。在一个理想的完美多任务操作系统中，每个进程的vruntime应该都是相同的（实际环境中做不到）。内核使用update_curr()函数来更新运行进程的vruntime，系统时钟（system timer）会定期调用update_curr()，此外每当有进程进入runnable状态或者blocked状态时，也会调用update_curr()来更新vruntime。
进程选择（Process Selection）
虽然无法做到让每个进程的vruntime相同，但是我们可以使vruntime尽可能的接近，所以CFS每次会选择vruntime最小的进程来运行。CFS使用红黑树来管理所有处于runnable状态的进程，使用进程的vruntime作为红黑树的key。红黑树是一种平衡二叉查找树，树最左边的节点是树的最小值，所以CFS每次都会选择最左边的节点的进程来运行，实际上，CFS并不会每次对红黑树进程查找，它使用rb_leftmost来存储最左边的节点，这样将查找最小节点的时间复杂度从O(lgN)降到了O(1)。如果红黑树为空，意味着没有runnnable的进程，此时CFS会选择idel task（PID为0的进程）来执行。
每当有进程进入runnable状态或者通过fork()创建了一个新的进程时，CFS就会将该进程加入红黑树。每当有进程进入blocked状态或者停止执行（terminate）时，CFS会将该进程从红黑树中移除。
调度程序入口（The Scheduler Entry Point）
最主要的调度程序入口是schedule()函数。schedule()函数会找到优先级最高的调度类（scheduler class），并从该调度类获得下一个要运行的进程，如果该调度类没有runnable进程，就会检查优先级次高的调度类，以此类推。例如，CFS是用来调度普通进程（normal process）的，调度实时进程（real-time process）的调度类优先级比CFS更高，所以会先检查实时进程的调度类，然后才到CFS。
睡眠和唤醒（Sleeping and Waking Up）
睡眠状态（sleeping），即阻塞状态（blocked）是一种特殊的不可运行（nonrunnable）状态。进程进入睡眠状态的原因多种多样，比如等待I/O完成或者是请求的资源暂时无法获得等。不管是什么情况，在内核中的表现是一样的：进程将自己标识为sleeping，将自己加入等待队列（wait queue），并将自己从runnable进程的红黑树中移除，然后调用schedule()，让调度器选择一个新的进程去执行。唤醒（waking up）是相反的：进程被标识为runnable，被从wait queue中移除，并插入runnable进程红黑树中（不一定马上运行，需要调度器选中它才可以运行）。
等待队列(wait queue)有很多个，每个等待队列存储等待某个特定事件的所有进程。当某个事件发生时，内核会唤醒该事件对应的等待队列上的所有进程。通常是导致该事件发生的代码调用wake_up()来唤醒该数据的等待队列上的所有进程。比如当磁盘中的数据读取完成时，VFS会调用wake_up（）。
上下文切换和调度时间点
CPU从一个进程切换到另一个进程需要进行上下文切换，schedule()会调用context_switch()函数来完成上下文切换。该函数首先会调用switch_mm()将虚拟内存映射从上一个进程的切换到下一个进程的，然后调用switch_to()来保存上一个进程的处理器状态并恢复下一个进程的处理器状态，包括栈信息、处理器寄存器和其他架构相关的每个进程自有（per-process）的处理器状态。
内核必须要知道什么时候该调用scheduler()，如果只让进程自己主动调用scheduler()的话，用户程序可以无限期地运行下去，这显然是不行的。内核使用need_resched flag来表明是否应该调用scheduler()。scheduler_tick()和try_to_wake_up()（当优先级比正在执行的进程高的进程被唤醒时try_to_wake_up()会被调用）都可能会设置need_resched。need_resched用来告诉内核有一个进程“更值得”运行，应该尽快调用scheduler()。
对于用户空间进程，调度可能会发生在（need_resched被设置时才会调用调度器）：
- 进程从系统调用中返回用户空间之前
- 进程从中断处理程序中返回用户空间之前
内核进程也是可以被抢占的，但是和用户进程有些不一样，当正在运行的进程是内核进程时，还要判断内核进程是否持有锁(lock），内核进程每获得一个锁，preempt_count就会加1，只有preempt_count为0且need_resched被设置时才会调用调度器。
对于内核空间进程，调度可能会发生在：
- 中断处理程序退出，在返回内核空间之前
- 内核进程可以被抢占时（即preempt_count**变为**0时）
- 内核进程自己主动调用scheduler()
- 内核进程阻塞（阻塞的结果是scheduler()会被调用）
书中没有提到用户空间进程阻塞的问题，我现在还不是很清楚，推测是因为阻塞只有可能发生在内核空间。
实时（Real-Time）调度策略
Linux提供了两种实时调度策略：SCHED_FIFO 和 SCHED_RR，非实时调度策略为SCHED_NORMAL。实时调度的进程优先级永远高于SCHED_NORMAL进程。
SCHED_FIFO是一个简单的先进先出的调度算法，没有时间片的概念。一个实时进程只有在阻塞、主动放弃处理器或者被更高优先级的实时进程抢占时才会暂停或者停止运行。同等优先级的进程使用循环（round-robin）的方式运行，但是也只有在实时进程阻塞或者主动放弃处理器时，才会执行循环队列中的下一个进程。低优先级的实时进程无法抢占高优先级的实时进程，高优先级的实时进程进入runnable状态时，总是会立刻抢占低优先级的实时进程。
SCHED_RR是SCHED_FIFO加上时间片的版本，每个实时进程用完时间片后，其他和该实时进程优先级相同的实时进程可以被调度。但是低优先级的仍然不会被调度，直到没有比它优先级更高的实时进程时才会被调度。和SCHED_FIFO一样，高优先级的实时进程总是可以立刻抢占低优先级的实时进程。
通过这两个调度策略，Linux提供了一个软实时调度，和硬实时调度的区别在于，软实时调度会尽力使进程能在deadline之前运行，但是不保证一定能做到。而硬实时调度就是保证可以满足任何调度要求。虽然不能做到硬实时调度，但是Linux的实时调度算法性能还是不错的。
进程优先级保存在进程描述符task_struct中的rt_priority域中，实时优先级和SCHED_NORMAL的优先级共用优先级空间（即共用rt_priority域），其中 [0, MAX_RT_PRIO) 为实时优先级空间，[MAX_RT_PRIO, MAX_RT_PRIO+40)为普通优先级区间，这个区间会被映射到[-20,+19]，即nice值的范围。MAX_RT_PRIO的默认值为100。
和调度程序相关的系统调用
| System Call | Description |
|---|---|
| nice() | Sets a process’s nice value |
| sched_setscheduler() | Sets a process’s scheduling policy |
| sched_getscheduler() | Gets a process’s scheduling policy |
| sched_setparam() | Sets a process’s real-time priority |
| sched_getparam() | Gets a process’s real-time priority |
| sched_get_priority_max() | Gets the maximum real-time priority |
| sched_get_priority_min() | Gets the minimum real-time priority |
| sched_rr_get_interval() | Gets a process’s timeslice value |
| sched_setaffinity() | Sets a process’s processor affinity |
| sched_getaffinity() | Gets a process’s processor affinity |
| sched_yield() | Temporarily yields the processor |
其中，只有root权限的进程可以给nice()传入负值（即减少nice值），进程的处理器affinity通过bitmask的方式表明该进程可以在哪些处理器上运行。普通进程和实时进程调用sched_yield()放弃处理器的结果是不一样的，实时进程只会放弃处理器，普通进程不仅会放弃处理器，还会造成进程一段时间内不会被再次运行。
参考资料
《Linux Kernel Development 3rd Edition》
《Understanding The Linux Kernel 3rd Edition》