Linux O(1)

Linux-O(1)调度器

简介

O(1)调度器是在Linux-2.6.0内核中支持的调度器，之所以叫O(1)调度器，是因为不管有多少进程，调度都能在常数时间内完成。

调度器的结构

对于O(1)调度来说，每个CPU都自己维护一个运行队列，运行队列由两个优先级数组组成，分别为活跃数组与过期数组。

优先级数组，从数据结构上来说其实就是一个二级数组（图的邻接表表示法），每一级代表着一个优先级，总共包含了MAX_PRIO个（140个）个优先级。当活跃数组中的一个进程用完自己的时间片之后，就会被移动到另一个过期数组中。在移动的同时，其优先级也会被重新计算。当活跃数组中的所有的进程都用完时间片之后，活跃数组与过期数组的指针就会进行互换。

在Linux-2.6.0内核中，运行队列runqueue的结构如下：

struct runqueue {
    ...
    /*
     * prio_array_t原型为prio_array
    */
	prio_array_t *active, *expired, arrays[2];
    ...
};

优先数组prio_array的定义如下：

struct prio_array {
	int nr_active;
	unsigned long bitmap[BITMAP_SIZE];
	struct list_head queue[MAX_PRIO];
};

至此，可以很清晰地看到运行队列的结构了。

调度

2.6.0内核的调度代码还是比较简洁的，在schedule(void)函数中（这是个系统调用）。

1. 做好切换调度前的准备，包括释放内核的自旋锁，给运行队列加上自旋锁
2. 选择下一个被执行的进程，这里会根据运行队列选出进程
3. 切换任务，包括切换上下文
4. 最后是释放运行队列的自旋锁，内核加锁，启用抢占等

其中在选择进程的时候，可能会重新计算进程的动态优先级，并放到过期数组中。