現(xiàn)代操作系統(tǒng)：原理與實現(xiàn)

目　　錄
序言一
序言二
前言
第一部分　操作系統(tǒng)基礎(chǔ)
第1章　操作系統(tǒng)概述 2
1.1　簡約但不簡單：從Hello World說起 2
1.2　什么是操作系統(tǒng) 3
1.3　操作系統(tǒng)簡史 6
1.3.1　GM-NAA I/O：第一個（批處理）操作系統(tǒng) 6
1.3.2　OS/360：從專用走向通用 6
1.3.3　Multics/UNIX/Linux：分時與多任務(wù) 7
1.3.4　macOS/Windows：以人為本的人機交互 8
1.4　操作系統(tǒng)接口 9
1.5　ChCore：一個簡單的實驗操作系統(tǒng) 11
參考文獻 12
第2章　硬件結(jié)構(gòu) 13
2.1　CPU與指令集架構(gòu) 14
2.1.1　指令集 14
2.1.2　特權(quán)級 15
2.1.3　寄存器 17
2.2　物理內(nèi)存與CPU緩存 17
2.2.1　緩存結(jié)構(gòu) 18
2.2.2　緩存尋址 19
2.3　設(shè)備與中斷 20
2.3.1　內(nèi)存映射輸入輸出 20
2.3.2　輪詢與中斷 21
2.4　思考題 22
參考文獻 22
第3章　操作系統(tǒng)結(jié)構(gòu) 23
3.1　操作系統(tǒng)的機制與策略 24
3.2　操作系統(tǒng)復(fù)雜度管理方法 25
3.3　操作系統(tǒng)內(nèi)核架構(gòu) 27
3.3.1　簡要結(jié)構(gòu) 27
3.3.2　宏內(nèi)核架構(gòu) 28
3.3.3　微內(nèi)核架構(gòu) 30
3.3.4　外核架構(gòu) 32
3.3.5　其他操作系統(tǒng)內(nèi)核架構(gòu) 34
3.4　操作系統(tǒng)框架結(jié)構(gòu) 35
3.4.1　Android系統(tǒng)框架 35
3.4.2　ROS系統(tǒng)框架 37
3.5　思考題 39
參考文獻 40
第4章　內(nèi)存管理 42
4.1　虛擬地址與物理地址 43
4.1.1　初識物理地址與虛擬地址 43
4.1.2　使用虛擬地址訪問物理內(nèi)存 44
4.1.3　分段與分頁機制 44
4.2　基于分頁的虛擬內(nèi)存 46
4.2.1　AArch64架構(gòu)下的4級頁表 47
4.2.2　加速地址翻譯的重要硬件：TLB 49
4.2.3　換頁與缺頁異常 52
4.2.4　頁替換策略 54
4.2.5　工作集模型 57
4.3　虛擬內(nèi)存功能 58
4.3.1　共享內(nèi)存 58
4.3.2　寫時拷貝 58
4.3.3　內(nèi)存去重 60
4.3.4　內(nèi)存壓縮 60
4.3.5　大頁 61
4.4　物理內(nèi)存分配與管理 62
4.4.1　目標(biāo)與評價維度 62
4.4.2　伙伴系統(tǒng) 63
4.4.3　SLAB分配器 65
4.4.4　常用的空閑鏈表 66
4.4.5　物理內(nèi)存與CPU緩存 68
4.5　案例分析：ChCore內(nèi)存管理機制 70
4.6　思考題 73
參考文獻 74
第5章　進程與線程 76
5.1　進程 76
5.1.1　進程的狀態(tài) 76
5.1.2　進程的內(nèi)存空間布局 78
5.1.3　進程控制塊和上下文切換 79
5.2　案例分析：Linux的進程操作 80
5.2.1　進程的創(chuàng)建：fork 80
5.2.2　進程的執(zhí)行：exec 84
5.2.3　進程管理 85
5.2.4　討論：fork過時了嗎 89
5.3　線程 92
5.3.1　多線程的地址空間布局 93
5.3.2　用戶態(tài)線程與內(nèi)核態(tài)線程 93
5.3.3　線程控制塊與線程本地存儲 94
5.3.4　線程的基本接口：以POSIX線程庫為例 95
5.4　案例分析：ChCore的線程上下文 99
5.4.1　線程的上下文和TCB 99
5.4.2　ChCore中上下文切換的實現(xiàn) 100
5.5　纖程 102
5.5.1　對纖程的需求：一個簡單的例子 103
5.5.2　POSIX的纖程支持：ucontext 103
5.5.3　纖程的上下文切換 105
5.6　思考題 106
參考文獻 107
第6章　操作系統(tǒng)調(diào)度 108
6.1　計算機調(diào)度簡介 108
6.1.1　操作系統(tǒng)調(diào)度 110
6.1.2　調(diào)度指標(biāo) 111
6.2　調(diào)度機制 113
6.2.1　長期、中期與短期調(diào)度 114
6.2.2　任務(wù)調(diào)度總覽 116
6.3　單核調(diào)度策略 117
6.3.1　經(jīng)典調(diào)度 118
6.3.2　優(yōu)先級調(diào)度 122
6.3.3　公平共享調(diào)度 127
6.3.4　實時調(diào)度 133
6.3.5　其他調(diào)度 138
6.4　多核調(diào)度策略 141
6.4.1　負載分擔(dān) 141
6.4.2　協(xié)同調(diào)度 142
6.4.3　兩級調(diào)度 144
6.4.4　負載追蹤與負載均衡 145
6.4.5　能耗感知調(diào)度 148
6.5　調(diào)度進階機制 151
6.5.1　處理器親和性 152
6.5.2　調(diào)度策略設(shè)置 153
6.6　案例分析：現(xiàn)代調(diào)度器 155
6.6.1　Linux調(diào)度器 155
6.6.2　macOS/iOS調(diào)度器 160
6.7　思考題 162
參考文獻 163
第7章　進程間通信 165
7.1　進程間通信基礎(chǔ) 165
7.1.1　一個簡單的進程間通信設(shè)計 166
7.1.2　數(shù)據(jù)傳遞 167
7.1.3　控制流轉(zhuǎn)移 169
7.1.4　單向和雙向 170
7.1.5　同步和異步 170
7.1.6　超時機制 171
7.1.7　通信連接管理 172
7.1.8　權(quán)限檢查 173
7.1.9　命名服務(wù) 174
7.2　宏內(nèi)核進程間通信 175
7.2.1　管道進程間通信 175
7.2.2　System V消息隊列 178
7.2.3　System V信號量 179
7.2.4　System V共享內(nèi)存 180
7.2.5　信號進程間通信 181
7.2.6　套接字進程間通信 185
7.3　微內(nèi)核進程間通信 186
7.3.1　Mach：早期的微內(nèi)核進程間通信設(shè)計 186
7.3.2　L4：圍繞進程間通信優(yōu)化而設(shè)計的微內(nèi)核系統(tǒng) 188
7.3.3　LRPC：遷移線程模型 193
7.4　案例分析：Android Binder 195
7.4.1　背景 195
7.4.2　Binder IPC總覽 196
7.4.3　Binder IPC內(nèi)核設(shè)計 196
7.4.4　匿名共享內(nèi)存 199
7.5　案例分析：ChCore 進程間通信機制 201
7.6　思考題 203
參考文獻 203
第8章　同步原語 206
8.1　互斥鎖 209
8.1.1　臨界區(qū)問題 209
8.1.2　硬件實現(xiàn)：關(guān)閉中斷 211
8.1.3　軟件實現(xiàn)：皮特森算法 211
8.1.4　軟硬件協(xié)同：使用原子操作實現(xiàn)互斥鎖 213
8.2　條件變量 219
8.2.1　條件變量的使用 219
8.2.2　條件變量的實現(xiàn) 222
8.3　信號量 223
8.3.1　信號量的使用 224
8.3.2　信號量的實現(xiàn) 225
8.4　讀寫鎖 229
8.4.1　讀寫鎖的使用 229
8.4.2　讀寫鎖的實現(xiàn) 230
8.5　RCU 233
8.5.1　訂閱/發(fā)布機制 234
8.5.2　寬限期 236
8.6　管程 237
8.7　同步帶來的問題 239
8.7.1　死鎖 239
8.7.2　活鎖 245
8.7.3　優(yōu)先級反轉(zhuǎn) 246
8.8　案例分析：Linux中的futex 249
8.9　案例分析：ChCore中的同步原語 251
8.10　思考題 252
參考文獻 254
第9章　文件系統(tǒng) 256
9.1　基于inode的文件系統(tǒng) 257
9.1.1　inode與文件 258
9.1.2　文件名與目錄 260
9.1.3　硬鏈接與符號鏈接 263
9.1.4　存儲布局 264
9.2　虛擬文件系統(tǒng) 266
9.2.1　面向文件系統(tǒng)的接口 266
9.2.2　面向應(yīng)用程序的接口 270
9.2.3　頁緩存、直接I/O與內(nèi)存映射 277
9.2.4　多種文件系統(tǒng)的組織和管理 280
9.2.5　偽文件系統(tǒng) 282
9.3　其他文件系統(tǒng) 284
9.3.1　FAT文件系統(tǒng) 284
9.3.2　NTFS 288
9.3.3　FUSE與用戶態(tài)文件系統(tǒng) 292
9.4　案例分析：ChCore文件系統(tǒng) 294
9.4.1　ChCore的文件系統(tǒng)架構(gòu) 294
9.4.2　內(nèi)存文件系統(tǒng) 295
9.5　思考題 296
參考文獻 297
第10章　設(shè)備管理 299
10.1　計算機設(shè)備的連接和通信 300
10.1.1　設(shè)備的連接：總線 300
10.1.2　可編程I/O 301
10.1.3　高效數(shù)據(jù)傳輸：DMA 301
10.1.4　設(shè)備地址翻譯：IOMMU 302
10.2　設(shè)備的識別 303
10.2.1　設(shè)備樹 303
10.2.2　ACPI 304
10.3　設(shè)備的中斷處理 305
10.3.1　中斷控制器 305
10.3.2　中斷的基本概念 306
10.3.3　中斷處理：以Linux上下半部的機制為例 308
10.4　設(shè)備驅(qū)動與設(shè)備驅(qū)動模型 313
10.4.1　設(shè)備驅(qū)動 313
10.4.2　設(shè)備驅(qū)動模型 315
10.5　案例分析：Linux設(shè)備驅(qū)動模型 315
10.5.1　Linux的設(shè)備抽象 315
10.5.2　Linux的設(shè)備驅(qū)動模型 318
10.5.3　Linux驅(qū)動的動態(tài)管理 319
10.5.4　Linux的sysfs文件系統(tǒng) 321
10.6　案例分析：L4設(shè)備驅(qū)動模型 322
10.7　案例分析：Linux的用戶態(tài)驅(qū)動框架 323
10.8　思考題 327
參考文獻 327
第11章　系統(tǒng)虛擬化 329
11.1　系統(tǒng)虛擬化技術(shù)概述 330
11.1.1　系統(tǒng)虛擬化及其組成部分 330
11.1.2　虛擬機監(jiān)控器的類型 331
11.2　CPU虛擬化 332
11.2.1　下陷和模擬 333
11.2.2　可虛擬化架構(gòu)與不可虛擬化架構(gòu) 333
11.2.3　解釋執(zhí)行 334
11.2.4　動態(tài)二進制翻譯 335
11.2.5　掃描和翻譯 336
11.2.6　半虛擬化技術(shù) 337
11.2.7　硬件虛擬化技術(shù) 338
11.2.8　小結(jié) 340
11.3　內(nèi)存虛擬化 341
11.3.1　影子頁表機制 343
11.3.2　影子頁表的缺頁異常處理流程 345
11.3.3　直接頁表映射機制 345
11.3.4　兩階段地址翻譯機制 346
11.3.5　換頁和內(nèi)存氣球機制 349
11.3.6　小結(jié) 351
11.4　I/O虛擬化 351
11.4.1　軟件模擬方法 352
11.4.2　半虛擬化方法 354
11.4.3　設(shè)備直通：IOMMU和SR-IOV 356
11.4.4　小結(jié) 359
11.5　中斷虛擬化 360
11.6　案例分析：QEMU/KVM 361
11.6.1　KVM API和一個簡單的虛擬機監(jiān)控器 362
11.6.2　KVM與QEMU 364
11.6.3　KVM內(nèi)部實現(xiàn)簡介 366
11.7　思考題 367
參考文獻 367
縮略語 369
在線章節(jié)一
第二部分　操作系統(tǒng)進階
第12章　多核與多處理器
第13章　文件系統(tǒng)崩潰一致性
第14章　網(wǎng)絡(luò)協(xié)議棧與系統(tǒng)
第15章　輕量級虛擬化
第16章　操作系統(tǒng)安全
第17章　操作系統(tǒng)調(diào)測
第18章　形式化證明
第三部分　ChCore課程實驗
第19章　實驗1：機器啟動
第20章　實驗2：內(nèi)存管理
第21章　實驗3：用戶進程與異常處理
第22章　實驗4：多核處理
第23章　實驗5：文件系統(tǒng)與Shell
第24章　實驗6：進階實踐