早在2001年12月，当2.5 Linux内核树的开发工作开始时，社区中就有很多关于扩展性的讨论。Linux开始出现在传统上由大型服务器担当的一些角色中，并且一些供应商正在提供适用于对称多处理 (SMP) 的 Linux 版本。尽管商业领域对这方面的兴趣似乎正在增长，但人们也越来越意识到，即使是 SMP Linux 的扩展性也不如预期的好。例如，如果两台单处理器桌面机器的性能可以超过一台四处理器机器，谁会想使用（或购买）四路机器呢？

内核中首先需要关注的领域之一是调度器。 显然，随着负载和 CPU 数量的增加，调度器工作得越来越辛苦，最终从它所调度的进程中占用了越来越多的时间。 在最坏的情况下，几乎整个系统都被用来决定下一步运行什么。

当我们谈论 Linux 调度器时，我们并不是指处理所有调度的特定任务。 相反，每个任务本身在每次获取或释放处理器时，通过调用内核中的调度器函数来完成一小部分调度工作。 因此，当我们谈论调度器做这个或那个时，我们实际上指的是调度器函数及其在其他任务上下文中的相关例程。

最初的 2.4 调度器非常简单。 系统上的所有任务都已经在一个名为 tasklist 的全局列表中，并且这些任务被分配了一个 goodness 评级。 Goodness 由以下因素决定：

因此，当一个处理器空闲时，2.4 调度器会检查 tasklist，寻找 goodness 值最高的任务，并选择该任务作为下一个运行的任务。 图 1 展示了 2.4 调度器的工作原理。 tasklist 就是 运行队列，并且因为它没有以任何有用的方式排序，所以调度器的每次迭代都会完全检查 tasklist，为空闲处理器寻找最佳候选者。 在多处理器的情况下，即使您是唯一可运行的任务，您是否会连续两次在同一个处理器上运行也是偶然的。

图 1. 2.4 调度器在处理器之间共享，并且没有以任何有用的方式排序。

这种模型具有易于实现且易于调试的优点。 tasklist 由单个读/写自旋锁保护。 这允许多个任务并行检查它，同时仍然为比较少见的更改事件提供获得独占访问的机制。

不幸的是，这些相同的特性也是该模型的缺点。 当时 2.4 调度器的检测开始集中于问题：单个读/写自旋锁往往成为繁忙系统和具有四个或更多 CPU 的系统上的争用点。 所有处理器仅使用一个队列，并且每次重新调度都必须完全检查该队列。 随着系统变得越来越繁忙，tasklist 变得更长； 线性搜索最佳任务也花费了更长的时间。 结果，在决定运行哪个进程后，您等待更长的时间才能独占地获取锁，以便将该任务从可运行列表中删除并标记为正在运行。 如果等待时间足够长，则多个处理器可能会选择相同的进程，但随后会发现该进程已被分配给不同的处理器。 然后，其他处理器将不得不返回线性搜索并找到另一个任务。 随着系统变得越来越繁忙，调度器消耗了更多的 CPU 时间，以至于调度进程花费的时间比运行进程花费的时间还要多。 需要进行更改，以使负载过重的系统不会将自己调度到停顿状态。

因此，为 2.6 中引入 O(1) 调度器奠定了基础，该调度器声称选择最佳任务并将其放到处理器上的时间是恒定的，无论系统上的负载或它正在调度的 CPU 数量如何。 对于每个 CPU 的 140 个可能的优先级中的每一个，都创建一个活动队列，而不是整个系统使用一个队列。 随着任务获得或失去优先级，它们会被放入上次运行的处理器上的相应队列中。 现在，为特定处理器找到最高优先级的任务是一件很简单的事情。 位图指示哪些队列不为空，并且各个队列是 FIFO 列表。 因此，您可以对一组 32 位位图执行高效的查找第一个位指令，然后每次从指示的队列中取出第一个任务。

当任务完成其时间片时，它们会进入每个处理器的一组 140 个并行队列中，这些队列称为过期队列。 当活动队列为空时，简单的指针赋值可以使过期队列再次成为活动队列，从而使周转非常高效。

如果不使用简单的点，则不可能绘制出现在每个 CPU 上的 140 个队列。 但是，图 2 提供了一个近似值，并突出了 2.4 和 2.6 调度器之间的主要区别。 除了在负载过重的系统上，大多数队列都是空的。 那些不为空的队列在其队列头部有最佳选择，因此搜索下一个要运行的任务变得容易。

图 2. 2.6 调度器每个处理器有 140 个队列，从而可以轻松搜索下一个可运行的任务。

这种 2.6 方法有一个缺点。 一旦任务落在一个处理器上，它可能会用完其时间片并被放回优先级队列以重新运行——但它怎么可能最终出现在另一个处理器上呢？ 实际上，如果一个处理器上的所有任务都退出，那么当另一个处理器轮询三个、十个或几十个其他任务时，一个处理器会不会空闲？ 为了解决这个基本问题，2.6 调度器必须偶尔查看是否需要跨 CPU 平衡。 现在这也是一项要求，因为正如前面提到的，一个 CPU 可能很忙，而另一个 CPU 却空闲。 等到任务即将完成其时间片才平衡队列往往会导致 CPU 空闲时间过长。 相反，2.5 和 2.6 利用进程记帐（由时钟滴答驱动）来定期检查队列。 每 200 毫秒，处理器都会检查以查看是否有任何其他处理器失去平衡并且需要与该处理器平衡。 如果处理器空闲，它会每 1 毫秒检查一次，以便尽快开始处理实际任务。

这并不是说调度器现在已经固定下来，并且所有关于它的工作都已停止。 某些工作负载和架构提供了一些有趣的场景，调度器仍然无法很好地处理这些场景。

一个成功的调度器的目标可以简单地陈述，即使这些目标并不总是能够简单地实现。

此外，Linux 调度器的理念是它应该在大多数时候都是基本正确的，而不是在很多时候都是完美的。 即使不同的工作负载表现出不同的行为并对系统施加不同的压力，调度器也应该足够通用和健壮，以便至少充分处理所有工作负载，而无需额外的调整。

2.6 中的大多数调度器调整都是为了改进交互式响应而进行的。 最初，这是传统意义上的交互，即在监视器上拖动窗口或在键盘上打字。 交互式任务旨在定义利用大量人机交互的任务。 但它已逐渐扩展为意味着“从自我强加的睡眠中醒来后应获得高优先级的任务”。 这包括之前的任务集，但也包括现在人类可以察觉到延迟的任务，例如音乐播放器中的延迟。 因为这是一个主观评估，所以可能永远无法让每个人都满意。 然而，来自测试人员的普遍共识是，使用 2.6 调度器后情况有所好转。

想象一下，两个任务花费大量时间通过管道或共享内存相互通信。 一些证据表明，如果它们位于 同一 处理器上，它们可能会做得更好，即使这意味着让另一个处理器空闲。 如果一个任务向另一个任务发送消息，然后等待回复，则两者都倾向于交替变为可运行状态，并且在它们都可运行状态时略有重叠。 换句话说，它们不会经常冲突。 最大的节省来自于处理器缓存预先加载了管道中的数据，因此无需再次获取并复制到另一个处理器的缓存中。 尽管处理器速度有所提高，但内存和总线速度却没有跟上。 必须检索曾经缓存的数据变得越来越痛苦。

移动使用少量内存的任务对处理器的影响与移动使用大量内存的任务对处理器的影响不同。 但是，根据具体情况，大型任务或小型任务都可能是正确的选择。 如果您将使用大量内存的任务从处理器中移开，留下许多不使用太多内存的小型任务，则这些任务中的每一个都可能在每次运行时发现其内存中有更高的百分比在缓存中。 另一方面，将该大型任务移动到另一个具有大型任务的处理器现在可能会导致 所有 任务都以冷缓存启动，并对它及其新邻居的性能产生负面影响。 当前代码根本没有考虑进程大小。

出于与进程亲和性几乎相同的原因，有时如果任务大量使用特定设备，则将处理器与任务一起过载可能会有所回报。 例如，Web 服务器通常有多个网卡，但不足以为每个 CPU 配备一个网卡。 将这些任务聚集在网络数据到达的处理器上可能被证明是非常有利的。 确定哪些任务可能使用哪些设备目前既不明显也不容易。

Shell 脚本可能会导致大量生命周期短的任务，尤其是当它们不使用或不能使用内置函数进行字符串或数字操作时。 尽管有人可能会争辩说这些是编码不良的脚本，但它们仍然表明调度器在 SMP 机器上平衡队列时可能太慢。 具有类似行为的工作负载也会受到影响。

想象一下一个将工作分成六个相等部分的程序，理想情况下所有部分都同时完成。 不幸的是，在四处理器机器上，两个处理器倾向于承担两个任务，而另外两个处理器倾向于承担一个任务，情况就是这样。 除非调度器努力分散压力，否则两个作业的完成速度会比其他四个作业快，因为它们在处理器上没有竞争。 另一方面，在大多数作业组合中，移动这些零星作业仍然会在两个处理器中的每个处理器上留下两个任务。

NUMA（非一致性内存访问）提出了一些有趣的特性需要担心。 在 NUMA 系统中，从那边（靠近另一个处理器）获取内存可能比从这边（靠近这个处理器）获取内存贵得多。 拥有一个空闲处理器是不够的； 您需要一个既空闲又迁移成本不太高的处理器。 例如，如果任务的大部分资源都位于当前位置，则迁移任务可能是不好的。 甚至可能糟糕到最好将其留在繁忙的处理器上，而不是将其移动到具有冷缓存的空闲处理器上。

超线程引入了又一个复杂性。 在超线程中，两个处理器共享以硬件相关方式重叠的内核。 由于这种相互依赖性，在一个处理器上运行的作业 会 影响在另一个处理器上运行的作业的速度。 尽管没有人会期望一台装有四个超线程处理器的盒子能与一台完整的八处理器机器相提并论，但具体期望会因工作负载而异。 唯一可以肯定的是，它不应产生 更低 的性能。

2.6 调度器比 2.4 调度器提供了一些强大的改进。 对于大多数工作负载，它在大型机器上具有更好的可伸缩性，而不会放弃构成 Linux 市场大部分的单处理器和双处理器用户所需的性能。 最近的更改使调度器能够在流畅地处理内核构建的同时播放您最喜欢的歌曲。 2.6 内核现在可供喜欢冒险的人在 www.kernel.org 上使用。 利用 2.6 内核的 Linux 供应商的完整发行版将会滞后，因为供应商会完成他们自己的测试并添加他们自己的支持功能； 您应该直接联系您喜欢的供应商以获取发布信息。