Linux进程调度算法

Linux中的进程如果从调度策略划分，可以分为两类，普通进程和实时进程。实时进程又可分为两类，FIFO，RR。实时进程的优先级远远大于普通进程。Linux的处理策略是如果有实时进程处于可运行状态，那么优先运行实时进程，知道所有的实时进程或者结束，或者被杀掉，或者处于阻塞状态。也就是说如果实时进程一直在运行，那么普通的进程就会被活活饿死。由于实时进程和普通进程所采用的调度策略不同，下面分别介绍。

（一）普通进程调度策略

每一个普通进程都有一个静态优先级。这个值会被调度器用来与作为参考来调度进程。在内核中调度的优先级的区间为[100，139]，数字越低，优先级越高。一个新的进程总是从它的父进程继承此值。从进程管理篇（一）中了解到每个进程都有分配时间片。那么时间片是如何分配的呢？时间片的计算公式如下（摘自《Understanding The Linux Kernel Version3》）：

由此可见时间片的分配只有静态优先级相关。静态优先级越高，时间片分配的越多。

系统在实际的调度过程中不仅要考虑静态优先级，也要考虑进程的属性。例如如果进程属于交互式进程，那么可以适当的调高它的优先级，使得界面反应地更加迅速，从而使用户得到更好的体验。Linux2.6 在这方面有了较大的提高。

Linux2.6认为，交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多，则越有可能属于交互式进程。则系统调度时，会给该进程更多的奖励（bonus），以便该进程有更多的机会能够执行。奖励（bonus）从0到10不等。

系统调度时，会计算进程的动态优先级。系统会严格按照动态优先级高低的顺序安排进程执行。动态优先级高的进程进入非运行状态，或者时间片消耗完毕才会轮到动态优先级较低的进程执行。动态优先级的计算主要考虑两个因素：静态优先级，进程的平均睡眠时间也即bonus。计算公式如下：                                    动态优先级 = max (100, min (   静态优先级 - 奖励 + 5, 139))。

在调度时，Linux2.6 使用了一个小小的trick，就是算法中经典的空间换时间的思想，使得计算最优进程能够在O(1)的时间内完成。与Linux2.4的相关比较详见。

（二）实时进程调度

每一个实时进程都会与一个实时优先级相关联。实时优先级在1到99之间。不同与普通进程，系统调度时，实时优先级高的进程总是先于优先级低的进程执行。知道实时优先级高的实时进程无法执行。实时进程总是被认为处于活动状态。

如果有数个 优先级相同的实时进程，那么系统就会按照进程出现在队列上的顺序选择进程。假设当前CPU运行的实时进程A的优先级为a，而此时有个优先级为b的实时进程B进入可运行状态，那么只要b

不同调度策略的实时进程只有在相同优先级时才有可比性：

1. 对于FIFO的进程，意味着只有当前进程执行完毕才会轮到其他进程执行。由此可见相当霸道。

2. 对于RR的进程。一旦时间片消耗完毕，则会将该进程置于队列的末尾，然后运行其他相同优先级的进程，如果没有其他相同优先级的进程，则该进程会继续执行。

总而言之，对于实时进程，高优先级的进程就是大爷。它执行到没法执行了，才轮到低优先级的进程执行。等级制度相当森严啊。



进程的三种基本状态　　1.等待态：等待某个事件的完成；

　　2.就绪态：等待系统分配处理器以便运行；

　　3.运行态：占有处理器正在运行。

　　运行态→等待态 往往是由于等待外设，等待主存等资源分配或等待人工干预而引起的。

　　等待态→就绪态 则是等待的条件已满足，只需分配到处理器后就能运行。

　　运行态→就绪态 不是由于自身原因，而是由外界原因使运行状态的进程让出处理器，这时候就变成就绪态。例如时间片用完，或有更高优先级的进程来抢占处理器等。

　　就绪态→运行态 系统按某种策略选中就绪队列中的一个进程占用处理器，此时就变成了运行态