Linux2.6内核进程调度队列

操作系统有分时操作系统，实时操作系统，实时操作系统主要应用于一些制造业工业等，需要快速响应，但是在互联网领域不会用实时操作系统

队列共有140个空间大小，但是我们不用考虑前面100个实时的，只需要考虑后面40个，和我们前面讲的进程的范围对应上了，我们通过FIFO队列去匹配，这里还有位图，bitmap，为什么是5呢，因为4个小于140，6个又过大，我们通过比特位的位置，1或者0去判断是否为空

但是这样如果去调度进程的时候，，每次都需要从头开始，效率会降低，所以，这里有两个指针可以解决这个问题，active表示现在的，expired表示过去的，相同的去匹配，如果没有的就交换两个地址

当我们出现一个新的进程的时候，我们把它放到expired里面，也就是就绪状态

一个CPU拥有一个runqueue

如果有多个CPU就要考虑进程个数的负载均衡问题

优先级

普通优先级：100～139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）

实时优先级：0～99（不关心）

活动队列

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

• 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)算法！