上个月，我们开始了关于 Linux 内核内部结构的新系列文章。在第一部分中，我们了解了 Linux 如何管理进程，以及在许多方面，Linux 在创建和维护进程方面比许多商业 UNIX 系统更出色。

这次，我们将深入探讨调度主题。令我惊讶的是，Linux 再次走了非正统的道路，无视内核理论中的传统智慧。结果非常出色。让我们看看是如何实现的。

在 Linux 2.2.x 中，进程分为三个类，这可以从调度器的数据定义中看出（来自 linux/include/linux/sched.h）

/* Scheduling Policies
*/
#define SCHED_OTHER  0
#define SCHED_FIFO   1
#define SCHED_RR     2

SCHED_OTHER 任务是正常的用户任务（默认）。

在 SCHED_FIFO 中运行的任务将永远不会被抢占。它们离开 CPU 仅仅是为了等待同步内核事件，或者如果用户空间请求了显式的睡眠或重新调度。

在 SCHED_RR 中运行的任务是实时 (RT) 任务，但如果运行队列中还有另一个实时任务，它们将离开 CPU。因此，CPU 功率将在所有 SCHED_RR 任务之间分配。如果至少有一个 RT 任务正在运行，则任何其他 SCHED_OTHER 任务都不允许在任何 CPU 中运行。每个 RT 任务都有一个 rt_priority，因此 SCHED_RR 类将被允许随意在所有 SCHED_RR 任务之间分配 CPU 功率。SCHED_RR 类的 rt_priority 的工作方式与 SCHED_OTHER（默认）类的普通优先级字段完全相同。

只有 root 用户可以通过 sched_setscheduler 系统调用更改当前任务的类。

内核的任务之一是确保系统即使在程序行为不端的情况下也能保持牢牢控制。一个这样的行为不端的程序可能会fork 过多的进程，速度太快。因此，内核变得非常忙于自身，以至于无法履行其其他职责。我发现 Linux 对用户态程序可以多快地派生子进程没有限制。HP-UX、Solaris 和 AIX 限制为每个处理器时钟滴答（在 Linux 下称为 jiffie）一个 fork。清单 1 中的补丁（见资源）将允许每个 jiffie 最多一个 fork（一个 jiffie 通常是 1/100 秒，但在 Alpha 架构上是 1/1024）。

线程对于允许您的进程利用多处理器是必要的。从内存管理和调度的角度来看，Linux 实际上并没有区分进程和线程。某些操作系统（如 Solaris）通过线程调度库管理用户进程中的线程。内核只看到进程，不知道用户进程内部实际执行的是哪个线程（如果有）。这节省了内核为每个进程的每个线程管理包含数千个条目的列表。

显然，在单个用户进程之上模拟的线程不允许在 SMP 上并发运行，因此用户空间方法在 SMP 机器上扩展性不太好。仅当所有线程都是 CPU 密集型而不是主要面向 I/O 时，线程才是绝对必要的。如果所有线程都是 CPU 密集型，您肯定希望能够为 SMP 扩展。

仅使用线程来等待事件是过度的。另一方面，让线程休眠是资源和性能的浪费。Linux 中的几乎所有子系统（例如 TCP/IP）都提供异步事件注册。通过 SIGIO 信号使用异步事件类似于 IRQ 驱动的处理。

使用用户空间方法，您至少可以避免 TLB（转换后备缓冲区）刷新，因为所有线程将共享相同的地址空间。

通过线程库在用户空间中管理线程的优势在于，内核将在用户空间中花费调度 CPU 成本。确实，在用户空间中，您可以选择实现一个非常快速的轮询调度器，与巧妙的（但执行路径更昂贵的）Linux 调度器相比，它可以降低调度成本。

说到 SMP，截至 Linux 2.4，我发现无法声明任何给定用户空间进程的处理器亲和性。

调度器可以跟踪进程的 CPU 亲和性声明，或者它可以自行确定进程的首选 CPU。前几天，我与意大利的 Andrea Arcangeli 一起设计了清单 2（见资源）中的简单内核补丁，该补丁实现了处理器亲和性。请注意，当其他进程被排除在在此 CPU 上运行时，处理器亲和性才最有意义。实现此补丁的更好方法是让系统管理员使用 nice 等外部调用来设置亲和性。

2.2.x SMP 内核调度器有一些错误，有时会使其效率低于 UP（单处理器）调度器。然而，Andrea 修复了所有此类错误，并从头开始重写了启发式方法，并且 SMP 调度器在负载下提供了令人印象深刻的 SMP 改进。SMP 更改仅在 2.3.x 内核中，我计划也将其集成到 2.2.x 中。您可以从 ftp.suse.com/pub/people/andrea/kernel-patches/my-2.2.12/SMP-scheduler-2_2_11-E 获取 Andrea 的补丁。该补丁可以用于 2.2.11 和 2.2.12，并加快 SMP 系统上内核的速度。该补丁已合并到 2.3.15 中，但尚未合并到 2.2.x 中，因为它只是一个性能问题，而不是真正的错误修复。

SMP 调度器启发式机制的工作原理是以下各项的函数（不按任何特定顺序排列）

该算法收集上述数据并选择最佳 CPU 以在其上重新调度 wakenup 任务。

Linux 调度器行为涉及两个路径

这两个路径共享 goodness 函数。goodness 函数可以被认为是 SMP 调度器的核心。它计算任务的“优良性”，作为以下各项的函数

清单 3

普通的调度仅基于 goodness 工作。正如您在清单 3 中看到的那样，普通的调度是 SMP 感知的。如果潜在的下一个任务的最后一个 CPU 是当前 CPU，则其 goodness 会增加。

然而，对于 CPU 亲和性和调度器延迟，reschedule_idle 更为关键；例如，如果您注释掉 reschedule_idle，调度器延迟将变为无限。此外，reschedule_idle 负责处理缓存刷新时间和任务平均时间片，这是 SMP 调度器真正有趣的部分。在 UP 中，reschedule_idle 不如 SMP 版本有趣。清单 4（见资源）是从 2.3.26（即将推出 2.4）中提取的 reschedule_idle 实现。

reschedule_idle 的最终目标是在 CPU 上调用调度，以便在其上重新调度唤醒任务。我们在 reschedule_idle 中使用 goodness，因为我们想要预测我们将发送到该 CPU 的未来调度的效果。通过预测未来调度的效果，我们可以选择最佳 CPU 以在唤醒时重新调度。当然，这省去了我们在没有正确 TLB 设置的 CPU 上执行的麻烦。如果要重新调度的 CPU 不是当前 CPU，我们会通过 CPU 间消息传递（i386 上的 SMP-IPI 中断）发送重新调度事件。

为了非常清楚：goodness 函数是 Linux 调度器的核心，并且是 SMP 感知的，而 reschedule_idle 是巧妙的 SMP 启发式方法的核心。

Linux 只能进行用户抢占。Linus Torvalds 似乎不相信内核抢占。这并不像看起来那么糟糕；对于信号量来说一切都很好。受信号量保护的临界区可以随时被抢占，因为每次争用都会以调度结束，并且不会出现任何死锁。但是，受快速自旋锁或手动锁保护的临界区除非我们阻止定时器 IRQ，否则无法被抢占。因此，所有自旋锁都应该是 IRQ 安全的。此外，通过避免内核抢占，内核变得更健壮和更简单，因为这样可以节省大量复杂的代码。

顺便说一句，有一些工具可以监控调度器延迟，以便让感兴趣的黑客捕获可能需要条件调度的代码段。

Linux 由于其 GPL 性质，允许我们比其他人更快地完成事情，因为您可以调整和重新编译自己的内核，而不是使用标准的通用内核。例如，在某些流行的专有操作系统（如 Solaris 7）中，许多代码段都已打包在 spin_lock 和 spin_unlock 中，以使相同的代码在 UP 和 SMP 系统中都能良好运行。虽然这些商业操作系统的供应商将此吹捧为重型 SMP 系统的明显优势，但这些锁实际上会拖慢 UP 系统和简单的 SMP 机器的速度，因为相同的二进制驱动程序必须在 SMP 和 UP 内核上都能工作。spin_unlock 是一个锁定的 ASM 指令

#define spin_unlock_string \
        "lock ; btrl $0,%0"

并且通过函数指针调用这样的清零位指令完全是过度。

另一方面，Linux 具有用于 UP 和 SMP 系统的内联代码段，可以适应其运行的机器。因此，如果只有单处理器系统托管内核，则不会浪费时间锁定不需要锁定的代码段。

最后但并非最不重要的一点，正如我们在上面看到的那样，goodness 函数使 Linux 中的 SMP 调度器非常巧妙。拥有一个巧妙的 SMP 调度器对于性能至关重要。如果调度器不是 SMP 感知的，操作系统理论告诉我们，SMP 机器上的性能甚至可能比 UP 机器上的性能更差。（这发生在 2.2.x 没有新的启发式方法的情况下，但现在已修复。）

这就是本月的内容。我希望您对 Linux 如何在 UP 和 SMP 系统上调度任务有了更深入的了解。

资源