1. linux 2.4调度器
在linux 2.4的调度器中，时间片重算算法要求在所有的进程都用尽它们的时间片以后，它们的新时间片才会被重新计算。这样的话在一个有很多处理器的系统中，当进程用完它们的时间片以后得等待重算（以得到新的时间片），从而导致大部分的处理器处于空闲状态；这将影响SMP的效率。除此之外，当空闲的处理器开始执行那些时间片尚未用尽的处于等待状态的进程（如果它们自己的处理器忙），会导致进程开始在处理器之间“跳跃”。当一个高优先级进程或者交互式进程发生跳跃时，整个系统的性能就会受到影响。
2. Linux 2.6中新的调度器
Linux 2.6的内核使用了由 Ingo Molnar 开发的新的调度器算法，称为O(1)算法，它在高负载的情况下执行得极其出色，并且当有很多处理器时也可以很好地扩展。
新的调度器解决上述问题的方法是，基于每个 CPU 来分布时间片，并且取消了全局同步和重算循环。调度器使用了两个优先级数组，即活动数组和过期数组，可以通过指针来访问它们。活动数组中包含了所有映射到某个CPU而且时间片尚未用尽的任务。过期数组中包含了一个时间片已经用尽的所有任务的有序列表。如果所有活动任务的时间片都已用尽，那么指向这两个数组的指针互换，过期数组（包含了准备运行的任务）成为活动数组，而空的活动数组成为包含过期任务的新数组。数组的索引存储在一个64位的位图中，找到最高优先级的任务是很容易的。
新的调度器现在不再有大的 runqueue_lock。它维持每个处理器的运行队列/锁机制，以使得两个不同处理器上的两个进程可以完全并行地休眠、唤醒和上下文切换。重算循环（为进程重新计算时间片）和 goodness 算法已经被取消。
从linux-2.6.11/kernel/sched.c中可找到O(1)算法相关的核心数据结构(以下程序片断若无特殊说明，均取自linux-2.6.11/kernel/sched.c)：其中nr_active记录了就绪队列中具有剩余时间片的任务总数，它也可以作为衡量一个CPU负荷轻重的指标之一。bitmap[]用于判断队列(queue[])中对应优先级链表中是否具有剩余时间片的任务(即是否为空)，通过它可以查找并取得就绪队列中高优先级任务一个位图字段。
考虑对于多个CPU的管理中，每个CPU都有一定的负荷，要提高系统整体的吞吐量，必然是要尽快的选择一个负荷最重的CPU上的runqueue进行处理,以保持多个CPU上负载的平衡；同时对于新创建的任务则需要尽快选择一个负荷最轻的CPU上的runqueue来加入。queue[]即为每个CPU上对应的优先级队列数组，且每个元素对应一个具有相同优先级的任务链表，相同级别的任务则先到者优先获得调度。
