上图是

Linux2.6

内核中进程队列的数据结构，之间关系也已经给大家画出来，方便大家理解。

一个

CPU

拥有一个

runqueue。

Linux真正的调度方式是通过runqueue进行调度的，我们知道进程的优先级范围是根据nice值确定的，而nice值的范围为[-20，19]，所以进程的优先级分40个级别。

如上图，runqueue中有一个数组array，这其实是一个结构体数组，其结构体成员为nr_active,bitmap[5],queue[140]三个，我们先从成员queue[140]开始介绍，其140个空间分别对应的是140个优先级，而0~99为实时优先级，这些一般是用在少数注重实时性操作系统上才会频繁使用的优先级，一般我们所用的操作系统都注重进程间调用的平衡，所以这里对于前0~99的优先级我们先暂且不淡，而100~139这40位优先级我们称为普通优先级，对应我们nice值的取值范围，所以在调用我们的进程可以根据其优先级60~99分别对应100~139进行排列调用，相同优先级的进程链接在同一优先级进程的后面

而我们在调用进程时并不是对queue队列进行遍历，而是通过bitmap[5]位图，一个long类型的大小为32比特，5个为160比特，足够进行对queue[140]的标注，我们可以在有进程的位置将二进制对应设置为1，那么在遍历时直接通过bitmap[0~4]进行每次32位的查找，若为0则表示该32位置比特没有进程调用，若不为0则再对32个比特中查找，那么这样我们就可以对位图进行操作，来确定队列中那个优先级存在进程，这样遍历调度队列时间复杂度基本为O(1)

从上图中我们可以看到结构体数组array其成员是开辟了两个的，其分别为活动队列和过期队列，活动队列保证进程只出不进（根据优先级调用排队等待执行的进程），而过期队列保证进程只进不出（调用过的进程或是新来的进程都进入过期队列进行排队等候），在CUP调用进程时始终调用的是活动队列，但CUP并不是直接去调用活动队列的，而是在runqueue队列中，通过两个指针*active，*expired，进行调度，*active指向活动队列，而*expired指向过期队列，当活动队列中的进程被调度完之后将指针*active和*expired进行交换，那么原先的过期队列就变成了活动队列，原先的活动队列就变成了过期队列，CUP通过指针*active再进行调度，通过指针active和expired的交换我们实现了时间复杂度为O(1)的进程调度。

活动队列

● 时间片还没有结束的所有进程都按照优先级放在该队列

● nr_active:

总共有多少个运行状态的进程

● queue[140]:

一个元素就是一个进程队列，相同优先级的进程按照

FIFO

规则进行排队调度

,

   所以，数组下

标就是优先级

● 从该结构中，选择一个最合适的进程，过程是怎么的呢？

        1. 从

0

下表开始遍历

queue[140]

        2. 找到第一个非空队列，该队列必定为优先级最高的队列

        3. 拿到选中队列的第一个进程，开始运行，调度完成

        4. 遍历

queue[140]

时间复杂度是常数！但还是太低效了

● bitmap[5]:

一共

140

个优先级，一共

140

个进程队列，为了提高查找非空队列的效率，就可以用

5*32

个

比特位表示队列是否为空，这样，便可以大大提高查找效率

过期队列

● 过期队列和活动队列结构一模一样

● 过期队列上放置的进程，都是时间片耗尽的进程

● 当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算

active

指针和

expired

指针

● active

指针永远指向活动队列

● expired

指针永远指向过期队列

● 可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都存在

的。

● 没关系，在合适的时候，只要能够交换

active

指针和

expired

指针的内容，就相当于有具有了一批新的活

动进程

在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度

O(1)

算法