操作系統(tǒng)導(dǎo)論

第 1章 關(guān)于本書的對(duì)話 1
第　2章 操作系統(tǒng)介紹　3
2．1　虛擬化CPU　4
2．2　虛擬化內(nèi)存　6
2．3　并發(fā)　7
2．4　持久性　9
2．5　設(shè)計(jì)目標(biāo)　11
2．6　簡(jiǎn)單歷史　12
2．7　小結(jié)　15
參考資料　15
第　1部分 虛擬化
第3章　關(guān)于虛擬化的對(duì)話　18
第4章　抽象：進(jìn)程　19
4．1　抽象：進(jìn)程　20
4．2　進(jìn)程API　20
4．3　進(jìn)程創(chuàng)建：更多細(xì)節(jié)　21
4．4　進(jìn)程狀態(tài)　22
4．5　數(shù)據(jù)結(jié)構(gòu)　24
4．6　小結(jié)　25
參考資料　25
作業(yè)　26
問題　26
第5章　插敘：進(jìn)程API　28
5．1　fork()系統(tǒng)調(diào)用　28
5．2　wait()系統(tǒng)調(diào)用　29
5．3　最后是exec()系統(tǒng)調(diào)用　30
5．4　為什么這樣設(shè)計(jì)API　32
5．5　其他API　34
5．6　小結(jié)　34
參考資料　34
作業(yè)（編碼）　35
問題　35
第6章　機(jī)制：受限直接執(zhí)行　37
6．1　基本技巧：受限直接執(zhí)行　37
6．2　問題1：受限制的操作　38
6．3　問題2：在進(jìn)程之間切換　40
6．4　擔(dān)心并發(fā)嗎　44
6．5　小結(jié)　45
參考資料　45
作業(yè)（測(cè)量）　47
第7章　進(jìn)程調(diào)度：介紹　48
7．1　工作負(fù)載假設(shè)　48
7．2　調(diào)度指標(biāo)　49
7．3　先進(jìn)先出（FIFO）　49
7．4　最短任務(wù)優(yōu)先（SJF）　50
7．5　最短完成時(shí)間優(yōu)先（STCF）　51
7．6　新度量指標(biāo)：響應(yīng)時(shí)間　52
7．7　輪轉(zhuǎn)　52
7．8　結(jié)合I/O　54
7．9　無法預(yù)知　54
7．10　小結(jié)　55
參考資料　55
作業(yè)　56
問題　56
第8章　調(diào)度：多級(jí)反饋隊(duì)列　57
8．1　MLFQ：基本規(guī)則　57
8．2　嘗試 #1：如何改變優(yōu)先級(jí)　58
8．3　嘗試 #2：提升優(yōu)先級(jí)　60
8．4　嘗試 #3：更好的計(jì)時(shí)方式　61
8．5　MLFQ調(diào)優(yōu)及其他問題　61
8．6　MLFQ：小結(jié)　62
參考資料　63
作業(yè)　64
問題　64
第9章　調(diào)度：比例份額　65
9．1　基本概念：彩票數(shù)表示份額　65
9．2　彩票機(jī)制　66
9．3　實(shí)現(xiàn)　67
9．4　一個(gè)例子　68
9．5　如何分配彩票　68
9．6　為什么不是確定的　69
9．7　小結(jié)　70
參考資料　70
作業(yè)　71
問題　71
第　10章 多處理器調(diào)度（高級(jí)）　73
10．1　背景：多處理器架構(gòu)　73
10．2　別忘了同步　75
10．3　最后一個(gè)問題：緩存親和度　76
10．4　單隊(duì)列調(diào)度　76
10．5　多隊(duì)列調(diào)度　77
10．6　Linux 多處理器調(diào)度　79
10．7　小結(jié)　79
參考資料　79
第　11章 關(guān)于CPU虛擬化的總結(jié)對(duì)話　81
第　12章 關(guān)于內(nèi)存虛擬化的對(duì)話　83
第　13章 抽象：地址空間　85
13．1　早期系統(tǒng)　85
13．2　多道程序和時(shí)分共享　85
13．3　地址空間　86
13．4　目標(biāo)　87
13．5　小結(jié)　89
參考資料　89
第　14章 插敘：內(nèi)存操作API　91
14．1　內(nèi)存類型　91
14．2　malloc()調(diào)用　92
14．3　free()調(diào)用　93
14．4　常見錯(cuò)誤　93
14．5　底層操作系統(tǒng)支持　96
14．6　其他調(diào)用　97
14．7　小結(jié)　97
參考資料　97
作業(yè)（編碼）　98
問題　98
第　15章 機(jī)制：地址轉(zhuǎn)換　100
15．1　假設(shè)　101
15．2　一個(gè)例子　101
15．3　動(dòng)態(tài)（基于硬件）重定位　103
15．4　硬件支持：總結(jié)　105
15．5　操作系統(tǒng)的問題　105
15．6　小結(jié)　108
參考資料　109
作業(yè)　110
問題　110
第　16章 分段　111
16．1　分段：泛化的基址/界限　111
16．2　我們引用哪個(gè)段　113
16．3　棧怎么辦　114
16．4　支持共享　114
16．5　細(xì)粒度與粗粒度的分段　115
16．6　操作系統(tǒng)支持　115
16．7　小結(jié)　117
參考資料　117
作業(yè)　118
問題　119
第　17章 空閑空間管理　120
17．1　假設(shè)　120
17．2　底層機(jī)制　121
17．3　基本策略　126
17．4　其他方式　128
17．5　小結(jié)　130
參考資料　130
作業(yè)　131
問題　131
第　18章 分頁：介紹　132
18．1　一個(gè)簡(jiǎn)單例子　132
18．2　頁表存在哪里　134
18．3　列表中究竟有什么　135
18．4　分頁：也很慢　136
18．5　內(nèi)存追蹤　137
18．6　小結(jié)　139
參考資料　139
作業(yè)　140
問題　140
第　19章 分頁：快速地址轉(zhuǎn)換（TLB）　142
19．1　TLB的基本算法　142
19．2　示例：訪問數(shù)組　143
19．3　誰來處理TLB未命中　145
19．4　TLB的內(nèi)容　146
19．5　上下文切換時(shí)對(duì)TLB的處理　147
19．6　TLB替換策略　149
19．7　實(shí)際系統(tǒng)的TLB表項(xiàng)　149
19．8　小結(jié)　150
參考資料　151
作業(yè)（測(cè)量）　152
問題　153
第　20章 分頁：較小的表　154
20．1　簡(jiǎn)單的解決方案：更大的頁　154
20．2　混合方法：分頁和分段　155
20．3　多級(jí)頁表　157
20．4　反向頁表　162
20．5　將頁表交換到磁盤　163
20．6　小結(jié)　163
參考資料　163
作業(yè)　164
問題　164
第　21章 超越物理內(nèi)存：機(jī)制　165
21．1　交換空間　165
21．2　存在位　166
21．3　頁錯(cuò)誤　167
21．4　內(nèi)存滿了怎么辦　168
21．5　頁錯(cuò)誤處理流程　168
21．6　交換何時(shí)真正發(fā)生　169
21．7　小結(jié)　170
參考資料　171
第　22章 超越物理內(nèi)存：策略　172
22．1　緩存管理　172
22．2　最優(yōu)替換策略　173
22．3　簡(jiǎn)單策略：FIFO　175
22．4　另一簡(jiǎn)單策略：隨機(jī)　176
22．5　利用歷史數(shù)據(jù)：LRU　177
22．6　工作負(fù)載示例　178
22．7　實(shí)現(xiàn)基于歷史信息的算法　180
22．8　近似LRU　181
22．9　考慮臟頁　182
22．10　其他虛擬內(nèi)存策略　182
22．11　抖動(dòng)　183
22．12　小結(jié)　183
參考資料　183
作業(yè)　185
問題　185
第　23章 VAX/VMS虛擬內(nèi)存系統(tǒng)　186
23．1　背景　186
23．2　內(nèi)存管理硬件　186
23．3　一個(gè)真實(shí)的地址空間　187
23．4　頁替換　189
23．5　其他漂亮的虛擬內(nèi)存技巧　190
23．6　小結(jié)　191
參考資料　191
第　24章 內(nèi)存虛擬化總結(jié)對(duì)話　193
第　2部分 并發(fā)
第　25章 關(guān)于并發(fā)的對(duì)話　196
第　26章 并發(fā)：介紹　198
26．1　實(shí)例：線程創(chuàng)建　199
26．2　為什么更糟糕：共享數(shù)據(jù)　201
26．3　核心問題：不可控的調(diào)度　203
26．4　原子性愿望　205
26．5　還有一個(gè)問題：等待另一個(gè)
線程　206
26．6　小結(jié)：為什么操作系統(tǒng)課要研究
并發(fā)　207
參考資料　207
作業(yè)　208
問題　208
第　27章 插敘：線程API　210
27．1　線程創(chuàng)建　210
27．2　線程完成　211
27．3　鎖　214
27．4　條件變量　215
27．5　編譯和運(yùn)行　217
27．6　小結(jié)　217
參考資料　218
第　28章 鎖　219
28．1　鎖的基本思想　219
28．2　Pthread鎖　220
28．3　實(shí)現(xiàn)一個(gè)鎖　220
28．4　評(píng)價(jià)鎖　220
28．5　控制中斷　221
28．6　測(cè)試并設(shè)置指令（原子交換）　222
28．7　實(shí)現(xiàn)可用的自旋鎖　223
28．8　評(píng)價(jià)自旋鎖　225
28．9　比較并交換　225
28．10　鏈接的加載和條件式存儲(chǔ)指令　226
28．11　獲取并增加　228
28．12　自旋過多：怎么辦　229
28．13　簡(jiǎn)單方法：讓出來吧，寶貝　229
28．14　使用隊(duì)列：休眠替代自旋　230
28．15　不同操作系統(tǒng)，不同實(shí)現(xiàn)　232
28．16　兩階段鎖　233
28．17　小結(jié)　233
參考資料　233
作業(yè)　235
問題　235
第　29章 基于鎖的并發(fā)數(shù)據(jù)結(jié)構(gòu)　237
29．1　并發(fā)計(jì)數(shù)器　237
29．2　并發(fā)鏈表　241
29．3　并發(fā)隊(duì)列　244
29．4　并發(fā)散列表　245
29．5　小結(jié)　246
參考資料　247
第30章　條件變量　249
30．1　定義和程序　250
30．2　生產(chǎn)者/消費(fèi)者（有界緩沖區(qū)）
問題　252
30．3　覆蓋條件　260
30．4　小結(jié)　261
參考資料　261
第31章　信號(hào)量　263
31．1　信號(hào)量的定義　263
31．2　二值信號(hào)量（鎖）　264
31．3　信號(hào)量用作條件變量　266
31．4　生產(chǎn)者/消費(fèi)者（有界緩沖區(qū)）
問題　268
31．5　讀者—寫者鎖　271
31．6　哲學(xué)家就餐問題　273
31．7　如何實(shí)現(xiàn)信號(hào)量　275
31．8　小結(jié)　276
參考資料　276
第32章　常見并發(fā)問題　279
32．1　有哪些類型的缺陷　279
32．2　非死鎖缺陷　280
32．3　死鎖缺陷　282
32．4　小結(jié)　288
參考資料　289
第33章　基于事件的并發(fā)（進(jìn)階）　291
33．1　基本想法：事件循環(huán)　291
33．2　重要API：select()（或poll()）　292
33．3　使用select()　293
33．4　為何更簡(jiǎn)單？無須鎖　294
33．5　一個(gè)問題：阻塞系統(tǒng)調(diào)用　294
33．6　解決方案：異步I/O　294
33．7　另一個(gè)問題：狀態(tài)管理　296
33．8　什么事情仍然很難　297
33．9　小結(jié)　298
參考資料　298
第34章　并發(fā)的總結(jié)對(duì)話　300
第3部分　持久性
第35章　關(guān)于持久性的對(duì)話　302
第36章　I/O設(shè)備　303
36．1　系統(tǒng)架構(gòu)　303
36．2　標(biāo)準(zhǔn)設(shè)備　304
36．3　標(biāo)準(zhǔn)協(xié)議　304
36．4　利用中斷減少CPU開銷　305
36．5　利用DMA進(jìn)行更高效的數(shù)據(jù)
傳送　306
36．6　設(shè)備交互的方法　307
36．7　納入操作系統(tǒng)：設(shè)備驅(qū)動(dòng)程序　307
36．8　案例研究：簡(jiǎn)單的IDE磁盤驅(qū)動(dòng)
程序　309
36．9　歷史記錄　311
36．10　小結(jié)　311
參考資料　312
第37章　磁盤驅(qū)動(dòng)器　314
37．1　接口　314
37．2　基本幾何形狀　314
37．3　簡(jiǎn)單的磁盤驅(qū)動(dòng)器　315
37．4　I/O時(shí)間：用數(shù)學(xué)　318
37．5　磁盤調(diào)度　320
37．6　小結(jié)　323
參考資料　323
作業(yè)　324
問題　324
第38章　廉價(jià)冗余磁盤陣列（RAID）　326
38．1　接口和RAID內(nèi)部　327
38．2　故障模型　327
38．3　如何評(píng)估RAID　328
38．4　RAID 0級(jí)：條帶化　328
38．5　RAID 1級(jí)：鏡像　331
38．6　RAID 4級(jí)：通過奇偶校驗(yàn)節(jié)省
空間　333
38．7　RAID 5級(jí)：旋轉(zhuǎn)奇偶校驗(yàn)　336
38．8　RAID比較：總結(jié)　337
38．9　其他有趣的RAID問題　338
38．10　小結(jié)　338
參考資料　339
作業(yè)　340
問題　340
第39章　插敘：文件和目錄　342
39．1　文件和目錄　342
39．2　文件系統(tǒng)接口　343
39．3　創(chuàng)建文件　343
39．4　讀寫文件　344
39．5　讀取和寫入，但不按順序　346
39．6　用fsync()立即寫入　346
39．7　文件重命名　347
39．8　獲取文件信息　348
39．9　刪除文件　349
39．10　創(chuàng)建目錄　349
39．11　讀取目錄　350
39．12　刪除目錄　351
39．13　硬鏈接　351
39．14　符號(hào)鏈接　353
39．15　創(chuàng)建并掛載文件系統(tǒng)　354
39．16　總結(jié)　355
參考資料　355
作業(yè)　356
問題　356
第40章　文件系統(tǒng)實(shí)現(xiàn)　357
40．1　思考方式　357
40．2　整體組織　358
40．3　文件組織：inode　359
40．4　目錄組織　363
40．5　空閑空間管理　364
40．6　訪問路徑：讀取和寫入　364
40．7　緩存和緩沖　367
40．8　小結(jié)　369
參考資料　369
作業(yè)　370
問題　371
第41章　局部性和快速文件系統(tǒng)　372
41．1　問題：性能不佳　372
41．2　FFS：磁盤意識(shí)是解決方案　373
41．3　組織結(jié)構(gòu)：柱面組　373
41．4　策略：如何分配文件和目錄　374
41．5　測(cè)量文件的局部性　375
41．6　大文件例外　376
41．7　關(guān)于FFS的其他幾件事　377
41．8　小結(jié)　378
參考資料　378
第42章　崩潰一致性：FSCK和日志　380
42．1　一個(gè)詳細(xì)的例子　380
42．2　解決方案＃1：文件系統(tǒng)檢查
程序　383
42．3　解決方案＃2：日志
（或預(yù)寫日志）　384
42．4　解決方案＃3：其他方法　392
42．5　小結(jié)　393
參考資料　393
第43章　日志結(jié)構(gòu)文件系統(tǒng)　395
43．1　按順序?qū)懭氪疟P　396
43．2　順序而高效地寫入　396
43．3　要緩沖多少　397
43．4　問題：查找inode　398
43．5　通過間接解決方案：inode映射　398
43．6　檢查點(diǎn)區(qū)域　399
43．7　從磁盤讀取文件：回顧　400
43．8　目錄如何　400
43．9　一個(gè)新問題：垃圾收集　401
43．10　確定塊的死活　402
43．11　策略問題：要清理哪些塊，
何時(shí)清理　403
43．12　崩潰恢復(fù)和日志　403
43．13　小結(jié)　404
參考資料　404
第44章　數(shù)據(jù)完整性和保護(hù)　407
44．1　磁盤故障模式　407
44．2　處理潛在的扇區(qū)錯(cuò)誤　409
44．3　檢測(cè)訛誤：校驗(yàn)和　409
44．4　使用校驗(yàn)和　412
44．5　一個(gè)新問題：錯(cuò)誤的寫入　412
44．6　最后一個(gè)問題：丟失的寫入　413
44．7　擦凈　413
44．8　校驗(yàn)和的開銷　414
44．9　小結(jié)　414
參考資料　414
第45章　關(guān)于持久的總結(jié)對(duì)話　417
第46章　關(guān)于分布式的對(duì)話　418
第47章　分布式系統(tǒng)　419
47．1　通信基礎(chǔ)　420
47．2　不可靠的通信層　420
47．3　可靠的通信層　422
47．4　通信抽象　424
47．5　遠(yuǎn)程過程調(diào)用（RPC）　425
47．6　小結(jié)　428
參考資料　429
第48章　Sun的網(wǎng)絡(luò)文件系統(tǒng)（NFS）　430
48．1　基本分布式文件系統(tǒng)　430
48．2　交出NFS　431
48．3　關(guān)注點(diǎn)：簡(jiǎn)單快速的服務(wù)器崩潰
恢復(fù)　431
48．4　快速崩潰恢復(fù)的關(guān)鍵：無狀態(tài)　432
48．5　NFSv2協(xié)議　433
48．6　從協(xié)議到分布式文件系統(tǒng)　434
48．7　利用冪等操作處理服務(wù)器故障　435
48．8　提高性能：客戶端緩存　437
48．9　緩存一致性問題　437
48．10　評(píng)估NFS的緩存一致性　439
48．11　服務(wù)器端寫緩沖的隱含意義　439
48．12　小結(jié)　440
參考資料　440
第49章　Andrew文件系統(tǒng)（AFS）　442
49．1　AFS版本1　442
49．2　版本1的問題　443
49．3　改進(jìn)協(xié)議　444
49．4　AFS版本2　444
49．5　緩存一致性　446
49．6　崩潰恢復(fù)　447
49．7　AFSv2的擴(kuò)展性和性能　448
49．8　AFS：其他改進(jìn)　450
49．9　小結(jié)　450
參考資料　451
作業(yè)　452
問題　452
第50章　關(guān)于分布式的總結(jié)對(duì)話　453
附錄A　關(guān)于虛擬機(jī)監(jiān)視器的對(duì)話　454
附錄B　虛擬機(jī)監(jiān)視器　455
附錄C　關(guān)于監(jiān)視器的對(duì)話　466
附錄D　關(guān)于實(shí)驗(yàn)室的對(duì)話　467
附錄E　實(shí)驗(yàn)室：指南　468
附錄F　實(shí)驗(yàn)室：系統(tǒng)項(xiàng)目　478
附錄G　實(shí)驗(yàn)室：xv6項(xiàng)目　480