計算機系統的性能建模與設計：排隊論實戰 (Performance Modeling and Design of Computer Systems: Queueing Theory in Action)

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合併獨立泊松過程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 UNI程壽命測量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