CPU虚拟化-进程调度 | 彩潭有鲤的札记

type

status

date

slug

summary

先进先出（FIFO）

FIFO有一些积极的特性：它很简单，而且易于实现。而且，对于假设，它的效果很好。

假设当它们都同时到达时，A 比B 早一点点，然后B 比C 早到达一点点。假设每个工作运行10s，这些工作的平均周转时间为

放宽假设，不再认为每个任务的运行时间相同，FIFO 表现如何？

再次假设3个任务（A、B 和C），但这次A 运行100s，而B 和C 运行10s。系统的平均周转时间是比较高的：

这个问题通常被称为护航效应（convoy effect），一些耗时较少的潜在资源消费者被排在重量级的资源消费者之后。

最短任务优先（SJF）

策略：先运行最短的任务，然后是次短的任务，如此下去

仅通过在A之前运行B 和C，SJF 将平均周转时间从降低到

事实上，考虑到所有工作同时到达的假设，可以证明SJF 确实是一个最优调度算法。

放宽另一个假设，现在假设工作可以随时到达，而不是同时到达，这导致了什么问题？

假设A在时到达，且需要运行。而B和C在到达，且各需要运行。用纯SJF：

可以看出，即使B 和C在A之后不久到达，它们仍然被迫等到A完成，从而遭遇同样的护航问题。平均周转时间为，即。

抢占式调度程序

在过去的批处理计算中，开发了一些非抢占式（non-preemptive）调度程序。这样的系统会将每项工作做完，再考虑是否运行新工作。几乎所有现代化的调度程序都是抢占式的（preemptive），非常愿意停止一个进程以运行另一个进程。特别是调度程序可以进行上下文切换，临时停止一个运行进程，并恢复（或启动）另一个进程。

最短完成时间优先（STCF）

向SJF 添加抢占，称为最短完成时间优先（Shortest Time-to-Completion First，STCF）或抢占式最短作业优先（Preemptive Shortest JobFirst ，PSJF）调度程序：每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。

STCF 将抢占A 并运行B 和C以完成。只有在它们完成后，才能调度A 的剩余时间：

如果知道任务长度，而且任务只使用CPU，而唯一的衡量是周转时间，STCF将是一个很好的策略。对于许多早期批处理系统，这些类型的调度算法有一定的意义。然而，引入分时系统改变了这一切。

现在，用户将会坐在终端前面，同时也要求系统的交互性好，响应时间度量标准非常重要。STCF 和相关方法在响应时间上并不是很好。例如，如果3 个工作同时到达，第三个工作必须等待前两个工作全部运行后才能运行。这种方法虽然有很好的周转时间，但对于响应时间和交互性是相当糟糕的。如何构建对响应时间敏感的调度程序？

轮转（Round-Robin，RR）

轮转基本思想很简单：RR 在一个时间片（time slice，有时称为调度量子，scheduling quantum）内运行一个工作，然后切换到运行队列中的下一个任务，而不是运行一个任务直到结束。它反复执行，直到所有任务完成。注：时间片长度必须是时钟中断周期的倍数。如果时钟中断是每10ms中断一次，则时间片可以是10ms、20ms 或10ms的任何其他倍数。

假设任务A、B 和C 在系统中同时到达，并且它们都希望运行5s：

RR 的平均响应时间是：；SJF 算法平均响应时间是：。

时间片长度对于RR是至关重要的，越短，RR 在响应时间上表现越好。然而，时间片太短是有问题的：突然上下文切换的成本将影响整体性能。因此，系统设计者需要权衡时间片的长度，使其足够长，以便摊销（amortize）上下文切换成本，而又不会使系统不及时响应。

摊销可以减少成本 当系统某些操作有固定成本时，通常会使用摊销技术（amortization）。通过减少成本的频度（即执行较少次的操作），系统的总成本就会降低。例如，如果时间片设置为10ms，并且上下文切换时间为1ms，那么浪费大约10%的时间用于上下文切换。如果要摊销这个成本，可以把时间片增加到100ms。在这种情况下，不到1%的时间用于上下文切换，因此时间片带来的成本就被摊销了。

上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。切换到另一个工作会导致此状态被刷新，且与当前运行的作业相关的新状态被引入，这可能导致显著的性能成本。

如果响应时间是我们的唯一指标，那么带有合理时间片的RR，就会是非常好的调度程序，但如果周转时间是我们的指标，那么RR 是最糟糕的策略之一。

更一般地说，任何公平（fair）的政策（如RR），即在小规模的时间内将CPU 均匀分配到活动进程之间，在周转时间这类指标上表现不佳。事实上，这是固有的权衡：如果你愿意不公平，可以运行较短的工作直到完成，但是要以响应时间为代价。如果重视公平性，则响应时间会较短，但会以周转时间为代价。这种权衡在系统中很常见。

结合I/O

如有可能，重叠（overlap）操作可以最大限度地提高系统的利用率

调度程序显然要在工作发起I/O 请求时做出决定，因为当前正在运行的作业在I/O 期间不会使用CPU，它被阻塞等待I/O完成。如果将I/O 发送到硬盘驱动器，则进程可能会被阻塞几毫秒或更长时间，具体取决于驱动器当前的I/O 负载。因此，这时调度程序应该在CPU上安排另一项工作。

假设有两项工作A 和B，每项工作需要50ms 的CPU时间。但是，有一个明显的区别：A 运行10ms，然后发出I/O 请求（假设I/O 每个都需要10ms），而B只是使用CPU 50ms，不执行I/O。调度程序先运行A，然后运行B。

假设构建STCF 调度程序，这样的调度程序应该如何考虑到这样的事实，即A分解成5个10ms 子工作，而B仅仅是单个50ms CPU 需求？显然，仅仅运行一个工作，然后运行另一个工作，而不考虑如何考虑I/O 是没有意义的。

一种常见的方法是将A 的每个10ms 的子工作视为一项独立的工作。因此，当系统启动时，它的选择是调度10ms 的A，还是50ms 的B。对于STCF，选择是明确的：选择较短的一个，在这种情况下是A。然后，A 的工作已完成，只剩下B，并开始运行。然后提交A的一个新子工作，它抢占B 并运行10ms。这样做可以实现重叠（overlap），一个进程在等待另一个进程的I/O 完成时使用CPU，系统因此得到更好的利用

多级反馈队列（Multi-level Feedback Queue，MLFQ）

多级反馈队列在没有关于任务时间的先验知识的情况下，同时要降低响应时间和周转时间。

1962 年，Corbato 首次提出多级反馈队列，应用于兼容时分共享系统（CTSS）。Corbato 因在CTSS 中的贡献和后来在Multics 中的贡献，获得了ACM 颁发的图灵奖（Turing Award）。该调度程序经过多年的一系列优化，出现在许多现代操作系统中。

基本规则

MLFQ 中有许多独立的队列（queue），每个队列有不同的优先级（priority level）。任何时刻，一个工作只能存在于一个队列中。MLFQ 总是优先执行较高优先级的工作（即在较高级队列中的工作）。当然，每个队列中可能会有多个工作，因此具有同样的优先级。在这种情况下，就对这些工作采用轮转调度。

MLFQ 调度策略的关键在于如何设置优先级：如果一个工作不断放弃CPU 去等待键盘输入，这是交互型进程的可能行为，MLFQ 因此会让它保持高优先级。如果一个工作长时间地占用CPU，MLFQ 会降低其优先级。通过这种方式，MLFQ 在进程运行过程中学习其行为，从而利用工作的历史来预测它未来的行为。

规则1：如果A 的优先级 > B 的优先级，运行A（不运行B）

规则2：如果A 的优先级 = B 的优先级，轮转运行A 和B

规则3：工作进入系统时，放在最高优先级（最上层队列）

规则4：工作用完整个时间片后，降低其优先级；如果工作在其时间片以内主动释放CPU，则优先级不变

改进：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级

规则5：经过一段时间S，就将系统中所有工作重新加入最高优先级队列。

MLFQ 有趣的原因是：它不需要对工作的运行方式有先验知识，而是通过观察工作的运行来给出对应的优先级。通过这种方式，MLFQ 可以同时满足各种工作的需求：对于短时间运行的交互型工作，获得类似于SJF/STCF 的很好的全局性能，同时对长时间运行的CPU 密集型负载也可以公平地、不断地稳步向前。因此，许多系统使用某种类型的MLFQ作为自己的基础调度程序，包括类BSD UNIX 系统、Solaris以及Windows NT 和其后的Window系列操作系统。

单个长工作

该工作首先进入最高优先级Q2。执行一个10ms 的时间片后，调度程序将工作的优先级减1，进入Q1。在Q1 执行一个时间片后，最终降低优先级进入系统的最低优先级Q0

一个短工作

有两个工作：A是一个长时间运行的CPU 密集型工作，B 是一个运行时间很短的交互型工作。假设A 执行一段时间后B 到达。会发生什么呢？对B 来说，MLFQ 会近似于SJF 吗？

A（用黑色表示）在最低优先级队列执行（长时间运行的CPU 密集型工作都这样）。B（用灰色表示）在时间时到达，并被加入最高优先级队列。由于它的运行时间很短（只有20ms），经过两个时间片，在被移入最低优先级队列之前，B 执行完毕。然后A 继续运行（在低优先级）。

如果有I/O呢

如果进程在时间片用完之前主动放弃CPU，则保持它的优先级不变。这条规则的意图很简单：假设交互型工作中有大量的I/O 操作（比如等待用户的键盘或鼠标输入），它会在时间片用完之前放弃CPU。在这种情况下，只是保持它的优先级不变。

交互型工作B（用灰色表示）每执行1ms便需要进行I/O操作，它与长时间运行的工作A（用黑色表示）竞争CPU

基本的MLFQ的一些问题

首先，会有饥饿（starvation）问题。如果系统有“太多”交互型工作，就会不断占用CPU，导致长工作永远无法得到CPU（它们饿死了）。其次，一个程序可能在不同时间表现不同。一个计算密集的进程可能在某段时间表现为一个交互型的进程。用基本的方法，它不会享受系统中其他交互型工作的待遇

如何避免饥饿问题，让CPU 密集型工作也能取得一些进展（即使不多）？一个简单的思路是周期性地提升（boost）所有工作的优先级

左边没有优先级提升，长工作在两个短工作到达后被饿死。右边每50ms 就有一次优先级提升，因此至少保证长工作会有一些进展，每过50ms就被提升到最高优先级，从而定期获得执行。

S的值应该如何设置？

如果S设置得太高，长工作会饥饿；如果设置得太低，交互型工作又得不到合适的CPU 时间比例。

最后，聪明的用户会重写程序，愚弄调度程序（game the scheduler）。愚弄调度程序指的是用一些卑鄙的手段欺骗调度程序，让它给你远超公平的资源。基本算法对如下的攻击束手无策：进程在时间片用完之前，调用一个I/O 操作（比如访问一个无关的文件），从而主动释放CPU。如此便可以保持在高优先级，占用更多的CPU 时间。做得好时（比如，每运行99%的时间片时间就主动放弃一次CPU），工作可以几乎独占CPU。

如何阻止调度程序被愚弄？为MLFQ 的每层队列提供更完善的CPU 计时方式

调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次用完的，还是拆成很多次用完。

MLFQ 调优及其他问题

关于MLFQ 调度算法还有一些问题。其中一个大问题是如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？

大多数的MLFQ 变体都支持不同队列可变的时间片长度。高优先级队列通常只有较短的时间片（比如10ms 或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是CPU 密集型工作，配置更长的时间片会取得更好的效果。

Solaris 的MLFQ 实现（时分调度类TS）很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级。管理员可以通过这些表，让调度程序的行为方式不同。该表默认有60 层队列，时间片长度从20ms（最高优先级），到几百ms（最低优先级），每一秒左右提升一次进程的优先级。

其他一些MLFQ 调度程序没用表，甚至没用规则，有些采用数学公式来调整优先级。例如，FreeBSD 调度程序（4.3 版本），会基于当前进程使用了多少CPU，通过公式计算某个工作的当前优先级。另外，使用量会随时间衰减，这提供了期望的优先级提升，但与这里描述方式不同。最后，许多调度程序有一些我们没有提到的特征。例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议（advice），比如通过命令行工具nice，可以增加或降低工作的优先级（稍微），从而增加或降低它在某个时刻运行的机会。

比例份额（proportional-share）

比例份额算法基于一个简单的想法：调度程序的最终目标，是确保每个工作获得一定比例的CPU 时间，而不是优化周转时间和响应时间。

比例份额调度程序有一个非常优秀的现代例子，由Waldspurger 和Weihl 发现，名为彩票调度（lottery scheduling）。基本思想很简单：每隔一段时间，都会举行一次彩票抽奖，以确定接下来应该运行哪个进程。越是应该频繁运行的进程，越是应该拥有更多地赢得彩票的机会。

基本概念：彩票数表示份额

彩票调度背后是一个非常基本的概念：彩票数（ticket）代表了进程（或用户或其他）占有某个资源的份额。一个进程拥有的彩票数占总彩票数的百分比，就是它占有资源的份额。

通过不断定时地（比如，每个时间片）抽取彩票，彩票调度从概率上获得这种份额比例。抽取彩票的过程很简单：调度程序知道总共的彩票数（假设有100 张）。调度程序抽取中奖彩票，这是从0 和99之间的一个数，拥有这个数对应的彩票的进程中奖。假设进程A 拥有0 到74 共75 张彩票，进程B 拥有75 到99 的25 张，中奖的彩票就决定了运行A 或B。调度程序然后加载中奖进程的状态，并运行它。

彩票调度最精彩的地方在于利用了随机性（randomness）。当需要做出决定时，采用随机的方式常常是既可靠又简单的选择。

随机方法相对于传统的决策方式，至少有3 点优势。

随机方法常常可以避免奇怪的边角情况，较传统的算法可能在处理这些情况时遇到麻烦。例如LRU 替换策略。虽然LRU 通常是很好的替换算法，但在有重复序列的负载时表现非常差。但随机方法就没有这种最差情况。

随机方法很轻量，几乎不需要记录任何状态。在传统的公平份额调度算法中，记录每个进程已经获得了多少的CPU 时间，需要对每个进程计时，这必须在每次运行结束后更新。而采用随机方式后每个进程只需要非常少的状态（即每个进程拥有的彩票号码）。

随机方法很快。只要能很快地产生随机数，做出决策就很快。因此，对运行速度要求高的场景非常适用。当然，越是需要快的计算速度，随机就会越倾向于伪随机。

彩票机制

彩票调度还提供了一些机制，以不同且有效的方式来调度彩票。一种方式是利用彩票货币（ticket currency）的概念。这种方式允许拥有一组彩票的用户以他们喜欢的某种货币，将彩票分给自己的不同工作。之后操作系统再自动将这种货币兑换为正确的全局彩票。比如，假设用户A 和用户B 每人拥有100 张彩票。用户A 有两个工作A1 和A2，他以自己的货币，给每个工作500 张彩票（共1000 张）。用户B 只运行一个工作，给它10 张彩票（总共10 张）。操作系统将进行兑换，将A1 和A2 拥有的A 的货币500 张，兑换成全局货币50 张。类似地，兑换给B1 的10 张彩票兑换成100 张。然后会对全局彩票货币（共200张）举行抽奖，决定哪个工作运行。

另一个有用的机制是彩票转让（ticket transfer）。通过转让，一个进程可以临时将自己的彩票交给另一个进程。这种机制在客户端/服务端交互的场景中尤其有用，在这种场景中，客户端进程向服务端发送消息，请求其按自己的需求执行工作，为了加速服务端的执行，客户端可以将自己的彩票转让给服务端，从而尽可能加速服务端执行自己请求的速度。服务端执行结束后会将这部分彩票归还给客户端。

最后，彩票通胀（ticket inflation）有时也很有用。利用通胀，一个进程可以临时提升或降低自己拥有的彩票数量。当然在竞争环境中，进程之间互相不信任，这种机制就没什么意义。一个贪婪的进程可能给自己非常多的彩票，从而接管机器。但是，通胀可以用于进程之间相互信任的环境。在这种情况下，如果一个进程知道它需要更多CPU 时间，就可以增加自己的彩票，从而将自己的需求告知操作系统，这一切不需要与任何其他进程通信。

实现

假定用列表记录A、B、C 这3 个进程，每个进程有一定数量的彩票。

在做出调度决策之前，首先要从彩票总数400 中选择一个随机数（中奖号码）。假设选择了300。然后，遍历链表，用一个简单的计数器帮助我们找到中奖者：

如何分配彩票

这是一个非常棘手的问题，系统的运行严重依赖于彩票的分配。假设用户自己知道如何分配，因此可以给每个用户一定量的彩票，由用户按照需要自主分配给自己的工作。然而这种方案似乎什么也没有解决——还是没有给出具体的分配策略。因此对于给定的一组工作，彩票分配的问题依然没有最佳答案。

步长调度（stride scheduling）

虽然随机方式可以使得调度程序的实现简单（且大致正确），但偶尔并不能产生正确的比例，尤其在工作运行时间很短的情况下。由于这个原因，Waldspurger 提出了步长调度，一个确定性的公平分配算法。

系统中的每个工作都有自己的步长，这个值与票数值成反比。在上面的例子中，A、B、C 这3 个工作的票数分别是100、50 和250，我们通过用一个大数分别除以他们的票数来获得每个进程的步长。比如用10000 除以这些票数值，得到了3 个进程的步长分别为100、200 和40。称这个值为每个进程的步长（stride）。每次进程运行后，我们会让它的计数器 [称为行程（pass）值] 增加它的步长，记录它的总体进展。

之后，调度程序使用进程的步长及行程值来确定调度哪个进程。基本思路很简单：当需要进行调度时，选择目前拥有最小行程值的进程，并且在运行之后将该进程的行程值增加一个步长。下面是Waldspurger给出的伪代码：

3 个进程（A、B、C）的步长值分别为100、200 和40，初始行程值都为0。因此，最初，所有进程都可能被选择执行。假设选择A（任意的，所有具有同样低的行程值的进程，都可能被选中）。A 执行一个时间片后，更新它的行程值为100。然后运行B，并更新其行程值为200。最后执行C，C 的行程值变为40。这时，算法选择最小的行程值，是C，执行并增加为80（C 的步长是40）。然后C 再次运行（依然行程值最小），行程值增加到120。现在运行A，更新它的行程值为200（现在与B 相同）。然后C 再次连续运行两次，行程值也变为200。此时，所有行程值再次相等，这个过程会无限地重复下去。

C 运行了5 次、A 运行了2 次，B 一次，正好是票数的比例——200、100 和 50。彩票调度算法只能一段时间后，在概率上实现比例，而步长调度算法可以在每个调度周期后做到完全正确。

彩票调度有一个步长调度没有的优势——不需要全局状态。假如一个新的进程在上面的步长调度执行过程中加入系统，应该怎么设置它的行程值呢？设置成0 吗？这样的话，它就独占CPU 了。而彩票调度算法不需要对每个进程记录全局状态，只需要用新进程的票数更新全局的总票数就可以了。因此彩票调度算法能够更合理地处理新加入的进程。

多处理器调度

操作系统应该如何在多CPU 上调度工作？会遇到什么新问题？已有的技术依旧适用吗？是否需要新的思路？

多处理器与单CPU 之间的基本区别的核心在于对硬件缓存（cache）的使用，以及多处理器之间共享数据的方式。

在单CPU 系统中，存在多级的硬件缓存（hardware cache），一般来说会让处理器更快地执行程序。缓存是很小但很快的存储设备，通常拥有内存中最热的数据的备份。相比之下，内存很大且拥有所有的数据，但访问速度较慢。通过将频繁访问的数据放在缓存中，系统似乎拥有又大又快的内存。

假设一个程序需要从内存中加载指令并读取一个值，系统只有一个CPU，拥有较小的缓存（如64KB）和较大的内存。

程序第一次读取数据时，数据在内存中，因此需要花费较长的时间（可能数十或数百纳秒）。处理器判断该数据很可能会被再次使用，因此将其放入CPU 缓存中。如果之后程序再次需要使用同样的数据，CPU 会先查找缓存。因为在缓存中找到了数据，所以取数据快得多（比如几纳秒），程序也就运行更快。

缓存是基于局部性（locality）的概念，局部性有两种，即时间局部性和空间局部性。时间局部性是指当一个数据被访问后，它很有可能会在不久的将来被再次访问，比如循环代码中的数据或指令本身。而空间局部性指的是，当程序访问地址为x 的数据时，很有可能会紧接着访问x 周围的数据，比如遍历数组或指令的顺序执行。由于这两种局部性存在于大多数的程序中，硬件系统可以很好地预测哪些数据可以放入缓存，从而运行得很好。

如果系统有多个处理器，并共享同一个内存，会怎样呢？

多CPU 的情况下缓存要复杂得多。例如，假设一个运行在CPU 1 上的程序从内存地址A 读取数据。由于不在CPU 1 的缓存中，所以系统直接访问内存，得到值D。程序然后修改了地址A 处的值，只是将它的缓存更新为新值D'。将数据写回内存比较慢，因此系统（通常）会稍后再做。假设这时操作系统中断了该程序的运行，并将其交给CPU 2，重新读取地址A 的数据，由于CPU 2 的缓存中并没有该数据，所以会直接从内存中读取，得到了旧值D，而不是正确的值D'。哎呀！

这一普遍的问题称为缓存一致性（cache coherence）问题。

硬件提供了这个问题的基本解决方案：通过监控内存访问，硬件可以保证获得正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探。每个缓存都通过监听链接所有缓存和内存的总线，来发现内存访问。如果CPU 发现对它放在缓存中的数据的更新，会作废（invalidate）本地副本（从缓存中移除），或更新（update）它（修改为新值）。回写缓存，如上面提到的，让事情更复杂（由于对内存的写入稍后才会看到），你可以想想基本方案如何工作。

既然缓存已经做了这么多工作来提供一致性，应用程序（或操作系统）还需要关心共享数据的访问吗？依然需要！

跨CPU 访问（尤其是写入）共享数据或数据结构时，需要使用互斥原语（比如锁），才能保证正确性（其他方法，如使用无锁（lock-free）数据结构，很复杂，偶尔才使用。。例如，假设多CPU 并发访问一个共享队列。如果没有锁，即使有底层一致性协议，并发地从队列增加或删除元素，依然不会得到预期结果。需要用锁来保证数据结构状态更新的原子性。

在设计多处理器调度时遇到的最后一个问题，是所谓的缓存亲和度（cache affinity）。这个概念很简单：一个进程在某个CPU 上运行时，会在该CPU 的缓存中维护许多状态。下次该进程在相同CPU 上运行时，由于缓存中的数据而执行得更快。相反，在不同的CPU 上执行，会由于需要重新加载数据而很慢（好在硬件保证的缓存一致性可以保证正确执行）。因此多处理器调度应该考虑到这种缓存亲和性，并尽可能将进程保持在同一个CPU 上。

单队列调度（Single Queue Multiprocessor Scheduling，SQMS）

何设计一个多处理器系统的调度程序。最基本的方式是简单地复用单处理器调度的基本架构，将所有需要调度的工作放入一个单独的队列中，称之为单队列多处理器调度。这个方法最大的优点是简单。它不需要太多修改，就可以将原有的策略用于多个CPU，选择最适合的工作来运行（例如，如果有两个CPU，它可能选择两个最合适的工作）。

然而，SQMS 有几个明显的短板。第一个是缺乏可扩展性（scalability）。为了保证在多CPU 上正常运行，调度程序的开发者需要在代码中通过加锁（locking）来保证原子性，如上所述。在SQMS 访问单个队列时（如寻找下一个运行的工作），锁确保得到正确的结果。

然而，锁可能带来巨大的性能损失，尤其是随着系统中的CPU 数增加时。随着这种单个锁的争用增加，系统花费了越来越多的时间在锁的开销上，较少的时间用于系统应该完成的工作（哪天在这里加上真正的测量数据就好了）。

SQMS 的第二个主要问题是缓存亲和性。比如，假设我们有5个工作（A、B、C、D、E）和4 个处理器。调度队列如下：

一段时间后，假设每个工作依次执行一个时间片，然后选择另一个工作，下面是每个CPU 可能的调度序列：

由于每个CPU 都简单地从全局共享的队列中选取下一个工作执行，因此每个工作都不断在不同CPU 之间转移，这与缓存亲和的目标背道而驰。

为了解决这个问题，大多数SQMS 调度程序都引入了一些亲和度机制，尽可能让进程在同一个CPU 上运行。保持一些工作的亲和度的同时，可能需要牺牲其他工作的亲和度来实现负载均衡。例如，针对同样的5个工作的调度如下：

这种调度中，A、B、C、D 这4 个工作都保持在同一个CPU 上，只有工作E 不断地来回迁移（migrating），从而尽可能多地获得缓存亲和度。为了公平起见，之后我们可以选择不同的工作来迁移。但实现这种策略可能很复杂。

SQMS 调度方式有优势也有不足。优势是能够从单CPU 调度程序很简单地发展而来，根据定义，它只有一个队列。然而，它的扩展性不好（由于同步开销有限），并且不能很好地保证缓存亲和度。

多队列调度（Multi-Queue Multiprocessor Scheduling，MQMS）

正是由于单队列调度程序的这些问题，有些系统使用了多队列的方案，比如每个CPU一个队列，称之为多队列多处理器调度。

在MQMS 中，基本调度框架包含多个调度队列，每个队列可以使用不同的调度规则，比如轮转或其他任何可能的算法。当一个工作进入系统后，系统会依照一些启发性规则（如随机或选择较空的队列）将其放入某个调度队列。这样一来，每个CPU 调度之间相互独立，就避免了单队列的方式中由于数据共享及同步带来的问题。

例如，假设系统中有两个CPU（CPU 0 和CPU 1）。这时一些工作进入系统：A、B、C和D。由于每个CPU 都有自己的调度队列，操作系统需要决定每个工作放入哪个队列。可能像下面这样做：

根据不同队列的调度策略，每个CPU 从两个工作中选择，决定谁将运行。例如，利用轮转，调度结果可能如下所示：

MQMS 比SQMS 有明显的优势，它天生更具有可扩展性。队列的数量会随着CPU 的增加而增加，因此锁和缓存争用的开销不是大问题。此外，MQMS 天生具有良好的缓存亲和度。所有工作都保持在固定的CPU 上，因而可以很好地利用缓存数据。

但是，有一个新问题（这在多队列的方法中是根本的），即负载不均（load imbalance）。假定和上面设定一样（4 个工作，2 个CPU），但假设一个工作（如C）这时执行完毕。现在调度队列如下：

如果对系统中每个队列都执行轮转调度策略，会获得如下调度结果：

从图中可以看出，A 获得了B 和D 两倍的CPU 时间，这不是期望的结果。更糟的是，假设A 和C 都执行完毕，系统中只有B 和D。调度队列看起来如下：

因此CPU 使用时间线看起来令人难过：

多队列多处理器调度程序应该如何处理负载不均问题，从而更好地实现预期的调度目标？

最明显的答案是让工作移动，这种技术我们称为迁移（migration）。通过工作的跨CPU迁移，可以真正实现负载均衡。

来看两个例子就更清楚了。同样，有一个CPU 空闲，另一个CPU 有一些工作。

在这种情况下，期望的迁移很容易理解：操作系统应该将B 或D迁移到CPU0。这次工作迁移导致负载均衡，皆大欢喜。

更棘手的情况是较早一些的例子，A 独自留在CPU 0 上，B 和D 在CPU 1 上交替运行

在这种情况下，单次迁移并不能解决问题。应该怎么做呢？答案是不断地迁移一个或多个工作。一种可能的解决方案是不断切换工作，如下面的时间线所示。可以看到，开始的时候A 独享CPU 0，B 和D 在CPU 1。一些时间片后，B 迁移到CPU 0 与A 竞争，D 则独享CPU 1 一段时间。这样就实现了负载均衡。

当然，还有其他不同的迁移模式。但现在是最棘手的部分：系统如何决定发起这样的迁移？

一个基本的方法是采用一种技术，名为工作窃取（work stealing）。通过这种方法，工作量较少的（源）队列不定期地“偷看”其他（目标）队列是不是比自己的工作多。如果目标队列比源队列（显著地）更满，就从目标队列“窃取”一个或多个工作，实现负载均衡。

当然，这种方法也有让人抓狂的地方——如果太频繁地检查其他队列，就会带来较高的开销，可扩展性不好，而这是多队列调度最初的全部目标！相反，如果检查间隔太长，又可能会带来严重的负载不均。找到合适的阈值仍然是黑魔法，这在系统策略设计中很常见。

Linux 多处理器调度

有趣的是，在构建多处理器调度程序方面，Linux 社区一直没有达成共识。一直以来，存在3 种不同的调度程序：O(1)调度程序、完全公平调度程序（CFS）以及BF 调度程序（BFS）。

O(1) CFS 采用多队列，而BFS 采用单队列，这说明两种方法都可以成功。当然它们之间还有很多不同的细节。例如，O(1)调度程序是基于优先级的（类似于MLFQ），随时间推移改变进程的优先级，然后调度最高优先级进程，来实现各种调度目标。交互性得到了特别关注。与之不同，CFS 是确定的比例调度方法（类似步长调度）。BFS作为三个算法中唯一采用单队列的算法，也基于比例调度，但采用了更复杂的方案，称为最早最合适虚拟截止时间优先算法（EEVEF）。

策略	内容	演化	缺点
FIFO	先到达的任务先执行	最符合直觉的策略	先到达的长任务让后到达的短任务饿死
SJF (1954)	最短的任务先执行	比FIFO优化了周转时间	任务会随时到达，而在长任务执行时到达的短任务饿死
STCF	能够以最短完成时间可以抢占其他任务	比SJF增加了抢占机制	无法确定任务的完成时间
Round Robin	所有进程轮番使用时间片	优化了响应时间	并不是所有的程序都能用完整个时间片，例如IO密集任务
（重叠式）RR	需要IO的任务让出时间片并在完成前不参与调度	比RR多了对IO考虑	周转时间差于SJF（但总体来说是有效的）
MLFQ (1962)	ㅤ	在没有任务长短的先验知识下，同时优化了周转时间和响应时间	稍显复杂（但被Windows、MacOS和Unix系统采用）
Lottery (1994)	给每个进程分发一定量的彩票，每次调度时随机抽出一个号码，被抽中的进程获得CPU	在给定优先级的环境下优化了公平性	只能在互信环境中使用，需要提前给定彩票数
Stride (1995)	给每个进程分发一定量的彩票，按彩票数的倒数计算步长，程序被调度一次则累计一次步长值，每次调度已经走过步长值最小的那一个	在给定优先级的环境下到达绝对公平，比Lottery优化了确定性	只能在互信环境中使用，需要提前给定彩票数
CFS (2007)	ㅤ	在给定优先级的情况下保持绝对公平，比Stride拥有更多细节	稍显复杂（提出后迅速被Linux系统采用）