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

出版者的话
译者序
序言
前言
致谢
部分排队论简介
章分析建模的功能及实例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.2DTMC的定义85
8.3有限状态DTMC的示例85
8.3.1维修设施问题85
8.3.2雨伞问题86
8.3.3程序分析问题86
8.4P的幂：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
0章真实世界的示例：Google、Aloha和HarderChains129
10.1Google的PageRank算法129
10.1.1Google的DTMC算法129
10.1.2真实网络图的问题131
10.1.3死角和蜘蛛陷阱问题的Google解决方案131
10.1.4PageRank算法的评估132
10.1.5实际实现的注意事项132
10.2Aloha协议分析132
10.2.1SlottedAloha协议133
10.2.2Aloha马尔可夫链133
10.2.3Aloha马尔可夫链的性质134
10.2.4改进Aloha协议135
10.3Aloha为更难的马尔可夫链生成函数136
10.3.1z变换136
10.3.2求解链136
10.4阅读材料138
10.5习题138
1章指数分布和泊松过程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
2章转换到连续时间马尔可夫链154
12.1定义CTMC154
12.2解决CTMC问题157
12.3泛化和解释159
12.3.1解释CTMC的平衡方程160
12.3.2CTMC的概要定理160
12.4习题160
3章M/M/1和PASTA161
13.1M/M/1队列161
13.2使用M/M/1队列的示例163
13.3PASTA164
13.4进一步阅读166
13.5习题166
第五部分服务器机群与网络：多服务器和多队列系统
4章服务器机群：M/M/k与M/M/k/k排队系统173
14.1连续时间马尔可夫链的时间可逆性173
14.2M/M/k/k损失系统174
14.3M/M/k176
14.4三种服务器组织模式的比较180
14.5阅读材料181
14.6习题181
5章服务器机群的容量规划184
15.1在M/M/k中，负载的真正含义是什么184
15.2M/M/∞185
15.2.1M/M/∞分析185
15.2.2M/M/k容量规划的首次削减规则186
15.3平方根配置187
15.4阅读材料189
15.5习题189
6章时间可逆性和Burke定理193
16.1有限状态CTMC的更多示例193
16.1.1缓冲空间有限的网络193
16.1.2M/M/2I/O的批处理系统194
16.2反向链195
16.3Burke定理198
16.4Burke定理的另一种(部分)证明198
16.5应用：串联式服务器199
16.6具有概率路由的一般非循环网络200
16.7阅读材料201
16.8习题201
7章队列网络和Jackson乘积形式203
17.1Jackson网络的定义203
17.2到达每个服务器的过程204
17.3解决Jackson网络205
17.4本地平衡法205
17.5阅读材料209
17.6习题209
8章分类队列网络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.3CPU密集型和I/O密集型作业示例222
18.7阅读材料224
18.8习题224
9章封闭队列网络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.3MVA示例233
19.4阅读材料234
19.5习题234
第六部分实际工作负载：高可变性和重尾
第20章尾巴的故事：实际工作负载的案例研究239
20.1研究生院的故事——过程迁移239
20.2UNIX进程寿命测量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.2PH工作负载的马尔可夫链建模249
21.3矩阵分析法251
21.4时变负载分析252
21.4.1不错别的想法252
21.4.2生成矩阵Q252
21.4.3R求解254
21.4.4寻找π→0254
21.4.5性能指标255
21.5更复杂的链256
21.6阅读材料和进一步的评论258
21.7习题258
第22章具有分时服务器的网络261
22.1乘积形式网络261
22.2BCMP结果261
22.2.1FCFS服务器的网络261
22.2.2PS服务器的网络262
22.3M/M/1/PS264
22.4M/Cox/1/PS264
22.5M/G/1/PS服务器的串联网络268
22.6具有概率路由的PS服务器网络269
22.7阅读材料270
22.8习题270
第23章M/G/1队列与检验悖论271
23.1检验悖论271
23.2M/G/1队列及其分析271
23.3更新奖励理论273
23.4申请更新奖励以获得预期的超量收益275
23.5回到检验悖论276
23.6回到M/G/1队列277
23.7习题278
第24章服务器机群的任务分配策略280
24.1FCFS服务器机群的任务分配281
24.2PS服务器机群的任务调度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.5M/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.2M/G/1的繁忙时段分析315
27.3M/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.1FCFS、LCFS和RANDOM330
29.2阅读材料332
29.3习题332
第30章调度：抢占式、非基于规模的策略333
30.1PS333
30.1.1PS的起源333
30.1.2M/G/1/PS系统中的作业年龄334
30.1.3响应时间作为作业规模的函数335
30.1.4对PS结果的直觉336
30.1.5理解FCFS的PS结果的含义337
30.2抢占式LCFS338
30.3FB调度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.4PSJF的变换分析355
32.5习题357
第33章调度：SRPT与公平性358
33.1最短剩余处理时间358
33.2SRPT等待时间的精确推导360
33.3与其他策略的比较361
33.3.1与PSJF的比较361
33.3.2SRPT与FB362
33.3.3所有调度策略的比较362
33.4SRPT的公平性363
33.5阅读材料366
参考文献367