三 Linux OS进程调度机制探讨
这里将探讨一下Linux OS的进程调度实现的原理，具体代码就不深挖了。
先来说说一些基础知识：
3.1 进程调度相关基础知识 在一个系统中，经常运行着多个进程，和CPU个数相比，当然是进程数远远大于CPU个数咯，那么就存在为进程分配CPU资源的问题。一般而言，有两种分配方式，一个是由进程间协调，例如一个比较友好的进程在一定的时刻主动让出CPU，这样其他进程就有机会使用CPU。但是这种类似道德上的约束往往行不通，因为总会有“恶意“进程存在嘛！另外一个比较难以克服的问题是友好的标准没法统一，例如什么时候该友好一下？除了这种不靠谱的道德约束外，大师们又引进了抢占式分配，这种分配方式类似法律约束。每个进程会分配一定的CPU资源，OS也会定时（处理时钟中断）+定点（比如系统调用返回到userspace前，）检查进程的CPU资源使用情况。一旦某个进程CPU资源消耗完毕，则会毫不留情地挑选下一个进程运行。 在操作系统理论中，CPU资源一般用时间片（time slice）来表示。直观意义就是分配给一个进程可以运行在CPU上的时间。也就是CPU资源是用时间单位来衡量的。当然，进程调度是一套复杂的算法，图2展示了Linux上进程调度算法的演化历史。
图2 Linux进程调度算法演化史
从使用CPU的方式来看，进程大体可分为I/O-bound和CPU-bound。二者有什么不同呢？I/O-bound类型的进程大部分时间都处于等待I/O的状态，当然这种I/O是广义的，例如等待用户按键事件，等待磁盘读写完成。而CPU-bound对于那种需要大量计算的进程，例如一个软件编解码算法，最极端的就是一个while死循环。从用户体验来说，I/O-B这种进程大部分都是需要人机交互的。OS设计进程调度算法时，一般偏向于IO-B进程，这样至少用户用起来不会感觉不爽。3.2 Linux进程调度研讨
1. 调度算法
我们先介绍下和进程调度息息相关的进程优先级相关的知识。
最直观的想法就是给每个进程设置一个调度优先级，然后按照round-robin方式每次挑选一个优先级最高的进程运行。那么，在Linux中，这个调度优先级是通过nice值来反映的，从-20到19。值越大表示该进程越nice，这个nice是对其他进程的nice，所以优先级越低。
再解决优先级的概念后，我们再来看第二个基本问题：CPU资源：time-slice是什么？以及它如何与优先级结合起来？
最先想到的就是time-slice应该是一个时间单位，例如20ms。然后每种调度优先级的time-slice和该级别有某种计算关系，例如线性。假设0级对应的时间片是20ms，那么1级的就是15ms。 默认时间片（对应0度优先级）该取多大呢？太大的话（例如2秒）则会导致漫长（从CPU速度来看）的用户等待，例如每个进程都需要运行2秒才会让出CPU，这样的系统运行起来给人一顿一顿的感觉。而太小的话（例如1ms）则会导致CPU把大量时间浪费在进程上下文切换。前辈们经过长期的实际使用，一般系统设置的默认时间片在20ms或者10ms。这种以时间（一般为ms）作为时间片单位，并且将时间片与优先级直接映射的方式有什么缺点呢？
我们考虑二个例子：
假设0级对应100ms的时间片，那么20级对应的时间片为5ms。现在系统上就一个0级进程和一个20级进程在运行。在105ms内，0级进程将运行100ms（占20/21），而20级进程将运行5ms（占1/21）。好。假设现在仅有2个20级进程，同样在105ms内，却要每5ms切换一下进程（因为20级进程每次只能运行5ms），那么105ms内切换了52次。从这个例子可以看出，简单的时间片映射对优先级低的进程极其不公平。例如在只有两个20级进程的105ms内，按道理应该也只需要切换两次进程即可。但是现在却切了52次。 假设0级进程时间片为100ms，每个优先级对应步进为5ms，则1级对应时间片为95ms。如此类推，18级优先级为10ms，19级优先级则为5ms。看出问题了吗？18级优先级进程时间片为19级的2倍！ 第三个问题就直接剑指时间片了，如果简单地以绝对时间作为时间片的单位，那么算法就得考虑不同机器提供的时间精度了，有些高精度的机器能提供精确到1ms的时间，而有些是10ms。那么Linux的CFS（Completely Fair Scheduler）算法是怎么做的呢？
CFS基于一种叫perfect multitasking模型来构建调度算法。
在一个能提供完美多任务能力的CPU中，每个进程能使用1/n的CPU时间。n是当前进程个数。不考虑调度时间（理论上的，这个时间被称为infinitely small schedule duration time），那么在任何相等时间段内，每次都会运行n个进程。上面这段话实在不太好理解。我们举个例子：
在普通调度模型中，10ms时间内有两个进程，那么每个都将运行5ms。在单个5ms内，每个进程占据100%CPU 在PM（perfect multitasking）模型中，10ms内每个进程都运行了10ms，但是每个只用50%的CPU。更难理解了？可以想象CPU飞快地进行线程切换，一下运行进程A，一下运行进程B。在10ms内，似乎每个进程都运行了10ms，但实际上每个进程只占据了50%的CPU。