Linux Kernel 2.6进程调度的分析(揭示了几乎所有2.6调度的东西)
第一章 Kernel 2.4存在的不 足
根据对2.4进程调度的分析，我们总结出看出2.4内核总的特点就是：
内核调度简单有效
内核不可抢占
但是经过对2.4内核的分析，我们也明显看到了它的缺点：
1.调度算法复杂度是O(n)，与系统负荷关系较大。而且调度算法在设计上也有缺陷
，比如：
(1) 2.4进程调度只设置了一个进程就绪队列，这样有的进程用完了自己时间片以后还要呆在就绪进程队列里面。这样这个进程虽然在这一轮调度循环里面已经无法取得CPU的使用权，但是还要参与goodness()值的计算，这样就白白浪费了时间。
(2) 就绪进程队列是一个全局数据结构，多个CPU只有一个就绪队列runqueue，因而调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈。
2.调度算法在内核态不可抢占。如果某个进程一旦进了内核态那么再高优先级的进程都无法剥夺，只有等进程返回内核态的时候才可以进行调度。缺乏对实时进程的支持。

第二章Kernel 2.6进程调度分析

一、基本思想
Kernel2.6调度算法仍然是基于优先级的调度，它的算法复杂度为O(1)，也就是说是调度器的开销是恒定的，与系统当前的负载没有关系。
1. 就绪队列的改进
每个CPU有两个按优先级排序的数组：一个是active array；一个是expired array。

Active array是当前CPU可能选择执行的运行进程队列，队列中的每个进程都有时间片剩下。Expired array是那些用户时间片的就绪进程队列。一旦active array里面
某个普通进程的时间片用完了，调度器将重新计算进程的时间片、优先级，将它从active array中删除，插入到expired array中相应得优先级队列中。Active array和expired array是通过两个指向每个CPU运行队列的指针来访问的。所以当active array中所有的进程都用完时间片，只需将两个指针切换一下就可以了，这比Kernel 2.4的切换要改进了很多。
2. 快速查找应该执行的进程
系统中往往有很多的就绪进程，如何快速找到CPU即将运行的进程就成了关系到系统性能的一个重要因素。针对2.4的缺点，Kernel 2.6进行了重新设计：引进了一个64bit的bitmap作为进程队列的索引，用bitmap来记载某个优先级的进程队列上有无进程，如果有则为1。这 样使得寻找优先级最高的任务只需要两个BSFL命令。
3. 引进"load estimator"
在一个负载很重的系统上有一个很好的交互感是一件很困难的事情，设计者经过研究发现一味的激励（boost）交互任务并不够，还需惩罚（punish）那 些需求大于可获得CPU时间的进程。调度器通过对用户睡眠时间和运行时间的纪录来判断进程是否是交互进程，一旦被认为是交互进程，调度器会给进程很多"奖 励"（bonus）。
4. 内核可抢占
内核可抢占可以说是2.6内核调度器优于2.4内核的一个很重要的原因。当内核进程没有访问内核的关键数据，也就是内核没有被加锁，此时内核代码是可重入的，因此更高优先级的进程可以在此时中断正在执行的进程，从而达到抢占的目的。
5. 调度器相关的负载均衡
负载均衡有两种策略，一种是从别的CPU上将进程迁移过来，称为"pull"；一种是将本CPU上的进程迁移出去，称为"push"。
二、数据结构
1. 进程优先级的划分
Kernel 2.6将进程优先级作了以下规定：进程优先级范围是从0 ~ MAX_PRIO-1，其中实时进程的优先级的范围是0 ~ MAX_RT_PRIO-1，普通进程的优先级是MAX_RT_PRIO ~ MAX_PRIO-1。数值越小优先级越高。
2. 就绪队列runqueue（kernel/sched.c）
struct runqueue是2.6调度器中一个非常重要的数据结构，它主要用于存放每个CPU的就绪队列信息。限于篇幅，这里只介绍其中相对重要的部分：
(1) prio_array_t *active, *expired, arrays[2]
这是runqueue中最重要的部分。每个CPU的就绪队列都是一个数组，按照时间片是否用完将就绪队列分为两个部分，分别用指针active和expired来指向数组的两个下标。prio_array_t的结构如下：
struct prio_array {
int nr_active;                              /*本进程组中进程个数*/
struct list_head queue[MAX_PRIO];           /*每个优先级的进程队列*/
unsigned long bitmap[BITMAP_SIZE];         /*上述进程队列的索引位图*/
};
数组queue[MAX_PRIO]里面存放的是优先级为i（MAX_PRIO>i>=0）的进程队列的链表头，即task_struct::runlist（通过runnlist即可找到task_struct）。
那么调度器在执行调度的任务时是怎么找到优先级最高的进程呢？
在结构体struct prio_array中有一个重要的数据unsigned long bitmap[BITMAP_SIZE]，这个数据是用来作为进程队列queue[MAX_PRIO]的索引位图，bitmap的每一位（bit
）都与queue[i]对应。当queue[i]的进程队列不为空时，bitmap的相应位就为1；否则就为0。这样我们只需要通过汇编指令从进程优先级 由高到低的方向找到第一个为1的位置idx即为当前就绪队列中最高的优先级（函数sched_find_first_bit()就是用来完成这一工作 的），那么queue[i]->next就是我们要找的task_struct::runlist。

当一个普通进程的时间片用完以后将重新计算进程的时间片和优先级，将该进程从active array中删除，添加到expired array中相应优先级的进程队列中。当Active array中没有进程时，则将active和expired指针调换一下就完成了切换工作。而在2.4内核中重新计算时间片是在所有就绪进程的时间片都用 完以后才统一进行的，因而进程时间片的计算非常耗时，而在2.6中计算时间片是分散的，而且通过以上的方法来实现时间片的轮转，这也是2.6调度器一个亮 点。
另外，程序将struct runqueue定义在sched.c里面而没有定义在sched.h里面是为了让抽象调度器部分的代码，使得内核的其他部分使用调度器提供的接口即可。
(2) spinlock_t lock
runqueue的自旋锁，当对runqueue进行操作的时候，需要对其加锁。由于每个CPU都有一个runqueue，这样会大大减少竞争的机会。
(3) task_t *curr
CPU当前运行的进程。在程序中还有一个全局变量current也是CPU当前运行的进程，它在通常情况下和runqueue的curr指针是相同的，但 是当调度器进行调度的时，如果已经找到最高优先级的进程，则此时做rq->curr = next;可见在进行任务切换之前，rq->curr和current的值是不同的。当唤醒一个进程的时候，很明显将唤醒进程与 rq->curr的优先级进行比较更有意义。
(4) unsigned long expired_timestamp
此变量是用来记录active array中最早用完时间片的时间（赋值jiffies）。因此，用这个量就可以记录expired array中等时间最长的进程的等待时间。这个值的主要
用处是用于宏EXPIRED_STARVING()（这个宏主要是用来判断expired array中的进程是否已经等待了足够长的时间，详见"进程调度的生与死"一节中"scheduler_tick()"函数的介绍）。
(5) unsigned long nr_running, nr_switches, nr_uninterruptible,timestamp_last_tic