操作系統(tǒng)設(shè)計(jì)：Xinu方法

Operating System Design：The Xinu Approach，Linksys Version

出版者的話
譯者序
前言
關(guān)于作者
第1章　引言和概述1
　1.1　操作系統(tǒng)1
　1.2　本書的研究方法1
　1.3　分層設(shè)計(jì)2
　1.4　Xinu操作系統(tǒng)3
　1.5　操作系統(tǒng)不是什么3
　1.6　從外面看操作系統(tǒng)4
　1.7　其他章節(jié)概要4
　1.8　觀點(diǎn)5
　1.9　總結(jié)5
　練習(xí)5
第2章　并發(fā)執(zhí)行與操作系統(tǒng)服務(wù)6
　2.1　引言6
　2.2　多活動(dòng)的編程模型6
　2.3　操作系統(tǒng)服務(wù)7
　2.4　并發(fā)處理的概念和術(shù)語7
　2.5　串行程序和并發(fā)程序的區(qū)別8
　2.6　多進(jìn)程共享同一段代碼9
　2.7　進(jìn)程退出與進(jìn)程終止11
　2.8　共享內(nèi)存、競爭條件和同步11
　2.9　信號(hào)量與互斥14
　2.10　Xinu中的類型命名方法15
　2.11　使用Kputc和Kprintf進(jìn)行操作系統(tǒng)的調(diào)試16
　2.12　觀點(diǎn)16
　2.13　總結(jié)16
　練習(xí)17
第3章　硬件和運(yùn)行時(shí)環(huán)境概覽18
　3.1　引言18
　3.2　E2100L的物理和邏輯結(jié)構(gòu)18
　3.3　處理器結(jié)構(gòu)和寄存器19
　3.4　總線操作：獲取-存儲(chǔ)范式19
　3.5　直接內(nèi)存訪問19
　3.6　總線地址空間20
　3.7　內(nèi)核段KSEG0和KSEG1的內(nèi)容20
　3.8　總線啟動(dòng)的靜態(tài)配置21
　3.9　調(diào)用約定和運(yùn)行時(shí)棧21
　3.10　中斷和中斷處理22
　3.11　異常處理23
　3.12　計(jì)時(shí)器硬件23
　3.13　串行通信24
　3.14　輪詢與中斷驅(qū)動(dòng)I/O24
　3.15　內(nèi)存緩存和KSEG124
　3.16　存儲(chǔ)布局24
　3.17　內(nèi)存保護(hù)25
　3.18　觀點(diǎn)25
　練習(xí)25
第4章　鏈表與隊(duì)列操作26
　4.1　引言26
　4.2　用于進(jìn)程鏈表的統(tǒng)一數(shù)據(jù)結(jié)構(gòu)26
　4.3　簡潔的鏈表數(shù)據(jù)結(jié)構(gòu)27
　4.4　隊(duì)列數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)28
　4.5　內(nèi)聯(lián)隊(duì)列操作函數(shù)29
　4.6　獲取鏈表中進(jìn)程的基礎(chǔ)函數(shù)29
　4.7　FIFO隊(duì)列操作30
　4.8　優(yōu)先級(jí)隊(duì)列的操作32
　4.9　鏈表初始化33
　4.10　觀點(diǎn)34
　4.11　總結(jié)34
　練習(xí)35
第5章　調(diào)度和上下文切換36
　5.1　引言36
　5.2　進(jìn)程表36
　5.3　進(jìn)程狀態(tài)38
　5.4　就緒和當(dāng)前狀態(tài)38
　5.5　調(diào)度策略38
　5.6　調(diào)度的實(shí)現(xiàn)39
　5.7　上下文切換的實(shí)現(xiàn)41
　5.8　內(nèi)存中保存的狀態(tài)41
　5.9　在MIPS處理器上切換上下文41
　5.10　重新啟動(dòng)進(jìn)程執(zhí)行的地址43
　5.11　并發(fā)執(zhí)行和null進(jìn)程44
　5.12　使進(jìn)程準(zhǔn)備執(zhí)行和調(diào)度不變式44
　5.13　推遲重新調(diào)度45
　5.14　其他進(jìn)程調(diào)度算法47
　5.15　觀點(diǎn)47
　5.16　總結(jié)47
　練習(xí)47
第6章　更多進(jìn)程管理49
　6.1　引言49
　6.2　進(jìn)程掛起和恢復(fù)49
　6.3　自我掛起和信息隱藏49
　6.4　系統(tǒng)調(diào)用的概念50
　6.5　禁止中斷和恢復(fù)中斷51
　6.6　系統(tǒng)調(diào)用模板51
　6.7　系統(tǒng)調(diào)用返回SYSERR和OK值51
　6.8　掛起的實(shí)現(xiàn)52
　6.9　掛起當(dāng)前進(jìn)程53
　6.10　suspend函數(shù)的返回值53
　6.11　進(jìn)程終止和進(jìn)程退出54
　6.12　進(jìn)程創(chuàng)建56
　6.13　其他進(jìn)程管理函數(shù)59
　6.14　總結(jié)60
　練習(xí)61
第7章　協(xié)調(diào)并發(fā)進(jìn)程62
　7.1　引言62
　7.2　進(jìn)程同步的必要性62
　7.3　計(jì)數(shù)信號(hào)量的概念63
　7.4　避免忙等待63
　7.5　信號(hào)量策略和進(jìn)程選擇63
　7.6　等待狀態(tài)64
　7.7　信號(hào)量數(shù)據(jù)結(jié)構(gòu)64
　7.8　系統(tǒng)調(diào)用wait65
　7.9　系統(tǒng)調(diào)用signal66
　7.10　靜態(tài)和動(dòng)態(tài)信號(hào)量分配66
　7.11　動(dòng)態(tài)信號(hào)量的實(shí)現(xiàn)示例67
　7.12　信號(hào)量刪除68
　7.13　信號(hào)量重置69
　7.14　多核處理器之間的協(xié)調(diào)69
　7.15　觀點(diǎn)70
　7.16　總結(jié)70
　練習(xí)71
第8章　消息傳遞72
　8.1　引言72
　8.2　兩種類型的消息傳遞服務(wù)72
　8.3　消息使用資源的限制72
　8.4　消息傳遞函數(shù)和狀態(tài)轉(zhuǎn)換73
　8.5　send的實(shí)現(xiàn)73
　8.6　receive的實(shí)現(xiàn)74
　8.7　非阻塞消息接收的實(shí)現(xiàn)75
　8.8　觀點(diǎn)75
　8.9　總結(jié)75
　練習(xí)76
第9章　基本內(nèi)存管理77
　9.1　引言77
　9.2　內(nèi)存的類型77
　9.3　重量級(jí)進(jìn)程的定義77
　9.4　小型嵌入式系統(tǒng)的內(nèi)存管理78
　9.5　程序段和內(nèi)存區(qū)域78
　9.6　嵌入式系統(tǒng)中的動(dòng)態(tài)內(nèi)存分配79
　9.7　低層內(nèi)存管理器的設(shè)計(jì)79
　9.8　分配策略和內(nèi)存持久性80
　9.9　追蹤空閑內(nèi)存80
　9.10　低層內(nèi)存管理的實(shí)現(xiàn)80
　9.11　分配堆存儲(chǔ)82
　9.12　分配棧存儲(chǔ)83
　9.13　釋放堆和棧存儲(chǔ)84
　9.14　觀點(diǎn)86
　9.15　總結(jié)87
　練習(xí)87
第10章　高級(jí)內(nèi)存管理和虛擬內(nèi)存88
　10.1　引言88
　10.2　分區(qū)空間分配88
　10.3　緩沖池88
　10.4　分配緩沖區(qū)89
　10.5　將緩沖區(qū)返回給緩沖池90
　10.6　創(chuàng)建緩沖池91
　10.7　初始化緩沖池表93
　10.8　虛擬內(nèi)存和內(nèi)存復(fù)用93
　10.9　實(shí)地址空間和虛地址空間93
　10.10　支持按需換頁的硬件94
　10.11　使用頁表的地址翻譯95
　10.12　頁表項(xiàng)中的元數(shù)據(jù)95
　10.13　按需換頁以及設(shè)計(jì)上的問題95
　10.14　頁面替換和全局時(shí)鐘算法96
　10.15　觀點(diǎn)97
　10.16　總結(jié)97
　練習(xí)97
第11章　高層消息傳遞98
　11.1　引言98
　11.2　進(jìn)程間通信端口98
　11.3　端口實(shí)現(xiàn)98
　11.4　端口表初始化99
　11.5　端口創(chuàng)建100
　11.6　向端口發(fā)送消息101
　11.7　從端口接收消息102
　11.8　端口的刪除和重置103
　11.9　觀點(diǎn)106
　11.10　總結(jié)106
　練習(xí)106
第12章　中斷處理107
　12.1　引言107
　12.2　中斷的優(yōu)點(diǎn)107
　12.3　中斷分配107
　12.4　中斷向量107
　12.5　中斷向量號(hào)的分配108
　12.6　硬件中斷108
　12.7　中斷請(qǐng)求的局限性和中斷多路復(fù)用109
　12.8　中斷軟件和分配109
　12.9　中斷分配器底層部分110
　12.10　中斷分配器高層部分112
　12.11　禁止中斷114
　12.12　函數(shù)中中斷代碼引起的限制115
　12.13　中斷過程中重新調(diào)度的必要性115
　12.14　中斷過程中的重新調(diào)度115
　12.15　觀點(diǎn)116
　12.16　總結(jié)116
　練習(xí)117
第13章　實(shí)時(shí)時(shí)鐘管理118
　13.1　引言118
　13.2　定時(shí)事件118
　13.3　實(shí)時(shí)時(shí)鐘和計(jì)時(shí)器硬件118
　13.4　處理實(shí)時(shí)時(shí)鐘中斷119
　13.5　延時(shí)與搶占119
　13.6　使用計(jì)時(shí)器來模擬實(shí)時(shí)時(shí)鐘120
　13.7　搶占的實(shí)現(xiàn)120
　13.8　使用增量鏈表對(duì)延遲進(jìn)行有效管理120
　13.9　增量鏈表的實(shí)現(xiàn)121
　13.10　將進(jìn)程轉(zhuǎn)入睡眠122
　13.11　定時(shí)消息接收124
　13.12　喚醒睡眠進(jìn)程127
　13.13　時(shí)鐘中斷處理127
　13.14　時(shí)鐘初始化128
　13.15　間隔計(jì)時(shí)器管理129
　13.16　觀點(diǎn)130
　13.17　總結(jié)130
　練習(xí)130
第14章　設(shè)備無關(guān)的I/O132
　14.1　引言132
　14.2　I/O和設(shè)備驅(qū)動(dòng)的概念結(jié)構(gòu)132
　14.3　接口抽象和驅(qū)動(dòng)抽象133
　14.4　I/O接口的一個(gè)示例134
　14.5　打開-讀-寫-關(guān)閉范式134
　14.6　綁定I/O操作和設(shè)備名134
　14.7　Xinu中的設(shè)備名135
　14.8　設(shè)備轉(zhuǎn)換表概念135
　14.9　設(shè)備和共享驅(qū)動(dòng)的多個(gè)副本136
　14.10　高層I/O操作的實(shí)現(xiàn)138
　14.11　其他高層I/O函數(shù)138
　14.12　打開、關(guān)閉和引用計(jì)數(shù)141
　14.13　devtab中的空條目和錯(cuò)誤條目143
　14.14　I/O系統(tǒng)的初始化143
　14.15　觀點(diǎn)146
　14.16　總結(jié)147
　練習(xí)147
第15章　設(shè)備驅(qū)動(dòng)示例148
　15.1　引言148
　15.2　tty抽象148
　15.3　tty設(shè)備驅(qū)動(dòng)的組成149
　15.4　請(qǐng)求隊(duì)列和緩沖區(qū)149
　15.5　上半部和下半部的同步150
　15.6　硬件緩沖區(qū)和驅(qū)動(dòng)設(shè)計(jì)151
　15.7　tty控制塊和數(shù)據(jù)聲明151
　15.8　次設(shè)備號(hào)153
　15.9　上半部tty字符輸入（ttyGetc）153
　15.10　通用上半部tty輸入（ttyRead）154
　15.11　上半部tty字符輸出（ttyPutc）155
　15.12　開始輸出（ttyKickOut）156
　15.13　上半部tty多字符輸出（ttyWrite）157
　15.14　下半部tty驅(qū)動(dòng)函數(shù)（ttyInterrupt）157
　15.15　輸出中斷處理（ttyInter_out）159
　15.16　tty輸入處理(tty Inter-in)161
　15.17　tty控制塊初始化（ttyInit）166
　15.18　設(shè)備驅(qū)動(dòng)控制168
　15.19　觀點(diǎn)169
　15.20　總結(jié)169
　練習(xí)169
第16章　DMA設(shè)備和驅(qū)動(dòng)（以太網(wǎng)）171
　16.1　引言171
　16.2　直接內(nèi)存訪問和緩沖區(qū)171
　16.3　多緩沖區(qū)和環(huán)171
　16.4　使用DMA的以太網(wǎng)驅(qū)動(dòng)例子172
　16.5　設(shè)備的硬件定義和常量172
　16.6　環(huán)和內(nèi)存緩沖區(qū)174
　16.7　以太網(wǎng)控制塊的定義175
　16.8　設(shè)備和驅(qū)動(dòng)初始化177
　16.9　分配輸入緩沖區(qū)181
　16.10　從以太網(wǎng)設(shè)備中讀取數(shù)據(jù)包182
　16.11　向以太網(wǎng)設(shè)備中寫入數(shù)據(jù)包183
　16.12　以太網(wǎng)設(shè)備的中斷處理185
　16.13　以太網(wǎng)控制函數(shù)187
　16.14　觀點(diǎn)189
　16.15　總結(jié)189
　練習(xí)189
第17章　最小互聯(lián)網(wǎng)協(xié)議棧190
　17.1　引言190
　17.2　所需的功能190
　17.3　同步對(duì)話、超時(shí)和進(jìn)程191
　17.4　ARP函數(shù)192
　17.5　網(wǎng)絡(luò)數(shù)據(jù)包的定義198
　17.6　網(wǎng)絡(luò)輸入進(jìn)程199
　17.7　UDP表的定義202
　17.8　UDP函數(shù)203
　17.9　互聯(lián)網(wǎng)控制報(bào)文協(xié)議210
　17.10　動(dòng)態(tài)主機(jī)配置協(xié)議211
　17.11　觀點(diǎn)214
　17.12　總結(jié)214
　練習(xí)214
第18章　遠(yuǎn)程磁盤驅(qū)動(dòng)215
　18.1　引言215
　18.2　磁盤抽象215
　18.3　磁盤操作驅(qū)動(dòng)支持215
　18.4　塊傳輸和高層I/O函數(shù)215
　18.5　遠(yuǎn)程磁盤范式216
　18.6　磁盤操作的語義216
　18.7　驅(qū)動(dòng)數(shù)據(jù)結(jié)構(gòu)的定義217
　18.8　驅(qū)動(dòng)初始化（rdsInit）221
　18.9　上半部打開函數(shù)（rdsOpen）223
　18.10　遠(yuǎn)程通信函數(shù)（rdscomm）224
　18.11　上半部寫函數(shù)（rdsWrite）226
　18.12　上半部讀函數(shù)（rdsRead）228
　18.13　刷新掛起的請(qǐng)求231
　18.14　上半部控制函數(shù)（rdsControl）231
　18.15　分配磁盤緩沖區(qū)（rdsbufalloc）233
　18.16　上半部關(guān)閉函數(shù)（rdsClose）234
　18.17　下半部通信進(jìn)程（rdsprocess）235
　18.18　觀點(diǎn)239
　18.19　總結(jié)239
　練習(xí)240
第19章　文件系統(tǒng)241
　19.1　文件系統(tǒng)是什么241
　19.2　文件操作的示例集合241
　19.3　本地文件系統(tǒng)的設(shè)計(jì)242
　19.4　Xinu文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)242
　19.5　索引管理器的實(shí)現(xiàn)243
　19.6　清空索引塊（lfibclear）246
　19.7　獲取索引塊（lfibget）247
　19.8　存儲(chǔ)索引塊（lfibput）247
　19.9　從空閑鏈表中分配索引塊（lfiballoc）248
　19.10　從空閑鏈表中分配數(shù)據(jù)塊（lfdballoc）249
　19.11　使用設(shè)備無關(guān)的I/O函數(shù)的文件操作250
　19.12　文件系統(tǒng)的設(shè)備設(shè)置和函數(shù)名稱251
　19.13　本地文件系統(tǒng)打開函數(shù)（lfsOpen）251
　19.14　關(guān)閉文件偽設(shè)備（lflClose）256
　19.15　刷新磁盤中的數(shù)據(jù)（lfflush）256
　19.16　文件的批量傳輸函數(shù)（lflWrite,lflRead）257
　19.17　在文件中查找一個(gè)新位置（lflSeek）258
　19.18　從文件中提取一個(gè)字節(jié)（lflGetc）259
　19.19　改變文件中的一個(gè)字節(jié)（lflPutc）260
　19.20　載入索引塊和數(shù)據(jù)塊（lfsetup）261
　19.21　主文件系統(tǒng)設(shè)備的初始化（lfsInit）264
　19.22　偽設(shè)備的初始化（lflInit）264
　19.23　文件截?cái)啵╨ftruncate）265
　19.24　初始文件系統(tǒng)的創(chuàng)建（lfscreate）267
　19.25　觀點(diǎn)269
　19.26　總結(jié)269
　練習(xí)269
第20章　遠(yuǎn)程文件機(jī)制270
　20.1　引言270
　20.2　遠(yuǎn)程文件訪問270
　20.3　遠(yuǎn)程文件語義270
　20.4　遠(yuǎn)程文件設(shè)計(jì)和消息271
　20.5　遠(yuǎn)程文件服務(wù)器通信276
　20.6　發(fā)送一個(gè)基本消息278
　20.7　網(wǎng)絡(luò)字節(jié)序279
　20.8　使用設(shè)備范式的遠(yuǎn)程文件系統(tǒng)279
　20.9　打開遠(yuǎn)程文件280
　20.10　檢查文件模式282
　20.11　關(guān)閉遠(yuǎn)程文件283
　20.12　讀遠(yuǎn)程文件284
　20.13　寫遠(yuǎn)程文件286
　20.14　遠(yuǎn)程文件的定位288
　20.15　遠(yuǎn)程文件單字符I/O288
　20.16　遠(yuǎn)程文件系統(tǒng)控制函數(shù)289
　20.17　初始化遠(yuǎn)程文件數(shù)據(jù)結(jié)構(gòu)292
　20.18　觀點(diǎn)293
　20.19　總結(jié)293
　練習(xí)294
第21章　句法名字空間295
　21.1　引言295
　21.2　透明與名字空間的抽象295
　21.3　多種命名方案295
　21.4　命名系統(tǒng)設(shè)計(jì)的其他方案296
　21.5　基于句法的名字空間296
　21.6　模式和替換297
　21.7　前綴模式297
　21.8　名字空間的實(shí)現(xiàn)297
　21.9　名字空間的數(shù)據(jù)結(jié)構(gòu)和常量297
　21.10　增加名字空間前綴表的映射298
　21.11　使用前綴表進(jìn)行名字映射299
　21.12　打開命名文件302
　21.13　名字空間初始化303
　21.14　對(duì)前綴表中的項(xiàng)進(jìn)行排序305
　21.15　選擇一個(gè)邏輯名字空間305
　21.16　默認(rèn)層次和空前綴305
　21.17　額外的對(duì)象操作函數(shù)306
　21.18　名字空間方法的優(yōu)點(diǎn)和限制306
　21.19　廣義模式307
　21.20　觀點(diǎn)307
　21.21　總結(jié)308
　練習(xí)308
第22章　系統(tǒng)初始化309
　22.1　引言309
　22.2　引導(dǎo)程序：從頭開始309
　22.3　操作系統(tǒng)初始化309
　22.4　在E2100L上啟動(dòng)一個(gè)可選的映像310
　22.5　Xinu初始化310
　22.6　系統(tǒng)啟動(dòng)312
　22.7　從程序轉(zhuǎn)化為進(jìn)程316
　22.8　觀點(diǎn)316
　22.9　總結(jié)316
　練習(xí)316
第23章　異常處理317
　23.1　引言317
　23.2　異常、陷阱和惡意中斷317
　23.3　panic的實(shí)現(xiàn)317
　23.4　觀點(diǎn)318
　23.5　總結(jié)318
　練習(xí)318
第24章　系統(tǒng)配置319
　24.1　引言319
　24.2　多重配置的需求319
　24.3　Xinu系統(tǒng)配置319
　24.4　Xinu配置文件的內(nèi)容320
　24.5　計(jì)算次設(shè)備號(hào)321
　24.6　配置Xinu系統(tǒng)的步驟322
　24.7　觀點(diǎn)322
　24.8　總結(jié)322
　練習(xí)322
第25章　一個(gè)用戶接口例子：Xinu殼323
　25.1　引言323
　25.2　用戶接口323
　25.3　命令和設(shè)計(jì)原則323
　25.4　一個(gè)簡化殼的設(shè)計(jì)決策324
　25.5　殼的組織和操作324
　25.6　詞法符號(hào)的定義324
　25.7　命令行語法的定義325
　25.8　Xinu殼的實(shí)現(xiàn)325
　25.9　符號(hào)的存儲(chǔ)327
　25.10　詞法分析器代碼327
　25.11　命令解釋器的核心330
　25.12　命令名查詢和內(nèi)部處理336
　25.13　傳給命令的參數(shù)336
　25.14　向外部命令傳遞參數(shù)337
　25.15　I/O重定向339
　25.16　示例命令函數(shù)（sleep）340
　25.17　觀點(diǎn)341
　25.18　總結(jié)341
　練習(xí)342
附錄1　操作系統(tǒng)移植343
附錄2　Xinu設(shè)計(jì)注解349
索引352