Linux2.6内核进程调度队列

前言

在前面学习并认识了进程之后，我们会发出一个疑问：Linux内核是如何调度进程的呢？

接下来我们就以Linux2.6内核为例深入探讨这个问题。

运行队列 runqueue

下图是Linux2.6内核中运行队列的数据结构。

• 一个CPU拥有一个runqueue （struct runqueue）。
• 如果有多个CPU就要考虑进程个数的负载均衡问题。
• 我们现在谈论的OS都是分时操作系统，调度时强调的是公平。

优先级

queue下标说明：

• 普通优先级：100 ~ 139。
• 实时优先级：0 ~ 99。

我们进程的都是普通的优先级，我们知道 nice 值的取值范围是 -20 ~ 19，共40个级别，依次对应 queue 当中普通优先级的下标100~139。

注意： 实时优先级对应实时进程，实时进程是指先将一个进程执行完毕再执行下一个进程，现在基本不存在这种机器了，所以对于 queue 当中下标为 0 ~ 99 的元素我们不关心。

活动队列

时间片还没有结束的所有进程都按照优先级放在活动队列当中，其中 nr_active 代表总共有多少个运行状态的进程，而 queue[140] 数组当中的一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进程排队调度。

调度过程如下：

1. 从0下标开始遍历queue[140]。
2. 找到第一个非空队列，该队列必定为优先级最高的队列。
3. 拿到选中队列的第一个进程，开始运行，调度完成。
4. 接着拿到选中队列的第二个进程进行调度，直到选中进程队列当中的所有进程都被调度。
5. 继续向后遍历queue[140]，寻找下一个非空队列。

注：bitmap[5]：queue数组当中一共有140个元素，即140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5 × 32个比特位表示队列是否为空，这样一来便可以大大提高查找效率。

总结： 在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不会随着进程增多而导致时间成本增加，我们称之为进程调度的O(1)算法。

过期队列

• 过期队列和活动队列的结构相同。
• 过期队列上放置的进程都是时间片耗尽的进程。
• 当活动队列上的进程被处理完毕之后，对过期队列的进程进行时间片重新计算。

活跃队列 VS 过期队列

• CPU调度时，需要把进程拿走的同时，把正在执行的进程剥离下来（被放入运行队列）。
• 运行队列中存在两套相同的结构体类型。
• 拿走的队列：活跃队列；放入队列：过期队列。
• 活跃队列表示当前CPU正在执行的运行队列，而正在执行的运行队列是不可以增加新的进程的 。
• 与此同时，操作系统设置了一个和活跃队列相同属性的过期队列，当活跃队列正在执行时如果有进程需要添加进运行队列，那么就会添加至过期队列当中，也就是说活跃队列的进程一直在减少，而过期队列中的进程一直在增多。
• 活跃队列是只出不进。
• 过期队列是只进不出。
• 两个队列是被存放在结构体数组中的，结构体数组存放在运行队列中
• 且运行队列中存在 active 指针和 expired 指针分别指向活跃队列和过期队列。

active指针和expired指针

• active指针永远指向活动队列。
• expired指针永远指向过期队列。

由于活动队列上时间片未到期的进程会越来越少，而过期队列上的进程数量会越来越多（新创建的进程都会被放到过期队列上），那么总会出现活动队列上的全部进程的时间片都到期的情况，这时将 active 指针和 expired 指针的内容交换，就相当于让过期队列变成活动队列，活动队列变成过期队列，就相当于又具有了一批新的活动进程，如此循环进行即可。

O(1)调度算法

有了对上述概念的认识，我们就能很好的理解内核调度进程队列的算法了：

• CPU正在执行访问的队列是 active 指向的 A 活跃队列（只出不进）。
• 另外一个被 expired 指向的结构相同的过期队列 B（只进不出）。
• 新创建的进程的 PCB 只链接到过期队列 B。
• CPU 调度的活跃队列 A 中的进程 PCB 被 CPU 调度时间片到了之后，也链接到过期队列 B。
• 最后 A 队列中的进程被 CPU 全部调度完，B 队列则链接了在 A 队列调度期间到来的新进程或是时间片到了的老进程。
• 接着将两个 active 指针和 expired 指针交换 swap(active，expired)，交换的是指针内容。
• 重复上诉过程。

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