目录

一、进程调度队列结构

二、活动队列与过期队列

1.queue[140]

2.bitmap[5]

---

一、进程调度队列结构

Linux系统中，每一个CPU都有一个进程调度队列runqueue，如图所示

二、活动队列与过期队列

运行队列runqueue中有两个指针*active、*expired。*active指针指向活动队列queue[140]，*expired指针指向过期队列queue[140]。

活动队列queue进程只出不进，过期队列进程只进不出。当时间合适时，操作系统会交换active和expired指针，这样就又有了一批新的活动进程。

1.queue[140]

queue[140]中0~99位置是实时优先级（范围是1~99，1的优先级最高，99的优先级最低），100~139位置是普通优先级（根据nice值-20~19确定优先级，nice值为-20优先级最高，nice值为19优先级最低）

queue中的每一个元素位置都是一个进程队列，操作系统会从0开始遍历找到第一个非空队列，再选中该队列中的第一个进程并运行，调度完成！

2.bitmap[5]

顺序遍历queue效率太低了，因此添加了一个long bitmap[5]，32位操作系统下，long为32位，5*32=160>140，所以我们就有了一个位图，通过位图来确定queue中哪个位置有进程队列，不需要再顺序遍历queue，而是遍历bitmap即可。1表示该位置有进程队列，0表示该位置为空。由于bitmap只有5个元素，所以时间复杂度为O(1)。

00000000000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000

00000000000000000000000000000000