进程调度程序是确保进程能有效工作的一个内核子系统。它将决定将哪个进程投入运行，何时运行以及运行多长时间。调度程序没有太复杂的原理，它的原则就是只要有可以执行的进程，那么就总会有程序正在执行。

多任务

多任务操作系统是能同时并发地交互执行多个进程的操作系统。可以划分为两类：非抢占式多任务和抢占式多任务。

Linux提供了抢占式的多任务模式。由调度程序决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会。这个强制的挂起动作称为抢占(preemption)。进程在被抢占之前能运行的时间是预先设置好的，这个时间被称为进程的时间片(timeslice)。时间片实际上就是分配给每个可运行进程的处理器时间段。有效管理时间片能够使调度程序从系统全局的角度做出调度决定，这样还可以避免个别进程独占系统资源。

策略

策略决定了调度程序在何时让什么进程运行。调度器的策略往往决定系统的整体印象，并且还要负责优化使用处理器时间。

1、I/O消耗型和处理器消耗型的进程

进程可以被分为I/O消耗型和处理器消耗型。

I/O消耗型的大部分时间用来提交I/O请求或者等待I/O请求。这样的进程会经常处于可运行状态，但通常都是运行短短一会。

处理器消耗型把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停运行。对于这种进程，调度策略往往都是尽量降低它们的调度频率，而延长其运行时间。

调度策略通常要在两个矛盾的目标中寻找平衡：进程响应迅速(响应时间短)和最大系统利用率(高吞吐量)。Linux为了保证交互式应用和桌面系统的性能，所有对进程的响应做了优化(缩短响应时间)，更倾向于优先调度I/O消耗型进程。但也并未忽略处理器消耗型进程。

2、进程优先级

调度算法中最基本的一类就是基于优先级的调度。通常做法就是优先级高的进程先运行，优先级低的后运行，相同优先级的进程按照轮转方式进行调度。

Linux采用了两种不同的优先级范围。第一种使用nice值，范围从-20到+19，默认为0，越大的nice值意味着更低的优先级。第二种是实时优先级，其值是可配置的，默认情况下它的变化范围是0到99，越高的实时优先级数值意味着进程优先级越高。任何实时进程的优先级都高于普通进程。

3、时间片

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片。但时间片过长会导致系统对交互的响应表现欠佳，时间片太短会明显增大进程切换带来的处理器消耗时。

Linux的进程调度

在Linux2.6.23内核版本中使用了新的进程调度算法，被称为“完全公平调度算法”，简称CFS

CFS原理

cfs定义了一种新的模型，它给cfs_rq（cfs的run queue）中的每一个进程安排一个虚拟时钟，vruntime。如果一个进程得以执行，随着时间的增长（也就是一个个tick的到来），其vruntime将不断增大。没有得到执行的进程vruntime不变。

而调度器总是选择vruntime跑得最慢的那个进程来执行。这就是所谓的“完全公平”。为了区别不同优先级的进程，优先级高的进程vruntime增长得慢，以至于它可能得到更多的运行机会。

CFS基本设计思路

CFS思路很简单，就是根据各个进程的权重分配运行时间。

进程的运行时间计算公式为:

分配给进程的运行时间 = 调度周期 * 进程权重 / 所有进程权重之和   (公式1)

调度周期很好理解，就是将所有处于TASK_RUNNING态进程都调度一遍的时间。

举个例子，比如只有两个进程A, B，权重分别为1和2，调度周期设为30ms，那么分配给A的CPU时间为:30ms*(1/(1+2)) = 10ms; 而B的CPU时间为：30ms*(2/(1+2)) = 20ms。那么在这30ms中A将运行10ms，B将运行20ms。

公平怎么体现呢？它们的运行时间并不一样啊？

其实公平是体现在另外一个量上面，叫做virtual runtime(vruntime)，它记录着进程已经运行的时间，但是并不是直接记录，而是要根据进程的权重将运行时间放大或者缩小一个比例。

我们来看下从实际运行时间到vruntime的换算公式

vruntime = 实际运行时间 * 1024 / 进程权重 (公式2)

为了不把大家搞晕，这里我直接写1024，实际上它等于nice为0的进程的权重，代码中是NICE_0_LOAD。也就是说，所有进程都以nice为0的进程的权重1024作为基准，计算自己的vruntime增加速度。

还以上面AB两个进程为例，B的权重是A的2倍，那么B的vruntime增加速度只有A的一半。现在我们把公式2中的实际运行时间用公式1来替换，可以得到这么一个结果：

vruntime = (调度周期 * 进程权重 / 所有进程总权重) * 1024 / 进程权重 = 调度周期 * 1024 / 所有进程总权重

看出什么眉目没有？没错，虽然进程的权重不同，但是它们的 vruntime增长速度应该是一样的 ，与权重无关。好，既然所有进程的vruntime增长速度宏观上看应该是同时推进的，
那么就可以用这个vruntime来选择运行的进程，谁的vruntime值较小就说明它以前占用cpu的时间较短，受到了“不公平”对待，因此下一个运行进程就是它。这样既能公平选择进程，又能保证高优先级进程获得较多的运行时间。这就是CFS的主要思想了。

或者可以这么理解：CFS的思想就是让每个调度实体（没有组调度的情形下就是进程，以后就说进程了）的vruntime互相追赶，而每个调度实体的vruntime增加速度不同，权重越大的增加的越慢，这样就能获得更多的cpu执行时间。

再补充一下权重的来源，权重跟进程nice值之间有一一对应的关系，可以通过全局数组prio_to_weight来转换，nice值越大，权重越低。

参考

《Linux内核设计与实现》 linux内核分析——CFS（完全公平调度算法）