Linux2.6调度器2_调度算法的发展历史

1 调度算法发展历史
      2.4 内核包含了相对简单的调度器，按 O(N) 的时间间隔运行。2.4 调度器将时间分割成 epoch，每个 epoch 中，每个任务允许执行到其时间切片用完。如果某个任务没有使用其所有的时间切片，那么剩余时间切片的一半将被添加到新时间切片使其在下个 epoch 中可以执行更长时间。 调度器只是迭代任务，应用 goodness 函数（指标）决定下面执行哪个任务。尽管这种方法比较简单，但是却比较低效、缺乏可扩展性而且不适合用在实时系统中。它还缺少利用新硬件架构（比如多核处理器）的能力。

      早期的 2.6 调度器，叫做 O(1) 调度器，它旨在解决 2.4 调度器存在的问题 — 该调度器不需要迭代整个任务列表来确定要调度的下一个任务（因此得名 O(1)，这意味着它效率更高，扩展性更好）。O(1) 调度器跟踪运行队列中可运行的任务（实际上，每个优先级水平有两个运行队列 — 一个用于活动任务，一个用于过期任务）， 这意味着要确定接下来执行的任务，调度器只需按优先级将下一个任务从特定活动的运行队列中取出即可）。 O(1) 调度器扩展性更好而且包含交互性，提供了大量启示用于确定任务是受 I/O 限制还是受处理器限制。 但是 O(1) 调度器在内核中很笨拙。需要大量代码计算启示，难以管理并且对于纯粹主义者而言未能体现算法的本质。

      为了解决 O(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 Con Kolivas 的内核补丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。
      Ingo Molnar，O(1) 调度器的创造者，围绕 Kolivas 的一些思想开发了基于 CFS 的调度器。

2.Linux2.6调度算法概述
       Linux2.6内核也支持三种调度策略。其中SCHED_FIFO和SCHED_RR用于实时进程，而SCHED_NORMAL用于普通进程。
       O(1)调度器在两个方面修改了Linux2.4调度器，一是进程优先级的计算方法；二是pick next算法。
       pick next是指：从所有候选进程中挑选下一个要被调度的进程的过程。

3.普通进程的优先级计算
       普通进程优先级是动态计算的，计算公式中包含了静态优先级。一般来讲，静态优先级越高，进程所能分配到的时间片越长，用户可以通过nice系统调用修改进程的静态优先级。

动态优先级由公式一计算得出：
公式一
                  dynamic priority = max (100, min ( static priority – bonus +5, 139))  
       其中bonus 取决于进程的平均睡眠时间。由此可以看出，在linux2.6中，一个普通进程的优先级和平均睡眠时间的关系为：平均睡眠时间越长，其bonus越大，从而得到更高的优先级。
       平均睡眠时间也被用来判断进程是否是一个交互式进程。如果满足下面的公式，进程就被认为是一个交互式进程：
公式二
                Dynamic priority ≤ 3 x static priority /4 + 28
       平均睡眠时间是进程处于等待睡眠状态下的时间，该值在进程进入睡眠状态时增加，而进入RUNNING状态后则减少。该值的更新时机分布在很多内核函数内：时钟中断scheduler_tick ()；进程创建；进程从TASK_INTERRUPTIBLE状态唤醒；负载平衡等。

4.实时进程的优先级计算
       实时进程的优先级由sys_sched_setschedule()设置。该值不会动态修改，而且总是比普通进程的优先级高。在进程描述符中用rt_priority域表示。

5.pick next算法
       普通进程的调度选择算法基于进程的优先级，拥有最高优先级的进程被调度器选中。2.4中，时间片counter同时也表示了一个进程的优先级。2.6中时间片用任务描述符中的time_slice域表示，而优先级用prio（普通进程）或者rt_priority（实时进程）表示。

       调度器为每一个CPU维护了两个进程队列数组：active数组和expire数组。数组中的元素着保存某一优先级的进程队列指针。系统一共有140个不同的优先级，因此这两个数组大小都是140。

       当需要选择当前最高优先级的进程时，2.6调度器不用遍历整个runqueue，而是直接从active数组中选择当前最高优先级队列中的第一个进程。假设当前所有进程中最高优先级为50(换句话说，系统中没有任何进程的优先级小于50)。则调度器直接读取active[49]，得到优先级为50的进程队列指针。该队列头上的第一个进程就是被选中的进程。这种算法的复杂度为O(1)，从而解决了2.4调度器的扩展性问题。

       为了实现上述算法active数组维护了一个bitmap，当某个优先级别上有进程被插入列表时，相应的比特位就被置位。Sched_find_first_bit()函数查询该bitmap，返回当前被置位的最高优先级的数组下标。在上例中sched_find_first_bit函数将返回49。在IA处理器上可以通过bsfl等指令实现。

为了提高交互式进程的响应时间，O(1)调度器可以动态地提高该类进程的优先级，还采用以下方法：
       每次时钟tick中断，进程的时间片(time_slice)被减一。当time_slice为0时，调度器判断当前进程的类型，如果是交互式进程或者实时进程，则重置其时间片并重新插入active数组。如果不是交互式进程则从active数组中移到expired数组。
       这样实时进程和交互式进程就总能优先获得CPU。然而这些进程不能始终留在active数组中，否则进入expire数组的进程就会产生饥饿现象。当进程已经占用CPU时间超过一个固定值后，即使它是实时进程或者交互式进程也会被移到expire数组中。
       当active数组中的所有进程都被移到expire数组中后，调度器交换active数组和expire数组。当进程被移入expire数组时，调度器会重置其时间片，因此新的active数组又恢复了初始情况，而expire数组为空，从而开始新的一轮调度。

schedule()函数的时间复杂度为O(1)。这取决于两个改进：
       一．Pick next算法借助于active数组，无需遍历runqueue；
       二．取消了定期更新所有进程counter的操作，动态优先级的修改分布在进程切换，时钟tick中断以及其它一些内核函数中进行。
       O(1)调度器区分交互式进程和批处理进程的算法与以前虽大有改进，但仍然在很多情况下会失效。有一些著名的程序总能让该调度器性能下降，导致交互式进程反应缓慢：
              fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c
       这些不足催生了Con Kolivas的楼梯调度算法SD，以及后来的改进版本RSDL。Ingo Molnar在RSDL之后开发了CFS，并最终被2.6.23内核采用。

参考文献
1.Linux 调度器发展简述. http://www.ibm.com/developerworks/cn/linux/l-cn-scheduler/index.html