Linux Kernel Development 笔记（三）进程调度

进程调度是内核一个控制哪个进程，什么时候，如何运行的一个很重要的子系统。进程调度把有限的处理器时间在可运行的进程中进行分配，是多任务操作系统的基础。调度

背后的原理很简单，就是如何最有效的利用处理器时间。多任务操作系统是一个能同时交叉执行多个进程的系统，可以让单处理器系统看上去多处理器系统一样工作。多任务分为协助式多任务以及抢占式多任务。Linux属于后者，就是说可以强迫正在运行的进程定制并让新的进程开始运行。在进程被抢占前的运行时间是不可预知的，这个时间称为时间片。

管理时间片，让调度系统可以对系统做出全局的调度决定，同时也阻止一个进程独占一个处理器。Linux的进程调度从简单但呆板（仅能让系统存在一个可运行的进程），到O(1)时间片算法的调度台（可处理不敢说100，但10个可运行进程），一直到目前的CFS（完全公平的调度系统）。策略是调度台决定进程什么时候运行的一种行为，通常会通盘考虑系统的情况来决定，对最优化使用处理器时间负责。

进程分为I/O限制的进程以及处理限制的进程。I/O限制的进程是指那些花多数时间来等待或递交I/O请求的进程。此类进程仅仅运行一小段时间，并最终会被阻塞在I/O上（这里的

I/O不是指一般的读写，包括任何类型的阻塞资源，如键盘，网络等）。大部分GUI应用，也可以算是I/O限制进程，因为他们虽然没有具体的参与I/O，但会花大部分时间等待用户

的交互响应。相反，处理限制进程则花大量时间用在代码的执行上，一直运行到被抢占为止。它们很少会阻塞在I/O请求上。调度策略会倾向让处理限制的进程运行时间长一些，

但次数少一些。一个极端的例子就是执行一个无限循环，一般的例子就是执行如Matlab之类的繁重处理的任务。当然，这个进程的分类不是互斥的，进程可以展示两种特性。

调度策略必须尝试满足两个目标：快速的处理响应（低延时）以及系统的最优化利用（高吞吐）。调度系统往往要采用负责的算法来完成这样不一致的要求，以决定让最值得

运行的进程运行同时也让低优先级的别的进程得到公平对待。Linux是基于拥有良好交互体验以及桌面性能为目标的，故此Linux会更多的偏向I/O限制进程，但也采用创新的方法

让处理限制的进程得到照顾。

一种普遍的调度算法类型是基于优先级的。目标是根据一个进程对自身重要性以及对处理时间的需求性来评级别，一般的做法（Linux不是这样做）是高优先级的进程先运行，

低优先级的进程后运行，相同优先级的进程则按照先导先得。Linux内核实现了两种分离的优先级范围。第一种是nice值，范围-20到+19，默认值为0.越大的nice值对应的优先级越低（就是说，你对别的进程很nice）。nice值在Unix系统是标准的优先级值，在Mac OS系统是控制进程获得绝对时间片分配，但在Linux则是控制获得时间片的比例。另外一种是实时优先级，这些值是可配置的，但默认是从0到99. 与nice相反，越高的数值代表越高的优先级。

时间片是一数字量值，代表一个进程运行到被抢占的时间。调度系统必须推荐一个进程默认的时间片，这是一个难题。时间过长会导致响应变慢，时间过短，会浪费处理器因频繁切换进程所耗的时间。I/O限制进程与处理限制进程的冲突也是一个难题，一个希望运行时间短，一个希望运行时间长，也给调度台造成难题。Linux采用了一种新奇的做法，就是只分配进程一个处理器的比例。因为进程获得的处理器的时间数量是一个依据系统目前的而定的函数。这个比例还会被后续进程的nice所影响。nice值就如一个权重，更改每个进程获取处理器的比例。在大部分的操作系统中，处于可运行状态的进程是否可以抢占当前运行的进程并立即运行，是由进程的优先级以及可获得的时间片决定的。而Linux，在采用CFS调度算法下，是由新的可运行的进程会占用处理器多少比例而定。如果它比例小，则可以抢占，否则不可以抢占，等待下一次。

考虑一下例子：

一个文本编辑的进程以及一个视频编解码的进程。文本编辑进程属于I/O限制进程，它大部分时间都是属于等待用户按键（不管用户按多快，事实还是达不到机器的速度），

一旦收到按键，用户是希望这个编辑器能立即响应。但视频编解码则不同，除去从硬盘读取数据外，大部分的时间都是处理编解码，故此其属于处理限制的进程。其不要求

有一个何时完成的限制，用户也不关心其响应时间。这个场景下，系统调度最理想的是给予文本编辑进程比视频编解码进程更多比例的处理器份额，因为文本编辑进程是交互

式的进程，需要快的反应。对与文本编辑进程，希望它能获得更多比例的处理器资源，并不是说它要占用很多处理器时间，而是为了让它有需要用处理器的时候可以很容易的

获得调度，同时也希望它在用户按下键的时候能抢占视频编解码进程。大部分的系统调度会给予文本编辑进程高的优先级以及大的时间片来达到以上目标。高级的调度算法，甚至可以检测到文本编辑进程是一个交互式的进程并自动的采用上述机制。Linux也能让文本编辑进程达到以上目标，但是采用别的方式。假设系统目前只有这两个进程，Linux给这两个进程的nice值一样，则意味着两个进程获得一样比例的处理器资源，但因为文本编辑进程每次运行的时间很短，同时大部分时间都处于等待，故此其即使被分配了50%

的处理器资源，但它用不上那么多。相反，视频编解码进程则会使用可能超过50%，以至于可以快点处理完。文本编辑进程被唤醒的时候，Linux注意到，它是被分配了50%的

处理器资源但却没有全用上，同时也判定它比视频编解码进程用的处理器资源少。因此，本着公平原则，Linux会立即的抢占视频编解码进程，给文本编辑进程运行。只要文本

编辑都没用用上系统给其分配的50%处理器资源，CFS（completely fair schedule）会一直采用此方式，保证文本编辑进程在有需要的时候可以运行并让视频处理进程获得余下的时间。

Linux的调度是模块化的，称为调度类，可以采用不同的调度算法来对不同类型的进程进行调度。调度类允许不同的插件算法一起工作，来调度它们自己类型的进程。每一个调度类都优先级，最高优先级并且其管辖下的进程处于可运行时候，此调度优先采用，其他调度则依优先级遍历一次。Linux采用CFS作为一般进程的调度算法。早期的UNIX调度算法是把nice值映射为进程能获得的处理器资源的具体时间片，这种做法存在以下弊端：

1. 要建立nice与时间片的映射必须考虑每一个nice值具体映射多少时间片。这导致了一个不良的进程切换行为。举个例子，加入0 nice值对应 100 毫秒时间片， 20 nice值对应5 毫秒时间片，再假设系统只有两个进程，一个nice为0，一个nice为20. 则在105毫秒的时间内，0 nice的进程获得20/21 比例的处理器资源，20 nice的进程获得1/21比例的处理器资源，则在105毫秒内，只切换一次进程。假如两个进程的nice是20，则两个进程获得的时间片是5毫秒，则在105毫秒时间内，这两个进程切换了许多次。从此可看出这种这两种分配方式都不是理想的。这都是因为nice与具体的时间片挂钩导致的。

2. nice值因为与具体的时间片挂钩，会造成nice减一导致的效果会因nice的起始值不同而变化很大。举例，假如nice从0到1变化，则时间片对应是100与95，则100与95相差不多。如果nice是从18到19，其对应的时间片是10跟5，则10跟5的差别就相当大了，因为是两倍的差别。

3. nice值要对应具体的时间片，则系统必须有能力提供一种可测量的方式让时间片可测量。对于系统来说，时间片或许是timer tick的整数倍。最小的时间片对应的timer tick时间也有一个底数，最高10毫秒或最低1毫秒。系统的timer限制了2个时间片的差值范围，连续的nice值也许对应的时间或跟10毫秒一样，或跟1毫秒一样。最后，时间片会因timer tick的不同而变化。

4. 对于那些希望优化交互操作进程的调度系统来说，也许会让新激活的进程优先级提高以便其可立即运行，即使它的时间片耗完。虽然此方法提高了交互的操作，但也引入了不好的情况，会让一个进程非公平性的获得过多的处理器时间，而让剩下的进程处于饥饿状态。

以上这些情况，都可以采取具体的方式来解决，但这些方法都是掩盖了问题的本质。CFS采用的方式，从根本上解决了此问题，那就是把nice与时间片的映射方式抛弃，采用nice与获得处理器资源的比例都应，从而获得固定的公平以及变化的进程切换率，而非原来的固定的进程切换率以及变化的公平。

CFS调度模型基于一个简单的概念：让进程调度就像系统拥有一个完全理想的多任务处理器。此系统中，每一个进程占用1/n的处理器时间（假如n个可运行进程），系统会用无限小的时间让进程运行，以达到在一个可测量时间内，所有进程都运行相同的时间。举个例子，两个进程在早期的Unix系统或许会分到5毫秒以及5毫秒的时间片，在依次在各自时间片内运行占用100%的处理器。但在理想的系统中，则会让两进程同时运行10毫秒，各占用50%处理器资源，这就是所谓的完美多任务。当然，这样的完美模型是不现实的，因为在单一处理器上，是不能做到字面理解上的多进程同时运行，而且也不可能让进程运行无限小的时间。虽然我们希望达到如此，但CFS不得不考虑更现实的问题，就是调度带来的开销以及性能问题。CFS不会直接指定一进程的时间片，而是采用了一个以可运行进程的数量为依据的方法来计算一个进程可运行多长。CFS采用权重的方式。

每个进程能运行的时间是与其权重成比例的。要计算具体的时间片，CFS会为在完美多任务系统中实现无限小调度时间设定一个目标，称之为目标时延。 越小目标时延产生更好的交互性能，但牺牲了进程切换的性能引起整体性能的问题。例如：设定目标时延为20毫秒，则2个同优先级的进程，每个进程就会分的10毫秒时间片。20个进程就每个分的1毫秒时间片。注意到，当可运行的进程数达到无限，则每个进程获得的处理器比例无限接近0，最终导致不可接受的切换代价。故此CFS设定了一个时间片的最低标准，称为最小粒度，一般为1毫秒。因此，就算有无数个进程，每个进程最少也能分的1毫秒时间片，从而保证了切换代价也有一个限度。每个进程获得的处理器比例是由不同进程间的nice差值决定的。

linux调度CFS是由四个部分组成的：时间计算，进程选择，调度入口点，休眠以及唤醒。

1. 所有的进程调度都会计算进程运行的时间。每一次系统时间tick，时间片就减少一个tick时间，当时间片为0，则进程被非0的时间片进程抢占。CFS是采用sched_entity结构体来跟踪进程时间计算的，此结构并作为task_struct的一个项。结构中的vruntime保存了一个进程的虚拟运行时间，是由实际运行时间基于可运行进程数目标准化的来的。单位是纳秒一次与tick时间是分开的。该变量是用来帮助近似达到CFS所希望的”理想化多任务处理器“目标。因为现实不能如此完美的多任务进行，我们必须顺序的执行每一个进程，故此虚拟运行时间来计算进程运行了多久以及应该运行多久。update_curr函数是用来更新此数值的函数，会被系统定期的执行，也在进程变成可运行或被阻塞变成不可运行状态下执行。在这样的方式下，vruntime是一种对进程运行时间准确的测量，以及对下一个该运行进程的指示。

2. 正因为现实不能实现完美的多任务，CFS尝试去平衡每个进程的虚拟运行时间：当CFS决定那个进程运行的时候，它会选最小虚拟运行时间的进程。CFS采用红黑树来管理所有的可运行状态的进程。查找最小vruntime的进程，就是查找红黑树的最左端节点。

3. 执行调度的入口是通过函数schedule来进行的。内核的其他系统会调用此函数来触发进程调度，决定那个进程要运行并运行它。对于调度类来说，它是最基本的，而且也是简单的，因为它仅仅就是选择拥有可运行进程的最高级别的调度类，并询问它下一个要运行的进程是那个。而schedule调用了pick_next_task来完成此任务，此函数会从高级别的调度类开始，遍历所有的调度类，并在最高级别的调度类中选择出最高优先级的进程。

4. 进程的休眠，会被内核打上非运行的状态，这样调度才会忽略此进程。进程的休眠有多种原因，但总是在等待某个事件。一般普遍的原因是读取文件或I/O。休眠的过程：进程给自己打上休眠的几好，把自己放到等待队列，把自己从可运行的红黑树中移除，最后调用schedule来选择一个新进程运行。唤醒是反过程：进程打上可运行的标志，从等待队列移除，把自己插进可运行红黑树上去。进程休眠是由等待队列来处理的，休眠的进程会被放进等待队列，等待某件事件的发生。进程执行休眠的过程如下：

a. 创建等待队列，由 DEFINE_WAIT 宏来创建

b. 把自己通过宏add_wait_queue放到等待队列里。当等待的条件为真的时候，进入休眠。

c. 调用prepare_to_wait去更改进程的状态为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTILE

d. 如果状态是变为TASK_INTERRUPTIBLE，信号可以唤醒进程。由信号唤醒的方式称为 伪唤醒（即唤醒不是等待的事件）

e. 如果进程被唤醒了，要检查条件是否正确，不正确则继续调用schedule

f. 如果条件正确，退出循环，调用finish_wait把进程状态设置为TASK_RUNNING并把自己从等待队列中移除。

唤醒过程则调用wake_up，让进程状态变为TASK_RUNNING，同时把进程加进可运行的红黑树里。要注意一点是，唤醒有可能是伪唤醒。

上下文切换（从一个进程切换到另外一个进程）是由context_switch来执行的，由schedule调用。该函数执行了两个基本的工作：

1. 调用swtch_mm来切换虚拟内存映射，从上一个进程到新进程。

2. 调用switch_to来切换处理器状态，这涉及到保存栈信息，寄存器和任何与架构指定相关的必须维护的状态。

内核必须知道啥时候去调用schedule。内核提供了一个need_resched的标志来表示是否需要重新调度，如果设置了，内核会调用schedule来切换进程。从返回到

用户态或从中端返回，都需要检查一下这个标志，如果设置了，在继续运行前，内核会调用schedule。这个标志是每个进程都拥有的，不是一个全局的，因为访问

进程描述结构比访问全局变量要快，linux早期，这个变量是全局的。

用户抢占发生在两种时候：当从系统调用返回到用户态时候，当从中断调用返回到用户态的时候。

内核抢占，必须发生在内核处于安全调度的时候才可以。所谓的安全调度时刻，是指内核没有持有锁（用来标识非抢占的区域）。为了实现此机制，提供了preempt_count变量（存在thread_info中)。初始值为0，当申请锁的时候，加一，释放锁的时候减一。当此变量为0时候，内核是可被抢占的。从中断返回时，会检查need_resched和preempt_cout。如果need_resched设置了，同时preempt_count为0，则更重要的进程就可以获得运行，此时内核是安全可被抢占的。如果preempt_count不为0，则中断直接返回当前执行的进程中。内核抢占发生在：当从中断调用返回到内核空间时，当内核代码变成可被抢占时，当在内核的进程主动调用Schedule时，当内核的进程被阻塞时。

Linux也提供了两种实时调度策略，SCHED_FIFO 和 SCHED_RR。 非实时的调度策略是SCHED_NORMAL。此种调度策略，通过调度类的框架，由一种特殊的实时调度来执行，而非CFS。SCHED_FIFO是一种先进先出的不需要时间片的调度算法。当SCHED_FIFO的进程可运行时候，它就会一直运行直到它被阻塞或自己放弃处理器。高优先级的SCHED_FIFO 或 SCHED_RR可以抢占一个SCHED_FIFO的进程。两个或更多的SCHED_FIFO同优先级进程会按顺序执行，但只有它们自愿才会让出处理器资源。如果一个SCHED_FIFO的进程在运行，则所有低优先级的SCHED_FIFO进程只有当其处于非运行状态才有可能被运行。SCHED_RR是一种带时间片的SCHED_FIFO，当时间片耗尽，则该进程也就释放处理器资源，让同等优先级SCHED_RR进程运行。高优先级的SCHED_RR也能抢占低优先级的SCHED_RR，即使其时间片没用完，但低优先级的SCHED_RR进程就算高优先级的进程时间片耗尽，也不能抢占高优先级的进程。两种实时调度策略都是采用静态优先级，即内核不能实时的调整优先级。这保证了给定优先级的进程能总是抢占低优先级的进程。这两种策略实现了软实时的能力（即系统尽量任务在指定的限期内完成，但不保证）。实时优先级是从0到99，SCHED_NORMAL优先级是与实时优先级使用同一个优先级空间，它们是从100开始。对与nice（-20到+19）来说，映射到100到139.

Linux提供了sched_yield系统调用来让进程明确的释放处理器资源给其他等待中的进程。该函数会把调用的进程从活跃队列中移除，并插入到过期队列中同时也让进程排到同等级别进程列表末尾。（实时调度的进程，则仅仅是排在同等级别的进程末尾，不需要插进过期列表中去）内核代码，会调用yield（会先保证该内核状态下的进程是运行中，然后再调用sched_yield)。用户态进程则直接调用sched_yield。