操作系統設計：Xinu方法（原書第2版）

出版者的話
譯者序
前言
關於作者

第1章　引言和概述1
1.1　作業系統1
1.2　本書的研究方法2
1.3　分層設計2
1.4　Xinu作業系統4
1.5　作業系統的界定4
1.6　從外部看作業系統5
1.7　其他章節概要6
1.8　觀點6
1.9　總結7
練習7

第2章　併發執行與作業系統服務8
2.1　引言8
2.2　多活動的程式設計模型8
2.3　作業系統服務9
2.4　併發處理的概念和術語9
2.5　串列程式和併發程式的區別11
2.6　多個進程共用同一段代碼12
2.7　進程退出與進程終止14
2.8　共用記憶體、競爭條件和同步14
2.9　信號量與互斥18
2.10　Xinu中的類型命名方法19
2.11　使用kputc和kprintf進行作業系統的調試20
2.12　觀點20
2.13　總結21
練習21

第3章　硬體與運行時環境概述22
3.1　引言22
3.2　開發平臺的物理和邏輯架構22
3.3　指令集23
3.4　通用寄存器23
3.5　I/O匯流排和存-取範例24
3.6　DMA機制25
3.7　匯流排位址空間25
3.8　匯流排啟動和配置26
3.9　函式呼叫約定和運行時棧26
3.10　中斷和中斷處理28
3.11　中斷向量29
3.12　異常向量和異常處理29
3.13　時鐘硬體29
3.14　串列通信30
3.15　輪詢與中斷驅動I/O30
3.16　存儲佈局30
3.17　記憶體保護31
3.18　硬體細節和片上系統體系結構31
3.19　觀點31
3.20　硬體參考資料32
練習32

第4章　鏈表與佇列操作33
4.1　引言33
4.2　進程鏈表的統一資料結構33
4.3　簡潔的鏈表資料結構34
4.4　佇列資料結構的實現35
4.5　內聯佇列操作函數36
4.6　獲取鏈表中進程的基礎函數37
4.7　FIFO佇列操作38
4.8　優先順序佇列的操作40
4.9　鏈表初始化42
4.10　觀點43
4.11　總結43
練習43

第5章　調度和上下文切換45
5.1　引言45
5.2　進程表45
5.3　進程狀態47
5.4　就緒和當前狀態48
5.5　調度策略48
5.6　調度的實現49
5.7　推遲重新調度52
5.8　上下文切換的實現52
5.9　記憶體中保存的狀態52
5.10　上下文切換操作53
5.11　重新開機進程執行的位址56
5.12　併發執行和空進程57
5.13　使進程就緒和調度常量57
5.14　其他進程調度演算法58
5.15　觀點58
5.16　總結59
練習59

第6章　更多進程管理60
6.1　引言60
6.2　進程掛起和恢復60
6.3　自我掛起和資訊隱藏60
6.4　系統調用61
6.5　禁止和恢復中斷62
6.6　系統調用範本63
6.7　系統調用返回值SYSERR和OK63
6.8　掛起的實現64
6.9　掛起當前進程65
6.10　suspend函數的返回值65
6.11　進程終止和進程退出66
6.12　進程創建68
6.13　其他進程管理函數72
6.14　總結74
練習74

第7章　協調併發進程76
7.1　引言76
7.2　進程同步的必要性76
7.3　計數信號量的概念77
7.4　避免忙等待77
7.5　信號量策略和進程選擇77
7.6　等候狀態78
7.7　信號量資料結構79
7.8　系統調用wait79
7.9　系統調用signal80
7.10　靜態和動態信號量分配81
7.11　動態信號量的實現示例82
7.12　信號量刪除83
7.13　信號量重置84
7.14　並行處理器（多核）之間的協調85
7.15　觀點86
7.16　總結86
練習87

第8章　消息傳遞88
8.1　引言88
8.2　兩種類型的消息傳遞服務88
8.3　消息使用資源的限制89
8.4　消息傳遞函數和狀態轉換89
8.5　send的實現90
8.6　receive的實現91
8.7　非阻塞消息接收的實現92
8.8　觀點92
8.9　總結92
練習93

第9章　基本記憶體管理94
9.1　引言94
9.2　記憶體的類型94
9.3　重量級進程的定義95
9.4　示例系統的記憶體管理95
9.5　程式段和記憶體區域95
9.6　動態記憶體分配96
9.7　底層記憶體管理器的設計97
9.8　分配策略和記憶體持久性97
9.9　追蹤空閒記憶體98
9.10　底層記憶體管理的實現98
9.11　使用空閒記憶體的資料結構定義99
9.12　分配堆存儲100
9.13　分配棧存儲102
9.14　堆和棧存儲的釋放103
9.15　觀點105
9.16　總結106
練習106

第10章　高級記憶體管理和虛擬記憶體107
10.1　引言107
10.2　分區空間分配107
10.3　緩衝集區108
10.4　分配緩衝區108
10.5　將緩衝區返還給緩衝集區110
10.6　創建緩衝集區111
10.7　初始化緩衝集區表112
10.8　虛擬記憶體和記憶體複用113
10.9　真實位址空間和虛位址空間113
10.10　支援按需分頁的硬體114
10.11　使用頁表的位址轉換114
10.12　分頁表項目中的中繼資料115
10.13　按需分頁以及設計上的問題116
10.14　頁面替換和全域時鐘演算法116
10.15　觀點117
10.16　總結117
練習118

第11章　高層消息傳遞119
11.1　引言119
11.2　進程間通訊連接埠119
11.3　埠實現119
11.4　埠表初始化120
11.5　埠創建121
11.6　向埠發送消息122
11.7　從埠接收消息124
11.8　埠的刪除和重置125
11.9　觀點128
11.10　總結128
練習128

第12章　中斷處理130
12.1　引言130
12.2　中斷的優點130
12.3　中斷處理130
12.4　中斷向量131
12.5　中斷和異常集成131
12.6　使用代碼的ARM異常向量132
12.7　設備中斷向量號的分配135
12.8　中斷分派136
12.9　中斷的軟體結構137
12.10　禁止中斷139
12.11　中斷代碼調用函數的限制140
12.12　中斷過程中重新調度的必要性140
12.13　中斷過程中的重新調度140
12.14　觀點141
12.15　總結142
練習142

第13章　即時時鐘管理143
13.1　引言143
13.2　定時事件143
13.3　即時時鐘和計時器硬體143
13.4　即時時鐘中斷處理144
13.5　延時與搶佔145
13.6　搶佔的實現145
13.7　使用增量鏈表對延遲進行有效管理146
13.8　增量鏈表的實現147
13.9　將進程轉入睡眠148
13.10　定時消息接收150
13.11　喚醒睡眠進程154
13.12　時鐘中斷處理154
13.13　時鐘初始化156
13.14　觀點159
13.15　總結159
練習159

第14章　設備無關的I/O161
14.1　引言161
14.2　I/O和設備驅動的概念結構161
14.3　介面抽象和驅動抽象162
14.4　I/O介面示例163
14.5　打開-讀-寫-關閉範例163
14.6　綁定I/O操作和設備名164
14.7　Xinu中的設備名164
14.8　設備轉換表概念165
14.9　設備的多個副本和共用驅動166
14.10　高層I/O操作的實現168
14.11　其他高層I/O函數169
14.12　打開、關閉和引用計數172
14.13　devtab中的空條目和錯誤條目174
14.14　I/O系統的初始化174
14.15　觀點178
14.16　總結179
練習179

第15章　設備驅動示例180
15.1　引言180
15.2　使用UART硬體進行串列通信180
15.3　tty抽象180
15.4　tty設備驅動的組織結構181
15.5　請求佇列和緩衝區182
15.6　上半部和下半部的同步183
15.7　UART硬體FIFO與驅動設計184
15.8　控制塊的概念184
15.9　tty控制塊和資料聲明184
15.10　次設備號186
15.11　上半部tty字元輸入（ttygetc）187
15.12　上半部tty讀取函數（ttyread）188
15.13　上半部tty字元輸出（ttyputc）189
15.14　開始輸出（ttykickout）190
15.15　上半部tty多字元輸出（ttywrite）191
15.16　下半部tty驅動函數（ttyhandler）192
15.17　輸出中斷處理（ttyhandle_out）194
15.18　tty輸入處理（ttyhandle_in）196
15.19　tty控制塊初始化（ttyinit）202
15.20　設備驅動控制（ttycontrol）204
15.21　觀點205
15.22　總結205
練習206

第16章　DMA設備和驅動（乙太網）207
16.1　引言207
16.2　直接記憶體存取和緩衝區207
16.3　多個緩衝區和緩衝區環207
16.4　使用DMA的乙太網驅動示例208
16.5　設備的硬體定義和常量209
16.6　環和記憶體緩衝區211
16.7　乙太網控制塊的定義213
16.8　設備和驅動初始化215
16.9　從乙太網設備讀取資料包221
16.10　向乙太網設備寫入資料包223
16.11　乙太網設備的中斷處理225
16.12　乙太網控制函數228
16.13　觀點229
16.14　總結229
練習229

第17章　最小互聯網協定棧230
17.1　引言230
17.2　所需的功能230
17.3　同步會話、超時和網路處理進程231
17.4　設計的影響232
17.5　ARP函數232
17.6　網路資料包的定義241
17.7　網路輸入進程242
17.8　IP的相關定義245
17.9　IP函數246
17.10　UDP表的定義255
17.11　UDP函數256
17.12　互聯網控制報文協議267
17.13　動態主機設定通訊協定268
17.14　觀點275
17.15　總結275
練習275

第18章　遠端磁片驅動277
18.1　引言277
18.2　磁片抽象277
18.3　磁片驅動支援的操作277
18.4　塊傳輸和高層I/O函數277
18.5　遠端磁片範例278
18.6　快取記憶體的重要概念278
18.7　磁片操作的語義279
18.8　驅動資料結構的定義280
18.9　驅動初始化（rdsinit）284
18.10　上半部打開函數（rdsopen）287
18.11　遠端通訊函數（rdscomm）289
18.12　上半部寫函數（rdswrite）291
18.13　上半部讀函數（rdsread）293
18.14　刷新掛起的請求296
18.15　上半部控制函數（rdscontrol）297
18.16　分配磁片緩衝區（rdsbufalloc）299
18.17　上半部關閉函數（rdsclose）300
18.18　下半部通信進程（rdsprocess）302
18.19　觀點306
18.20　總結306
練習306

第19章　檔案系統308
19.1　什麼是檔案系統308
19.2　檔操作的示例集308
19.3　本地檔案系統的設計309
19.4　Xinu檔案系統的資料結構309
19.5　索引管理器的實現310
19.6　清空索引塊（lfibclear）314
19.7　獲取索引塊（lfibget）315
19.8　存儲索引塊（lfibput）315
19.9　從空閒鏈表中分配索引塊（lfiballoc）316
19.10　從空閒鏈表中分配資料塊（lfdballoc）317
19.11　使用設備無關的I/O函數進行檔操作319
19.12　檔案系統的設備配置和函數名稱320
19.13　本地檔案系統打開函數（lfsopen）320
19.14　關閉檔偽設備（lflclose）326
19.15　刷新磁片中的資料（lfflush）328
19.16　檔的批量傳輸函數（lflwrite、lflread）328
19.17　在檔中查找新位置（lflseek）330
19.18　從檔中提取一位元組（lflgetc）331
19.19　改變檔中的一位元組（lflputc）332
19.20　載入索引塊和資料塊（lfsetup）334
19.21　主檔案系統設備的初始化（lfsinit）337
19.22　偽設備的初始化（lflinit）338
19.23　文件截斷（lftruncate）339
19.24　初始檔案系統的創建（lfscreate）341
19.25　觀點343
19.26　總結343
練習343

第20章　遠程檔機制345
20.1　引言345
20.2　遠端檔訪問345
20.3　遠程文件語義345
20.4　遠端檔設計和消息346
20.5　遠端檔案伺服器通信（rfscomm）352
20.6　發送基本消息（rfsndmsg）354
20.7　網路位元組序355
20.8　使用設備範例的遠端檔案系統355
20.9　打開遠程文件（rfsopen）356
20.10　檢查檔模式（rfsgetmode）359
20.11　關閉遠程文件（rflclose）360
20.12　讀遠程文件（rflread）361
20.13　寫遠程文件（rflwrite）363
20.14　遠端文件的定位（rflseek）365
20.15　遠端檔單字元I/O（rflgetc、rflputc）366
20.16　遠端檔案系統控制函數（rfscontrol）367
20.17　初始化遠程檔案系統（rfsinit、rflinit）370
20.18　觀點372
20.19　總結372
練習372

第21章　句法名字空間374
21.1　引言374
21.2　透明與名字空間抽象374
21.3　多種命名方案375
21.4　命名系統設計的其他方案376
21.5　基於句法的名字空間376
21.6　模式和替換376
21.7　首碼模式377
21.8　名字空間的實現377
21.9　名字空間的資料結構和常量377
21.10　增加名字空間首碼表的映射378
21.11　使用首碼表進行名字映射379
21.12　打開命名檔383
21.13　名字空間初始化383
21.14　對首碼表中的項進行排序386
21.15　選擇邏輯名字空間386
21.16　預設層次和空首碼387
21.17　額外的物件操作函數387
21.18　名字空間方法的優點和限制388
21.19　廣義模式388
21.20　觀點389
21.21　總結389
練習390

第22章　系統初始化391
22.1　引言391
22.2　引導程式：從零開始391
22.3　一個通過網路啟動的例子392
22.4　作業系統初始化392
22.5　Xinu初始化393
22.6　Xinu系統啟動395
22.7　從程式轉化為進程399
22.8　觀點399
22.9　總結399
練習400

第23章　子系統初始化和記憶體標記401
23.1　引言401
23.2　自初始化模組401
23.3　併發系統中的自初始化模組402
23.4　重新啟動後的自初始化403
23.5　使用登錄號初始化404
23.6　廣義記憶體標記方案405
23.7　記憶體標記系統的資料聲明406
23.8　標記的實現407
23.9　觀點408
23.10　總結408
練習408

第24章　異常處理409
24.1　引言409
24.2　術語：故障、檢測、陷阱和異常409
24.3　向量異常和可遮罩中斷 409
24.4　異常的類型410
24.5　處理異常410
24.6　異常向量初始化411
24.7　面對災難時的panic411
24.8　panic函數的實現411
24.9　觀點412
24.10　總結412
練習412

第25章　系統組態413
25.1　引言413
25.2　多重配置的需求413
25.3　Xinu系統組態414
25.4　Xinu設定檔的內容414
25.5　計算次設備號416
25.6　配置Xinu系統的步驟417
25.7　觀點417
25.8　總結417
練習417

第26章　一個使用者介面例子：Xinu shell419
26.1　引言419
26.2　什麼是使用者介面419
26.3　命令和設計原則419
26.4　一個簡化shell的設計決策420
26.5　shell的組織和操作420
26.6　詞法符號的定義421
26.7　命令列語法的定義421
26.8　Xinu shell的實現422
26.9　符號的存儲424
26.10　詞法分析器代碼424
26.11　命令直譯器的核心428
26.12　命令名查詢和內部處理434
26.13　傳遞給命令的參數435
26.14　向外部命令傳遞參數435
26.15　I/O重定向438
26.16　命令函數（sleep）的例子439
26.17　觀點440
26.18　總結441
練習441

附錄1　作業系統移植443
附錄2　Xinu設計注解450
索引454