Multiprocessor Scheduling
简介
当涉及多个CPU时，调度算法 可能会变得棘手，由于英特尔的超线程技术 (一个复杂的CPU显示为多个CPU)，多处理器的操作系统开发也成为了爱好者可以接触的内容...
突然之间，多CPU体系结构的细节变得比单处理器系统更加重要。 内存管理单元 (MMU) 是如何设计的？一些CPU能够在其翻译后备缓冲区 (TLB) 中保存多个进程的页表 - 如果相同的进程始终在相同的CPU上运行，而不是每次调度时使用不同的进程，这将有利于系统性能。
另一个问题是多线程。 在单CPU系统上，多线程 (即单个地址空间中的多个控制流) 是一件好事，如果操作正确，可以极大地提高系统的性能。 但是在多处理器系统上，赢得的好处会更大-同时实现它们变得越来越困难。
调度程序激活
调度程序激活是一种机制，可以在内核中实现用户级线程并在提供内核线程功能的同时提供用户级线程的好处。 内核级调度程序调度任务或进程，任何任务都可以从中调度进程调度程序。 每当该任务由内核中的系统范围的任务调度程序选择和调度时，它将在用户空间中执行进程调度程序。 进程级调度程序将具有用户级线程的结构，可以在用户模式本身中创建，暂停，等待和销毁。 “M” 数量的任务可以引用进程调度器 (因为在M:N模型中有 “M” 数量的内核线程)，并且该调度器将保存 “N” 数量的用户级线程。 这允许在没有任何上下文切换的情况下对用户空间中的线程进行超快速管理。
进程级调度对于具有短寿命的线程 (例如输入和输出线程) 的进程特别有用。 当相当多的线程处于睡眠状态或等待其他线程时，这也将很有帮助。 这些依赖关系可以在用户空间本身中解决。
通过为每个内核线程设置单独的运行队列，可以在多处理器系统中扩展此模型。 就像linux内核如何在系统中的每个CPU上维护单独的任务队列一样。 这减少了进程调度程序中的并发开销，并允许无锁调度算法。 但这将导致更高水平的复杂性。
调度每个CPU分配有自己的运行队列
传统的调度技术使用一种数据结构来保存系统中的所有任务。 这是许多成本和缺点，降低了整个操作系统的效率和产量，即-
1. Synchronization Overhead - 当每个CPU访问系统中任务的 “全局运行队列” 时，它们将不得不锁定数据结构的特定部分 (如果不是整体)，并且同步将极大地影响系统中的并行性。
2. Caching & TLB Usage - 如果每个CPU使用相同的数据结构，那么所有任务将不断从一个CPU跳到另一个CPU。 这意味着任务永远不会有机会用自己的代码和数据填充缓存和TLB。 在现代处理器中，L1，L2，L3和L4高速缓存的有效使用对于最佳性能和降低TLB冲洗速度在虚拟内存中执行至关重要。
为了克服这些限制，为每个CPU分配了自己的运行队列，它在不获取任何锁的情况下访问该队列。 运行队列上的操作可以通过关闭中断来完成，以避免 “运行队列平衡器” (我们将在稍后介绍) 在实际调度程序使用运行队列时访问运行队列。
任务平衡或运行队列平衡
所有多处理器调度器都遭受系统中不同处理器之间的负载不平衡。 这意味着一个处理器可能会被任务轰炸，而另一个处理器可能会小睡一会儿 (开玩笑)。 这种不一致性解决了内核的任务平衡器。 每当任务平衡器运行 (以特定的内核时间间隔) 以平衡cpu的两个域之间的任务时，它就会将任务从负载重的任务转移到负载少的任务。 根据其实现，它可以执行一个负载较重的处理器，一个负载较少的处理器，或者两者兼而有之。 它从负载沉重的处理器中获取任务，并将其分配给系统中的空闲或负载较少的处理器。 它将访问两个处理器的任务队列 (也可以执行休眠任务)。 对于无锁多处理器调度器，应关闭中断 (除非已经在中断上下文中，其中下一个中断将排队，直到IRET执行)，同时访问运行队列以进行任何操作，例如从中添加或删除任务。
其他事实...
我在该主题上读过的一件事是，某些线程可能 *固定* 在特定的CPU上，而其他线程将在第一个可用的CPU上执行。 这可能是有意义的，例如，使GUI服务器的主线程 “驻留” 在CPU上，以实现高响应 (其他想要与GUI交互的线程可以这样做，而不会产生上下文切换损失:)
将线程固定到CPU也有助于CPU的缓存。 如果一个线程在每次运行时在CPU之间跳跃，它永远不会有机会用代码或数据填充CPU的缓存: 它可能会运行一会儿，并从主内存加载一些指令，然后被抢占。 下次计划时，它可能会在其他CPU上运行，在该CPU上需要重新加载缓存。 如果调度程序可以为每个线程分配自己喜欢的CPU，则可以帮助提高缓存性能。 当然，如果两个具有相同喜欢的CPU的线程希望在双处理器系统上同时运行，则其中一个将不得不使用 “错误的” CPU。
SVR4 Unix有一个很好的同步工具 (一种智能自旋锁)，用于多处理器，允许线程忙碌-等待资源，只要资源持有者在另一个CPU上处于活动状态，并在持有者不运行时进入睡眠状态。 这已经在论文中得到证明 (我丢失了参考文献)，这种方法支付并导致比资源繁忙时总是进入睡眠状态更好的性能。
一个简单的方法
多处理器调度的一种简单方法是为每个CPU分配自己的调度程序。 然后当你加载一个线程时，它被分配给某个CPU。 这涉及固定，但你必须在线程终止后保持工作负载平衡。
另见
文章
论坛主题
外部链接
- Multiprocessor Specification
- Process Sleep and Wakeup on a Shared-memory Multiprocessor, describes the approach taken in Plan 9 from Bell Labs. Paper written by Rob Pike, Ken Thompson and others.