本书讲述建模、分析和设计大型计算机系统同时使其具有良好性能且成本较低的方法和技术。其中重点强调的排队论也正好是作者非常擅长的理论研究。除了必要的理论方法，还包括丰富的计算机系统设计实例和练习。目的是使读者不仅能够定制现有的计算机系统设计和分析，还可以自己发明适合自己系统设计的方法。全书内容有趣而且易于阅读，采用“苏格拉底式”的问答模式进行叙述，适合该领域的科研和工程人员阅读参考，也适合高校计算机相关专业学生阅读。
源于CMU课程讲义，掌握排队论建模和分析技能，改进计算机系统的设计
计算机系统设计的特殊世界
计算机系统的设计通常被视为艺术而非科学。关于使用哪种调度策略、运行多少服务器、每台服务器运行多快等决定，通常是基于直觉而不是数学公式。内核中内置的特定策略经常充斥着秘密的“伏都教常数” “伏都教常数”一词是由John Ousterhout教授在加州大学伯克利分校讲学期间创造的。，没有任何解释，但在某些基准测试工作负载下似乎“运行良好”。学习计算机系统的学生经常被告知首先构建系统，然后更改策略以提高系统性能，而不是首先在纸上创建正式模型和系统设计，以确保系统满足性能目标。
即使在尝试评估现有计算机系统的性能时，我们通常也会鼓励学生模拟系统并花费许多天时间在不同的工作负载下运行模拟，然后等待发生的情况。鉴于可能的工作负载和输入参数的搜索空间通常很大，因此需要大量的模拟来适当地覆盖这一空间。尽管如此，我们依然很少创建系统的数学模型，并且很少随机地描述工作负载。我们没有对计算机系统可能表现良好的参数空间和可能表现较差的参数空间进行正式分析。毫无疑问，学生会感到系统评估和设计的整个过程非常特殊。例如，考虑在许多版本的Linux内核中更新资源调度的试错法。
计算机系统的分析建模
但不一定是这样！系统设计人员可以对系统进行数学建模，随机地表征工作负载和性能目标，然后根据工作负载和输入参数分析性地推导出系统性能。分析建模和随机过程这一领域已经存在了近一个世纪，它们可以为系统设计者节省大量的实验和纠错时间，同时提高性能。分析建模也可以与模拟结合使用，以帮助指导模拟过程，减少需要探索的案例数量。
不幸的是，在关于随机过程的数百本书中，几乎没有一本涉及计算机系统。这些书中的例子和所涵盖的材料主要面向运筹学研究领域，例如制造系统，或呼叫中心接听电话的人类操作员，或具有不同优先级作业的某些装配线系统。
在许多方面，设计制造系统所用的分析方法与计算机系统并没有太大的区别。人类操作员和计算机服务器之间有许多相似之处：人类操作员有动作快的也有动作慢的（就像计算机服务器一样）；人类操作员有时会生病（就像计算机服务器有时会崩溃一样）；不需要时, 可以让人类操作员回家以节省资金（就像关闭计算机服务器以节省电力一样）；让人类操作员复工需要启动资金（就像开启计算机服务器需要预热一样）。这样的例子不胜枚举。
但是，制造系统和计算机系统之间也存在许多差异。首先，计算机系统工作负载已经显示出在作业规模（服务要求）方面具有极高的可变性，平方变异系数高达100。这与制造系统工作负载中作业规模的低可变性服务时间特征非常不同。这种可变性差异可导致跨数量级的性能差异。其次，计算机系统的工作负载通常是可抢占的，并且CPU的时间共享（处理器共享）非常普遍。相比之下，大多数制造系统的工作负载都是非抢占式的（先来先服务的服务顺序是最常见的）。因此，大多数关于随机过程和排队论的书籍都省略了关于处理器共享的章节或更高级的抢占式策略，如最短剩余处理时间，而这些都是计算机系统的核心。在分析服务器机群时，处理器共享尤其重要，在计算机系统中，服务器机群通常由处理器共享服务器组成，而不是先来先服务的服务器。这里还涉及在用户之间共享带宽的任何计算应用程序，这通常采用处理器共享，而不是先来先服务方式。与制造系统相比，计算机系统的性能指标也可能不同（例如，电力使用是计算机系统的一项重要指标，在讨论随机过程的书籍中没有提到）。闭环体系结构在计算机系统中非常常见，其中新的作业在现有作业完成之前不会被创建，并且性能目标是最大化吞吐量，但这些通常被排除在讨论排队论的书籍之外。最后，在磁盘、网络协议、数据库、内存控制器和其他计算机系统中发生的特定类型的交互与传统排队论书籍中分析的非常不同。
本书目标
我多次走进一名计算机科学家同事的办公室，很高兴在书架上找到一本关于排队论的书。不幸的是，我的同事很快回答说他从未读过这本书，因为“世界看起来不像是一个M/M/1队列，而且除了那一章，其他的我都无法理解”。问题在于排队论的书对计算机科学家来说并不“友好”。其中的应用不是面向计算机的，并且所使用的假设对于计算机系统而言通常是不现实的。此外，这些书很深奥，不具备研究生数学水平的人通常都难以理解。从某种意义上说，这是很难避免的，如果一个人想要做的不仅仅是为读者提供“插入”的公式，那么就必须学会推导出自己的公式， 这需要掌握大量的数学知识。幸运的是，作为我最喜欢的作家之一，Sheldon Ross已经表明，有可能以一种有趣而简单的方式讲授大量的随机分析，而不需要首先学习测量理论和实际分析的相关课程。
我编写本书的动机是引领计算机科学家迈入排队论建模和分析的强大世界，从而改进计算机系统的设计。就我个人而言，我发现排队论分析在我大部分的研究中是非常有价值的，包括为网络设计路由协议，为Web服务器和数据库管理系统设计更好的调度算法，涵盖磁盘调度、内存分配、超级计算资源调度，以及数据中心的电源管理和容量供应。就内容而言，我有两个目标。首先，我想从计算机系统中选取足够的应用，使这本书对计算机科学家来说具有相关性和趣味性。为此，书中几乎一半的章节都是“应用”章节。其次，我想使这本书在数学上足够丰富，使读者能够自己创建新的排队分析，而不仅仅是应用现有的分析。随着计算机系统及其工作负载的不断发展，它们已变得越来越复杂，假设可以用已知的排队框架和分析进行建模是不现实的。作为计算机系统的设计者，我经常发现必须发明新的排队概念来模拟计算机系统的各个方面。
本书如何成为现实
1998年，作为麻省理工学院的博士后，我开发并讲授了一门新的计算机科学课程，我称之为“计算机系统的性能分析与设计”。该课程的描述如下：
在设计计算机系统时，通常会受到某些性能目标的限制（例如，低响应时间、高吞吐量或低能耗）。另一方面，在设计过程中通常会有很多选择：一个快磁盘，还是两个慢磁盘？什么速度的CPU就足够了？我们应该投资更多的缓冲空间还是更快的处理器？处理器应该如何安排作业？迁移活动作业是否值得？哪个路由策略最有效？服务器之间应该平衡负载吗？我们如何才能最好地应对高可变性的工作负载？通常这些问题的答案是反直觉的。理想情况下，在投入时间和金钱建立一个系统之前，人们希望得到这些问题的答案。本课程将向学生介绍分析随机建模，它将帮助系统设计人员回答上述问题。
从那时起，我通过在卡内基·梅隆大学计算机科学系的10多轮讲授而进一步改进了这门课程，在那里我为计算机科学、工程、数学等领域的博士生和高年级本科生讲授此课程。2002年，卡内基·梅隆大学泰珀商学院的运营管理系要求所有运营管理专业的学生必修这门课程。
当其他教师，包括我以前的博士生，开始在自己的课堂上采用我的讲稿时，他们经常请求我把讲稿变成一本书。这就是本书的由来。
本书概要
本书以问答方式编写，模仿我在教学中使用的苏格拉底风格。我认为课堂“讲座”理想上应该是一系列打散的问题，学生可以轻松地提供答案，并借此引导学生找到正确的直觉。在阅读本书时，尝试回答每个问题而不查看答案是非常重要的。这些问题的目的是提醒读者“思考”而不仅仅是“阅读”，并提醒教师提问而不仅仅是陈述事实。
除第1、28、33章外，其余各章末尾都配有习题。习题是本书不可或缺的一部分，不应该被忽略。许多习题用于说明理论在计算机系统设计中的应用，通常用于阐明关键问题。所有习题都与对应章所涉及的材料有关，部分习题是材料的直接应用，部分习题是对更大难度的材料的扩展。
这本书分为七个部分，大部分是建立在彼此的基础上的。
第一部分介绍排队论，并提供了计算机系统设计的实例，可以使用基本的排队分析来解答。还介绍了基本的排队论术语，包括封闭和开放排队模型及性能指标。
第二部分复习概率知识。为了使本书自成一体，我们在这些章节中包含了本书其余部分所需的全部概率知识。包括对常见离散和连续随机变量、它们的矩以及条件期望和概率的总结，还包括一些关于生成随机变量以进行模拟的材料。最后，我们讨论了样本路径、随机变量序列的收敛性以及时间均值与整体均值的关系。
第三部分讨论运筹定律，或“估算”分析。这些是非常简单的法则，适用于所有表现良好的排队系统。特别是，不要求对到达过程或工作量做任何假设（如泊松到达或指数服务时间）。这些定律允许我们快速推理高级别的系统行为（仅限均值），并就哪些修改将对性能产生最大影响做出设计决策。高层次计算机系统设计中的应用会贯穿本部分。
第四部分介绍马尔可夫链及其在计算机系统随机分析中的应用。马尔可夫链通过表示系统可能存在状态的完整空间，允许对系统进行更详细的分析。虽然借助第三部分中的运筹定律，我们通常可以回答有关系统中总体平均作业数的问题，但通过马尔可夫链我们能推导出在多服务器系统的服务器j上排队的作业的概率。第四部分包括离散时间和连续时间马尔可夫链。应用包括Google的PageRank算法、Aloha（以太网）网络协议以及有限缓冲路由器中的丢弃概率分析。
第五部分开发了第四部分介绍的马尔可夫链理论，以便分析更复杂的网络，包括服务器机群。我们分析具有复杂路由规则的队列网络，其中作业可以与确定其通过网络的路由的“类”相关联（这些被称为BCMP网络）。第五部分还推导出有关服务器机群容量配置的定理，例如“平方根配置规则”，它确定了为提供延迟保证所需的最小服务器数量。
由于第四部分和第五部分是基于马尔可夫链的，在分析中需要进行某些“马尔可夫”（无记忆）假设。特别是，假设作业的服务要求（大小）遵循指数分布，并且作业到达之间的时间也是指数分布的。许多应用通过这些指数假设进行了相当好的建模，使我们能够使用马尔可夫分析来获得对系统性能的深入了解。但是，在某些情况下，捕获经验工作负载中存在的高可变性作业规模的分布或相关性是非常重要的。
第六部分介绍了支持我们用高可变性分布替换这些指数分布的技术。同时，引入了相位型分布，这使得我们可以利用对指数分布以及第四和第五部分的马尔可夫链的理解，通过混合的指数对几乎所有的一般分布进行建模。然后，开发矩阵分析技术来分析到达过程和服务过程中具有相位型工作负载的系统。通过引入M/G/1队列，并讨论诸如检验悖论之类的概念，描述了真实世界的工作负载，包括重尾分布。另外，还引入了变换技术，以便使用一般分布。最后，甚至队列中的服务顺序也从简单的先来先服务顺序推广到时间共享（处理器共享）服务顺序，这在计算机系统中更为常见。应用比比皆是，我们对具有高可变性作业规模的服务器机群中的资源分配（任务分配）进行了广泛的研究，包括具有非抢占工作负载的服务器机群和具有分时服务器的Web服务器机群。另外，还研究了单个服务器和数据中心的电源管理策略。
第七部分是本书的最后部分，主要讨论调度方面。智能调度在计算机系统中非常重要，因为它可以显著提高系统性能，而无须购买任何新硬件。调度是操作系统的核心，涉及网络中的带宽分配、磁盘、数据库、存储器层次结构等。目前在计算机系统领域进行的大部分研究涉及新调度策略的设计和采用。然而，调度可能违反直觉，甚至基本调度策略的分析也远非易事，通常通过模拟评估调度策略来完成。在向读者介绍评估调度策略的分析技术时，我们希望通过分析可以评估更多此类策略。
我们希望读者大多按顺序阅读这些章节，但有以下例外。第一，可以跳过任何标有星号(*)的部分，而不会影响阅读。第二，关于变换的章节（第25章）可被有意地移到最后，这本书的大部分内容不依赖于对变换分析的了解。但是，由于学习变换分析需要一些时间，因此我们建议任何计划涵盖这一内容的教师在课程早期便开始一点一点地介绍。为了实现这一点，我们在第25章末尾包含了大量的习题，这些习题不要求读者掌握后面章节中的材料，可以在课程的早期分配给学生练习。最后，我们敦促读者查看以下网站，了解新的勘误/软件：
http：//www.cs.cmu.edu/～harchol/PerformanceModeling/errata.html
http：//www.cs.cmu.edu/～harchol/PerformanceModeling/software.html
请将任何其他错误发送至harchol@cs.cmu.edu。
计算机体系结构
计算机系统设计通常被视为艺术而非科学。本书针对计算机系统设计人员关心的问题，将排队论带回计算机科学中。全书采用“苏格拉底风格”的问答模式进行叙述，包含丰富的应用示例和300多道习题，帮助读者掌握建模、分析和设计具有良好性能和低成本的大型计算机系统所需的技能。
在本书中，你将找到以下问题的答案：
在具有速度s的单台机器和具有速度s/n的n台机器之间，应该如何选择？
如果到达率和服务率都加倍，平均响应时间是否保持不变？
系统是否真的旨在平衡负载，或者这仅仅是一个神话？
如果调度策略有利于一组作业，是否一定会影响其他作业？
贪婪算法、最短延迟、路由策略在服务器机群中是否有意义？
高作业规模可变性和重尾工作负载如何影响调度策略的选择？
如何在设计计算机系统时权衡能源和延迟？
假设当到达率为9个作业/秒时，需要12台服务器来满足延迟保证。当到达率升至9000个作业/秒时，需要12000台服务器吗？
莫尔·哈肖尔-巴尔特（Mor Harchol-Balter） 卡内基·梅隆大学（CMU）计算机科学系教授。1996年，她在美国科学院院士、图灵奖得主Manuel Blum教授的指导下获得了加州大学伯克利分校的博士学位。1996~1999年，在麻省理工学院从事博士后研究。1999年加入CMU，2008~2011年担任博士项目负责人。她是ACM Fellow和IEEE Fellow。曾被授予McCandless Chair，并曾荣获NSF CAREER奖以及多项最佳伦文奖和杰出教学成果奖。此外，她一直在积极参与SIGMETRICS/PERFORMANCE研究社区的工作。
方娟 北京工业大学教授，博士生导师，信息学部计算机学院体系结构研究所所长，物联网工程专业负责人。曾获北京市优秀人才、北京市中青年骨干等称号，发表论文100余篇，授权国家发明专利21项。
蔡旻 张佳玥 博士，北京工业大学讲师，信息学部计算机学院体系结构研究所教师。
我一直对寻找更好的计算机系统设计感兴趣，这些设计可以在不购买额外资源的情况下提高性能。当我回顾已解决的问题并展望希望解决的问题时，我意识到问题的表述越来越简单，我的立足点也越来越不安全。我曾经相信的每一种智慧，现在都会质疑：如果调度策略有助于一组作业，是否一定会影响其他一些作业，或者这些“保护法”被曲解了？贪婪的路由策略在服务器机群中是否有意义？或者对个体有好处的东西实际上对整个系统是灾难性的？当比较单台快速机器和n台慢速机器（每台的速度都是1/n）时，单台快速机器通常要贵得多，但这是否意味着它必然更好？分布式系统是否真的旨在平衡负载，或者这只是一个神话？循环窃取，机器可以在空闲时互相帮助——这听起来是个好主意，但我们能否量化实际效益？调度策略的性能受到达率和服务率的变化以及负载波动的影响有多大？我们可以做些什么来对抗变化？这些问题中固有的是真实用户行为和实际工作负载对重尾、高度可变服务需求以及相关到达流程的影响。在我的工作中，交织在一起的是理论分析与实施现实之间的紧张关系，每一个都激励着另一个。在寻找新的研究技术来回答这些和其他问题的过程中，我发现自己正在朝着定义所有这些问题的基本核心靠拢，这使得反直觉更加可信。
[美]莫尔·哈肖尔-巴尔特（Mor Harchol-Balter） 著：---作者简介---
莫尔·哈肖尔-巴尔特（Mor Harchol-Balter） 卡内基•梅隆大学（CMU）计算机科学系教授。1996年，她在美国科学院院士、图灵奖得主Manuel Blum教授的指导下获得了加州大学伯克利分校的博士学位。1996~1999年，在麻省理工学院从事博士后研究。1999年加入CMU，2008~2011年担任博士项目负责人。她是ACM Fellow和IEEE Fellow。曾被授予McCandless Chair，并曾荣获NSF CAREER奖以及多项最佳伦文奖和杰出教学成果奖。此外，她一直在积极参与SIGMETRICS/PERFORMANCE研究社区的工作。
---译者简介---
方娟，北京工业大学教授，博士生导师，信息学部计算机学院体系结构研究所所长，物联网工程专业负责人。曾获北京市优秀人才、北京市中青年骨干等称号，发表论文100余篇，授权国家发明专利21项。
蔡旻 张佳玥 博士，北京工业大学讲师，信息学部计算机学院体系结构研究所教师。
研究计算机性能离不开一系列衡量计算机系统性能的指标，性能评价技术研究的就是将性能建模为数量化的、能进行度量和评比的客观指标，以及从系统本身或从系统模型中获取有关性能信息的方法。
正如作者所言，本书的目的是引领计算机科学家迈入排队论建模和分析的强大世界，从而改进计算机系统的设计。对于从事计算机系统性能研究的科研工作者来说，本书无疑是首选。本书的主要内容包括排队论、概率知识、运筹定律、马尔可夫链及其应用、指数分布、智能调度等方面，适合研究生教学及研究者使用。本书集合了大量学术界和工业界的世界级专家的智慧，不仅涵盖计算机性能建模领域的基本原理，同时通过实例分析了大量的应用，从而激发读者的学习兴趣和研究兴趣。
从传统的计算机体系结构领域的研究，到现在体系结构领域中关于高性能与低功耗技术的研究，本书中精辟的论述、大量的案例，给我们的教学和科研工作带来了巨大的帮助。对正在从事这方面研究的国内学者来说，这无疑是一个福音。
在本书的翻译过程中，我们力求忠实原作。蔡旻老师负责翻译第1～13章，张佳玥老师负责翻译第14～18章，方娟老师负责翻译第19～33章。在此特别感谢几位研究生的大力协助，张迪、曾文正等在本书初稿翻译中协助完成了部分工作。蔡旻老师在全书的翻译工作中付出了很大努力，陆帅冰老师在翻译和校对工作中做了很多工作，全书由方娟老师负责统稿。
限于译者水平，本书的翻译难免会存在纰漏，恳请广大读者批评指正。
译者
2020年5月
出版者的话
译者序
序言
前言
致谢
第一部分 排队论简介
第1章 分析建模的功能及实例2
1.1 什么是排队论2
1.2 排队论实例3
第2章 排队论术语8
2.1 我们将去向何方8
2.2 单服务器网络8
2.3 排队网络的分类9
2.4 开放网络10
2.5 更多指标：吞吐量和利用率10
2.6 封闭网络12
2.6.1 交互式（终端驱动）系统13
2.6.2 批处理系统14
2.6.3 封闭系统中的吞吐量14
2.7 封闭网络和开放网络之间的差异15
2.8 阅读材料16
2.9 习题16
第二部分 必要的概率背景知识
第3章 概率知识复习18
3.1 样本空间和事件18
3.2 事件定义的概率18
3.3 事件的条件概率19
3.4 独立事件和有条件独立事件20
3.5 总概率定律21
3.6 贝叶斯定律22
3.7 离散随机变量与连续随机变量22
3.8 概率和密度23
3.8.1 离散：概率质量函数23
3.8.2 连续：概率密度函数25
3.9 期望和方差27
3.10 联合概率和独立性29
3.11 条件概率和期望30
3.12 基于条件化的概率和期望34
3.13 期望的线性性质35
3.14 正态分布36
3.14.1 线性变换特性37
3.14.2 中心极限定理39
3.15 随机变量的随机数的和40
3.16 习题41
第4章 生成用于模拟的随机变量45
4.1 逆变换方法45
4.1.1 连续情况45
4.1.2 离散情况46
4.2 接受拒绝方法47
4.2.1 离散情况47
4.2.2 连续情况48
4.2.3 一些更难的问题50
4.3 阅读材料50
4.4 习题50
第5章 样本路径、收敛和均值52
5.1 收敛52
5.2 强/弱大数定律55
5.3 时间均值与整体均值56
5.3.1 动机56
5.3.2 定义57
5.3.3 解释57
5.3.4 等价性58
5.3.5 模拟59
5.3.6 系统时间均值60
5.4 阅读材料60
5.5 习题60
第三部分 简单运筹定律的预测能力：“假设”问题和答案
第6章 Little定律和其他运筹定律62
6.1 开放系统的Little定律62
6.2 直觉62
6.3 封闭系统的Little定律63
6.4 开放系统的Little定律证明63
6.4.1 基于时间均值的陈述64
6.4.2 证明64
6.4.3 推论65
6.5 封闭系统的Little定律证明66
6.5.1 基于时间均值的陈述66
6.5.2 证明66
6.6 广义的Little定律67
6.7 应用Little定律的示例67
6.8 更多运筹定律：强制流定律69
6.9 运筹定律组合70
6.10 设备需求72
6.11 与Little定律相关的阅读和其他主题73
6.12 习题73
第7章 修改分析：封闭系统的“假设”75
7.1 回顾75
7.2 封闭系统的渐近界限76
7.3 封闭系统的修改分析78
7.4 更多修改分析示例78
7.5 封闭网络和开放网络的比较80
7.6 阅读材料81
7.7 习题81
第四部分 从马尔可夫链到简单队列
第8章 离散时间马尔可夫链84
8.1 离散时间与连续时间马尔可夫链84
8.2 DTMC的定义85
8.3 有限状态DTMC的示例85
8.3.1 维修设施问题85
8.3.2 雨伞问题86
8.3.3 程序分析问题86
8.4 P的幂：n步转移概率87
8.5 平稳方程88
8.6 平稳分布等于极限分布89
8.7 求解平稳方程的示例90
8.7.1 维修设施成本问题90
8.7.2 雨伞问题91
8.8 无限状态DTMC91
8.9 无限状态平稳性结果91
8.10 求解无限状态DTMC中的平稳方程93
8.11 习题95
第9章 遍历性理论97
9.1 遍历性问题97
9.2 有限状态DTMC98
9.2.1 极限分布的存在98
9.2.2 访问状态之间的平均时间101
9.2.3 时间均值102
9.3 无限状态马尔可夫链102
9.3.1 常返与瞬时103
9.3.2 无限随机游走示例106
9.3.3 正常返与零常返108
9.4 马尔可夫链的遍历定理109
9.5 时间均值110
9.6 极限概率解释为速率112
9.7 时间可逆性定理113
9.8 当链是周期性的或者不可约的114
9.8.1 周期链115
9.8.2 不可约的链119
9.9 结论119
*9.10 马尔可夫链的遍历定理的证明119
9.11 习题124*
第10章 真实世界的示例：Google、Aloha和Harder Chains129
10.1 Google的PageRank算法129
10.1.1 Google的DTMC算法129
10.1.2 真实网络图的问题131
10.1.3 死角和蜘蛛陷阱问题的Google解决方案131
10.1.4 PageRank算法的评估132
10.1.5 实际实现的注意事项132
10.2 Aloha协议分析132
10.2.1 Slotted Aloha协议133
10.2.2 Aloha马尔可夫链133
10.2.3 Aloha马尔可夫链的性质134
10.2.4 改进Aloha协议135
10.3 Aloha为更难的马尔可夫链生成函数136
10.3.1 z变换136
10.3.2 求解链136
10.4 阅读材料138
10.5 习题138
第11章 指数分布和泊松过程141
11.1 指数分布的定义141
11.2 指数的无记忆特性142
11.3 通过δ-步将指数与几何相关联143
11.4 指数的更多属性144
11.5 著名的泊松过程146
11.6 合并独立泊松过程149
11.7 泊松分裂149
11.8 均匀性151
11.9 习题152
第12章 转换到连续时间马尔可夫链154
12.1 定义CTMC154
12.2 解决CTMC问题157
12.3 泛化和解释159
12.3.1 解释CTMC的平衡方程160
12.3.2 CTMC的概要定理160
12.4 习题160
第13章 M/M/1和PASTA161
13.1 M/M/1队列161
13.2 使用M/M/1队列的示例163
13.3 PASTA164
13.4 进一步阅读166
13.5 习题166
第五部分 服务器机群与网络：多服务器和多队列系统
第14章 服务器机群：M/M/k与M/M/k/k排队系统173
14.1 连续时间马尔可夫链的时间可逆性173
14.2 M/M/k/k损失系统174
14.3 M/M/k176
14.4 三种服务器组织模式的比较180
14.5 阅读材料181
14.6 习题181
第15章 服务器机群的容量规划184
15.1 在M/M/k中，负载的真正含义是什么184
15.2 M/M/∞185
15.2.1 M/M/∞分析185
15.2.2 M/M/k容量规划的首次削减规则186
15.3 平方根配置187
15.4 阅读材料189
15.5 习题189
第16章 时间可逆性和Burke定理193
16.1 有限状态CTMC的更多示例193
16.1.1 缓冲空间有限的网络193
16.1.2 M/M/2 I/O的批处理系统194
16.2 反向链195
16.3 Burke定理198
16.4 Burke定理的另一种(部分)证明198
16.5 应用：串联式服务器199
16.6 具有概率路由的一般非循环网络200
16.7 阅读材料201
16.8 习题201
第17章 队列网络和Jackson乘积形式203
17.1 Jackson网络的定义203
17.2 到达每个服务器的过程204
17.3 解决Jackson网络205
17.4 本地平衡法205
17.5 阅读材料209
17.6 习题209
第18章 分类队列网络212
18.1 概述212
18.2 分类网络的动机212
18.3 分类Jackson网络的符号和建模214
18.4 单服务器分类网络215
18.5 乘积形式定理216
18.6 分类网络示例220
18.6.1 面向连接的ATM网络示例220
18.6.2 作业类别分布示例221
18.6.3 CPU密集型和I/O密集型作业示例222
18.7 阅读材料224
18.8 习题224
第19章 封闭队列网络226
19.1 动机226
19.2 乘积形式的解227
19.2.1 封闭网络的局部平衡方程227
19.2.2 推导极限概率的示例229
19.3 均值分析230
19.3.1 到达定理230
19.3.2 平均响应时间的迭代推导232
19.3.3 MVA示例233
19.4 阅读材料234
19.5 习题234
第六部分 实际工作负载：高可变性和重尾
第20章 尾巴的故事：实际工作负载的案例研究239
20.1 研究生院的故事——过程迁移239
20.2 UNIX进程寿命测量240
20.3 帕累托分布的性质241
20.4 有界帕累托分布242
20.5 重尾242
20.6 活动进程迁移的益处243
20.7 帕累托分布无处不在243
20.8 习题244
第21章 相位型分布和矩阵分析方法246
21.1 用指数代表一般分布246
21.2 PH工作负载的马尔可夫链建模249
21.3 矩阵分析法251
21.4 时变负载分析252
21.4.1 高级别的想法252
21.4.2 生成矩阵Q252
21.4.3 R求解254
21.4.4 寻找π→0254
21.4.5 性能指标255
21.5 更复杂的链256
21.6 阅读材料和进一步的评论258
21.7 习题258
第22章 具有分时服务器的网络261
22.1 乘积形式网络261
22.2 BCMP结果261
22.2.1 FCFS服务器的网络261
22.2.2 PS服务器的网络262
22.3 M/M/1/PS264
22.4 M/Cox/1/PS264
22.5 M/G/1/PS服务器的串联网络268
22.6 具有概率路由的PS服务器网络269
22.7 阅读材料270
22.8 习题270
第23章 M/G/1队列与检验悖论271
23.1 检验悖论271
23.2 M/G/1队列及其分析271
23.3 更新奖励理论273
23.4 申请更新奖励以获得预期的超量收益275
23.5 回到检验悖论276
23.6 回到M/G/1队列277
23.7 习题278
第24章 服务器机群的任务分配策略280
24.1 FCFS服务器机群的任务分配281
24.2 PS服务器机群的任务调度288
24.3 最佳服务器机群设计291
24.4 阅读材料和进一步跟进294
24.5 习题296
第25章 变换分析298
25.1 变换的定义和一些示例298
25.2 从变换中获取矩：剥洋葱300
25.3 变换的线性性质302
25.4 条件303
25.5 M/M/1系统中响应时间的分布304
25.6 结合拉普拉斯变换和z变换305
25.7 变换的更多结果305
25.8 阅读材料306
25.9 习题306
第26章 M/G/1变换分析309
26.1 系统中数字的z变换309
26.2 系统中时间的拉普拉斯变换311
26.3 阅读材料313
26.4 习题313
第27章 功率优化应用314
27.1 功率优化问题314
27.2 M/G/1的繁忙时段分析315
27.3 M/G/1与设置成本318
27.4 比较ON/IDLE与ON/OFF320
27.5 阅读材料321
27.6 习题321
第七部分 M/G/1中的智能调度
第28章 性能指标327
28.1 传统度量标准327
28.2 单一队列的常用度量标准327
28.3 当下流行的度量标准328
28.4 饥饿/公平指标328
28.5 导出性能指标329
28.6 阅读材料329
第29章 调度：非抢占式、非基于规模的策略330
29.1 FCFS、LCFS和RANDOM330
29.2 阅读材料332
29.3 习题332
第30章 调度：抢占式、非基于规模的策略333
30.1 PS333
30.1.1 PS的起源333
30.1.2 M/G/1/PS系统中的作业年龄334
30.1.3 响应时间作为作业规模的函数335
30.1.4 对PS结果的直觉336
30.1.5 理解FCFS的PS结果的含义337
30.2 抢占式LCFS338
30.3 FB调度339
30.4 阅读材料342
30.5 习题343
第31章 调度：非抢占式、基于规模的策略345
31.1 优先级排队345
31.2 非抢占式优先级346
31.3 最短作业优先348
31.4 关于非抢占式策略的问题350
31.5 习题350
第32章 调度：抢占式、基于规模的策略351
32.1 动机351
32.2 抢占式优先级排队351
32.3 抢占式最短作业优先354
32.4 PSJF的变换分析355
32.5 习题357
第33章 调度：SRPT与公平性358
33.1 最短剩余处理时间358
*33.2 SRPT等待时间的精确推导360
33.3 与其他策略的比较361
33.3.1 与PSJF的比较361
33.3.2 SRPT与FB362
33.3.3 所有调度策略的比较362
33.4 SRPT的公平性363
33.5 阅读材料366
参考文献367
