計算機系統(tǒng)的性能建模與設(shè)計:排隊論實戰(zhàn)
定 價:139 元
叢書名:計算機科學(xué)叢書
- 作者:[美]莫爾·哈肖爾-巴爾特(Mor Harchol-Balter)
- 出版時間:2020/8/1
- ISBN:9787111659938
- 出 版 社:機械工業(yè)出版社
- 中圖法分類:TP302
- 頁碼:0
- 紙張:
- 版次:1
- 開本:16K
本書講述建模、分析和設(shè)計大型計算機系統(tǒng)同時使其具有良好性能且成本較低的方法和技術(shù)。其中重點強調(diào)的排隊論也正好是作者非常擅長的理論研究。除了必要的理論方法,還包括豐富的計算機系統(tǒng)設(shè)計實例和練習(xí)。目的是使讀者不僅能夠定制現(xiàn)有的計算機系統(tǒng)設(shè)計和分析,還可以自己發(fā)明適合自己系統(tǒng)設(shè)計的方法。全書內(nèi)容有趣而且易于閱讀,采用“蘇格拉底式”的問答模式進行敘述,適合該領(lǐng)域的科研和工程人員閱讀參考,也適合高校計算機相關(guān)專業(yè)學(xué)生閱讀。
出版者的話
譯者序
序言
前言
致謝
第一部分 排隊論簡介
第1章 分析建模的功能及實例2
1.1 什么是排隊論2
1.2 排隊論實例3
第2章 排隊論術(shù)語8
2.1 我們將去向何方8
2.2 單服務(wù)器網(wǎng)絡(luò)8
2.3 排隊網(wǎng)絡(luò)的分類9
2.4 開放網(wǎng)絡(luò)10
2.5 更多指標(biāo):吞吐量和利用率10
2.6 封閉網(wǎng)絡(luò)12
2.6.1 交互式(終端驅(qū)動)系統(tǒng)13
2.6.2 批處理系統(tǒng)14
2.6.3 封閉系統(tǒng)中的吞吐量14
2.7 封閉網(wǎng)絡(luò)和開放網(wǎng)絡(luò)之間的差異15
2.8 閱讀材料16
2.9 習(xí)題16
第二部分 必要的概率背景知識
第3章 概率知識復(fù)習(xí)18
3.1 樣本空間和事件18
3.2 事件定義的概率18
3.3 事件的條件概率19
3.4 獨立事件和有條件獨立事件20
3.5 總概率定律21
3.6 貝葉斯定律22
3.7 離散隨機變量與連續(xù)隨機變量22
3.8 概率和密度23
3.8.1 離散:概率質(zhì)量函數(shù)23
3.8.2 連續(xù):概率密度函數(shù)25
3.9 期望和方差27
3.10 聯(lián)合概率和獨立性29
3.11 條件概率和期望30
3.12 基于條件化的概率和期望34
3.13 期望的線性性質(zhì)35
3.14 正態(tài)分布36
3.14.1 線性變換特性37
3.14.2 中心極限定理39
3.15 隨機變量的隨機數(shù)的和40
3.16 習(xí)題41
第4章 生成用于模擬的隨機變量45
4.1 逆變換方法45
4.1.1 連續(xù)情況45
4.1.2 離散情況46
4.2 接受拒絕方法47
4.2.1 離散情況47
4.2.2 連續(xù)情況48
4.2.3 一些更難的問題50
4.3 閱讀材料50
4.4 習(xí)題50
第5章 樣本路徑、收斂和均值52
5.1 收斂52
5.2 強/弱大數(shù)定律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 系統(tǒng)時間均值60
5.4 閱讀材料60
5.5 習(xí)題60
第三部分 簡單運籌定律的預(yù)測能力:“假設(shè)”問題和答案
第6章 Little定律和其他運籌定律62
6.1 開放系統(tǒng)的Little定律62
6.2 直覺62
6.3 封閉系統(tǒng)的Little定律63
6.4 開放系統(tǒng)的Little定律證明63
6.4.1 基于時間均值的陳述64
6.4.2 證明64
6.4.3 推論65
6.5 封閉系統(tǒng)的Little定律證明66
6.5.1 基于時間均值的陳述66
6.5.2 證明66
6.6 廣義的Little定律67
6.7 應(yīng)用Little定律的示例67
6.8 更多運籌定律:強制流定律69
6.9 運籌定律組合70
6.10 設(shè)備需求72
6.11 與Little定律相關(guān)的閱讀和其他主題73
6.12 習(xí)題73
第7章 修改分析:封閉系統(tǒng)的“假設(shè)”75
7.1 回顧75
7.2 封閉系統(tǒng)的漸近界限76
7.3 封閉系統(tǒng)的修改分析78
7.4 更多修改分析示例78
7.5 封閉網(wǎng)絡(luò)和開放網(wǎng)絡(luò)的比較80
7.6 閱讀材料81
7.7 習(xí)題81
第四部分 從馬爾可夫鏈到簡單隊列
第8章 離散時間馬爾可夫鏈84
8.1 離散時間與連續(xù)時間馬爾可夫鏈84
8.2 DTMC的定義85
8.3 有限狀態(tài)DTMC的示例85
8.3.1 維修設(shè)施問題85
8.3.2 雨傘問題86
8.3.3 程序分析問題86
8.4 P的冪:n步轉(zhuǎn)移概率87
8.5 平穩(wěn)方程88
8.6 平穩(wěn)分布等于極限分布89
8.7 求解平穩(wěn)方程的示例90
8.7.1 維修設(shè)施成本問題90
8.7.2 雨傘問題91
8.8 無限狀態(tài)DTMC91
8.9 無限狀態(tài)平穩(wěn)性結(jié)果91
8.10 求解無限狀態(tài)DTMC中的平穩(wěn)方程93
8.11 習(xí)題95
第9章 遍歷性理論97
9.1 遍歷性問題97
9.2 有限狀態(tài)DTMC98
9.2.1 極限分布的存在98
9.2.2 訪問狀態(tài)之間的平均時間101
9.2.3 時間均值102
9.3 無限狀態(tài)馬爾可夫鏈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 當(dāng)鏈?zhǔn)侵芷谛缘幕蛘卟豢杉s的114
9.8.1 周期鏈115
9.8.2 不可約的鏈119
9.9 結(jié)論119
*9.10 馬爾可夫鏈的遍歷定理的證明119
9.11 習(xí)題124*
第10章 真實世界的示例:Google、Aloha和Harder Chains129
10.1 Google的PageRank算法129
10.1.1 Google的DTMC算法129
10.1.2 真實網(wǎng)絡(luò)圖的問題131
10.1.3 死角和蜘蛛陷阱問題的Google解決方案131
10.1.4 PageRank算法的評估132
10.1.5 實際實現(xiàn)的注意事項132
10.2 Aloha協(xié)議分析132
10.2.1 Slotted Aloha協(xié)議133
10.2.2 Aloha馬爾可夫鏈133
10.2.3 Aloha馬爾可夫鏈的性質(zhì)134
10.2.4 改進Aloha協(xié)議135
10.3 Aloha為更難的馬爾可夫鏈生成函數(shù)136
10.3.1 z變換136
10.3.2 求解鏈136
10.4 閱讀材料138
10.5 習(xí)題138
第11章 指數(shù)分布和泊松過程141
11.1 指數(shù)分布的定義141
11.2 指數(shù)的無記憶特性142
11.3 通過δ-步將指數(shù)與幾何相關(guān)聯(lián)143
11.4 指數(shù)的更多屬性144
11.5 著名的泊松過程146
11.6 合并獨立泊松過程149
11.7 泊松分裂149
11.8 均勻性151
11.9 習(xí)題152
第12章 轉(zhuǎn)換到連續(xù)時間馬爾可夫鏈154
12.1 定義CTMC154
12.2 解決CTMC問題157
12.3 泛化和解釋159
12.3.1 解釋CTMC的平衡方程160
12.3.2 CTMC的概要定理160
12.4 習(xí)題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 習(xí)題166
第五部分 服務(wù)器機群與網(wǎng)絡(luò):多服務(wù)器和多隊列系統(tǒng)
第14章 服務(wù)器機群:M/M/k與M/M/k/k排隊系統(tǒng)173
14.1 連續(xù)時間馬爾可夫鏈的時間可逆性173
14.2 M/M/k/k損失系統(tǒng)174
14.3 M/M/k176
14.4 三種服務(wù)器組織模式的比較180
14.5 閱讀材料181
14.6 習(xí)題181
第15章 服務(wù)器機群的容量規(guī)劃184
15.1 在M/M/k中,負載的真正含義是什么184
15.2 M/M/∞185
15.2.1 M/M/∞分析185
15.2.2 M/M/k容量規(guī)劃的首次削減規(guī)則186
15.3 平方根配置187
15.4 閱讀材料189
15.5 習(xí)題189
第16章 時間可逆性和Burke定理193
16.1 有限狀態(tài)CTMC的更多示例193
16.1.1 緩沖空間有限的網(wǎng)絡(luò)193
16.1.2 M/M/2 I/O的批處理系統(tǒng)194
16.2 反向鏈195
16.3 Burke定理198
16.4 Burke定理的另一種(部分)證明198
16.5 應(yīng)用:串聯(lián)式服務(wù)器199
16.6 具有概率路由的一般非循環(huán)網(wǎng)絡(luò)200
16.7 閱讀材料201
16.8 習(xí)題201
第17章 隊列網(wǎng)絡(luò)和Jackson乘積形式203
17.1 Jackson網(wǎng)絡(luò)的定義203
17.2 到達每個服務(wù)器的過程204
17.3 解決Jackson網(wǎng)絡(luò)205
17.4 本地平衡法205
17.5 閱讀材料209
17.6 習(xí)題209
第18章 分類隊列網(wǎng)絡(luò)212
18.1 概述212
18.2 分類網(wǎng)絡(luò)的動機212
18.3 分類Jackson網(wǎng)絡(luò)的符號和建模214
18.4 單服務(wù)器分類網(wǎng)絡(luò)215
18.5 乘積形式定理216
18.6 分類網(wǎng)絡(luò)示例220
18.6.1 面向連接的ATM網(wǎng)絡(luò)示例220
18.6.2 作業(yè)類別分布示例221
18.6.3 CPU密集型和I/O密集型作業(yè)示例222
18.7 閱讀材料224
18.8 習(xí)題224
第19章 封閉隊列網(wǎng)絡(luò)226
19.1 動機226
19.2 乘積形式的解227
19.2.1 封閉網(wǎng)絡(luò)的局部平衡方程227
19.2.2 推導(dǎo)極限概率的示例229
19.3 均值分析230
19.3.1 到達定理230
19.3.2 平均響應(yīng)時間的迭代推導(dǎo)232
19.3.3 MVA示例233
19.4 閱讀材料234
19.5 習(xí)題234
第六部分 實際工作負載:高可變性和重尾
第20章 尾巴的故事:實際工作負載的案例研究239
20.1 研究生院的故事——過程遷移239
20.2 UNIX進程壽命測量240
20.3 帕累托分布的性質(zhì)241
20.4 有界帕累托分布242
20.5 重尾242
20.6 活動進程遷移的益處243
20.7 帕累托分布無處不在243
20.8 習(xí)題244
第21章 相位型分布和矩陣分析方法246
21.1 用指數(shù)代表一般分布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 性能指標(biāo)255
21.5 更復(fù)雜的鏈256
21.6 閱讀材料和進一步的評論258
21.7 習(xí)題258
第22章 具有分時服務(wù)器的網(wǎng)絡(luò)261
22.1 乘積形式網(wǎng)絡(luò)261
22.2 BCMP結(jié)果261
22.2.1 FCFS服務(wù)器的網(wǎng)絡(luò)261
22.2.2 PS服務(wù)器的網(wǎng)絡(luò)262
22.3 M/M/1/PS264
22.4 M/Cox/1/PS264
22.5 M/G/1/PS服務(wù)器的串聯(lián)網(wǎng)絡(luò)268
22.6 具有概率路由的PS服務(wù)器網(wǎng)絡(luò)269
22.7 閱讀材料270
22.8 習(xí)題270
第23章 M/G/1隊列與檢驗悖論271
23.1 檢驗悖論271
23.2 M/G/1隊列及其分析271
23.3 更新獎勵理論273
23.4 申請更新獎勵以獲得預(yù)期的超量收益275
23.5 回到檢驗悖論276
23.6 回到M/G/1隊列277
23.7 習(xí)題278
第24章 服務(wù)器機群的任務(wù)分配策略280
24.1 FCFS服務(wù)器機群的任務(wù)分配281
24.2 PS服務(wù)器機群的任務(wù)調(diào)度288
24.3 最佳服務(wù)器機群設(shè)計291
24.4 閱讀材料和進一步跟進294
24.5 習(xí)題296
第25章 變換分析298
25.1 變換的定義和一些示例298
25.2 從變換中獲取矩:剝洋蔥300
25.3 變換的線性性質(zhì)302
25.4 條件303
25.5 M/M/1系統(tǒng)中響應(yīng)時間的分布304
25.6 結(jié)合拉普拉斯變換和z變換305
25.7 變換的更多結(jié)果305
25.8 閱讀材料306
25.9 習(xí)題306
第26章 M/G/1變換分析309
26.1 系統(tǒng)中數(shù)字的z變換309
26.2 系統(tǒng)中時間的拉普拉斯變換311
26.3 閱讀材料313
26.4 習(xí)題313
第27章 功率優(yōu)化應(yīng)用314
27.1 功率優(yōu)化問題314
27.2 M/G/1的繁忙時段分析315
27.3 M/G/1與設(shè)置成本318
27.4 比較ON/IDLE與ON/OFF320
27.5 閱讀材料321
27.6 習(xí)題321
第七部分 M/G/1中的智能調(diào)度
第28章 性能指標(biāo)327
28.1 傳統(tǒng)度量標(biāo)準(zhǔn)327
28.2 單一隊列的常用度量標(biāo)準(zhǔn)327
28.3 當(dāng)下流行的度量標(biāo)準(zhǔn)328
28.4 饑餓/公平指標(biāo)328
28.5 導(dǎo)出性能指標(biāo)329
28.6 閱讀材料329
第29章 調(diào)度:非搶占式、非基于規(guī)模的策略330
29.1 FCFS、LCFS和RANDOM330
29.2 閱讀材料332
29.3 習(xí)題332
第30章 調(diào)度:搶占式、非基于規(guī)模的策略333
30.1 PS333
30.1.1 PS的起源333
30.1.2 M/G/1/PS系統(tǒng)中的作業(yè)年齡334
30.1.3 響應(yīng)時間作為作業(yè)規(guī)模的函數(shù)335
30.1.4 對PS結(jié)果的直覺336
30.1.5 理解FCFS的PS結(jié)果的含義337
30.2 搶占式LCFS338
30.3 FB調(diào)度339
30.4 閱讀材料342
30.5 習(xí)題343
第31章 調(diào)度:非搶占式、基于規(guī)模的策略345
31.1 優(yōu)先級排隊345
31.2 非搶占式優(yōu)先級346
31.3 最短作業(yè)優(yōu)先348
31.4 關(guān)于非搶占式策略的問題350
31.5 習(xí)題350
第32章 調(diào)度:搶占式、基于規(guī)模的策略351
32.1 動機351
32.2 搶占式優(yōu)先級排隊351
32.3 搶占式最短作業(yè)優(yōu)先354
32.4 PSJF的變換分析355
32.5 習(xí)題357
第33章 調(diào)度:SRPT與公平性358
33.1 最短剩余處理時間358
*33.2 SRPT等待時間的精確推導(dǎo)360
33.3 與其他策略的比較361
33.3.1 與PSJF的比較361
33.3.2 SRPT與FB362
33.3.3 所有調(diào)度策略的比較362
33.4 SRPT的公平性363
33.5 閱讀材料366
參考文獻367