CONTENTS
目　　錄
叢書序言
序言一
序言二
前言
第一部分　操作系統(tǒng)基礎(chǔ)
第1章　操作系統(tǒng)概述　2
1.1　簡約不簡單?：從Hello World
說起　2
1.2　什么是操作系統(tǒng)　3
1.3　操作系統(tǒng)簡史　5
1.3.1　GM-NAA I/O?：第一個(gè)
（批處理）操作系統(tǒng)　5
1.3.2　OS/360?：從專用走向通用　6
1.3.3　Multics/UNIX/Linux?：分時(shí)與多任務(wù)　6
1.3.4　macOS/Windows?：以人
為本的人機(jī)交互　7
1.3.5　iOS/Android?：移動互聯(lián)網(wǎng)
時(shí)代的操作系統(tǒng)　8
1.4　操作系統(tǒng)接口　10
1.5　思考題　12
參考文獻(xiàn)　12
第2章　操作系統(tǒng)結(jié)構(gòu)　13
2.1　操作系統(tǒng)的機(jī)制與策略　14
2.2　操作系統(tǒng)復(fù)雜性的管理方法　15
2.3　操作系統(tǒng)內(nèi)核架構(gòu)　17
2.3.1　簡要結(jié)構(gòu)　18
2.3.2　宏內(nèi)核　18
2.3.3　微內(nèi)核　20
2.3.4　外核　22
2.3.5　其他操作系統(tǒng)內(nèi)核架構(gòu)　24
2.4　操作系統(tǒng)框架結(jié)構(gòu)　26
2.4.1　Android系統(tǒng)框架　26
2.4.2　ROS系統(tǒng)框架　28
2.5　操作系統(tǒng)設(shè)計(jì)?：Worse is better？　29
2.6　ChCore?：教學(xué)科研型微內(nèi)核操作系統(tǒng)　31
2.7　思考題　32
參考文獻(xiàn)　32
第3章　硬件環(huán)境與軟件抽象　35
3.1　應(yīng)用程序的硬件運(yùn)行環(huán)境　35
3.1.1　程序的運(yùn)行?：用指令序列
控制處理器　36
3.1.2　處理數(shù)據(jù)?：寄存器、運(yùn)算和訪存　38
3.1.3　條件結(jié)構(gòu)?：程序分支和
條件碼　43
3.1.4　函數(shù)的調(diào)用、返回與�！�46
3.1.5　函數(shù)的調(diào)用慣例　50
3.1.6　小結(jié)?：應(yīng)用程序依賴的
處理器狀態(tài)　52
3.2　操作系統(tǒng)的硬件運(yùn)行環(huán)境　54
3.2.1　特權(quán)級別與系統(tǒng)ISA　54
3.2.2　異常機(jī)制與異常向量表　57
3.2.3　案例分析?：ChCore啟動與
異常向量表初始化　60
3.2.4　用戶態(tài)與內(nèi)核態(tài)的切換　61
3.2.5　系統(tǒng)調(diào)用　64
3.2.6　系統(tǒng)調(diào)用的優(yōu)化　66
3.3　操作系統(tǒng)提供的基本抽象與
接口　67
3.3.1　進(jìn)程?：對處理器的抽象　69
3.3.2　案例分析?：使用POSIX
進(jìn)程接口實(shí)現(xiàn)shell　70
3.3.3　虛擬內(nèi)存?：對內(nèi)存的
抽象　73
3.3.4　進(jìn)程的虛擬內(nèi)存布局　75
3.3.5　文件?：對存儲設(shè)備的
抽象　77
3.3.6　文件?：對所有設(shè)備的
抽象　79
3.4　思考題　80
3.5　練習(xí)答案　81
參考文獻(xiàn)　82
第4章　虛擬內(nèi)存管理　83
4.1　CPU的職責(zé)?：內(nèi)存地址翻譯　84
4.1.1　地址翻譯　84
4.1.2　分頁機(jī)制　85
4.1.3　多級頁表　87
4.1.4　頁表項(xiàng)與大頁　91
4.1.5　TLB?：頁表的緩存　93
4.2　操作系統(tǒng)的職責(zé)?：管理頁表映射　96
4.2.1　操作系統(tǒng)為自己配置頁表　96
4.2.2　如何填寫進(jìn)程頁表　97
4.2.3　何時(shí)填寫進(jìn)程頁表?：立即映射　101
4.2.4　何時(shí)填寫進(jìn)程頁表?：延遲映射　104
4.2.5　常見的改變虛擬內(nèi)存區(qū)域的接口　108
4.2.6　虛擬內(nèi)存擴(kuò)展功能　109
4.3　案例分析?：ChCore虛擬內(nèi)存
管理　112
4.3.1　ChCore內(nèi)核頁表初始化　112
4.3.2　ChCore內(nèi)存管理　115
4.4　思考題　118
4.5　練習(xí)答案　119
參考文獻(xiàn)　121
第5章　物理內(nèi)存管理　122
5.1　操作系統(tǒng)的職責(zé)?：管理物理
內(nèi)存資源　122
5.1.1　目標(biāo)與評價(jià)維度　122
5.1.2　基于位圖的連續(xù)物理頁
分配方法　123
5.1.3　伙伴系統(tǒng)原理　126
5.1.4　案例分析?：ChCore中伙伴
系統(tǒng)的實(shí)現(xiàn)　127
5.1.5　SLAB分配器的基本設(shè)計(jì)　131
5.1.6　常用的空閑鏈表　133
5.2　操作系統(tǒng)如何獲得更多物理內(nèi)存資源　134
5.2.1　換頁機(jī)制　134
5.2.2　頁替換策略　137
5.2.3　頁表項(xiàng)中的訪問位與
頁替換策略實(shí)現(xiàn)　140
5.2.4　工作集模型　141
5.2.5　利用虛擬內(nèi)存抽象節(jié)約物理內(nèi)存資源　142
5.3　性能導(dǎo)向的內(nèi)存分配擴(kuò)展機(jī)制　143
5.3.1　物理內(nèi)存與CPU緩存　144
5.3.2　物理內(nèi)存分配與CPU
緩存　146
5.3.3　多核與內(nèi)存分配　147
5.3.4　CPU緩存的硬件劃分　147
5.3.5　非一致內(nèi)存訪問
（NUMA架構(gòu)）　149
5.3.6　NUMA架構(gòu)與內(nèi)存分配　150
5.4　思考題　151
5.5　練習(xí)答案　152
參考文獻(xiàn)　152
第6章　進(jìn)程與線程　154
6.1　進(jìn)程的內(nèi)部表示與管理接口　154
6.1.1　進(jìn)程的內(nèi)部表示—
PCB　154
6.1.2　進(jìn)程創(chuàng)建的實(shí)現(xiàn)　155
6.1.3　進(jìn)程退出的實(shí)現(xiàn)　159
6.1.4　進(jìn)程等待的實(shí)現(xiàn)　160
6.1.5　exit與waitpid之間的信息傳遞　162
6.1.6　進(jìn)程等待的范圍與父子
進(jìn)程關(guān)系　164
6.1.7　進(jìn)程睡眠的實(shí)現(xiàn)　166
6.1.8　進(jìn)程執(zhí)行狀態(tài)及其管理　166
6.2　案例分析?：ChCore微內(nèi)核的
進(jìn)程管理　169
6.2.1　進(jìn)程管理器與分離式
PCB　169
6.2.2　ChCore的進(jìn)程操作?：
以進(jìn)程創(chuàng)建為例　170
6.3　案例分析?：Linux的進(jìn)程創(chuàng)建　172
6.3.1　經(jīng)典的進(jìn)程創(chuàng)建方法?：
fork　172
6.3.2　其他進(jìn)程創(chuàng)建方法　175
6.4　進(jìn)程切換　179
6.4.1　進(jìn)程的處理器上下文　180
6.4.2　進(jìn)程的切換節(jié)點(diǎn)　180
6.4.3　進(jìn)程切換的全過程　181
6.4.4　案例分析?：ChCore的
進(jìn)程切換實(shí)現(xiàn)　182
6.5　線程及其實(shí)現(xiàn)　191
6.5.1　為什么需要線程　191
6.5.2　用戶視角看線程　192
6.5.3　線程的實(shí)現(xiàn)?：內(nèi)核數(shù)據(jù)
結(jié)構(gòu)　194
6.5.4　線程的實(shí)現(xiàn)?：管理接口　195
6.5.5　線程切換　200
6.5.6　內(nèi)核態(tài)線程與用戶態(tài)
線程　200
6.6　纖程　202
6.6.1　對纖程的需求?：一個(gè)簡單的例子　203
6.6.2　POSIX的纖程支持?：ucontext　204
6.6.3　纖程切換　206
6.7　思考題　207
6.8　練習(xí)答案　208
參考文獻(xiàn)　209
第7章　處理器調(diào)度　210
7.1　處理器調(diào)度機(jī)制　210
7.1.1　處理器調(diào)度對象　211
7.1.2　處理器調(diào)度概覽　211
7.2　處理器調(diào)度指標(biāo)　214
7.3　經(jīng)典調(diào)度策略　216
7.3.1　先到先得　216
7.3.2　短任務(wù)優(yōu)先　218
7.3.3　短完成時(shí)間優(yōu)先　219
7.3.4　時(shí)間片輪轉(zhuǎn)　220
7.3.5　經(jīng)典調(diào)度策略的比較　221
7.4　優(yōu)先級調(diào)度策略　222
7.4.1　高響應(yīng)比優(yōu)先　223
7.4.2　多級隊(duì)列與多級反饋
隊(duì)列　223
7.4.3　優(yōu)先級調(diào)度策略的比較　229
7.5　公平共享調(diào)度策略　229
7.5.1　彩票調(diào)度　231
7.5.2　步幅調(diào)度　233
7.5.3　份額與優(yōu)先級的比較　235
7.6　多核處理器調(diào)度機(jī)制　236
7.6.1　運(yùn)行隊(duì)列　236
7.6.2　負(fù)載均衡與負(fù)載追蹤　237
7.6.3　處理器親和性　238
7.7　案例分析?：Linux調(diào)度器　239
7.7.1　O（N）調(diào)度器　240
7.7.2　O（1）調(diào)度器　241
7.7.3　完全公平調(diào)度器　242
7.7.4　Linux的細(xì)粒度負(fù)載
追蹤　244
7.7.5　Linux的NUMA感知
調(diào)度　245
7.8　思考題　246
7.9　練習(xí)答案　247
參考文獻(xiàn)　248
第8章　進(jìn)程間通信　249
8.1　進(jìn)程間通信基礎(chǔ)　250
8.1.1　進(jìn)程間通信接口　250
8.1.2　一個(gè)簡單的進(jìn)程間通信
設(shè)計(jì)　253
8.1.3　數(shù)據(jù)傳遞　255
8.1.4　通知機(jī)制　257
8.1.5　單向和雙向　257
8.1.6　同步和異步　258
8.1.7　超時(shí)機(jī)制　259
8.1.8　通信連接　260
8.1.9　權(quán)限檢查　261
8.1.10　命名服務(wù)　262
8.1.11　總結(jié)　263
8.2　文件接口IPC?：管道　264
8.2.1　Linux管道使用案例　265
8.2.2　Linux中管道進(jìn)程間通信的實(shí)現(xiàn)　267
8.2.3　命名管道和匿名管道　269
8.3　內(nèi)存接口IPC?：共享內(nèi)存　270
8.3.1　共享內(nèi)存　270
8.3.2　基于共享內(nèi)存的進(jìn)程間
通信　272
8.4　消息接口IPC?：消息隊(duì)列　273
8.4.1　消息隊(duì)列的結(jié)構(gòu)　274
8.4.2　基本操作　274
8.5　案例分析?：L4微內(nèi)核的IPC
優(yōu)化　275
8.5.1　L4消息傳遞　275
8.5.2　L4控制流轉(zhuǎn)移　277
8.5.3　L4通信連接　279
8.5.4　L4通信控制（權(quán)限
檢查）　279
8.6　案例分析?：LRPC的遷移線程
模型　280
8.6.1　遷移線程模型　281
8.6.2　LRPC設(shè)計(jì)　281
8.7　案例分析?：ChCore進(jìn)程間
通信機(jī)制　283
8.8　案例分析?：Binder IPC　285
8.8.1　總覽　286
8.8.2　Binder IPC內(nèi)核
設(shè)計(jì)　286
8.8.3　匿名共享內(nèi)存　290
8.9　思考題　291
8.10　練習(xí)答案　292
參考文獻(xiàn)　292
第9章　并發(fā)與同步　294
9.1　同步場景　295
9.1.1　一個(gè)例子?：多線程
計(jì)數(shù)器　295
9.1.2　同步的典型場景　297
9.2　同步原語　299
9.2.1　互斥鎖　300
9.2.2　讀寫鎖　302
9.2.3　條件變量　304
9.2.4　信號量　313
9.2.5　同步原語的比較　316
9.3　死鎖　318
9.3.1　死鎖的定義　318
9.3.2　死鎖檢測與恢復(fù)　320
9.3.3　死鎖預(yù)防　321
9.3.4　死鎖避免　322
9.3.5　哲學(xué)家問題　325
9.4　活鎖　326
9.5　思考題　327
9.6　練習(xí)答案　330
參考文獻(xiàn)　335
第10章　同步原語的實(shí)現(xiàn)　336
10.1　互斥鎖的實(shí)現(xiàn)　336
10.1.1　臨界區(qū)問題　336
10.1.2　硬件實(shí)現(xiàn)?：關(guān)閉中斷　337
10.1.3　軟件實(shí)現(xiàn)?：皮特森
算法　337
10.1.4　軟硬件協(xié)同?：使用原子
操作實(shí)現(xiàn)互斥鎖　340
10.2　條件變量的實(shí)現(xiàn)　345
10.3　信號量的實(shí)現(xiàn)　346
10.3.1　非阻塞信號量　347
10.3.2　阻塞信號量　348
10.4　讀寫鎖的實(shí)現(xiàn)　352
10.4.1　偏向讀者的讀寫鎖　353
10.4.2　偏向?qū)懻叩淖x寫鎖　354
10.5　案例分析?：Linux中的futex　356
10.6　案例分析?：微內(nèi)核中的同步
原語　360
10.7　思考題　361
10.8　練習(xí)答案　364
參考文獻(xiàn)　364
第11章　文件系統(tǒng)　366
11.1　基于inode的文件系統(tǒng)　367
11.1.1　一個(gè)不用inode的簡單
文件系統(tǒng)　367
11.1.2　inode與文件　368
11.1.3　多級inode　370
11.1.4　文件名與目錄　374
11.1.5　存儲布局　377
11.1.6　從文件名到鏈接　378
11.1.7　符號鏈接（軟鏈接）　381
11.2　基于表的文件系統(tǒng)　382
11.2.1　FAT文件系統(tǒng)　382
11.2.2　NTFS　386
11.3　虛擬文件系統(tǒng)　392
11.3.1　文件系統(tǒng)的內(nèi)存結(jié)構(gòu)　392
11.3.2　面向文件系統(tǒng)的接口　394
11.3.3　多文件系統(tǒng)的組織和
管理　398
11.3.4　偽文件系統(tǒng)　400
11.4　VFS與緩存　402
11.4.1　訪問粒度不一致問題和
一些優(yōu)化　402
11.4.2　讀緩存　403
11.4.3　寫緩沖區(qū)與寫合并　403
11.4.4　頁緩存　403
11.4.5　直接I/O和緩存I/O　404
11.4.6　內(nèi)存映射　405
11.5　用戶態(tài)文件系統(tǒng)　405
11.5.1　為什么需要用戶態(tài)文件系統(tǒng)　406
11.5.2　FUSE　406
11.5.3　ChCore的文件系統(tǒng)
架構(gòu)　407
11.6　思考題　410
11.7　練習(xí)答案　411
參考文獻(xiàn)　412
第12章　文件系統(tǒng)崩潰一致性　414
12.1　崩潰一致性　415
12.2　同步寫入與文件系統(tǒng)一致性
檢查　417
12.2.1　同步寫入　417
12.2.2　文件系統(tǒng)一致性檢查　418
12.2.3　fsck的局限和問題　420
12.3　原子更新技術(shù)?：日志　421
12.3.1　日志機(jī)制的原理　421
12.3.2　日志的批量化與合并
優(yōu)化　423
12.3.3　日志應(yīng)用實(shí)例?：JBD2　423
12.3.4　討論和小結(jié)　427
12.4　原子更新技術(shù)?：寫時(shí)拷貝　427
12.4.1　寫時(shí)拷貝的原理　428
12.4.2　寫時(shí)拷貝在文件系統(tǒng)
中的應(yīng)用　429
12.4.3　寫時(shí)拷貝的問題與
優(yōu)化　430
12.4.4　討論和小結(jié)　430
12.5　Soft updates　431
12.5.1　Soft updates的三條
規(guī)則　432
12.5.2　依賴追蹤　434
12.5.3　撤銷和重做　435
12.5.4　文件系統(tǒng)恢復(fù)　437
12.5.5　討論和小結(jié)　437
12.6　案例分析?：日志結(jié)構(gòu)文件系統(tǒng)　438
12.6.1　基本概念與空間布局　438
12.6.2　數(shù)據(jù)訪問與操作　439
12.6.3　基于段的空間管理　441
12.6.4　檢查點(diǎn)和前滾　444
12.6.5　小結(jié)　446
12.7　思考題　446
參考文獻(xiàn)　447
第13章　設(shè)備管理　449
13.1　硬件設(shè)備基礎(chǔ)　450
13.1.1　總線互聯(lián)　451
13.1.2　設(shè)備的硬件接口　452
13.1.3　幾種常見的設(shè)備　452
13.2　設(shè)備發(fā)現(xiàn)與交互　457
13.2.1　CPU與設(shè)備的交互方式概覽　458
13.2.2　設(shè)備發(fā)現(xiàn)　460
13.2.3　設(shè)備寄存器的訪問　463
13.2.4　中斷　466
13.2.5　直接內(nèi)存訪問　470
13.3　設(shè)備管理的共性功能　475
13.3.1　設(shè)備的文件抽象　475
13.3.2　設(shè)備的邏輯分類　477
13.3.3　設(shè)備的緩沖區(qū)管理　478
13.3.4　設(shè)備的使用接口　482
13.4　應(yīng)用I/O框架　484
13.4.1　應(yīng)用層I/O庫　484
13.4.2　用戶態(tài)I/O　486
13.5　案例分析?：Android操作系統(tǒng)的
硬件抽象層　488
13.6　思考題　490
13.7　練習(xí)答案　491
參考文獻(xiàn)　491
第14章　系統(tǒng)虛擬化　493
14.1　系統(tǒng)虛擬化技術(shù)概述　494
14.1.1　系統(tǒng)虛擬化及其組成
部分　494
14.1.2　虛擬機(jī)監(jiān)控器的類型　495
14.2　“下陷-模擬”方法　496
14.2.1　版本零?：用進(jìn)程模擬
虛擬機(jī)內(nèi)核態(tài)　497
14.2.2　版本一?：模擬時(shí)鐘
中斷　498
14.2.3　版本二?：模擬用戶態(tài)與
系統(tǒng)調(diào)用　500
14.2.4　版本三?：虛擬機(jī)內(nèi)支持
多個(gè)用戶態(tài)線程　501
14.2.5　版本四?：用線程模擬
多個(gè)vCPU　502
14.2.6　小結(jié)　504
14.3　CPU虛擬化　505
14.3.1　可虛擬化架構(gòu)與不可
虛擬化架構(gòu)　505
14.3.2　解釋執(zhí)行　506
14.3.3　動態(tài)二進(jìn)制翻譯　507
14.3.4　掃描-翻譯　508
14.3.5　半虛擬化技術(shù)　509
14.3.6　硬件虛擬化技術(shù)　509
14.3.7　小結(jié)　512
14.4　內(nèi)存虛擬化　513
14.4.1　影子頁表機(jī)制　514
14.4.2　直接頁表映射機(jī)制　517
14.4.3　兩階段地址翻譯機(jī)制　518
14.4.4　換頁和氣球機(jī)制　521
14.4.5　小結(jié)　523
14.5　I/O虛擬化　523
14.5.1　軟件模擬方法　524
14.5.2　半虛擬化方法　526
14.5.3　設(shè)備直通方法?：IOMMU
和SR-IOV　528
14.5.4　小結(jié)　531
14.6　中斷虛擬化　532
14.7　案例分析?：QEMU/KVM　534
14.7.1　KVM API和一個(gè)簡單的
虛擬機(jī)監(jiān)控器　534
14.7.2　KVM和QEMU　536
14.7.3　KVM內(nèi)部實(shí)現(xiàn)簡介　538
14.8　思考題　539
參考文獻(xiàn)　540
縮略語　541
在線章節(jié)
第二部分　操作系統(tǒng)進(jìn)階
第15章　多核與多處理器
第16章　可擴(kuò)展同步原語
第17章　多場景文件系統(tǒng)
第18章　存儲系統(tǒng)
第19章　輕量級虛擬化
第20章　網(wǎng)絡(luò)與系統(tǒng)
第21章　操作系統(tǒng)安全
第22章　操作系統(tǒng)調(diào)測
第23章　形式化證明
第24章　云操作系統(tǒng)
第三部分　ChCore課程實(shí)驗(yàn)
實(shí)驗(yàn)1：機(jī)器啟動
實(shí)驗(yàn)2：內(nèi)存管理
實(shí)驗(yàn)3：進(jìn)程與線程、異常處理
實(shí)驗(yàn)4：多核、多進(jìn)程、調(diào)度與IPC
實(shí)驗(yàn)5：文件系統(tǒng)與shell
實(shí)驗(yàn)6：設(shè)備驅(qū)動與持久化
實(shí)驗(yàn)7：進(jìn)階實(shí)踐