操作系统中的多处理器调度

多处理器调度或多核调度侧重于设计包含多个处理器的系统的调度功能。在多处理器调度中，多个CPU分担负载（负载分担），以便同时运行各种进程。通常，多处理器调度比单处理器调度复杂。在多处理器调度中，有许多处理器，它们是相同的，我们可以在任何时候运行任何进程。

系统中的多个CPU之间紧密通信，共享一个公共总线、内存和其他外围设备。因此，我们可以说该系统是紧耦合的。这些系统用于处理大量数据，主要用于卫星、天气预报等领域。

在多处理器调度中，处理器在功能上是相同的，即同质的。我们可以使用任何可用的处理器来运行队列中的任何进程。

多处理器系统可以是异构的（不同类型的CPU）或同构的（相同的CPU）。可能会有特殊的调度约束，例如通过专用总线仅连接到单个CPU的设备。

没有哪项策略或规则可以被宣布为单处理器系统的最佳调度解决方案。同样，也没有多处理器系统的最佳调度解决方案。

多处理器调度的方法

操作系统中有两种多处理器调度方法：对称多处理和非对称多处理。

1. 对称多处理：它用于每个处理器都自调度的系统。所有进程都可能在一个公共就绪队列中，或者每个处理器都可能有自己的私有就绪进程队列。调度通过每个处理器的调度器检查就绪队列并选择一个进程来执行而继续进行。
2. 非对称多处理：它用于所有调度决策和I/O处理都由一个称为主服务器的单个处理器处理的系统。其他处理器只执行用户代码。这种方法简单，减少了数据共享的需求，整个场景被称为非对称多处理。

处理器亲和性

处理器亲和性意味着一个进程对其当前正在运行的处理器具有亲和性。当一个进程在特定处理器上运行时，会对缓存内存产生一定影响。进程最近访问的数据会填充该处理器的缓存。因此，进程后续的内存访问通常在缓存内存中得到满足。

现在，假设进程迁移到另一个处理器。在这种情况下，第一个处理器的缓存内存内容必须失效，并且第二个处理器的缓存必须重新填充。由于失效和重新填充缓存的成本很高，大多数SMP（对称多处理）系统试图避免进程从一个处理器迁移到另一个处理器，并使进程在同一处理器上运行。这就是处理器亲和性。处理器亲和性有两种类型，例如：

1. 软亲和性：当操作系统有一项策略，即让进程在同一处理器上运行，但不保证一定会这样做时，这种情况称为软亲和性。
2. 硬亲和性：硬亲和性允许进程指定一个可以在其上运行的处理器子集。一些Linux系统实现了软亲和性，并提供了诸如sched_setaffinity()之类的系统调用，这些调用也支持硬亲和性。

负载均衡

负载均衡是使SMP系统中所有处理器上的工作负载均匀分布的现象。负载均衡仅在每个处理器都有自己的私有可执行进程队列的系统上才需要。

负载均衡是不必要的，因为它一旦处理器空闲，就会立即从公共运行队列中提取一个可运行的进程。在SMP（对称多处理）上，保持所有处理器之间的工作负载平衡很重要，以充分利用拥有多个处理器的优势。一个或多个处理器将处于空闲状态，而其他处理器工作负载很高，同时还有等待CPU的处理器列表。负载均衡有两种通用方法：

1. 推式迁移：在推式迁移中，任务会定期检查每个处理器的负载。如果发现不平衡，它会通过将进程从过载处理器移动到空闲或不那么繁忙的处理器来均匀分配每个处理器上的负载。
2. 拉式迁移：拉式迁移发生在空闲处理器从繁忙处理器拉取等待任务以执行时。

多核处理器

在多核处理器中，多个处理器核心放置在同一个物理芯片上。每个核心都有一个寄存器集来维护其架构状态，因此对操作系统来说它是一个独立的物理处理器。使用多核处理器的SMP系统比每个处理器都有自己物理芯片的系统更快，功耗更低。

然而，多核处理器可能会使调度问题复杂化。当处理器访问内存时，它会花费大量时间等待数据可用。这种情况称为内存停顿。它由于各种原因发生，例如缓存未命中，即访问不在缓存内存中的数据。

在这种情况下，处理器可能会花费多达50%的时间等待数据从内存中可用。为了解决这个问题，最近的硬件设计实现了多线程处理器核心，其中每个核心分配两个或更多硬件线程。因此，如果一个线程在等待内存时停顿，核心可以切换到另一个线程。有两种方法可以使处理器多线程化：

1. 粗粒度多线程：在粗粒度多线程中，线程在处理器上执行，直到发生长延迟事件，例如内存停顿。由于长延迟事件造成的延迟，处理器必须切换到另一个线程才能开始执行。线程之间切换的成本很高，因为必须终止指令管道，然后其他线程才能开始在处理器核心上执行。一旦新线程开始执行，它就会开始用其指令填充管道。
2. 细粒度多线程：这种多线程在更细的粒度级别之间切换线程，主要在指令周期的边界。细粒度系统的架构设计包括线程切换逻辑，因此线程之间切换的成本很小。

对称多处理器

对称多处理器 (SMP) 是第三种模型。在此模型中，内存中只有一个操作系统的副本，但任何中央处理单元都可以运行它。现在，当进行系统调用时，进行系统调用的中央处理单元会陷入内核并处理该系统调用。该模型动态平衡进程和内存。这种方法使用对称多处理，其中每个处理器都是自调度的。

调度通过每个处理器的调度器检查就绪队列并选择一个进程来执行而继续进行。在这个系统中，所有进程都可能在一个公共就绪队列中，或者每个处理器都可能有自己的私有就绪进程队列。多处理器操作系统中主要存在三个争用源：

• 锁定系统：正如我们所知，多处理器系统中资源是共享的，因此需要保护这些资源，以确保多个处理器之间的安全访问。锁定方案的主要目的是将多个处理器对资源的访问序列化。
• 共享数据：当多个处理器同时访问相同数据时，可能会出现数据不一致的情况，因此为了保护数据，我们必须使用一些协议或锁定方案。
• 缓存一致性：它是存储在多个本地缓存中的共享资源数据。假设两个客户端都有内存的缓存副本，并且一个客户端更改了内存块。另一个客户端可能会在没有收到更改通知的情况下留下无效缓存，因此可以通过维护数据的一致视图来解决此冲突。

主从多处理器

在此多处理器模型中，有一个单一数据结构用于跟踪就绪进程。在此模型中，一个中央处理单元充当主处理器，另一个充当从处理器。所有处理器都由一个称为主服务器的单一处理器处理。

主服务器运行操作系统进程，从服务器运行用户进程。内存和输入输出设备在所有处理器之间共享，所有处理器都连接到一条公共总线。该系统简单且减少了数据共享，因此该系统称为非对称多处理。

虚拟化与线程

在这种类型的多处理器调度中，即使是单个CPU系统也充当多处理器系统。在采用虚拟化的系统中，虚拟化会为系统上运行的每个虚拟机提供一个或多个虚拟CPU。然后，它在虚拟机之间调度物理CPU的使用。

• 大多数虚拟化环境都有一个宿主操作系统和许多客户操作系统，宿主操作系统创建和管理虚拟机。
• 每个虚拟机都安装了一个客户操作系统，并且应用程序在该客户操作系统内运行。
• 每个客户操作系统都可以分配用于特定的用例、应用程序或用户，包括分时或实时操作。
• 任何假设在给定时间内取得一定进展的客户操作系统调度算法都将受到虚拟化的负面影响。
• 一个分时操作系统试图为每个时间片分配100毫秒，以给用户一个合理的响应时间。一个给定的100毫秒时间片可能需要远远超过100毫秒的虚拟CPU时间。根据系统繁忙程度，时间片可能需要一秒或更长时间，这导致登录到该虚拟机的用户响应时间非常差。
• 这种调度分层的最终效果是，即使单个虚拟化操作系统认为自己正在接收所有CPU周期并调度所有这些周期，它实际上也只接收可用CPU周期的一部分。虚拟机中的时间日历通常不正确，因为计时器触发所需的时间并不比在专用CPU上更长。
• 因此，虚拟化可能会抵消虚拟机内操作系统良好的调度算法工作。

多处理器调度的算法类型

操作系统使用各种多处理器调度算法。一些最常见的类型是：

• 轮询调度：轮询调度算法为每个CPU分配一个时间量子，并设置程序以轮询方式在每个处理器上执行。这种方法在所有应用程序具有相同优先级的系统中可能很有用，因为它保证每个进程获得相等的CPU时间。
• 优先级调度：这种方法为每个进程分配一个优先级，优先级较高的进程首先被调度执行。在某些任务（例如实时任务）需要更高优先级的系统中，这种策略可能很有用。
• 最短作业优先（SJF）：该算法根据估计的完成时间调度任务。最短的任务应该首先运行，其次是下一个最短的任务，依此类推。由于它可以减少典型的响应时间，因此该方法在具有多个快速进程的系统中可能很有用。
• 公平共享调度：这种技术中分配给每个进程的时间量取决于其优先级和处理器数量。这种方法在混合有长进程和短进程的系统中可能很有用，因为它保证每个进程获得公平的处理时间。
• 最早截止时间优先（EDF）：在此算法中，每个进程都有一个截止时间，具有最早截止时间的进程将首先运行。此方法在具有严格截止时间的实时活动的系统中可能很有用。
• 使用多级反馈队列（MLFQ）进行调度：多层反馈队列（MLFQ）使用一系列优先级级别分配给进程，并且它们可以根据其行为在优先级级别之间上下移动。对于同时具有短进程和长进程的系统，这种策略可能很有帮助。

调度多个处理器的优点

• 更大的吞吐量：多处理器调度允许多个进程同时在不同的CPU上运行。这种并行性导致比单处理器系统更高的吞吐量，因为在给定时间内完成了更多的任务。
• 提高资源利用率：当有多个处理器可用时，操作系统可以有效地分配工作，防止某些处理器过载，而另一些处理器空闲。
• 更快的响应时间：由于多个处理器可以同时处理多个请求，进程的等待时间更短，从而加快了用户应用程序和系统级任务的速度。
• 提高系统可靠性和容错能力：系统设计允许在处理器发生故障时，其他处理器接管工作负载，从而实现连续运行而不会导致系统完全崩溃。
• 可扩展性：多处理器系统可以通过添加更多处理器轻松扩展。这消除了从头开始重新设计系统架构以适应要求苛刻的应用程序或处理不断增长的工作负载的必要性。

多处理器调度的缺点

• 调度算法变得更加复杂。管理多个处理器比管理一个处理器困难得多。调度器需要考虑处理器亲和性、负载均衡和同步，这增加了算法和实现的复杂性。
• 同步和通信带来的开销。当多个处理器需要访问共享数据或资源时，需要使用锁或信号量等同步技术。由于争用和延迟，这会增加开销，并可能降低并行性的优势。
• 处理器亲和性问题。在某些系统中，定期在同一CPU上调度的进程表现更好（由于缓存使用）。保持处理器亲和性可能会阻碍最佳负载均衡，并引入额外的复杂性。
• 负载分配不均。在没有有效负载均衡的情况下，一些处理器可能仍然未充分利用，而另一些处理器则过载，这可能导致资源使用效率低下和性能下降。
• 价格和功耗。多处理器系统的硬件和功耗成本更高。它们需要更先进的散热解决方案，导致更高的运营成本。

常见问题

什么是多处理器调度？

多处理器调度是操作系统用于在两个或多个CPU之间分配和管理任务的一种技术。同时管理多个进程的目标是平衡负载、最大化CPU利用率并提高系统性能。

对称多处理与非对称多处理有何不同？

对称多处理（SMP）将工作负载平均分配给所有处理器，这是它与非对称多处理的区别。在非对称多处理（AMP）中，单个处理器（通常称为主处理器）控制系统并将任务分配给从处理器，然后从处理器完成任务。

为什么负载均衡在多处理器系统中很重要？

在多处理器系统中，负载均衡是必要的，以确保每个处理器都被平等使用。没有它，一些CPU将空闲和过载，这可能对性能产生不利影响。有效分配负载可以提高生产力并减少瓶颈。

什么是处理器亲和性，为什么要使用它？

将特定CPU分配给进程的过程称为处理器亲和性。将进程保持在同一处理器上可以提高缓存性能，因为它每次运行时需要加载到缓存内存中的数据更少。

所有操作系统都能调度和管理多个处理器吗？

不是。只有具有多处理器意识的操作系统，例如最新版本的Windows、Linux和macOS，才能有效处理多个处理器。过旧或简单的操作系统可能只支持单处理器环境。