操作系統(tǒng)設(shè)計：Xinu方法（原書第2版）

出版者的話
譯者序
前言
關(guān)于作者
第1章　引言和概述1
1.1　操作系統(tǒng)1
1.2　本書的研究方法2
1.3　分層設(shè)計2
1.4　Xinu操作系統(tǒng)4
1.5　操作系統(tǒng)的界定4
1.6　從外部看操作系統(tǒng)5
1.7　其他章節(jié)概要6
1.8　觀點6
1.9　總結(jié)7
練習7
第2章　并發(fā)執(zhí)行與操作系統(tǒng)服務(wù)8
2.1　引言8
2.2　多活動的編程模型8
2.3　操作系統(tǒng)服務(wù)9
2.4　并發(fā)處理的概念和術(shù)語9
2.5　串行程序和并發(fā)程序的區(qū)別11
2.6　多個進程共享同一段代碼12
2.7　進程退出與進程終止14
2.8　共享內(nèi)存、競爭條件和同步14
2.9　信號量與互斥18
2.10　Xinu中的類型命名方法19
2.11　使用kputc和kprintf進行操作系統(tǒng)的調(diào)試20
2.12　觀點20
2.13　總結(jié)21
練習21
第3章　硬件與運行時環(huán)境概述22
3.1　引言22
3.2　開發(fā)平臺的物理和邏輯架構(gòu)22
3.3　指令集23
3.4　通用寄存器23
3.5　I/O總線和存-取范例24
3.6　DMA機制25
3.7　總線地址空間25
3.8　總線啟動和配置26
3.9　函數(shù)調(diào)用約定和運行時棧26
3.10　中斷和中斷處理28
3.11　中斷向量29
3.12　異常向量和異常處理29
3.13　時鐘硬件29
3.14　串行通信30
3.15　輪詢與中斷驅(qū)動I/O30
3.16　存儲布局30
3.17　內(nèi)存保護31
3.18　硬件細節(jié)和片上系統(tǒng)體系結(jié)構(gòu)31
3.19　觀點31
3.20　硬件參考資料32
練習32
第4章　鏈表與隊列操作33
4.1　引言33
4.2　進程鏈表的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)33
4.3　簡潔的鏈表數(shù)據(jù)結(jié)構(gòu)34
4.4　隊列數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)35
4.5　內(nèi)聯(lián)隊列操作函數(shù)36
4.6　獲取鏈表中進程的基礎(chǔ)函數(shù)37
4.7　FIFO隊列操作38
4.8　優(yōu)先級隊列的操作40
4.9　鏈表初始化42
4.10　觀點43
4.11　總結(jié)43
練習43
第5章　調(diào)度和上下文切換45
5.1　引言45
5.2　進程表45
5.3　進程狀態(tài)47
5.4　就緒和當前狀態(tài)48
5.5　調(diào)度策略48
5.6　調(diào)度的實現(xiàn)49
5.7　推遲重新調(diào)度52
5.8　上下文切換的實現(xiàn)52
5.9　內(nèi)存中保存的狀態(tài)52
5.10　上下文切換操作53
5.11　重新啟動進程執(zhí)行的地址56
5.12　并發(fā)執(zhí)行和空進程57
5.13　使進程就緒和調(diào)度常量57
5.14　其他進程調(diào)度算法58
5.15　觀點58
5.16　總結(jié)59
練習59
第6章　更多進程管理60
6.1　引言60
6.2　進程掛起和恢復(fù)60
6.3　自我掛起和信息隱藏60
6.4　系統(tǒng)調(diào)用61
6.5　禁止和恢復(fù)中斷62
6.6　系統(tǒng)調(diào)用模板63
6.7　系統(tǒng)調(diào)用返回值SYSERR和OK63
6.8　掛起的實現(xiàn)64
6.9　掛起當前進程65
6.10　suspend函數(shù)的返回值65
6.11　進程終止和進程退出66
6.12　進程創(chuàng)建68
6.13　其他進程管理函數(shù)72
6.14　總結(jié)74
練習74
第7章　協(xié)調(diào)并發(fā)進程76
7.1　引言76
7.2　進程同步的必要性76
7.3　計數(shù)信號量的概念77
7.4　避免忙等待77
7.5　信號量策略和進程選擇77
7.6　等待狀態(tài)78
7.7　信號量數(shù)據(jù)結(jié)構(gòu)79
7.8　系統(tǒng)調(diào)用wait79
7.9　系統(tǒng)調(diào)用signal80
7.10　靜態(tài)和動態(tài)信號量分配81
7.11　動態(tài)信號量的實現(xiàn)示例82
7.12　信號量刪除83
7.13　信號量重置84
7.14　并行處理器（多核）之間的協(xié)調(diào)85
7.15　觀點86
7.16　總結(jié)86
練習87
第8章　消息傳遞88
8.1　引言88
8.2　兩種類型的消息傳遞服務(wù)88
8.3　消息使用資源的限制89
8.4　消息傳遞函數(shù)和狀態(tài)轉(zhuǎn)換89
8.5　send的實現(xiàn)90
8.6　receive的實現(xiàn)91
8.7　非阻塞消息接收的實現(xiàn)92
8.8　觀點92
8.9　總結(jié)92
練習93
第9章　基本內(nèi)存管理94
9.1　引言94
9.2　內(nèi)存的類型94
9.3　重量級進程的定義95
9.4　示例系統(tǒng)的內(nèi)存管理95
9.5　程序段和內(nèi)存區(qū)域95
9.6　動態(tài)內(nèi)存分配96
9.7　底層內(nèi)存管理器的設(shè)計97
9.8　分配策略和內(nèi)存持久性97
9.9　追蹤空閑內(nèi)存98
9.10　底層內(nèi)存管理的實現(xiàn)98
9.11　使用空閑內(nèi)存的數(shù)據(jù)結(jié)構(gòu)定義99
9.12　分配堆存儲100
9.13　分配棧存儲102
9.14　堆和棧存儲的釋放103
9.15　觀點105
9.16　總結(jié)106
練習106
第10章　高級內(nèi)存管理和虛擬內(nèi)存107
10.1　引言107
10.2　分區(qū)空間分配107
10.3　緩沖池108
10.4　分配緩沖區(qū)108
10.5　將緩沖區(qū)返還給緩沖池110
10.6　創(chuàng)建緩沖池111
10.7　初始化緩沖池表112
10.8　虛擬內(nèi)存和內(nèi)存復(fù)用113
10.9　實地址空間和虛地址空間113
10.10　支持按需分頁的硬件114
10.11　使用頁表的地址轉(zhuǎn)換114
10.12　頁表項中的元數(shù)據(jù)115
10.13　按需分頁以及設(shè)計上的問題116
10.14　頁面替換和全局時鐘算法116
10.15　觀點117
10.16　總結(jié)117
練習118
第11章　高層消息傳遞119
11.1　引言119
11.2　進程間通信端口119
11.3　端口實現(xiàn)119
11.4　端口表初始化120
11.5　端口創(chuàng)建121
11.6　向端口發(fā)送消息122
11.7　從端口接收消息124
11.8　端口的刪除和重置125
11.9　觀點128
11.10　總結(jié)128
練習128
第12章　中斷處理130
12.1　引言130
12.2　中斷的優(yōu)點130
12.3　中斷處理130
12.4　中斷向量131
12.5　中斷和異常集成131
12.6　使用代碼的ARM異常向量132
12.7　設(shè)備中斷向量號的分配135
12.8　中斷分派136
12.9　中斷的軟件結(jié)構(gòu)137
12.10　禁止中斷139
12.11　中斷代碼調(diào)用函數(shù)的限制140
12.12　中斷過程中重新調(diào)度的必要性140
12.13　中斷過程中的重新調(diào)度140
12.14　觀點141
12.15　總結(jié)142
練習142
第13章　實時時鐘管理143
13.1　引言143
13.2　定時事件143
13.3　實時時鐘和計時器硬件143
13.4　實時時鐘中斷處理144
13.5　延時與搶占145
13.6　搶占的實現(xiàn)145
13.7　使用增量鏈表對延遲進行有效管理146
13.8　增量鏈表的實現(xiàn)147
13.9　將進程轉(zhuǎn)入睡眠148
13.10　定時消息接收150
13.11　喚醒睡眠進程154
13.12　時鐘中斷處理154
13.13　時鐘初始化156
13.14　觀點159
13.15　總結(jié)159
練習159
第14章　設(shè)備無關(guān)的I/O161
14.1　引言161
14.2　I/O和設(shè)備驅(qū)動的概念結(jié)構(gòu)161
14.3　接口抽象和驅(qū)動抽象162
14.4　I/O接口示例163
14.5　打開-讀-寫-關(guān)閉范例163
14.6　綁定I/O操作和設(shè)備名164
14.7　Xinu中的設(shè)備名164
14.8　設(shè)備轉(zhuǎn)換表概念165
14.9　設(shè)備的多個副本和共享驅(qū)動166
14.10　高層I/O操作的實現(xiàn)168
14.11　其他高層I/O函數(shù)169
14.12　打開、關(guān)閉和引用計數(shù)172
14.13　devtab中的空條目和錯誤條目174
14.14　I/O系統(tǒng)的初始化174
14.15　觀點178
14.16　總結(jié)179
練習179
第15章　設(shè)備驅(qū)動示例180
15.1　引言180
15.2　使用UART硬件進行串行通信180
15.3　tty抽象180
15.4　tty設(shè)備驅(qū)動的組織結(jié)構(gòu)181
15.5　請求隊列和緩沖區(qū)182
15.6　上半部和下半部的同步183
15.7　UART硬件FIFO與驅(qū)動設(shè)計184
15.8　控制塊的概念184
15.9　tty控制塊和數(shù)據(jù)聲明184
15.10　次設(shè)備號186
15.11　上半部tty字符輸入（ttygetc）187
15.12　上半部tty讀取函數(shù)（ttyread）188
15.13　上半部tty字符輸出（ttyputc）189
15.14　開始輸出（ttykickout）190
15.15　上半部tty多字符輸出（ttywrite）191
15.16　下半部tty驅(qū)動函數(shù)（ttyhandler）192
15.17　輸出中斷處理（ttyhandle_out）194
15.18　tty輸入處理（ttyhandle_in）196
15.19　tty控制塊初始化（ttyinit）202
15.20　設(shè)備驅(qū)動控制（ttycontrol）204
15.21　觀點205
15.22　總結(jié)205
練習206
第16章　DMA設(shè)備和驅(qū)動（以太網(wǎng)）207
16.1　引言207
16.2　直接內(nèi)存訪問和緩沖區(qū)207
16.3　多個緩沖區(qū)和緩沖區(qū)環(huán)207
16.4　使用DMA的以太網(wǎng)驅(qū)動示例208
16.5　設(shè)備的硬件定義和常量209
16.6　環(huán)和內(nèi)存緩沖區(qū)211
16.7　以太網(wǎng)控制塊的定義213
16.8　設(shè)備和驅(qū)動初始化215
16.9　從以太網(wǎng)設(shè)備讀取數(shù)據(jù)包221
16.10　向以太網(wǎng)設(shè)備寫入數(shù)據(jù)包223
16.11　以太網(wǎng)設(shè)備的中斷處理225
16.12　以太網(wǎng)控制函數(shù)228
16.13　觀點229
16.14　總結(jié)229
練習229
第17章　最小互聯(lián)網(wǎng)協(xié)議棧230
17.1　引言230
17.2　所需的功能230
17.3　同步會話、超時和網(wǎng)絡(luò)處理進程231
17.4　設(shè)計的影響232
17.5　ARP函數(shù)232
17.6　網(wǎng)絡(luò)數(shù)據(jù)包的定義241
17.7　網(wǎng)絡(luò)輸入進程242
17.8　IP的相關(guān)定義245
17.9　IP函數(shù)246
17.10　UDP表的定義255
17.11　UDP函數(shù)256
17.12　互聯(lián)網(wǎng)控制報文協(xié)議267
17.13　動態(tài)主機配置協(xié)議268
17.14　觀點275
17.15　總結(jié)275
練習275
第18章　遠程磁盤驅(qū)動277
18.1　引言277
18.2　磁盤抽象277
18.3　磁盤驅(qū)動支持的操作277
18.4　塊傳輸和高層I/O函數(shù)277
18.5　遠程磁盤范例278
18.6　高速緩存的重要概念278
18.7　磁盤操作的語義279
18.8　驅(qū)動數(shù)據(jù)結(jié)構(gòu)的定義280
18.9　驅(qū)動初始化（rdsinit）284
18.10　上半部打開函數(shù)（rdsopen）287
18.11　遠程通信函數(shù)（rdscomm）289
18.12　上半部寫函數(shù)（rdswrite）291
18.13　上半部讀函數(shù)（rdsread）293
18.14　刷新掛起的請求296
18.15　上半部控制函數(shù)（rdscontrol）297
18.16　分配磁盤緩沖區(qū)（rdsbufalloc）299
18.17　上半部關(guān)閉函數(shù)（rdsclose）300
18.18　下半部通信進程（rdsprocess）302
18.19　觀點306
18.20　總結(jié)306
練習306
第19章　文件系統(tǒng)308
19.1　什么是文件系統(tǒng)308
19.2　文件操作的示例集308
19.3　本地文件系統(tǒng)的設(shè)計309
19.4　Xinu文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)309
19.5　索引管理器的實現(xiàn)310
19.6　清空索引塊（lfibclear）314
19.7　獲取索引塊（lfibget）315
19.8　存儲索引塊（lfibput）315
19.9　從空閑鏈表中分配索引塊（lfiballoc）316
19.10　從空閑鏈表中分配數(shù)據(jù)塊（lfdballoc）317
19.11　使用設(shè)備無關(guān)的I/O函數(shù)進行文件操作319
19.12　文件系統(tǒng)的設(shè)備配置和函數(shù)名稱320
19.13　本地文件系統(tǒng)打開函數(shù)（lfsopen）320
19.14　關(guān)閉文件偽設(shè)備（lflclose）326
19.15　刷新磁盤中的數(shù)據(jù)（lfflush）328
19.16　文件的批量傳輸函數(shù)（lflwrite、lflread）328
19.17　在文件中查找新位置（lflseek）330
19.18　從文件中提取一字節(jié)（lflgetc）331
19.19　改變文件中的一字節(jié)（lflputc）332
19.20　載入索引塊和數(shù)據(jù)塊（lfsetup）334
19.21　主文件系統(tǒng)設(shè)備的初始化（lfsinit）337
19.22　偽設(shè)備的初始化（lflinit）338
19.23　文件截斷（lftruncate）339
19.24　初始文件系統(tǒng)的創(chuàng)建（lfscreate）341
19.25　觀點343
19.26　總結(jié)343
練習343
第20章　遠程文件機制345
20.1　引言345
20.2　遠程文件訪問345
20.3　遠程文件語義345
20.4　遠程文件設(shè)計和消息346
20.5　遠程文件服務(wù)器通信（rfscomm）352
20.6　發(fā)送基本消息（rfsndmsg）354
20.7　網(wǎng)絡(luò)字節(jié)序355
20.8　使用設(shè)備范例的遠程文件系統(tǒng)355
20.9　打開遠程文件（rfsopen）356
20.10　檢查文件模式（rfsgetmode）359
20.11　關(guān)閉遠程文件（rflclose）360
20.12　讀遠程文件（rflread）361
20.13　寫遠程文件（rflwrite）363
20.14　遠程文件的定位（rflseek）365
20.15　遠程文件單字符I/O（rflgetc、rflputc）366
20.16　遠程文件系統(tǒng)控制函數(shù)（rfscontrol）367
20.17　初始化遠程文件系統(tǒng)（rfsinit、rflinit）370
20.18　觀點372
20.19　總結(jié)372
練習372
第21章　句法名字空間374
21.1　引言374
21.2　透明與名字空間抽象374
21.3　多種命名方案375
21.4　命名系統(tǒng)設(shè)計的其他方案376
21.5　基于句法的名字空間376
21.6　模式和替換376
21.7　前綴模式377
21.8　名字空間的實現(xiàn)377
21.9　名字空間的數(shù)據(jù)結(jié)構(gòu)和常量377
21.10　增加名字空間前綴表的映射378
21.11　使用前綴表進行名字映射379
21.12　打開命名文件383
21.13　名字空間初始化383
21.14　對前綴表中的項進行排序386
21.15　選擇邏輯名字空間386
21.16　默認層次和空前綴387
21.17　額外的對象操作函數(shù)387
21.18　名字空間方法的優(yōu)點和限制388
21.19　廣義模式388
21.20　觀點389
21.21　總結(jié)389
練習390
第22章　系統(tǒng)初始化391
22.1　引言391
22.2　引導(dǎo)程序：從零開始391
22.3　一個通過網(wǎng)絡(luò)啟動的例子392
22.4　操作系統(tǒng)初始化392
22.5　Xinu初始化393
22.6　Xinu系統(tǒng)啟動395
22.7　從程序轉(zhuǎn)化為進程399
22.8　觀點399
22.9　總結(jié)399
練習400
第23章　子系統(tǒng)初始化和內(nèi)存標記401
23.1　引言401
23.2　自初始化模塊401
23.3　并發(fā)系統(tǒng)中的自初始化模塊402
23.4　重新啟動后的自初始化403
23.5　使用登錄號初始化404
23.6　廣義內(nèi)存標記方案405
23.7　內(nèi)存標記系統(tǒng)的數(shù)據(jù)聲明406
23.8　標記的實現(xiàn)407
23.9　觀點408
23.10　總結(jié)408
練習408
第24章　異常處理409
24.1　引言409
24.2　術(shù)語：故障、檢測、陷阱和異常409
24.3　向量異常和可屏蔽中斷 409
24.4　異常的類型410
24.5　處理異常410
24.6　異常向量初始化411
24.7　面對災(zāi)難時的panic411
24.8　panic函數(shù)的實現(xiàn)411
24.9　觀點412
24.10　總結(jié)412
練習412
第25章　系統(tǒng)配置413
25.1　引言413
25.2　多重配置的需求413
25.3　Xinu系統(tǒng)配置414
25.4　Xinu配置文件的內(nèi)容414
25.5　計算次設(shè)備號416
25.6　配置Xinu系統(tǒng)的步驟417
25.7　觀點417
25.8　總結(jié)417
練習417
第26章　一個用戶接口例子：Xinu shell419
26.1　引言419
26.2　什么是用戶接口419
26.3　命令和設(shè)計原則419
26.4　一個簡化shell的設(shè)計決策420
26.5　shell的組織和操作420
26.6　詞法符號的定義421
26.7　命令行語法的定義421
26.8　Xinu shell的實現(xiàn)422
26.9　符號的存儲424
26.10　詞法分析器代碼424
26.11　命令解釋器的核心428
26.12　命令名查詢和內(nèi)部處理434
26.13　傳遞給命令的參數(shù)435
26.14　向外部命令傳遞參數(shù)435
26.15　I/O重定向438
26.16　命令函數(shù)（sleep）的例子439
26.17　觀點440
26.18　總結(jié)441
練習441
附錄1　操作系統(tǒng)移植443
附錄2　Xinu設(shè)計注解450
索引454