计算机系统的性能建模与设计：排队论实战pdf下载pdf下载

计算机系统的性能建模与设计：排队论实战百度网盘pdf下载

作者:
简介:本篇主要提供计算机系统的性能建模与设计：排队论实战pdf下载
出版社：机械工业出版社自营官方旗舰店
出版时间：2020-08
pdf下载价格：0.00￥

免费下载

前去下载

书籍下载

下载地址

内容介绍

内容简介

本书讲述建模、分析和设计大型计算机系统同时使其具有良好性能且成本较低的方法和技术。其中重点强调的排队论也正好是作者非常擅长的理论研究。除了必要的理论方法，还包括丰富的计算机系统设计实例和练习。目的是使读者不仅能够定制现有的计算机系统设计和分析，还可以自己发明适合自己系统设计的方法。全书内容有趣而且易于阅读，采用“苏格拉底式”的问答模式进行叙述，适合该领域的科研和工程人员阅读参考，也适合高校计算机相关专业学生阅读。

作者简介

莫尔·哈肖尔-巴尔特（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章　分析建模的功能及实例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

查看全部↓

前言/序言

计算机系统设计的特殊世界
计算机系统的设计通常被视为艺术而非科学。关于使用哪种调度策略、运行多少服务器、每台服务器运行多快等决定，通常是基于直觉而不是数学公式。内核中内置的特定策略经常充斥着秘密的“伏都教常数”　“伏都教常数”一词是由John Ousterhout教授在加州大学伯克利分校讲学期间创造的。，没有任何解释，但在某些基准测试工作负载下似乎“运行良好”。学习计算机系统的学生经常被告知首先构建系统，然后更改策略以提高系统性能，而不是首先在纸上创建正式模型和系统设计，以确保系统满足性能目标。
即使在尝试评估现有计算机系统的性能时，我们通常也会鼓励学生模拟系统并花费许多天时间在不同的工作负载下运行模拟，然后等待发生的情况。鉴于可能的工作负载和输入参数的搜索空间通常很大，因此需要大量的模拟来适当地覆盖这一空间。尽管如此，我们依然很少创建系统的数学模型，并且很少随机地描述工作负载。我们没有对计算机系统可能表现良好的参数空间和可能表现较差的参数空间进行正式分析。毫无疑问，学生会感到系统评估和设计的整个过程非常特殊。例如，考虑在许多版本的Linux内核中更新资源调度的试错法。
计算机系统的分析建模
但不一定是这样！系统设计人员可以对系统进行数学建模，随机地表征工作负载和性能目标，然后根据工作负载和输入参数分析性地推导出系统性能。分析建模和随机过程这一领域已经存在了近一个世纪，它们可以为系统设计者节省大量的实验和纠错时间，同时提高性能。分析建模也可以与模拟结合使用，以帮助指导模拟过程，减少需要探索的案例数量。
不幸的是，在关于随机过程的数百本书中，几乎没有一本涉及计算机系统。这些书中的例子和所涵盖的材料主要面向运筹学研究领域，例如制造系统，或呼叫中心接听电话的人类操作员，或具有不同优先级作业的某些装配线系统。
在许多方面，设计制造系统所用的分析方法与计算机系统并没有太大的区别。人类操作员和计算机服务器之间有许多相似之处：人类操作员有动作快的也有动作慢的（就像计算机服务器一样）；人类操作员有时会生病（就像计算机服务器有时会崩溃一样）；不需要时, 可以让人类操作员回家以节省资金（就像关闭计算机服务器以节省电力一样）；让人类操作员复工需要启动资金（就像开启计算机服务器需要预热一样）。这样的例子不胜枚举。
但是，制造系统和计算机系统之间也存在许多差异。首先，计算机系统工作负载已经显示出在作业规模（服务要求）方面具有极高的可变性，平方变异系数高达100。这与制造系统工作负载中作业规模的低可变性服务时间特征非常不同。这种可变性差异可导致跨数量级的性能差异。其次，计算机系统的工作负载通常是可抢占的，并且CPU的时间共享（处理器共享）非常普遍。相比之下，大多数制造系统的工作负载都是非抢占式的（先来先服务的服务顺序是最常见的）。因此，大多数关于随机过程和排队论的书籍都省略了关于处理器共享的章节或更高级的抢占式策略，如最短剩余处理时间，而这些都是计算机系统的核心。在分析服务器机群时，处理器共享尤其重要，在计算机系统中，服务器机群通常由处理器共享服务器组成，而不是先来先服务的服务器。这里还涉及在用户之间共享带宽的任何计算应用程序，这通常采用处理器共享，而不是先来先服务方式。与制造系统相比，计算机系统的性能指标也可能不同（例如，电力使用是计算机系统的一项重要指标，在讨论随机过程的书籍中没有提到）。闭环体系结构在计算机系统中非常常见，其中新的作业在现有作业完成之前不会被创建，并且性能目标是最大化吞吐量，但这些通常被排除在讨论排队论的书籍之外。最后，在磁盘、网络协议、数据库、内存控制器和其他计算机系统中发生的特定类型的交互与传统排队论书籍中分析的非常不同。
本书目标
我多次走进一名计算机科学家同事的办公室，很高兴在书架上找到一本关于排队论的书。不幸的是，我的同事很快回答说他从未读过这本书，因为“世界看起来不像是一个M/M/1队列，而且除了那一章，其他的我都无法理解”。问题在于排队论的书对计算机科学家来说并不“友好”。其中的应用不是面向计算机的，并且所使用的假设对于计算机系统而言通常是不现实的。此外，这些书很深奥，不具备研究生数学水平的人通常都难以理解。从某种意义上说，这是很难避免的，如果一个人想要做的不仅仅是为读者提供“插入”的公式，那么就必须学会推导出自己的公式， 这需要掌握大量的数学知识。幸运的是，作为我最喜欢的作家之一，Sheldon Ross已经表明，有可能以一种有趣而简单的方式讲授大量的随机分析，而不需要首先学习测量理论和实际分析的相关课程。
我编写本书的动机是引领计算机科学家迈入排队论建模和分析的强大世界，从而改进计算机系统的设计。就我个人而言，我发现排队论分析在我大部分的研究中是非常有价值的，包括为网络设计路由协议，为Web服务器和数据库管理系统设计更好的调度算法，涵盖磁盘调度、内存分配、超级计算资源调度，以及数据中心的电源管理和容量供应。就内容而言，我有两个目标。首先，我想从计算机系
查看全部↓