系统调度(一)

任务调度

在讲完多线程并发之后，我们终于可以进入进程管理的最后一部分内容，任务调度。一些参考书上把这一部分内容叫做进程调度，我们之所以叫它任务调度，是因为在很多系统中、被调度的单位并不一定是进程。上一章开头我们已经提到，Linux 系统中所有线程都是内核级线程，因此一个线程可以作为一个相对独立的单位被调度器调度。我们将一个被调度的单位称为 任务（task） ，这一章中我们就来认识一下任务调度的常用算法。

在开始探讨具体的算法以前，我们先来明确一下任务调度发生的情境——上下文切换。上下文切换是从一个任务向下一个任务切换的过程，它有可能由两种情形触发。一种情形是任务没有运行完，但主动让出了处理器使用权；依赖这种形式触发上下文切换的系统是 合作式多任务系统（cooperative multitasking） 。另一种情形是操作系统在任务运行一段时间后向进程发出中断，然后在中断处理器中选择下一个运行的任务、切换至该进程。这种系统叫做 抢占式多任务系统（preemptive multitasking） 。我们所谈到的任务调度是基于后一种多任务系统，即操作系统必须拥有抢占处理器的能力。

在抢占式多任务系统中，每个任务会被给予一段时间，我们将这段时间称为 时间片（time slice） 。时间片耗尽后，系统会引发 计时器中断（timer interrupt） ，使得现在正在运行的任务被切换至内核态，在系统空间中运行计时器中断的处理函数，我们所关心的任务调度算法就发生在计时器中断的处理函数中。在这个处理函数中，系统会根据任务调度算法、从就绪队列里选择下一个运行的任务（有可能仍然是现在的这个任务），然后在处理上载入这个任务的处理器状态、在存储管理部件里载入这个任务对应的页表的起始地址、开始运行。

为了使用户获得流畅的体验，我们希望一个好的任务调度算法能够让所有任务在一段时间内都产生一定的进度、不让任何任务等待太久、又不浪费太多时间在算法本身的计算中。为了能有效衡量一个算法是否符合上面的标准，我们接下来要介绍几个用来衡量任务调度算法表现的量。

吞吐率（throughput） ，吞吐率指的是单位时间内处理器处理的任务数量。如果我们在一段时间内处理了很多所需时间较短的任务，那么我们的吞吐率就会比同样长的一段时间内只处理了较长的任务高许多。

系统的吞吐率如果较高，则说明单位时间内完成的任务数量高，但这并不一定代表每个任务都产生了进度。比如，如果我们有 4 个任务，各需要100，200， 700， 10000 毫秒完成，然后我们在第一秒钟完成了前三个任务，那么我们的吞吐率（在单位时间为 1 秒时）就是 3，但最后一个任务完全没有产生进度。如果有用户此时正在等待第四个任务产生进度，则该用户会观察到第四个任务产生了明显的停滞。

为了能更准确地衡量各个任务的进度，我们还应该引入一个能够表示一个任务反应快慢的量和一个表示任务从提交给系统到完成所需时间的量，这就是 响应时间（response time） 和 周转时间（turnaround time） 。响应时间指的是一个任务从提交开始到处理器第一次反馈过去的时间，周转时间指的是一个任务从提交到完成所需的总时间，也就是等待时间与实际运行时间之和。我们希望一个任务的响应时间与周转时间都比较低，这样任务反应会比较快，且能够快速完成。

我们可以进一步定义一个量叫做带权周转时间，它是一个任务周转时间与实际运行时间的比值。由于排队时间不为 0，带权周转时间永远大于1。一个系统中所有任务的平均带权周转时间越接近 1，这个系统的效率就越高。

除了上述用于衡量任务运行快慢的量以外，操作系统还需要保证资源分配的公平性和资源较高的使用率。

绝对的公平性指的是在一段无限小的时间区间 Δt 里，n 个优先级相同的线程应该各获得了 Δt / n 的处理器时间，但这一点在一个处理器上实际上是做不到的，因此我们只能要求在一段我们规定长度的时间里，所有任务都能分得它们应有的处理器时间的长度，没有一个任务能持续地抢占处理器。

资源使用率高指的是处理器工作时间与其工作时间和空闲时间之和的比例应该较高，也就是说处理器不应该花时间等待 I/O 操作的完成，而应该在需要等待 I/O 时完成其它有意义的工作。

最后，一个好的调度算法还应该能够保持一个互动性高的任务一直能得到响应。比如，在一个文本编辑器中，我们不希望编辑器在输入文字 1 秒后才显示出刚输入的文字，因此我们需要保证，等待 I/O 的任务在获得 I/O 后能马上运行。我们将这种 I/O 操作所占比例很大的任务称为 I/O 密集型（I/O bound） ；我们将绝大多数时间都在利用处理器进行计算的任务称为 计算密集型（CPU bound） ，在后几节有关各种调度算法的讨论中，我们会经常用到这两个术语代表具有着两种特征的任务。

学完了一个理想调度算法应符合的标准后，我们就可以开始学习各种调度算法了。我们将在学习具体的算法的过程中，在不同的情境下用这些标准来衡量调度算法。你很快就会意识到，所有算法都有其最优情境和最差情境。在选择算法时，我们也要根据不同的情境来选择合适的算法。

SJF 与 SRTF

还记得在讲页面替换算法时，我们讲的第一个算法就是最佳页面替换算法；虽然最佳页面替换算法要求我们能够预知未来，但它可以被证明是在同一页面使用序列下缺页中断率最低的算法。这一节中我们要讲的两个算法也是这样——它们实际上很难被实现，但是它们能够保证最短的平均周转时间，因此我们在学习其它可以实现的算法时就能以这两个算法为基准衡量其它算法的表现。

我们要介绍的第一个算法是 最短作业优先算法（Shortest Job First，SJF） 。顾名思义，它永远会运行最短的那个任务。如果 A，B，C 三个长度分别为 4，2，8 的任务在同一时刻进入系统，那么系统就会以 B，A，C 的顺序运行这三个任务。

最短作业优先算法有一个坏处，就是它不是抢占式的，也就是说如果上面的 A，B，C 以 C，A，B 的顺序进入系统，那么即使 C 和 A 的运行长度大于 B，这个算法还是会选择先进入系统的 C 来运行；如果 B 在 A 开始运行后才进入系统，那么 B 也需要等待 A 完成后才能继续运行。为了解决这个问题，我们需要对最短作业优先算法做一个小改动。
我们希望在一个运行时间比现在运行的任务的剩余时间短的任务进入系统时，我们可以先运行这个比较短的任务，然后再继续运行当前任务，这就是 最短剩余时间优先算法（Shortest Remaining Time First，SRTF） ，又叫 抢占式最短作业优先算法（preemptive SJF） 。同样使用上面的例子，假设 A，B，C 以下面的顺序进入系统：

从上面的例子我们可以看出，最短剩余时间优先算法是优于非抢占式的最短作业优先算法的。因此，我们在谈到最短作业优先算法时指的一般都是抢占式最短作业优先算法（最短剩余时间优先算法）。接下来我们就来证明下面这个结论：对于同一个任务流，最短剩余时间优先算法可以使所有任务的平均周转时间达到最短。
我们可以将 SRTF 看成是一个动态的 SJF，它在每次有新任务进入系统时都重新运行 SJF。因此我们只要证明，对于一个固定的任务流（没有新任务加入的任务流）SJF 的平均周转时间是最短的，我们就可以证明 SRTF 对于一个有新任务加入的任务流的平均周转时间是最短的。（因为我们在每一个时间点上都做了最佳的选择，那么我们整体的选择也是最佳的）

下面我们就来证明 SJF 能够针对一个固定的任务流给出最低的平均周转时间。为了证明这个结论，我们先来证明一个辅助定理：穿插运行几个任务比连续运行几个任务所需时间更长。这个证明是很简单的，因为穿插运行的几个任务中后结束的任务的周转时间一定大于等于它之间结束的几个任务的运行时间与它的运行时间之和。因此为了减小周转时间，我们希望上面的值取等，这就相当于要求所有的任务都连续运行至结束再切换至下一个任务运行。

由于我们已经证明任务不应该穿插运行，我们就可以把每个任务的运行看做一个整体，只需考虑系统中任务运行的顺序。假设 ALT 算法产生的运行顺序下任务的平均周转时间低于 SJF 算法产生的运行顺序下任务的平均周转时间。设 \ t_d t
d
​
为两个算法第一次产生分歧的时间点，在这个时间点 ALT 选择了任务i，SJF 选择了任务j。因为 SJF 选择的作业运行时间都是最短的， i 的运行时间肯定不小于j。如果我们在 ALT 产生的运行顺序中将 i 与 j 对调，那么这对于 i 之前和 j 之后的任务的周转时间没有影响；对于 i 之后j 之前的任务，我们知道他们的周转时间都包含了等待 i 运行完毕的时间，但 j 的运行时间小于等于 i 的运行时间，因此交换后这些任务的周转时间不会增加，由此我们就证明了这样的交换不会导致平均周转时间增加。我们可以利用数学归纳法得出，我们可以交换 ALT 中任何与 SJF 不同的任务，使得 ALT 与 SJF 产生完全相同的顺序而不增加平均周转时间。因此，SJF 的平均周转时间与 ALT 相同，都是最短的。
从上面的证明中我们已经看出，SRTF 和 SJF 的优点就是它们能够缩短任务平均周转时间。但 SRTF 和 SJF 也有明显的缺点——在短任务不断进入系统的情况下，它们会导致运行时间长的任务不断等待，产生饥饿。下一节中我们可以看到，为了减少任务的等待时间、提高公平性，我们可以采用一些别的算法。

HRRF, FIFO 与 Round-Robin 调度算法

最短作业优先算法和最短剩余时间优先算法共同面临的一大问题，那就是在短任务不断进入系统时，长任务会不断等待。
我们要介绍的第一种算法是 SJF 的改进版，它叫做 最高响应比优先算法（Highest Response Ratio First，HRRF） 。这种算法与 SJF 相同，都是非抢占式的，且需要任务事先提交它估计的运行时间，系统会根据运行时间和任务进入系统后已经等待的时间计算出任务的响应比，其计算方法如下：

响应比 = （任务等待时间 + 任务预计运行时间）/ 任务预计运行时间
      =  1 + 任务等待时间 / 任务预计运行时间

从上面的公式中我们可以看出，由于任务预计运行时间不变，任务的响应比只取决于任务进入系统后等待的时间。**任务等待时间越高，其响应比也越高，那么这个任务就越优先。**每次一个任务放弃处理器的使用权或者离开系统时，系统就会从所有的等待任务中选取响应比最高的来运行。

我们可以看出，这种算法避免了 SJF 和 SRTF 导致长任务不断等待的问题。即使一个任务预计运行时间很长，在等待足够长时间后它还是会被运行。当然，它并不能避免 SJF 和 SRTF 的另一个问题，那就是一个任务很少能准确地预估自己的运行时间，何况一个希望抢占更多资源的任务可以上报给系统一个很短的运行时间、借此来抢占系统。我们希望使用一个不需要任务预估运行时间的算法，这就是我们接下来介绍的两种算法——先进先出算法与轮询调度算法

我们首先要介绍的是 先进先出算法（First in First Out，FIFO） ，它又被称为 先来先服务算法（First Come First Served，FCFS） 。它跟我们在页面替换算法里学习的先进先出算法类似，使先进入系统的任务先运行至结束，然后再使下一个进入系统的任务运行。这种算法不会使后进入系统的短任务耽误先进入系统的长任务，因此解决了 SJF 和 SRTF 的问题，但 FIFO 也有自己的问题。

如果一个长任务先进入系统，后面有很多短任务进入系统，那么这些短任务都需要等待长任务运行完之后才能运行，平均周转时间会变得很长；另一方面，如果一个任务的大部分时间都花在 I/O 操作上，那么 FIFO 这种非抢占式的算法会导致 CPU 长时间空闲，降低了资源利用率。

我们可以看到 FIFO 和 SJF、SRTF 一样都有公平性较差的问题，只不过 SJF 和 SRTF 偏向短任务，而 FIFO 偏向长任务。我们想要一个更公平的算法，使得不同的任务在一段时间内都能产生进度，这就是 轮转调度算法（Round-Robin，RR） 。

在 RR 中，我们会规定一个固定长度的时间片。处于就绪队列中的进程将按照他们进入就绪队列的顺序轮流获得一个时间片运行，当时间片耗尽时任务就会被中断、加入就绪队列的结尾，下一个任务开始运行。如果一个任务因为 I/O 操作或无法获取锁等原因被阻塞，那么即使它无法用完自己的时间片也会放弃处理器的使用权。

RR 与 SRTF 一样，都是抢占式算法，它的优点是对于计算密集型的任务分配资源较为公平，且不会产生饥饿。然而，I/O 密集型的任务在这种算法下会不断因 I/O 放弃处理器使用权，因此获取的资源较少。不仅如此，RR 算法的平均周转时间较长，这主要有两个原因——第一，原本只需要几个时间片就可以运行完的任务在 RR 中需要等待整个就绪队列的任务都运行完一遍以后才能获得一次时间片，因此等待时间很长；第二，每次时间片消耗完或任务主动让出处理器时都会出现上下文切换，而上下文切换的代价是很大的，因此如果时间片太小、浪费在上下文切换上的时间比例就会很大。由于上述这种原因，在某些情况下 RR 的平均周转时间可能比 FIFO 的平均周转时间更长。
假设 RR 的时间片长度为 2，下面我们给出了一个任务流，在这个任务流下，RR 的劣势就充分体现出来了：

可见在这种任务流下，RR 是非常不占优势的。

多级反馈队列调度算法

前几节中我们讲了 FIFO 和 RR 这两种比较基本的算法，它们各自都有最适宜（optimal）和最不适宜（pessimal）的任务流种类。为了避免某一种基本算法在一些不适宜使用该算法的任务流下表现很差，我们需要以这些基本算法为基石、设计一些更综合的算法。这一节中我们就来讲一个在很多系统中都得到应用的、比较综合的算法：多级反馈队列调度算法（Multi-Level Feedback Queue，MLFQ）
在 MFLQ 算法中，我们有 n 个队列，这n 个队列的优先级递减，其中前 n−1 个队列实行 RR 算法、时间片长度递增，最后一个队列使用 FIFO 算法。在多个队列中都含有等待的任务时，这个算法会选择优先级最高的队列优先运行。

在一个新任务进入系统时，它会进入优先级最高的队列。当一个任务在运行时耗尽了它的时间片时，它就会被移到优先级低一级的队列的末尾；反之，如果它因为等待 I/O 而主动放弃处理器使用权，那么它就会保持在原来的位置，或向上移动一个等级。如果它不断地耗尽它的时间片，那么它就会被移到最后一个先进先出的队列中。
一旦涉及到优先级，我们就必须考虑一个问题，那就是 优先级倒置（priority inversion） 。优先级倒置指的是当一个优先级低的线程持有了一个被优先级高的线程需要的锁时，优先级高的线程就会进入阻塞态，但这时优先级介于这两个线程之间的线程会先于锁的持有者运行，因此高优先级的线程可能需要无限等待下去。事实上，这个 bug 甚至影响了 1997 年登上火星的火星探路者飞船，尽管它并没有导致数据的丢失或机器的损坏。这更证明了学好这一部分知识的重要性。
为了避免这种情况，许多操作系统都使用了一种机制叫做 优先级捐赠（priority donation） 。优先级捐赠会在一个优先级高的线程需要获得一个优先级低的线程持有的锁时发生，这时优先级高的线程会将优先级低的线程的优先级暂时提高到和自己一样，使得这个优先级低的线程在没有新的优先级更高的线程进入系统时可以立即开始运行。当线程释放锁时，线程的优先级会重新回到原来的低优先级，这时处理器就会被抢占，等待锁的线程会获得锁并继续运行。

优先级捐赠的过程看起来简单，其实是很复杂的。比如，如果低优先级线程 1 持有锁 B，中优先级线程 2 持有锁 A，高优先级线程 3 试图获得 A 失败后将被阻塞，将自己的优先级捐赠给线程 2；线程 2 运行后试图获得 B 失败后也被阻塞，这时它就必须把线程 3 捐赠给它的优先级和它自己的优先级同时捐赠给线程 1，因为如果它只捐赠自己的优先级，那么线程 1 的优先级仍然不一定是最高的。 我们把这种循环式的捐赠叫做 recursive donation。

还有一种情况我们必须考虑，那就是在一个线程持有多个锁并释放其中一个的时候，我们应该把它的优先级降到什么程度呢？我们要避免剩下几个锁产生优先级倒置，就需要这个线程的优先级不低于任何一个等待它的线程的优先级，否则两个优先级之间就会出现能够抢先运行的线程。因此我们应该把它的优先级降到所有它持有的锁的等待者中的最高优先等级。我们甚至可能面临这样一种情况：线程释放的锁不是把这个线程的优先级提高到目前等级的线程所等待的锁，在这种情况下，线程的优先级就不会变化了。

虽然我们管这种提升优先级的方式叫捐赠，但更好的考虑方法应该是一种“暂时提拔”。捐赠会给人一种捐多少就要还多少的感觉，但实际上捐赠时线程优先级增加与它释放锁时优先级减少的值并不一定相等（在线程持有多个锁时很可能不相等）。

Linux 调度算法

== Linux 内核中用过的两种算法==
自 Linux 内核版本 2.4 开始使用的 Linux 的 \ \mathcal{O}(1) O(1) 算法就是一种特殊的 MFLQ 算法，但与 MFLQ 算法不同的是 \ \mathcal{O}(1) O(1) 算法下、越优先的任务获得的时间片也越长，而且它的运行时间是 \ \mathcal{O}(1) O(1)，也就是说无论系统中有多少个任务，它所需要的时间都是恒定的。

由于 Linux 中对实时任务做出了区分，最终任务优先级的范围是0 到 139，因此它有 \ 280 280 个队列， 140 个优先级每个对应两个队列，一个为 active（活跃）队列、一个为 expired（过期）队列。为了达到 O(1)，Linux 还在系统中保留了两个长度都为140 的位图（bitmap），一个代表140 个 active 队列哪些不为空，另一个代表 140 个 expired 队列哪些不为空。每次任务运行完毕，系统先查看 active 队列的位图，找到优先级最高的、不为空的 active 队列，取其第一个任务运行；如果所有 active 队列都为空，那么系统就交换 active 队列位图与 expired 队列位图的指针。由于 140 是一个常数，上面这些操作的运行时间在任何情况下都是常数，因此这个算法被称为 O(1) 算法。

下面是这个算法的示意图：

虽然这个算法在运行时间方面的优势明显，但它的缺点也很明显：正如一般的 MLFQ 算法一般，它会导致计算密集型任务的饥饿。而且，O(1) 算法在分配运行时间时给每个优先级的任务规定了一个绝对的运行时间长度，而这个长度是很难被决定的；适用于一个任务的运行时间长度不一定适用于另一个任务。而且我们希望当两个任务 nice 值的差相同时，它们的运行时间相差也是相同的，然而这样如果 nice 值为 19 的任务运行时间片长度为 5，nice 值为 18 的任务运行时间片长度为 10，那 nice 值为 0 的任务运行时间片长度就是 100，nice 值为 −1 的任务运行时间片长度是 105。这种差异明显是不合理的：

这种看似相同的运行时间片长度从比例上来讲相差是很多的。我们想要一个更加公平、且普遍适用于各种类型的任务的算法。
在本章的开头我们已经提到，在一个理想的公平算法中，假设现在有 N 个优先等级相同的任务，那么为了公平起见，在一段任意小的时间区间 \ Δt 里，他们应该各获得 Δt/N 的处理器时间来运行，但“任意小的时间区间”这个标准在处理器上是达不到的，而且切换太频繁会导致存储在高速缓存里的数据被频繁地无效化、降低了系统效率。

因此我们可以规定一个最小时间区间 T，将它称为 目标延迟（targeted latency） ，在这个区间内我们的分配是公平的。（之所以我们叫这个区间目标延迟，是因为这是我们可以接受的一个任务的最高延迟，由于一个任务在这段时间里一定可以获得它应得的运行时间，它一定能产生进度，因此不会产生比这个值更大的延迟）假如我们希望偏袒一些比较重要的任务，那么我们可以赋予每个任务 i 一个权重 wi，重要的任务权重高，这样任务 i 获得的处理器时间应该是总时间的
∑j wj/​wi。根据上面的标准，我们保证在任意一个时间区间 T 内，我们保证一个任务 i 一定可以获得 ∑jw j w i ⋅T 的运行时间。这就是 Linux 内核版本 2.6 开始使用的、取代了 O(1) 算法的 完全公平算法（Completely Fair Scheduler，CFS） 所使用的标准。

在 CFS 算法中，一个任务的权重 w 由它的 nice 值决定。假设 nice 的值为 n，那么 w= c1/c2
其中 c1和 c2 都是常数。我们可以看出来，随着 nice 的减小，权重会呈指数级增长。这种规定方法有一个好处，那就是当两个 nice 值的差保持不变时，无论两个任务的 nice 值得绝对值是多少，它们的运行时间比例相差都是一样的，你可以用数学知识自己证明一下。

这种计算方法有一个坏处就是当任务总数增加时每个任务分到的时间越来越小，而当小到一定地步时操作系统的时间精度就不能够再支持这种时间分割了。**Linux 系统支持的最小时间分割单位叫做最小粒度，这个最小粒度的值默认为1ms。**设最小粒度为 a，那么当 a⋅∑i. ​wi >T 时，系统就会出现一个目标延迟区间中一些任务没能运行的情况。这个问题可以通过一些较为繁复的方法解决，但 CFS 的设计者们故意没有采用这些方法，因为 CFS 就是针对任务总数不超过这个数值的系统设计的。

**在 CFS 算法下，每个任务都有一个对应的数据结构，其中存储了根据运行任务总数规范化的运行的时间vruntime。**每次一个任务被选中运行时，它会被给予一个长度与 ∑ w i/ j w j 成正比的时间片，这一时间会在被规范化后加到vruntime中；每次一个任务时间片耗尽时，系统就会选择目前系统中vruntime最小的任务来运行。

为了选择vruntime最小的任务，Linux 系统中使用了红黑树的结构，这样最小的vruntime对应的结点一定是树最靠左的叶子。使用红黑树的结构就牺牲了这一算法的运行时间：插入一个任务或移除一个任务需要 O(logn) 的时间，而最左边的叶子被存放在了一个代表整个调度系统的数据结构中，因此寻找最左边的叶子只需要 O(1) 的时间。

多处理器调度

如你所知，现代的很多大型计算机都是多处理器的；在大的数据中心中（如谷歌的数据中心），一整个装满处理器和磁盘的仓库可能是同一台计算机（这种计算机被称为 Warehouse-Scale Computer，WSC）。在这种情况下，一个操作系统的调度器就需要处理将工作分摊到多个处理器上的功能。你可能会问，为什么不直接按照单处理器的调度算法给空闲的处理器分配任务呢？接下来我们就来看看，按照这种思路调度任务会有什么问题。

我们知道，一个任务不一定等于一个进程；一个线程也可以是一个任务。那么，如果一个进程希望充分利用多处理器的资源，它就可以分出多个线程，并行地完成一段计算，完成这段计算后再合并线程或让所有线程进入下一阶段的计算。然而，在计算机中，由于系统把这几个线程当成独立的任务，系统可能把它们分开运行，这样就会出现所有线程都需要等待最慢的那个线程完成才能进入下一阶段的问题，并行对于运算速度的提升就大打折扣了。如果几个线程中有一个获得了一个锁，然后它的处理器被抢占了，那么剩余的线程即使获得了处理器也只能等待锁。如果这个锁是自旋锁的话，那么所有这个进程下的线程都会在自旋中浪费处理器时间，导致其它进程也不能产生进度。

可见，这种盲目（oblivious）地利用单处理器的方法在多处理器计算机上调度任务的方法是不可行的。

为了解决上述的问题，我们在此向你介绍一种解决方法： 成组调度（Gang Scheduling） 。**成组调度的想法很简单，那就是把一组相关的线程同时放到处理器上运行，一段时间后再同时撤下去、换上下一组线程。**当我们只有一个并行程序时，这种调度方法是非常方便的——我们可以用一些处理器专门运行一组线程，用剩下的处理器来运行其它程序，这样我们既保证了这组并行线程的效率、又保证了其它程序的运行。

然而这种调度方法在我们有多个并行程序需要调度时就比较麻烦了。每个并行程序可能使用不同数量的处理器，那么现在系统中有几个处理器可以用于调度就成为了一个变量。有时，增加处理器并不能增加一个程序的运行速度，这时一个更好的调度方法可能是减少分给一组线程的处理器数量，然后用节省出的处理器去运行别的并行程序。这个话题的深度远超过了这节课可以探讨的范围，因此我们在这里不做讨论。之所以我们要给你讲多处理器的调度问题是因为我们不希望你在上完这门课以后对于现实中多处理器的计算机毫无认知。

排队论

== 一种量化地计算系统效率的方法， **排队论（Queuing theory） **==
排队论适用的范围和它涉及到的变量。下图表示的是排队论适用的系统：

排队论描述的系统包含了两部分，一部分是任务队列，另一部分是实际运行任务、提供服务的部分，我们将后一部分称为运行部分。
之所以我们要区分等待和运行这两部分，是因为我们使用排队论的目的就是分析一个任务在
等待和运行这两个部分分别花费的时间长度。前面几节中我们已经说过，一个任务的周转时间等于它的等待时间与运行时间之和，假设其运行时间是不变的，那么它的等待时间就成为了限制系统表现的主要问题。如果一个系统中运行的部分时间较短、而等待时间很长，那么我们就应该考虑换一种调度算法或者多买几个处理器；如果一个系统中运行部分时间和等待时间都很长，那我们就应该考虑，等待时间过长可能是由系统处理速度慢于任务进入系统的速度导致的，那我们就有必要改一改现在运行所使用的算法或买一个更快的处理器了。

在一个系统中，我们用 Tw 来表示一个任务的平均等待时间，用 Q 来表示队列中平均的任务数量， Ts 表示在 没有队列的情况下 系统处理一个任务所需的平均时间，Tr 表示一个任务在进入系统后产生响应的平均时间，也就是Tw与 Ts之和。

从直观上我们可以知道，Tw 与任务进入系统的速度是直接关联的。如果短时间内忽然有一大波任务进入了系统，那么这些系统的平均等待时间势必会很长。我们用 λ 表示任务进入系统的速率，用 μ 表示任务离开系统的速率（注意，μ= 1/Ts
​），接下来我们就来定义一下系统的利用率 U（Utilization）。我们知道，假如每秒最多能有 10 个任务离开系统，而实际上每秒只有 5 个任务进入系统，那么系统只需要一半的时间就可以处理完这五个任务，系统的利用率就是 50%。因此，在这种情况下、系统的利用率 U= λ / μ
。但是，假如每秒有 100 个任务进入系统，而系统还是最多只能让 10 个任务离开系统，那么显然系统的利用率会达到 100%，且不能变得更大。因此，当 λ≥μ 时， U=1。
根据系统利用率的定义，我们知道一个系统在单位时间内可以完成的任务的数量 X 等于 U⋅μ。你很容易从直观上证明这一点：一个系统在单位时间内完成的任务数量肯定是由输入速度与输出速度中比较小的那个决定的。

最后一个我们需要介绍的量是系统中存在的任务数量 N，它等于系统中两部分所含的任务数量之和。接下来我们要介绍的一条定理就是用来计算一个稳定的系统中所含的任务数量的。

在一个稳定的系统中，任务进入和离开系统的速率相同，这时系统中任务的数量 N=XR。这个法则被称为 利特尔法则（Little’s Law） 。从这条法则的描述中你可以看出，这条法则除了稳定性以外对系统没有任何要求。这正是这个法则的优秀之处——我们不需要知道系统内部的机理就可以利用这条法则计算其内部的任务数量，因为任务进出系统的速率是可以从外部观察的。

为什么这个法则是对的呢？我们知道 R 是一个任务从进入系统到产生响应（也就是离开系统）需要的时间，那么在时间点 t0 进入系统的所有任务，在 t0+R 时就都会离开系统，而在 t0
离开系统的任务是在 t0−R 时进入系统的，也就是说从 t 0−R 到 t0
这段时间里进入系统的任务是 t0
​这个时间点在系统中的全部任务，这些任务的数量就等于 XR。

如果任务进入系统和离开系统的速率不同，那么我们显然就不能使用上面这种计算方法了，因为同一时间离开系统的任务不一定是同一时间进入的。

在实际生活中，有时我们不仅需要考虑 λ， μ 这两个平均值，而需要考虑瞬时进入系统和离开系统的任务数量。即使任务进入系统的平均速率很低，我们还是有可能在短时间内产生一个等待队列，因为所有任务可能集中在短时间内进入系统，这时系统的响应时间就会因为等待时间变长而变长。现实生活中，任务进入系统的速率和离开系统的速率都符合泊松分布。鉴于有些同学可能没有学过概率论的内容，我们这里就不讲这部分内容的具体证明了。在泊松分布中，一个随机变量的值等于 x 的概率等于 λe−λ
，你可以直观地把这理解成 x 越接近 0 概率越大，越接近正无穷概率越小。通过这种分布的性质我们可以导出下面这个公式：
R= S/1−U
对公式感兴趣的可以自行去推导证明一下。