2.数据结构

O(1)调度算法通过几个数据结构可以巧妙的实现常数级的复杂度。

2.1可运行队列

调度程序每次在进程发生切换时，都要在就绪队列中选取一个最佳的进程来运行。Linux内核使用runqueue数据结构（在最新内核中该结构为rq）表示一个可运行队列（也就是就绪队列），每个CPU都有且只有一个这样的结构。该结构不仅描述了每个处理器中处于可运行状态（TASK_RUNNING）的进程链表，而且还描述了该处理器的调度信息。下面对该结构中的部分字段作详细描述。

spinlock_t lock：保护进程链表的自旋锁；
unsigned long nr_running：运行队列链表中进程数量；
unsigned long long nr_switches：CPU执行进程切换的次数；
unsigned long nr_uninterruptible：之前在运行队列链表中而现在处于重度睡眠状态的进程总数；
unsigned long expired_timestamp：过期队列中最老的进程被插入队列的时间；
unsigned long long timestamp_last_tick：最近一次定时器终端的时间；
task_t *curr：指向本地CPU当前正在运行的进程的进程描述符，即current；
task_t *idle：指向本地CPU上的idle进程描述符的指针；
struct mm_struct *prev_mm：在进程进行切换时用来存放被替换进程内存描述符的地址；
prio_array_t *active：指向可运行队列中活动链表；
prio_array_t *expired：指向可运行队列中过期链表；
prio_array_t arrays[2]：该数组的元素分别表示可运行队列中的活动进程集合和过期进程集合；
int best_expired_prio：过期进程中优先级最高的进程；

到目前为止，你可能对上述字段的理解还不是很深，最好的办法是学习完下面的内容后再回过头来重新看这些字段的用途。我们在上面说过，runqueue结构最主要的功能是描述处于可运行状态进程所组成的链表。不过，所谓的可运行队列并不是将一些列的runqueue结构连接在一些，而是由runqueue结构中的arrays数组来体现，该数组的元素为prio_array_t类型。

2.2优先级数组

O(1)算法的另一个核心数据结构即为prio_array结构体。该结构体中有一个用来表示进程动态优先级的数组queue，它包含了每一种优先级进程所形成的链表。

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define MAX_PRIO                (MAX_RT_PRIO + 40)
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO];
};

由于进程优先级的最大值为139，因此MAX_PRIO的最大值取140（具体的是，普通进程使用100到139的优先级，实时进程使用0到99的优先级）。因此，queue数组中包含140个可运行状态的进程链表，每一条优先级链表上的进程都具有相同的优先级，而不同进程链表上的进程都拥有不同的优先级。

除此之外，prio_array结构中还包括一个优先级位图bitmap。该位图使用一个位（bit）来代表一个优先级，而140个优先级最少需要5个32位来表示，因此BITMAP_SIZE的值取5。起初，该位图中的所有位都被置0，当某个优先级的进程处于可运行状态时，该优先级所对应的位就被置1。

因此，O(1)算法中查找系统最高的优先级就转化成查找优先级位图中第一个被置1的位。与2.4内核中依次比较每个进程的优先级不同，由于进程优先级个数是定值，因此查找最佳优先级的时间恒定，它不会像以前的方法那样受可执行进程数量的影响。

如果确定了优先级，那么选取下一个进程就简单了，只需在queue数组中对应的链表上选取一个进程即可。

2.3活动进程和过期进程

在操作系统原理课上我们知道，当处于运行态的进程用完时间片后就会处于就绪态，此时调度程序再从就绪态的进程中选取一个作为即将要运行的进程。

而在具体Linux内核中，就绪态和运行态统一称为可运行态（TASK_RUNNING）。对于系统内处于可运行状态的进程，我们可以分为三类，首先是正处于执行状态的那个进程；其次，有一部分处于可运行状态的进程则还没有用完他们的时间片，他们等待被运行；剩下的进程已经用完了自己的时间片，在其他进程没有用完它们的时间片之前，他们不能再被运行。

据此，我们将进程分为两类，活动进程，那些还没有用完时间片的进程；过期进程，那些已经用完时间片的进程。因此，调度程序的工作就是在活动进程集合中选取一个最佳优先级的进程，如果该进程时间片恰好用完，就将该进程放入过期进程集合中。

在可运行队列结构中，arrays数组的两个元素分别用来表示刚才所述的活动进程集合和过期进程集合，active和expired两个指针分别直接指向这两个集合。

关于可运行队列和两个优先级数组的关系可参考下面的图：

正如上面分析的那样，可运行队列结构和优先级数组结构使得Q(1)调度算法在有限的时间内就可以完成，它不依赖系统内可运行进程的数量。

3. 调度算法

Linux2.4版本的内核调度算法理解起来简单：在每次进程切换时，内核依次扫描就绪队列上的每一个进程，计算每个进程的优先级，再选择出优先级最高的进程来运行；尽管这个算法理解简单，但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多，花费的时间就越大，时间复杂度为O(n)。伪代码如下：

for (系统中的每个进程) {
	重新计算时间片;
	重新计算优先级;
}

而2.6内核所采用的O(1)算法则很好的解决了这个问题，该算法可以在恒定的时间内为每个进程重新分配好时间片，而且在恒定的时间内可以选取一个最高优先级的进程，重要的是这两个过程都与系统中可运行的进程数无关，这也正是该算法取名为O(1)的缘故。

3.1 O(1)中时间片的计算

O(1)算法采用过期进程数组和活跃进程数组解决以往调度算法所带来的O(n)复杂度问题。过期数组中的进程都已经用完了时间片，而活跃数组的进程还拥有时间片。当一个进程用完自己的时间片后，它就被移动到过期进程数组中，同时这个过期进程在被移动之前就已经计算好了新的时间片。可以看到O(1)调度算法是采用分散计算时间片的方法，并不像以往算法中集中为所有可运行进程重新计算时间片。

当活跃进程数组中没有任何进程时，说明此时所有可运行的进程都用完了自己的时间片。那么此时只需要交换一下两个数组即可将过期进程切换为活跃进程，进而继续被调度程序所调度。两个数组之间的切换其实就是指针之间的交换，因此花费的时间是恒定的。下面的代码说明了两个数组之间的交换：

struct prop_array *array = rq->active;
if (array->nr_active != 0) {
	rq->active = rq->expired;
	rq->expired = array;
}

通过分散计算时间片、交换过期和活跃两个进程集合的方法可以使得O(1)算法在恒定的时间内为每个进程重新计算好时间片。

3.2 O(1)中进程的选择

进程调度的本质就是在当前可运行的进程集合中选择一个最佳的进程，这个最佳则是以进程的动态优先级为选取标准的。不管是过期进程集合还是活跃进程集合，都将每个优先级的进程组成一个链表，因此每个集合就有140个不同优先级的进程链表。同时，两个集合中还采用优先级位图来标记每个优先级链表中是否存在进程。

调度程序在选取最高优先级的进程时，首先利用优先级位图从高到低找到第一个被设置的位，该位对应着一条进程链表，这个链表中的进程是当前系统所有可运行进程中优先级最高的。在该优先级链表中选取头一个进程，它拥有最高的优先级，即为调度程序马上要执行的进程。上述进程的选取过程可用下述代码描述：

struct task_struct *prev, *next;
struct list_head *queue;
struct prio_array *array;
int idx;

prev = current;
array = rq->active;
idx = sehed_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, struct task_struct, run_list);
if (prev != next)
	context_switch();

sehed_find_first_bit()用于在位图中快速查找第一个被设置的位。如果prev和next不是一个进程，那么此时进程切换就开始执行。

通过上述的内容可以发现，在恒定的时间重新分配时间片和选择一个最佳进程是Q(1)算法的核心。
参考：

1.深入理解LINUX内核(第三版) ；（美）博韦，西斯特 著； 陈莉君 张琼声 张宏伟译； 中国电力出版社；

2.Linux内核设计与实现；（美）拉芙（Love，R.）著，陈莉君 等译；机械工业出版社；