进程调度, since 2020-11-07 Sat
(2020.11.07 Sat)
内核负责决定如何在进程间分配有限的计算资源，最终让用户获得最佳的使用体验，内核中安排进程执行的模块叫做调度器(scheduler)。
进程状态Process status
- 就绪(ready)：进程已经获得了CPU以外的所有必要资源，如进程空间，网络连接等，就绪状态下的进程等到CPU，便可立即执行
- 执行(running)：进程获得CPU，执行程序
- 阻塞：当进程由于等待某个时间而无法执行时，便放弃CPU，处于阻塞状态
进程被创建后，自动变成就绪状态。如果内核把CPU分配给进程，则从就绪变成执行状态。执行状态下，进程执行指令，最为活跃。正在执行的进程可以主动进入阻塞状态，比如这个进程需要将一部分硬盘中的数据读取到内存中，读取期间，进程主动进入阻塞状态，让出CPU。读取结束，计算机硬件发出信号，进程再从阻塞状态恢复为就绪状态。进程也可以被迫进入阻塞状态，比如收到SIGSTOP信号。
调度器是CPU时间管理员。它需要做两件事：
- 选择某些就绪的进程来执行
- 打断某些执行中的进程，使其变回就绪状态
并不是所有的调度器都有上面第二个功能。有些调度器是单向切换，即只能使进程从就绪变成执行，不能反过来。支持双向状态切换的调度器被称为抢占式(pre-emptive)调度器。
调度器让一个进程变回就绪，就会让另一个就绪的进程开始执行，从而最大效率使用CPU时间。如果执行的进程主动进入阻塞状态，调度器会选一个就绪的进程来使用CPU时间。上下文切换(context switch)是指进程在CPU中切换执行的过程。内核承担上下文切换的任务，负责存储和重建进程被切换之前的CPU状态，使得进程感觉不到自己被切换。开发者不用专门写代码处理上下文切换。
进程的优先级
根据优先级，进程分为两类：
- 实时进程(real-time process)，优先级高，需要尽快被执行的进程。他们不能被普通进程所阻挡，如视频播放和监测系统
- 普通进程(normal process)，优先级低，更长执行时间的进程，如文本编辑器，批处理一端文档，图形渲染
其中的普通进程根据行为的不同，还分为互动进程(interactive process)和批处理进程(batch process)。互动进程有图形界面，需要处于长时间的等待状态，一旦特定事件发生，互动进程需要尽快被激活。批处理进程没有与用户交互，往往在后台被默默执行。
实时进程由Linux系统创造，普通用户只能创建普通进程，这两种进程的优先级不同，实时进程优先级永远高于普通进程。进程优先级是从0到139的整数，数字越小，优先级越高。0-99留给实时进程，100-139留给用户进程。
一个普通进程的默认优先级是120，修改用户进程的默认优先级的指令
$nice -n -20 ./app # -20指的是从默认优先级减去20，该整数范围-20到19
默认优先级调整之后将会变成执行时的静态优先级(static priority)。调度器最终使用的优先级根据的是进程动态优先级，公式
如果结果小于100或答曰139，会取100到139范围内最接近计算结果的数字作为实际的动态优先级。Bonus是一个估计值，越大，代表着它可能越需要被优先执行。如果内核发现进程需要经常跟用户交互，会把Bonus设置成大于5的数字。否则设置成小于5.
O(1)和O(n)调度器
最原始的调度策略是按照优先级排列好进程，等到一个进程运行完了再运行优先级较低的一个，但是这个策略完全无法发挥多任务系统的优势。随着时间推移，操作系统的调度器多次进化。
Linux2.4退出O(n)调度器，该表达与算法复杂度的表达一样，n代表操作系统中的活跃进程数量，O(n)表示该调度器的时间复杂度和活跃进程的数量成正比。
该调度器把时间分成大量的微小时间片(Epoch)，每个时间片开始的时候，调度器会检察所有处在就绪状态的进程，计算其优先级，选择优先级最高的进程执行。一旦切换，进程可以不被打扰的用尽这个时间片，如果没有用尽这个时间片，该epoch的剩余时间会增加到下一个时间片中。
该调度器每次使用epoch前会检察所有就绪进程的优先级。检查时间和进程数目n成正比，这也是称为O(n)的原因。该调度器没有很好的可扩展性。
Linux2.6开始使用O(1)调度器。该调度器每次选择要执行的时间都是1个单位的常数，和进程数量无关。该调度器的创新处在于，它会把进程按优先级拍好，放入特定的数据结构中(heap?)，在选择下一个要执行的进程时，不用遍历进程，直接选择优先级最高的进程。
O(1)也把epoch分配给进程，优先级为120以下的进程epoch为
优先级为120及以上的epoch为
O(1)会用两个队列来存放进程，一个称为活跃队列，存储那些待分配epoch的进程；一个称为过期队列，存储已经享用过epoch的进程。调度器把epoch从活跃队列中调出一个进程。这个进程用尽epoch，就会转移到过期队列。当活跃队列所有进程都被执行后，会把活跃队列和过期队列对调，用同样的方式继续执行。
加入优先级之后，上述过程变得复杂。系统会创建140个活跃队列和过期队列，对应优先级从0到139的进程。最初，所有进程都被放进活跃队列中。系统从优先级最高的活跃队列开始依次选择进程来执行，如果两个进程的优先级相同，则被选中的概率也相同。执行一次后，该进程会被从活跃队列中剔除。如果该进程在epoch中没有被彻底完成，会被加入到同优先级的过期队列中。当140个活跃队列的所有进程都被执行完成后，过期队列中可能会有很多进程，此时调度器将其对调，继续执行。直到结束。
普通进程的执行策略并没有保证优先级高的进程会被先执行完进入结束状态在执行优先级低的进程，而是在每个对调活跃和过期队列的周期中都有机会被执行，这种设计是为了避免进程饥饿(starvation)，也就是优先级低的进程很久都没有机会被执行。
O(1)的缺点在于进程的运行顺序和epoch长度依赖于优先级。调度器根据平均休眠时间来调整进程优先级，假设那些休眠时间长的进程在等待用户互动，这些互动类的进程应该获得高的优先级，以便获得更好的用户体验。一旦这个假设不成立，O(1)调度器对CPU的调度就会出现问题。
完全公平调度器Completely fair scheduler
2007年的Linux2.6.23用CFS取代O(1)。CFS不对进程进行任何形式的估计和猜测。
CFS增加了一个虚拟运行时(virtual runtime, vr)概念。每次一个进程在CPU中被执行了一段时间，会增加它的vr记录。每次选择要执行的进程时，不是优先选择最高优先级的进程，而是vr最少的进程。采用的是红黑树结构取代了O(1)调度器的140个队列。红黑树可以高效的找到vr最小的进程 。
CFS能让所有进程公平的使用CPU。为了使得优先级的设置有意义，CFS会根据进程的优先级来计算一个epoch因子。同样是增加250纳秒的vr，优先级低的进程实际获得的可能只有200纳秒，而优先级高的进程实际获得的可能有300纳秒。
Reference
1 Vamei，周昕梓著，树莓派开始，玩转Linux，中国工信出版社，电子工业出版社，2018
