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

出版者的話
譯者序
前言
關(guān)于作者
第1章　引言和概述1
1.1　操作系統(tǒng)1
1.2　本書的研究方法2
1.3　分層設(shè)計(jì)2
1.4　Xinu操作系統(tǒng)4
1.5　操作系統(tǒng)的界定4
1.6　從外部看操作系統(tǒng)5
1.7　其他章節(jié)概要6
1.8　觀點(diǎn)6
1.9　總結(jié)7
練習(xí)7
第2章　并發(fā)執(zhí)行與操作系統(tǒng)服務(wù)8
2.1　引言8
2.2　多活動(dòng)的編程模型8
2.3　操作系統(tǒng)服務(wù)9
2.4　并發(fā)處理的概念和術(shù)語9
2.5　串行程序和并發(fā)程序的區(qū)別11
2.6　多個(gè)進(jìn)程共享同一段代碼12
2.7　進(jìn)程退出與進(jìn)程終止14
2.8　共享內(nèi)存、競爭條件和同步14
2.9　信號量與互斥18
2.10　Xinu中的類型命名方法19
2.11　使用kputc和kprintf進(jìn)行操作系統(tǒng)的調(diào)試20
2.12　觀點(diǎn)20
2.13　總結(jié)21
練習(xí)21
第3章　硬件與運(yùn)行時(shí)環(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機(jī)制25
3.7　總線地址空間25
3.8　總線啟動(dòng)和配置26
3.9　函數(shù)調(diào)用約定和運(yùn)行時(shí)棧26
3.10　中斷和中斷處理28
3.11　中斷向量29
3.12　異常向量和異常處理29
3.13　時(shí)鐘硬件29
3.14　串行通信30
3.15　輪詢與中斷驅(qū)動(dòng)I/O30
3.16　存儲布局30
3.17　內(nèi)存保護(hù)31
3.18　硬件細(xì)節(jié)和片上系統(tǒng)體系結(jié)構(gòu)31
3.19　觀點(diǎn)31
3.20　硬件參考資料32
練習(xí)32
第4章　鏈表與隊(duì)列操作33
4.1　引言33
4.2　進(jìn)程鏈表的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)33
4.3　簡潔的鏈表數(shù)據(jù)結(jié)構(gòu)34
4.4　隊(duì)列數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)35
4.5　內(nèi)聯(lián)隊(duì)列操作函數(shù)36
4.6　獲取鏈表中進(jìn)程的基礎(chǔ)函數(shù)37
4.7　FIFO隊(duì)列操作38
4.8　優(yōu)先級隊(duì)列的操作40
4.9　鏈表初始化42
4.10　觀點(diǎn)43
4.11　總結(jié)43
練習(xí)43
第5章　調(diào)度和上下文切換45
5.1　引言45
5.2　進(jìn)程表45
5.3　進(jìn)程狀態(tài)47
5.4　就緒和當(dāng)前狀態(tài)48
5.5　調(diào)度策略48
5.6　調(diào)度的實(shí)現(xiàn)49
5.7　推遲重新調(diào)度52
5.8　上下文切換的實(shí)現(xiàn)52
5.9　內(nèi)存中保存的狀態(tài)52
5.10　上下文切換操作53
5.11　重新啟動(dòng)進(jìn)程執(zhí)行的地址56
5.12　并發(fā)執(zhí)行和空進(jìn)程57
5.13　使進(jìn)程就緒和調(diào)度常量57
5.14　其他進(jìn)程調(diào)度算法58
5.15　觀點(diǎn)58
5.16　總結(jié)59
練習(xí)59
第6章　更多進(jìn)程管理60
6.1　引言60
6.2　進(jìn)程掛起和恢復(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　掛起的實(shí)現(xiàn)64
6.9　掛起當(dāng)前進(jìn)程65
6.10　suspend函數(shù)的返回值65
6.11　進(jìn)程終止和進(jìn)程退出66
6.12　進(jìn)程創(chuàng)建68
6.13　其他進(jìn)程管理函數(shù)72
6.14　總結(jié)74
練習(xí)74
第7章　協(xié)調(diào)并發(fā)進(jìn)程76
7.1　引言76
7.2　進(jìn)程同步的必要性76
7.3　計(jì)數(shù)信號量的概念77
7.4　避免忙等待77
7.5　信號量策略和進(jìn)程選擇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)和動(dòng)態(tài)信號量分配81
7.11　動(dòng)態(tài)信號量的實(shí)現(xiàn)示例82
7.12　信號量刪除83
7.13　信號量重置84
7.14　并行處理器（多核）之間的協(xié)調(diào)85
7.15　觀點(diǎn)86
7.16　總結(jié)86
練習(xí)87
第8章　消息傳遞88
8.1　引言88
8.2　兩種類型的消息傳遞服務(wù)88
8.3　消息使用資源的限制89
8.4　消息傳遞函數(shù)和狀態(tài)轉(zhuǎn)換89
8.5　send的實(shí)現(xiàn)90
8.6　receive的實(shí)現(xiàn)91
8.7　非阻塞消息接收的實(shí)現(xiàn)92
8.8　觀點(diǎn)92
8.9　總結(jié)92
練習(xí)93
第9章　基本內(nèi)存管理94
9.1　引言94
9.2　內(nèi)存的類型94
9.3　重量級進(jìn)程的定義95
9.4　示例系統(tǒng)的內(nèi)存管理95
9.5　程序段和內(nèi)存區(qū)域95
9.6　動(dòng)態(tài)內(nèi)存分配96
9.7　底層內(nèi)存管理器的設(shè)計(jì)97
9.8　分配策略和內(nèi)存持久性97
9.9　追蹤空閑內(nèi)存98
9.10　底層內(nèi)存管理的實(shí)現(xiàn)98
9.11　使用空閑內(nèi)存的數(shù)據(jù)結(jié)構(gòu)定義99
9.12　分配堆存儲100
9.13　分配棧存儲102
9.14　堆和棧存儲的釋放103
9.15　觀點(diǎn)105
9.16　總結(jié)106
練習(xí)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　實(shí)地址空間和虛地址空間113
10.10　支持按需分頁的硬件114
10.11　使用頁表的地址轉(zhuǎn)換114
10.12　頁表項(xiàng)中的元數(shù)據(jù)115
10.13　按需分頁以及設(shè)計(jì)上的問題116
10.14　頁面替換和全局時(shí)鐘算法116
10.15　觀點(diǎn)117
10.16　總結(jié)117
練習(xí)118
第11章　高層消息傳遞119
11.1　引言119
11.2　進(jìn)程間通信端口119
11.3　端口實(shí)現(xiàn)119
11.4　端口表初始化120
11.5　端口創(chuàng)建121
11.6　向端口發(fā)送消息122
11.7　從端口接收消息124
11.8　端口的刪除和重置125
11.9　觀點(diǎn)128
11.10　總結(jié)128
練習(xí)128
第12章　中斷處理130
12.1　引言130
12.2　中斷的優(yōu)點(diǎn)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　觀點(diǎn)141
12.15　總結(jié)142
練習(xí)142
第13章　實(shí)時(shí)時(shí)鐘管理143
13.1　引言143
13.2　定時(shí)事件143
13.3　實(shí)時(shí)時(shí)鐘和計(jì)時(shí)器硬件143
13.4　實(shí)時(shí)時(shí)鐘中斷處理144
13.5　延時(shí)與搶占145
13.6　搶占的實(shí)現(xiàn)145
13.7　使用增量鏈表對延遲進(jìn)行有效管理146
13.8　增量鏈表的實(shí)現(xiàn)147
13.9　將進(jìn)程轉(zhuǎn)入睡眠148
13.10　定時(shí)消息接收150
13.11　喚醒睡眠進(jìn)程154
13.12　時(shí)鐘中斷處理154
13.13　時(shí)鐘初始化156
13.14　觀點(diǎn)159
13.15　總結(jié)159
練習(xí)159
第14章　設(shè)備無關(guān)的I/O161
14.1　引言161
14.2　I/O和設(shè)備驅(qū)動(dòng)的概念結(jié)構(gòu)161
14.3　接口抽象和驅(qū)動(dòng)抽象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è)備的多個(gè)副本和共享驅(qū)動(dòng)166
14.10　高層I/O操作的實(shí)現(xiàn)168
14.11　其他高層I/O函數(shù)169
14.12　打開、關(guān)閉和引用計(jì)數(shù)172
14.13　devtab中的空條目和錯(cuò)誤條目174
14.14　I/O系統(tǒng)的初始化174
14.15　觀點(diǎn)178
14.16　總結(jié)179
練習(xí)179
第15章　設(shè)備驅(qū)動(dòng)示例180
15.1　引言180
15.2　使用UART硬件進(jìn)行串行通信180
15.3　tty抽象180
15.4　tty設(shè)備驅(qū)動(dòng)的組織結(jié)構(gòu)181
15.5　請求隊(duì)列和緩沖區(qū)182
15.6　上半部和下半部的同步183
15.7　UART硬件FIFO與驅(qū)動(dòng)設(shè)計(jì)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ū)動(dòng)函數(shù)（ttyhandler）192
15.17　輸出中斷處理（ttyhandle_out）194
15.18　tty輸入處理（ttyhandle_in）196
15.19　tty控制塊初始化（ttyinit）202
15.20　設(shè)備驅(qū)動(dòng)控制（ttycontrol）204
15.21　觀點(diǎn)205
15.22　總結(jié)205
練習(xí)206
第16章　DMA設(shè)備和驅(qū)動(dòng)（以太網(wǎng)）207
16.1　引言207
16.2　直接內(nèi)存訪問和緩沖區(qū)207
16.3　多個(gè)緩沖區(qū)和緩沖區(qū)環(huán)207
16.4　使用DMA的以太網(wǎng)驅(qū)動(dòng)示例208
16.5　設(shè)備的硬件定義和常量209
16.6　環(huán)和內(nèi)存緩沖區(qū)211
16.7　以太網(wǎng)控制塊的定義213
16.8　設(shè)備和驅(qū)動(dòng)初始化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　觀點(diǎn)229
16.14　總結(jié)229
練習(xí)229
第17章　最小互聯(lián)網(wǎng)協(xié)議棧230
17.1　引言230
17.2　所需的功能230
17.3　同步會(huì)話、超時(shí)和網(wǎng)絡(luò)處理進(jìn)程231
17.4　設(shè)計(jì)的影響232
17.5　ARP函數(shù)232
17.6　網(wǎng)絡(luò)數(shù)據(jù)包的定義241
17.7　網(wǎng)絡(luò)輸入進(jìn)程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)控制報(bào)文協(xié)議267
17.13　動(dòng)態(tài)主機(jī)配置協(xié)議268
17.14　觀點(diǎn)275
17.15　總結(jié)275
練習(xí)275
第18章　遠(yuǎn)程磁盤驅(qū)動(dòng)277
18.1　引言277
18.2　磁盤抽象277
18.3　磁盤驅(qū)動(dòng)支持的操作277
18.4　塊傳輸和高層I/O函數(shù)277
18.5　遠(yuǎn)程磁盤范例278
18.6　高速緩存的重要概念278
18.7　磁盤操作的語義279
18.8　驅(qū)動(dòng)數(shù)據(jù)結(jié)構(gòu)的定義280
18.9　驅(qū)動(dòng)初始化（rdsinit）284
18.10　上半部打開函數(shù)（rdsopen）287
18.11　遠(yuǎn)程通信函數(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　下半部通信進(jìn)程（rdsprocess）302
18.19　觀點(diǎn)306
18.20　總結(jié)306
練習(xí)306
第19章　文件系統(tǒng)308
19.1　什么是文件系統(tǒng)308
19.2　文件操作的示例集308
19.3　本地文件系統(tǒng)的設(shè)計(jì)309
19.4　Xinu文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)309
19.5　索引管理器的實(shí)現(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ù)進(jìn)行文件操作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　文件截?cái)啵╨ftruncate）339
19.24　初始文件系統(tǒng)的創(chuàng)建（lfscreate）341
19.25　觀點(diǎn)343
19.26　總結(jié)343
練習(xí)343
第20章　遠(yuǎn)程文件機(jī)制345
20.1　引言345
20.2　遠(yuǎn)程文件訪問345
20.3　遠(yuǎn)程文件語義345
20.4　遠(yuǎn)程文件設(shè)計(jì)和消息346
20.5　遠(yuǎn)程文件服務(wù)器通信（rfscomm）352
20.6　發(fā)送基本消息（rfsndmsg）354
20.7　網(wǎng)絡(luò)字節(jié)序355
20.8　使用設(shè)備范例的遠(yuǎn)程文件系統(tǒng)355
20.9　打開遠(yuǎn)程文件（rfsopen）356
20.10　檢查文件模式（rfsgetmode）359
20.11　關(guān)閉遠(yuǎn)程文件（rflclose）360
20.12　讀遠(yuǎn)程文件（rflread）361
20.13　寫遠(yuǎn)程文件（rflwrite）363
20.14　遠(yuǎn)程文件的定位（rflseek）365
20.15　遠(yuǎn)程文件單字符I/O（rflgetc、rflputc）366
20.16　遠(yuǎn)程文件系統(tǒng)控制函數(shù)（rfscontrol）367
20.17　初始化遠(yuǎn)程文件系統(tǒng)（rfsinit、rflinit）370
20.18　觀點(diǎn)372
20.19　總結(jié)372
練習(xí)372
第21章　句法名字空間374
21.1　引言374
21.2　透明與名字空間抽象374
21.3　多種命名方案375
21.4　命名系統(tǒng)設(shè)計(jì)的其他方案376
21.5　基于句法的名字空間376
21.6　模式和替換376
21.7　前綴模式377
21.8　名字空間的實(shí)現(xiàn)377
21.9　名字空間的數(shù)據(jù)結(jié)構(gòu)和常量377
21.10　增加名字空間前綴表的映射378
21.11　使用前綴表進(jìn)行名字映射379
21.12　打開命名文件383
21.13　名字空間初始化383
21.14　對前綴表中的項(xiàng)進(jìn)行排序386
21.15　選擇邏輯名字空間386
21.16　默認(rèn)層次和空前綴387
21.17　額外的對象操作函數(shù)387
21.18　名字空間方法的優(yōu)點(diǎn)和限制388
21.19　廣義模式388
21.20　觀點(diǎn)389
21.21　總結(jié)389
練習(xí)390
第22章　系統(tǒng)初始化391
22.1　引言391
22.2　引導(dǎo)程序：從零開始391
22.3　一個(gè)通過網(wǎng)絡(luò)啟動(dòng)的例子392
22.4　操作系統(tǒng)初始化392
22.5　Xinu初始化393
22.6　Xinu系統(tǒng)啟動(dòng)395
22.7　從程序轉(zhuǎn)化為進(jìn)程399
22.8　觀點(diǎn)399
22.9　總結(jié)399
練習(xí)400
第23章　子系統(tǒng)初始化和內(nèi)存標(biāo)記401
23.1　引言401
23.2　自初始化模塊401
23.3　并發(fā)系統(tǒng)中的自初始化模塊402
23.4　重新啟動(dòng)后的自初始化403
23.5　使用登錄號初始化404
23.6　廣義內(nèi)存標(biāo)記方案405
23.7　內(nèi)存標(biāo)記系統(tǒng)的數(shù)據(jù)聲明406
23.8　標(biāo)記的實(shí)現(xiàn)407
23.9　觀點(diǎn)408
23.10　總結(jié)408
練習(xí)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)難時(shí)的panic411
24.8　panic函數(shù)的實(shí)現(xiàn)411
24.9　觀點(diǎn)412
24.10　總結(jié)412
練習(xí)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　計(jì)算次設(shè)備號416
25.6　配置Xinu系統(tǒng)的步驟417
25.7　觀點(diǎn)417
25.8　總結(jié)417
練習(xí)417
第26章　一個(gè)用戶接口例子：Xinu shell419
26.1　引言419
26.2　什么是用戶接口419
26.3　命令和設(shè)計(jì)原則419
26.4　一個(gè)簡化shell的設(shè)計(jì)決策420
26.5　shell的組織和操作420
26.6　詞法符號的定義421
26.7　命令行語法的定義421
26.8　Xinu shell的實(shí)現(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　觀點(diǎn)440
26.18　總結(jié)441
練習(xí)441
附錄1　操作系統(tǒng)移植443
附錄2　Xinu設(shè)計(jì)注解450
索引454