我有一个关于如何进行调度的问题。我知道，当一个系统有多个CPU时，调度通常是在每个处理器的基础上完成的。每个处理器都运行自己的调度程序，访问仅在其上运行的进程的就绪列表
那么，与所有处理器共享一个就绪列表的方法相比，优缺点是什么呢？
比如，将进程分配给处理器时会出现什么问题，如果进程始终位于一个处理器上，可能会导致什么问题？就数据结构的互斥锁和等待锁所花费的时间而言，这有什么问题吗？
当涉及到多核CPU系统时，通常会有一个巨大的问题——缓存一致性。
缓存一致性是什么意思
很难访问主存储器。根据内存频率的不同，访问RAM中的一些数据可能需要几千到几百万个周期——这是CPU没有做任何有用工作的大量时间。如果我们尽可能减少这段时间，情况会好得多，但这样做所需的硬件很昂贵，而且通常必须非常靠近CPU本身(我们说的是在离核心几毫米的范围内)。
这就是缓存的作用所在。缓存将主内存的一小部分保持在靠近核心的位置，从而使对该内存的访问速度比主内存快几个数量级。对于读取来说，这是一个简单的过程——如果内存在缓存中，则从缓存中读取，否则从主内存中读取。
写作有点棘手。写入缓存很快，但现在主内存仍然保持原始值。我们可以更新内存，但这需要一段时间，有时甚至比读取更长，这取决于内存类型和电路板布局。我们如何将这种情况降到最低？
最常见的方法是使用回写缓存，当写入时，当CPU空闲或不做任何事情时，它会在稍后的某个时间点将缓存中包含的数据刷新回主内存。根据CPU架构的不同，这可以在空闲条件下进行，也可以与CPU指令交错进行，或者在计时器上进行(这取决于CPU的设计者/制造商)。
为什么这是个问题
在单核系统中，只有一条路径可供读取和写入-它们在通往主存的路上必须经过缓存，这意味着在CPU上运行的程序只能看到它们的期望-如果它们读取一个值，修改它，然后读回它，它就会被更改。
然而，在多核系统中，数据在返回主存储器时有多条路径可供使用，这取决于发出读取或写入的CPU。这就给写回缓存带来了一个问题，因为"稍后"会引入一个缺口，在这个缺口中，一个CPU可能会读取尚未更新的内存。
想象一下一个双核系统。作业在CPU 0上启动并读取内存块。由于内存块不在CPU 0的缓存中，因此它是从主内存中读取的。稍后，作业会写入该内存。由于缓存是回写的，因此将对CPU 0的缓存进行写操作，并在稍后刷新回主内存。如果CPU1随后尝试读取同一存储器，则CPU1将再次尝试从主存储器读取，因为它不在CPU1的高速缓存中。但是来自CPU 0的修改还没有离开CPU 0的缓存，所以您返回的数据是无效的——您的修改还未完成。你的程序现在可能会以微妙、不可预测和潜在的破坏性方式崩溃。
因此，缓存同步可以缓解这种情况。存在应用程序ID、地址监视和其他硬件机制来同步多个CPU之间的缓存。所有这些方法都有一个共同的问题——它们都迫使CPU花时间记账，而不是实际有用的计算。
避免这种情况的最佳方法实际上是尽可能多地将进程保留在一个处理器上。如果进程不在CPU之间迁移，则不需要保持缓存同步，因为其他CPU不会同时访问该内存(除非内存在多个进程之间共享，但我们在此不讨论)。
现在我们来讨论如何设计我们的调度器，以及其中的三个主要问题——避免进程迁移、最大限度地提高CPU利用率和可扩展性。
单队列多处理器调度(SQMS)
您建议使用单队列多处理器调度器——一个队列包含可用进程，每个核心访问该队列以运行下一个作业。这实现起来相当简单，但有几个主要缺点——它可能会导致大量的进程迁移，并且不能很好地扩展到具有更多核心的大型系统。
想象一下，一个有四个核心和五个作业的系统，每个作业的运行时间大致相同，并且每个作业在完成后都会重新安排。在第一次运行时，CPU 0获取作业A，CPU 1获取作业B，CPU 2获取作业C，CPU 3获取作业D，而E留在队列中。假设CPU 0完成作业A，将其放在共享队列的后面，然后寻找另一个要做的作业。E当前位于队列的前面，而CPU 0获取E，然后继续。现在，CPU 1完成作业B，将B放在队列的背面，然后寻找下一个作业。它现在看到A，并开始运行A。但由于A以前在CPU 0上，CPU 1现在需要将其缓存与CPU 0同步，这导致CPU 0和CPU 1都失去了时间。此外，如果两个CPU同时完成操作，它们都需要写入共享列表，这必须按顺序进行，否则列表将损坏(就像在多线程中一样)。这需要两个CPU中的一个等待另一个完成写入，并将缓存同步回主内存，因为列表在共享内存中！添加的CPU越多，这个问题就越严重，导致大型服务器(可能有16甚至32个CPU核)出现重大问题，并且在超级计算机上完全不可用(其中一些计算机的核数超过1000)。
多队列多处理器调度(MQMS)
多队列多处理器调度器每个CPU核心只有一个队列，确保所有本地核心调度都可以完成，而无需使用共享锁或同步缓存。这使得具有数百个核心的系统能够在每个调度间隔(每秒可能发生数百次)在不相互干扰的情况下运行。
MQMS的主要问题来自CPU利用率，其中一个或多个CPU核心承担大部分工作，以及调度公平性(其中计算机上的一个进程比具有相同优先级的任何其他进程调度得更频繁)。
CPU利用率是最大的问题——如果安排了作业，那么任何CPU都不应该空闲。然而，如果所有CPU都很忙，所以我们将一个作业调度到一个随机的CPU，而另一个CPU最终变为空闲，那么它应该从原始CPU"窃取"调度的作业，以确保每个CPU都在做真正的工作。然而，这样做需要锁定两个CPU核心，并可能同步缓存，这可能会降低我们通过窃取计划作业而获得的任何加速。
结论
这两种方法都存在于野外——Linux实际上有三种不同的主流调度算法，其中一种是SQMS。调度器的选择实际上取决于调度器的实现方式、计划运行它的硬件以及打算运行的作业类型。如果您知道只有两个或四个核心来运行作业，那么SQMS可能就足够了。如果你运行的超级计算机的开销是一个主要问题，那么MQMS可能是最好的选择。对于桌面用户来说，只要相信发行版，无论是Linux操作系统、Mac还是Windows。一般来说，你所拥有的操作系统的程序员已经做好了功课，明确了对于他们系统的典型用例，什么调度器是最佳选择。
本白皮书描述了现有的两种类型的调度算法之间的差异。