Linux-CFS调度器

CFS调度器是在2.6.23内核中开始引入的调度器。事实上，在（我写这篇文章时）最新的5.17.3内核上，你仍然可以看到他的身影。

虚拟运行时间

虚拟运行时间是CFS引入的一个概念，与实际的运行时间成正比，与权重成反比。

权重

进程的虚拟运行时间与权重成反比，实际上，这个权重是由进程的优先级来决定的，在Linux中为nice值。进程的优先级越高，则权重越高，进程的虚拟运行时间就越小。

调度

那么进程的虚拟运行时间是怎么影响到进程执行的顺序的呢？CFS调度使用了红黑树，键值为虚拟运行时间，每次从红黑树中取值最小的进程来运行（树中的最左子节点）。

例如，如果两个进程的运行时间相同，那么他们的运行优先级就是由他们的静态优先级nice值来决定的。如果进程A的运行时间大于进程B的运行时间（A虚拟运行时间增加，动态优先级降低），那么通过增加进程A的静态优先级（A增加静态优先级后，平衡掉增加的虚拟运行时间），这两个进程所可以获得的运行时间还是有可能接近的。CFS就是以这样一种方式来保证了公平性。

Linux-O(1)调度器

简介

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

调度器的结构

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

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

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

1
2
3
4
5
6
7
8

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

优先数组prio_array的定义如下：

1
2
3
4
5

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. 最后是释放运行队列的自旋锁，内核加锁，启用抢占等

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