在参与面试的时候，Linux 的进程应该算是我的必问题目，因为很多语言并没有去实现一套进程管理和调度，而是直接借用了操作系统的能力，尤其 Python 社区认为这方面没必要重复造轮子，而使用了系统调用的简单封装。因此，如果对 Linux 进程不甚了解，很难真的了解自己写的并发代码到底会发生什么。
调度程序是内核中确保进程能有效工作的子系统，负责决定将哪个进程投入运行，何时运行以及运行多少时间。调度程序的合理调度，是将系统资源最大限度发挥的保证。
从 1991 年 Linux 的初版直到 2.4 版本的内核，Linux 的调度程序都相当简陋，设计非常原始。但在 2.5 的内核中，调度程序采用了一种叫做 O(1) 的调度程序（因为其调度算法的时间复杂度为 O(1)）。但是 O(1) 调度程序对时间敏感、需要用户交互的程序先天不足，表现欠佳（也许因为这个原因早期 Linux 桌面版推进缓慢），在 2.6 内核的开发时便特意对交互类程序优化，并引入了新的调度算法，其中最著名的即是 翻转楼梯最后期限调度算法（Rotating Staircase Deadline scheduler，RSDL）。直到 2.6.23 内核中，该算法彻底地替换掉了 O(1) 算法，并被称为 完全公平调度算法，即 CFS。本文将重点介绍 O(1) 算法和 CFS 算法，并简单讲下 CFS 是如何实现的。
多任务与调度基本概念
Linux 能同时并发的交互执行多个进程的多任务操作系统。在多核处理器机器上，多任务操作系统能使多个进程在不同处理器上真正的并行执行，而在单核处理器机器上，只是产生多个进程同时执行的幻觉。无论是单核还是多核，操作系统都能使得多个进程处于阻塞或者睡眠状态，只将适合执行的进程交给处理器执行。
多任务系统一般分为 非抢占式多任务 和 抢占式多任务。而 Linux 属于后者，也就是 由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会 。其中，这个强制挂起的动作，即是抢占（preemption），而进程在被抢占之前能够运行的时间是预先设置好的，而且有一个专门的名字，叫进程的时间片（timeslice）。
时间片是实际分给每个 可运行进程 的处理器时间段，很多操作系统都采用了动态时间片计算方式，也就是说分给进程的时间片具体是多少绝对时间是根据机器的负载动态计算的，而不是指定完就不再变化的。不过，Linux 的调度程序本身并没有通过分配时间片来达到公平的调度。
调度程序的精髓在于调度算法，算法策略决定调度程序在何时让什么进程执行，那么我们先提几个实际的问题来理解调度算法要做的事情。
IO 密集型和 CPU 密集型
进程可以被分为 IO 密集型和 CPU 密集型。前者的大部分时间用来提交 IO 请求或者等待 IO 请求，这样的进程经常处于运行的状态，但是通常每次都会运行短短的一会儿，因为它在等待更多的 IO 请求时最后总会阻塞。相反，CPU 密集型把时间大多用在执行代码上，除非被抢占，否则会一直执行下去，因为它们没有太大的 IO 请求或者没有太多可能被阻塞。而操作系统为了响应速度的考虑，调度器并不会让它们经常运行。
因为系统需要考虑到响应速度，调度器只需要保证不让 CPU 密集型长时间运行就可以，但有些程序不完全符合这两种分类，比如 Word 之类的办公软件，经常等待键盘输入（等待 IO），而在任意时刻，又可能粘住处理器疯狂的处理拼写检查和宏计算。
怎么让调度策略在两个矛盾的目标中间寻找平衡：响应迅速和最大系统利用率。不同的系统有不同的解决策略，但通常是一套复杂的算法，但大部分算法都无法保证低优先级的进程能被公平对待，而 Linux 的 CFS 基本解决这个问题（进程数量不会巨大的情况下）。
进程优先级问题
调度算法中最基本的一类就是基于优先级的调度，这是一种根据进程的价值和其他对处理器需求分级的想法。而一般分为两种，一种是优先级高的先运行，低的后运行，相同优先级的进程按轮转的方式进行调度。另一种是优先级高的进程使用的时间片比较长，调度程序总选择时间片未用尽而且优先级最高的进程运行。
Linux 采用了两种不同的优先级范围，第一种是用 nice 值，它的范围是 -20 ~ +19，默认为 0，而且 nice 值越高优先级越低。相对低优先级（高 nice 值）的进程，高优先级（低 nice 值）的进程可以获得更多的处理器时间。但对这个时间的分配，各个系统采用不同的方法，比如 macOS 采用了时间片的绝对值，而 Linux 中使用时间片的比例。
第二种范围是实时优先级，默认值为 0 ~ 99，与 nice 值相反，实时优先级数值越高，优先级越高，任何实时进程的优先级都高于普通进程，也就是说，这两个优先级范围是独立不相交的。而实时进程是 Linux 为有时间有严格要求进程的优待。
时间片
时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略都会规定一个默认的时间片，但对于默认时间片的确定并不简单，如果时间片太长，往往就会延迟进程切换，使得系统对交互的响应表现欠佳，如果时间片太短，会明显增大进程切换带来的处理器耗时。
所以，任何时长的时间片都会导致系统表现欠佳，很多操作系统都非常重视这点，因此时间片默认一个比较适中的大小，比如 10ms。在 Linux 中 CFS 并没有使用绝对长度，而是将 CPU 的使用 时间比 分配给了进程，这样一来，Linux 中的进程获得的处理器时间和机器负载密切相关。
Linux 中进程获得的比例还会受到 nice 值影响，从而体现了优先级的作用。在多重条件影响下，内核就可以以时间片为依据来决定进程的运行：如果新的进程消耗的使用比当前执行的进程小，这立马剥夺当前进程的执行权，并把新进程投入运行。
需要用户交互的进程
前面提到，用户交互的进程更注重实时性，因此处理起来非常特别，我们举一个实际的例子来说明 Linux 是怎么处理需要用户交互的进程的。
如果有一个非常消耗 CPU 的进程，比如编译一个巨大的 C 程序，以及一个非常注重交互的记事本等类似的文字处理程序。对于编译进程来说，我们并不在意什么时候运行，早半秒还是晚半秒对我们来说没有差别，但是如果能尽快完成就再好不过了，而对于记事本进程，我们更希望在敲击键盘后立马看到反馈（立马抢占编译进程）。
对于实现上述需求依靠的是系统对记事本分配更高的优先级和更多的时间片（可能涉及到系统自动识别记事本程序需要更高的优先级），但在 Linux 中却采用了非常简单的方式，甚至不需要分配不同的优先级。如果两个进程 nice 值相同，那么这两个进程会分别各获得 50% 的 CPU 时间（Linux 下的时间片是个比例）。因为记事本不停的等待用户的输入，无疑大部分时间将是编译进程在执行，因此，记事本肯定用不到 CPU 的 50% 而编译程序肯定超过 50%。当用户输入的时候，会发现刚被唤醒的记事本使用比小于正在执行的编译进程，便立马抢占，从而快速响应。在记事本完成工作继续等待用户输入时，会被挂起将执行权再次分配给编译进程。
调度算法
上文通过一些简单的概念来描述了调度器做了什么，下面就开始正式讨论调度算法。
调度器类
在讲调度算法之前，需要先说明调度器类。Linux 调度器是以模块的方式提供的，这是为了允许不同类型的进程可以有针对性的选择调度算法。而提供不同调度算法的模块即是调度器类。像 CFS 就是一个针对普通进程的调度器类（定义在 kernel/sched_fair.c 中），在 Linux 中称为 SCHED_NORMAL（在 POSIX 中称为 SCHED_OTHER）。
每个调度器都有一个优先级，内核会先选择优先级最高的调度器，然后由该调度器调度进程并执行。
O(1) 调度算法
在讲 CFS 之前，先介绍下传统的 Unix 调度算法：O(1) 调度算法。现代进程调度器有两个通用的概念： 进程优先级和时间片 ，时间片是指进程运行多少时间，进程创建之后就被赋予一个时间片，优先级更高的进程运行的更频繁，而且往往拥有更多的时间片，这就是 O(1) 调度算法的实质。
很明显，除了让优先级更高的进程可以尽可能抢占之外，O(1) 调度算法还根据优先级来给时间片加权。但是，前面提到，传统的调度算法使用的 绝对的时间长度，这也引起了部分问题，比如有两个不同优先级的进程，一个 nice 值为 0，另一个为 1，那么他们经过加权的时间片长度分别是 100ms 和 95ms，他们的时间片非常接近，但是如果将 nice 值改为 18 和 19，这时他们的时间片变为了 10ms 和 5 ms，这时前者是后者两倍的运行时间，因此，尽管 nice 值只相差 1 但最后的结果却是差别巨大。
因此 CFS 完全摒弃时间片的绝对分配，而是分配处理器的使用比重。
CFS 调度算法
CFS 的出发点基于一个简单的理念： 进程调度的效果应该如同系统具备一个理想中的完美多任务处理器 。在这种系统中，每个进程将获得 1/n 的处理器时间（如果有 n 个进程）。比如我们有两个可运行进程，先运行其中一个 5ms，然后再运行另外一个进程 5ms，如果进程切换够快，那么在 10ms 内仿佛可以同时运行两个进程而且各自使用了处理器一半的能力。
当然这并不现实，首先一个处理器无法真正的同时运行多个任务，而且进程间切换是有损耗的，也无法做到无限快的切换，CFS 采用了折中的做法：让每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法。 CFS 在所有可以运行的进程总数基础上计算出一个进程应该运行多久，而不是依靠 nice 值来计算时间片（nice 值只影响比重而不是绝对值）。
每个进程都按其权重在全部可运行进程中所占比例的 “时间片” 来运行，为了准确的计算时间片，CFS 为完美多任务中的无限小调度周期的近似值设定了一个目标，称为：目标延迟。越小的调度周期带来越好的交互性，同时也越接近完美的多任务（但同时需要更多的切换开销）。举例我们将目标延迟定位 20ms，那么如果有两个同优先级的进程，那么每个进程在被抢占前只能运行 10ms，而如果有 5 个这样的任务，那每个任务只能允许 4ms。
但是，上面这个例子中，如果进程数目非常多，比如超过 20 个，那么每个进程获得运行时间还不到 1ms，甚至可能小于进程切换所消耗的时间。当然，Linux 为了避免这种事情发生，设定了一个底线，被称为最小粒度（一般默认 1ms）。因此，只能说 CFS 在进程数目不巨大的情况下比较公平（一般系统中也就运行几百个进程，这种规模下 CFS 还是非常公平的）。而对于不同优先级的进程中，CFS 也是表现良好，比如目标延迟依然为 20ms，这两个进程一个 nice 为 0，另一个为 5，那么后者的权重将是前者的 1/3，即两个进程分别获得了 15ms（20 * 2/3） 和 5ms（20 * 1/3） 的处理器时间。而如果两个进程的 nice 值分别为 10 和 15，因为权重关系没有改变，因此两个进程依然分别获得 15ms 和 5ms 的处理器时间。所以，nice 值 不在影响调度决策，只有相对值才会影响处理器时间的分配比例。
在 CFS 下，任何进程所获得的处理器时间是由它自己和其他所有可运行进程 nice 值的相对差值决定的。nice 值由算数加权变为了几何加权，正是将时间片的绝对值变为了使用比，使得在多进程环境下有了更低的调度延迟。
CFS 的实现
在讨论了种种概念之后，终于到了重点，即 CFS 算法的实现。相关的代码在 kernel/sched_fair.c 中，我们的关注点主要下面四个地方：
- 运行时间的记录
- 选择投入运行的进程
- 调度器的选择
- 睡眠与唤醒
运行时间的记录
上文讲到，CFS 的核心在于 CPU 的使用比，那么对于进程的运行时间的记录非常重要。多数 Unix 系统，分配一个绝对时间的时间片给进程，当每次系统时钟节拍发生时，时间片都会被减少一个节拍周期。每当一个进程的时间片被减少到 0，他就会被尚未减少到 0 的进程抢占。
但 CFS 并没有绝对的时间片，但它依然需要对每个进程的运行时间记账，以确保每个进程只在公平分配给它的处理器运行时间内运行。而记账的信息会保存其结构体指针 se 在进程的 task_struct 中（参照前一篇文章《你需要了解的 Linux 进程管理》）。
在结构体中，有一个重要的成员变量 vruntime，即是记录了该进程的总运行时间（花在运行上的时间和），而且这个时间经过了加权（优先级、机器负载等因素）。虚拟时间是以 ns 为单位的，因此 vruntime 和系统定时器节拍不再相关。
内核通过定时调用 uodate_curr() 函数（定义在 kernel/sched_fair.c）来更新进程的 vruntime，该函数计算了当前进程的执行时间，并将调用 __uodate_curr() 获得根据机器负载（可运行的进程总数）对运行时间加权后的值，然后将该值与原有的 vruntime 相加获得新的 vruntime。
选择投入运行的进程
如果存在上文中描述的 “完美多任务处理器”，那么每个可运行的进程的 vruntime 值应该一致。然而这样的处理器是不存在的，那么 CFS 就会尽力去向这个方向靠拢，即在每次选择进程时，会挑选 vruntime 最小的进程。
CFS 使用红黑树来组织可运行队列，红黑树简称 rbtree，是一种自平衡的二叉搜索树，树上的每一个节点都对应了一个键值，可以通过键值来快速检索节点上的数据。后面我会单独写文章介绍数据结构（数据库索引一般也是基于红黑树）。
CFS 会维护一个包含了所有可运行进程的红黑树（相关代码在 kernel/sched_fair.c 中），节点的键值便是可运行进程的虚拟运行时间，CFS 调度器需要选取下一个运行的进程时，只需要 __pick_next_entity() 方法找到树中虚拟运行时间最小的进程（即搜索树的最左侧的叶子节点，其实为了快速访问这个节点，内核专门拿出了一个全局变量），并将这个进程投入运行。
如果有阻塞的进程满足了等待的条件或者有通过 fork() 创建的新进程，便会通过 enqueue_entity() 方法插入到该红黑树中，为了保证能尽快响应，新插入的节点会和最左叶子节点比较，如果新节点是最左叶子节点，调度器会立马把新进程投入运行。
相反，如果有进程堵塞（或者其他）变为不可运行的状态，调度器会通过 dequeue_entity() 方法将该进程从红黑树中移除，如果移除的是最左节点，这会调用 rb_next() 方法找到新的最左节点。
调度器的选择
正如前面讲到的，内核支持多种调度器，而 CFS 只不过是其中一种。进程调度的主要入口点是定义在 kernel/sched.c 下的函数 schedule()，它完成的事情就是选择一个进程，并将其投入运行，而它的逻辑非常简单：
- 调用
pick_next_task()获得一个 task - 将这个 task 投入运行
而真正和调度器相关的逻辑在 pick_next_task() 中，pick_next_task() 做了下面的事情：
- 按照调度类的优先级遍历
- 只有该调度类下有可运行进程，立马返回
pick_next_task() 为 CFS 做了一个简单的优化，如果所有的可运行任务都在 CFS 调度器下，就不再遍历其他调度类，而是不停的从 CFS 调度器里拿任务。
睡眠与唤醒
休眠（阻塞）的进程处于一个特殊不可执行的状态，阻塞的原因可能很多，比如等待一个信号，或者等待用户键盘的输入等，无论哪种，内核的操作是相同的：进程把自己标记为休眠状态，从可执行红黑树中移除并放入等待队列，然后调用 schedule() 选择和执行一个其他进程。
上一篇文章讲过，休眠有两种进程状态：TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE，无论哪种状态，休眠的进程都在同一个等待队列上。
等待队列 是由等待某些事件发生的进程组成的简单链表，当与等待队列相关的事件发生时，队列上的进程会被唤醒，为了避免产生竞争条件，休眠和唤醒的实现不能有批量。但如果简单的实现，有可能导致在判定条件为真后，进程却开始了休眠，那么就会使进程无限期地休眠下去，因此进程按以下处理加入等待队列：
- 调用宏
DEFINE_WAIT()创建一个等待队列的项 - 调用
add_wait_queue()把自己加入到队列中 - 调用
prepare_to_wait()将进程的状态变为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE - 如果状态被设置的是
TASK_INTERRUPTIBLE则信号唤醒（伪唤醒），以检查并处理信号 - 唤醒之后检查等待条件是否为真，是则跳出循环，否则再次调用
schedule()并一直重复 - 跳出循环（条件满足）后，进程将自己设置为
TASK_RUNNING并调用finish_wait()方法把自己移除等待队列
唤醒操作通过 wake_up() 完成，它会唤醒指定的等待队列上的所有进程，wake_up() 的主要逻辑在调用的 try_to_wake_up() 中：
- 将进程设置为
TASK_RUNNING - 调用
enqueue_task()将此进程放入红黑树中 - 如果唤醒的进程比当前执行的进程优先级高则立马抢占
- 设置
need_resched标记（标记是否触发重新调度）
不过如上面提到的，因为有伪唤醒，所以进程被唤醒不一定都是因为等待的条件达成。
抢占进程上下文切换
上下文切换是指从一个可执行进程切换到另一个可执行进程。在文章的最后，讲讲进程的上下文切换和抢占的问题。
内核处理的上下文切换的函数 context_switch() 定义在 kernel/sched.c，他基本完成了两件事情：
- 调用
switch_mm()把虚拟内存从上一个进程映射切换到新进程中 - 调用
switch_to()从上一个进程处理器状态切换到新进程的处理器状态（包含栈信息、寄存器信息等）
内核即将返回用户空间的时候，如果 need_resched 被标记，则会导致 schedule() 被调用，此时就会发生用户抢占。因为从内核返回到用户空间的进程知道自己是安全的，它既可以继续执行，也可以选择一个新进程去执行，所以无论是系统调用后还是中断后，进程都可以检查 need_resched 被标记，来判断是否需要重新调用 schedule()。总之，一般用户抢占发生在：
- 从系统调用返回用户空间
- 从中断处理程序返回用户空间
因为 Linux 完整的支持内核抢占，所以只要调度是安全的（没有持有锁），内核就可以在任何时间抢占正在执行的任务。Linux 的锁的判断是通过计数实现的，在 thread_info 中引入了 preempt_count 来记录持有的锁，当该值为 0 的时候，则该进程是安全的，而恰好该新进程设置了 need_resched 标记，那么当前进程可以被抢占。
如果内核中的进程被阻塞了，或显式调用了 schedule()，则内核会发生显式的抢占。显式的抢占从来都是受支持的，因为如果一个函数显式的调用 schedule()，说明它自己是清楚可以被安全的抢占。
内核的抢占一般发生在：
- 中断处理程序正在执行，且返回内核空间之前
- 内核代码再一次具有可抢占性的时候
- 如果内核中的任务显式调用
schedule()的时候 - 内核中的任务阻塞时
