Linux2.6内核进程调度队列详细讲解
上图是 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) 算法