四、Linux调度器分析
1．Linux2.6调度器的特性
2.6 调度系统从设计之初就把开发重点放在更好满足实时性和多处理机并行性上，并且基本实现了它的设计目标。新调度系统的特性概括为如下几点：
继承和发扬 2.4 版调度器的特点：
交互式作业优先
轻载条件下调度/唤醒的高性能
公平共享
基于优先级调度
高 CPU 使用率
SMP 高效亲和
实时调度和 cpu 绑定等调度手段
在此基础之上的新特性：
O(1)调度算法，调度器开销恒定（与当前系统负载无关），实时性能更好
高可扩展性，锁粒度大幅度减小
新设计的 SMP 亲和方法
优化计算密集型的批处理作业的调度
重载条件下调度器工作更平滑
子进程先于父进程运行等其他改进
?
2．新的数据结构 runqueue
2.4 的就绪队列是一个简单的以 runqueue_head 为头的双向链表，在 2.6 中，就绪队列定义为一个复杂得多的数据结构 struct runqueue，并且，尤为关键的是，每一个 CPU 都将维护一个自己的就绪队列，--这将大大减小竞争。
1) prio_array_t *active, *expired, arrays[2]
runqueue 中最关键的数据结构。每个 CPU 的就绪队列按时间片是否用完分为两部分，分别通过 active 指针和 expired 指针访问，active 指向时间片没用完、当前可被调度的就绪进程，expired 指向时间片已用完的就绪进程。每一类就绪进程都用一个 struct prio_array 的结构表示：
struct prio_array {
??????????????????? int nr_active;???????????????? /* 本进程组中的进程数 */
??????????????????? struct list_head queue[MAX_PRIO];??? /* 以优先级为索引的 HASH 表，见下 */
??????????????????? unsigned long bitmap[BITMAP_SIZE]; /* 加速以上 HASH 表访问的位图，见下 */
};

?
图1：active、expired 数组示例

在新的 O(1) 调度中，调度过程分解为 n 步，每一步所耗费的时间都是 O(1) 量级的。
prio_array 中包含一个就绪队列数组，数组的索引是进程的优先级（共 140 级，详见下 "static_prio" 属性的说明），相同优先级的进程放置在相应数组元素的链表 queue 中。调度时直接给出就绪队列 active 中具有最高优先级的链表中的第一项作为候选进程（参见"调度器"），而优先级的计算过程则分布到各个进程的执行过程中进行（见"优化了的优先级计算方法"）。
为了加速寻找存在就绪进程的链表，2.6 核心又建立了一个位映射数组来对应每一个优先级链表，如果该优先级链表非空，则对应位为 1，否则为 0。核心还要求每个体系结构都构造一个 sched_find_first_bit() 函数来执行这一搜索操作，快速定位第一个非空的就绪进程链表。
采用这种将集中计算过程分散进行的算法，保证了调度器运行的时间上限，同时在内存中保留更加丰富的信息的做法也加速了候选进程的定位过程。这一变化简单而又高效，是 2.6 内核中的亮点之一。
arrays 二元数组是两类就绪队列的容器，active 和 expired 分别指向其中一个。active 中的进程一旦用完了自己的时间片，就被转移到 expired 中，并设置好新的初始时间片；而当 active 为空时，则表示当前所有进程的时间片都消耗完了，此时，active 和 expired 进行一次对调，重新开始下一轮的时间片递减过程（参见"调度器"）。
回忆一下 2.4 调度系统，进程时间片的计算是比较耗时的，在早期内核版本中，一旦时间片耗尽，就在时钟中断中重新计算时间片，后来为了提高效率，减小时钟中断的处理时间，2.4 调度系统在所有就绪进程的时间片都耗完以后在调度器中一次性重算。这又是一个 O(n) 量级的过程。为了保证 O(1) 的调度器执行时间，2.6 的时间片计算在各个进程耗尽时间片时单独进行，而通过以上所述简单的对调来完成时间片的轮转（参见"调度器"）。这又是 2.6 调度系统的一个亮点。
2) spinlock_t lock
runqueue 的自旋锁，当需要对 runqueue 进行操作时，仍然应该锁定，但这个锁定操作只影响一个 CPU 上的就绪队列，因此，竞争发生的概率要小多了。
3) task_t *curr
本 CPU 正在运行的进程。
4) tast_t *idle
指向本 CPU 的 idle 进程，相当于 2.4 中 init_tasks[this_cpu()] 的作用。
5) int best_expired_prio
记录 expired 就绪进程组中的最高优先级（数值最小）。该变量在进程进入 expired 队列的时候保存（schedule_tick()），用途见 "expired_timestamp"的解释）。
6) unsigned long expired_timestamp
当新一轮的时间片递减开始后，这一变量记录着最早发生的进程耗完时间片事件的时间（jiffies 的绝对值，在 schedule_tick() 中赋），它用来表征 expired 中就绪进程的最长等待时间。它的使用体现在 EXPIRED_STARVING(rq) 宏上。
7) struct mm_struct *prev_mm
保存进程切换后被调度下来的进程（称之为 prev）的 active_mm 结构指针。因为在 2.6 中 prev 的 active_mm 是在进程切换完成之后释放的（mmdrop()），而此时 prev 的 active_mm 项可能为 NULL，所以有必要在 runqueue 中预先保留。
8) unsigned long nr_running
本 CPU 上的就绪进程数，该数值是 active 和 expired 两个队列中进程数的总和，是说明本 CPU 负载情况的重要参数（详见"调度器相关的负载平衡"）。
9) unsigned long nr_switches
记录了本 CPU 上自调度器运行以来发生的进程切换的次数。
10) unsigned long nr_uninterruptible
记录本 CPU 尚处于 TASK_UNINTERRUPTIBLE 状态的进程数，和负载信息有关。
11) atomic_t nr_iowait
记录本 CPU 因等待 IO 而处于休眠状态的进程数。
12) unsigned long timestamp_last_tick
本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到（见"调度器相关的负载平衡"）。
13) int prev_cpu_load[NR_CPUS]
记录进行负载平衡时各个 CPU 上的负载状态（此时就绪队列中的 nr_running 值），以便分析负载情况（见"调度器相关的负载平衡"）。
14) atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]
这两个属性仅在 NUMA 体系结构下有效，记录各个 NUMA 节点上的就绪进程数和上一次负载平衡操作时的负载情况（见"NUMA 结构下的调度"）。
15) task_t *migration_thread
指向本 CPU 的迁移进程。每个 CPU 都有一个核心线程用于执行进程迁移操作（见"调度器相关的负载平衡"）。
16) struct list_head migration_queue
需要进行迁移的进程列表（见"调度器相关的负载平衡"）。
3．改进后的 task_struct
2.6 版的内核仍然用 task_struct 来表征进程，尽管对线程进行了优化，但线程的内核表示仍然与进程相同。随着调度器的改进，task_struct 的内容也有了改进，交互式进程优先支持、内核抢占支持等新特性，在 task_struct 中都有所体现。在 task_struct 中，有的属性是新增加的，有的属性的值的含义发生了变化，而有的属性仅仅是改了一下名字。
4．新的运行时间片表现
2.6 中，time_slice 变量代替了 2.4 中的 counter 变量来表示进程剩余运行时间片。time_slice 尽管拥有和 counter 相同的含义，但在内核中的表现行为已经大相径庭，下面分三个方面讨论新的运行时间片表现：
1) time_slice 基准值
和 counter 类似，进程的缺省时间片与进程的静态优先级（在 2.4 中是 nice 值）相关，使用如下公式得出：
MIN_TIMESLICE + ((MAX_TIM