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.）著，陈莉君 等译；机械工业出版社；

对于分时操作系统而言，表面上看起来是多个进程同时在执行，而在系统内部则进行着从一个进程到另一个进程的切换动作。这样的进程并发执行涉及到进程切换（process switch）和进程调度（process scheduling）两大问题。本文主要说明Linux2.6中的普通进程调度策略（实时进程和普通进程在调度上稍有不同）问题，即系统何时进行进程切换以及选择哪一个进程进行切换。

1.调度策略

理想的进程调度目标应该是：进程响应时间尽可能的快，后台作业吞吐量高，避免某些进程出现饥饿现象，包括低优先级在内的所有进程都有被调度的可能。由此看来，进程调度的工作就是要处理好这几个方面的协调关系，使进程调度的综合性能达到最佳。

与进程调度最为密切的因素是进程的优先级，进程优先级通过一个数值来实现，每个进程都与一个值相关联。调度程序根据进程的优先级将CPU适当的分配给某一个进程。进程的优先级又跟进程的许多因素有关，接下来我们将依次分析这些因素与进程优先级的关系。

1.1进程的分类

进程可以被分为两种类型：I/O消耗型和CPU消耗型。前种类型的进程频繁使用I/O设备，并且大部分时间处于等待状态，以得到新的I/O请求，比如键盘活动等。后一种类型的进程则大部分时间都在占用CPU，对I/O设备并没有过多的需求。

为了使系统有较强的响应能力，I/O消耗型进程必须很快能被唤醒，以实现进程的切换。否则，用户会感到系统反应迟钝。对于CPU消耗型进程，由于它们常常位于后台运行，并且没有过多的I/O需求，因此系统并不需要对这类进程做出快速反应。

正如上面所说的，调度程序通常要处理好这两类进程之间的调度关系：系统既要有迅速的响应能力，又要有最大的CPU利用率（高吞吐量）。这种满足关系其实是矛盾的，如果系统要达到最大利用率，那么CPU就会被一直占用，这样就不能对I/O请求做出迅速响应。调度程序为了调和这种冲突，通常会倾向于I/O消耗型进程。也就是说，调度程序会优先调用这类进程以提高系统的响应能力，而尽量将CPU消耗型进程压后执行。但这并不意味着这类进程就被调度程序忽略。

1.2时间片

Linux的调度是基于分时技术的，多个进程以“时间多路复用”的形式运行，CPU的时间被划分成一小段，即所谓的时间片（slice）。每个进程都会得到一个时间片，在具体某个时间片内，一个进程会独享CPU时间。如果该进程在这个时间片内没有运行完毕，调度程序就会切换该进程使得其他拥有时间片的进程运行。

时间片的划分对系统来说也是一件难事，既不能过长又不能过短。过长的时间片会导致系统的响应能力下降；而过短的时间片会导致系统频繁发生进程切换，由此将带来不必要的处理器消耗。显然，I/O消耗型进程希望时间片越短越好，这样那些等待I/O的进程就能被迅速切换；而CPU消耗型进程则希望时间片越长越好，这样它们就可以一直占用CPU。因此，I/O消耗型进程和CPU消耗型进程的矛盾再一次显现出来。

Linux调度程序解决这种矛盾的方法是，提供一个较长的默认时间片，但是却提高交互进程的优先级，以使得这些进程运行的更频繁。在Linux的调度算法中，每个进程在诞生时总是继承父进程一半的时间片，而之后的时间片则是调度程序根据进程的静态优先级而分配。

1.3优先级

我们上面说过，调度程序在选取下一个执行的进程时依据的是进程的优先级。通过上面对进程的划分可以看出，不同类型的进程应该有不同的优先级。每个进程与生俱来（即从父进程那里继承而来）都有一个优先级，我们将其称为静态优先级。普通进程的静态优先级范围从100到139，100为最高优先级，139为最低优先级。

当进程用完了时间片后，系统就会为该进程分配新的时间片（即基本时间片），静态优先级本质上决定了时间片分配的大小。静态优先级和基本时间片的关系如下：

静态优先级<120，基本时间片=max((140-静态优先级)*20, MIN_TIMESLICE)
静态优先级>=120，基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)

其中MIN_TIMESLICE为系统规定的最小时间片。从该计算公式可以看出，静态优先级越高（值越低），进程得到的时间片越长。其结果是，优先级高的进程会获得更长的时间片，而优先级低的进程得到的时间片则较短。

进程除了拥有静态优先级外，还有动态优先级，其取值范围是100到139。当调度程序选择新进程运行时就会使用进程的动态优先级，动态优先级和静态优先级的关系可参考下面的公式：

动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)

从上面看出，动态优先级的生成是以静态优先级为基础，再加上相应的惩罚或奖励(bonus)。这个bonus并不是随机的产生，而是根据进程过去的平均睡眠时间做相应的惩罚或奖励。

所谓平均睡眠时间（sleep_avg，位于task_struct结构中）就是进程在睡眠状态所消耗的总时间数，这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长，随着进程的运行而减少。因此，平均睡眠时间记录了进程睡眠和执行的时间，它是用来判断进程交互性强弱的关键数据。如果一个进程的平均睡眠时间很大，那么它很可能是一个交互性很强的进程。反之，如果一个进程的平均睡眠时间很小，那么它很可能一直在执行。另外，平均睡眠时间也记录着进程当前的交互状态，有很快的反应速度。比如一个进程在某一小段时间交互性很强，那么sleep_avg就有可能暴涨（当然它不能超过MAX_SLEEP_AVG），但如果之后都一直处于执行状态，那么sleep_avg就又可能一直递减。

理解了平均睡眠时间，那么bonus的含义也就显而易见了。交互性强的进程会得到调度程序的奖励（bonus为正），而那些一直霸占CPU的进程会得到相应的惩罚（bonus为负）。其实bonus相当于平均睡眠时间的缩影，此时只是将sleep_avg调整成bonus数值范围内的大小。

参考：

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

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