自研作業系統：DIM-SUM設計與實現

第1章 準備工作 1
1.1 DIM-SUM簡介 1
1.2 DIM-SUM是什麼 1
1.2.1 DIM-SUM的第一個版本為什麼是HOT-POT 1
1.2.2 DIM-SUM歡迎什麼 2
1.2.3 DIM-SUM不歡迎什麼 3
1.3 獲得原始程式碼 3
1.3.1 通過網頁下載原始程式碼 3
1.3.2 通過Git獲取原始程式碼 3
1.4 搭建調試開發環境 4
1.4.1 安裝ubuntu 16.04 4
1.4.2 ubuntu 16.04環境配置 5
1.4.3 搭建編譯環境 6
1.4.4 編譯HOT-POT 7
1.4.5 運行HOT-POT 8
1.4.6 開始調試 10
1.5 向DIM-SUM作業系統提交補丁 11
1.5.1 心態 11
1.5.2 準備工作 11
1.5.3 製作補丁 13
1.5.4 製作正確的補丁 14
1.5.5 發送補丁 16
1.6 獲得幫助 17
1.7 提醒 17

第2章 演算法基礎 18
2.1 鏈表 18
2.2 散列表 19
2.3 紅黑樹 20
2.4 基樹 22

第 3章 計數與互斥同步 23
3.1 計數 23
3.1.1 計數的難題 24
3.1.2 計數器 24
3.1.3 近似計數器 27
3.1.4 引用計數 31
3.2 內核互斥原語 32
3.2.1 每CPU變數 32
3.2.2 自旋鎖 38
3.2.3 自旋位鎖 42
3.2.4 自旋順序鎖 44
3.2.5 自旋讀/寫鎖 47
3.2.6 讀/寫信號量 50
3.2.7 互斥鎖 56
3.3 內核同步原語 60
3.3.1 信號量的設計原理 60
3.3.2 信號量的數據結構 61
3.3. 3 信號量API 61
3.3.4 信號量的實現 62

第4章 調度 65
4.1 基本概念 65
4.1.1 進程和執行緒 65
4.1.2 任務 66
4.1.3 任務搶佔 66
4.1.4 idle執行緒 66
4.2 SMP CPU初始化 66
4.3 數據結構 71
4.3.1 執行緒 71
4.3.2 調度佇列 76
4.3.3 雜項 77
4.4 調度子系統初始化 77
4.4.1 init_sched_early函數 78
4.4.2 init_idle_process函數 78
4.4.3 init_sched函數 79
4.5 執行緒調度 79
4.5.1 上下文切換 79
4.5.2 喚醒執行緒 82
4.6 調度API 85
4.6.1 等待佇列 85
4.6.2 位元等待佇列 89
4.6.3 執行緒睡眠 93
4.6.4 訊息佇列 96

第5章 中斷及計時器 108
5.1 中斷控制器初始化 108
5.1.1 主CPU中斷控制器初始化 109
5.1.2 從CPU中斷控制器初始化 110
5.2 中斷控制器維護 110
5.2.1 中斷號映射 110
5.2.2 邏輯中斷的控制 113
5.2.3 設備中斷處理函數 116
5.3 中斷處理 119
5.3.1 序言 119
5.3.2 中斷處理通用流程 120
5.3.3 處理外部設備中斷 122
5.3.4 處理核間中斷 126
5.3.5 軟中斷 126
5.3.6 尾聲 126
5.4 工作隊列 128
5.4.1 工作隊列的數據結構 128
5.4.2 工作隊列的全域變數 130
5.4.3 工作隊列的API 130
5.4.4 工作隊列的實現 131
5.5 計時器與時間管理 139
5.5.1 初始化 139
5.5.2 計時器的數據結構 139
5.5.3 計時器的全域變數 141
5.5.4 計時器的API 141
5.5.5 計時器的實現 141
5.5.6 計時器中斷處理 144
5.5.7 時間管理 148

第6章 記憶體管理 151
6.1 記憶體初始化 151
6.1.1 艱難地準備C運行環境 151
6.1.2 準備BOOT記憶體空間 152
6.1.3 實體記憶體塊管理 152
6.1.4 早期設備記憶體映射 153
6.1.5 初始化每CPU變數 157
6.1.6 初始化線性映射 157
6.1.7 其他記憶體初始化工作 160
6.2 BOOT記憶體分配器 160
6.2.1 BOOT記憶體分配API 161
6.2.2 BOOT記憶體分配器的實現 161
6.2.3 BOOT記憶體分配器的銷毀 163
6.3 頁面編號 163
6.3.1 頁面編號的數據結構 164
6.3.2 頁面編號的全域變數 165
6.3.3 頁面編號的API 165
6.3.4 頁面編號的實現 165
6.4 頁面分配器 168
6.4.1 頁面分配器的設計原理 168
6.4.2 頁面分配器的數據結構 169
6.4.3 頁面分配器的全域變數 174
6.4.4 頁面分配器的API 175
6.4.5 頁面分配器的實現 176
6.4.6 頁面分配器的初始化 192
6.5 Beehive記憶體分配器 193
6.5.1 Beehive記憶體分配器的設計原理 193
6.5.2 Beehive記憶體分配器的數據結構 195
6.5.3 Beehive記憶體分配器的全域變數 197
6.5.4 Beehive記憶體分配器的API 199
6.5.5 Beehive記憶體分配器的實現 199
6.5.6 Beehive記憶體分配器的初始化 214
6.6 I/O記憶體映射 216

第7章 塊設備 219
7.1 磁片及其分區 220
7.1.1 磁片及其分區的數據結構 220
7.1.2 磁片及其分區的全域變數 222
7.1.3 磁片及其分區的API 222
7.1.4 磁片及其分區的實現 222
7.2 塊設備維護 228
7.2.1 塊設備的數據結構 228
7.2.2 塊設備的全域變數 230
7.2.3 塊設備的API 231
7.2.4 塊設備的實現 231
7.3 I/O請求 242
7.3.1 I/O請求的數據結構 243
7.3.2 I/O請求的全域變數 250
7.3.3 I/O請求的API 250
7.3.4 I/O請求的實現 251
7.4 I/O調度 265
7.4.1 I/O調度的數據結構 265
7.4.2 I/O調度的全域變數 267
7.4.3 I/O調度的API 267
7.4.4 I/O調度的實現 268

第8章 虛擬檔案系統 271
8.1 掛載、卸載檔案系統 271
8.1.1 掛載、卸載檔案系統的數據結構 272
8.1.2 掛載、卸載檔案系統的全域變數 277
8.1.3 掛載、卸載檔案系統的API 278
8.1.4 掛載、卸載檔案系統的實現 278
8.2 文件節點緩存 285
8.2.1 檔節點緩存的數據結構 286
8.2.2 文件節點緩存的全域變數 288
8.2.3 文件節點緩存的API 289
8.2.4 檔節點緩存的實現 290
8.3 打開、關閉文件 304
8.3.1 打開、關閉檔的數據結構 305
8.3.2 打開、關閉文件的全域變數 308
8.3.3 打開、關閉文件的API 309
8.3.4 打開、關閉檔的實現 309
8.4 讀/寫文件 319
8.4.1 讀/寫檔的數據結構 320
8.4.2 讀/寫文件的全域變數 323
8.4.3 讀/寫文件的API 323
8.4.4 讀/寫檔的實現 323
8.5 其他功能 337

第9章 雜項檔案系統 338
9.1 檔案系統的掛載 338
9.1.1 第一次載入根檔案系統 338
9.1.2 第二次載入根檔案系統 340
9.2 記憶體檔案系統 340
9.2.1 記憶體檔案系統的數據結構 340
9.2.2 記憶體檔案系統的全域變數 340
9.2.3 記憶體檔案系統的API 341
9.2.4 記憶體檔案系統的實現 341
9.3 設備檔案系統 349
9.3.1 設備檔案系統的數據結構 349
9.3.2 設備檔案系統的全域變數 350
9.3.3 設備檔案系統的API 351
9.3.4 設備檔案系統的實現 351

第10章 LEXT3檔案系統 358
10.1 簡介 358
10.1.1 第一塊 359
10.1.2 塊組描述符 359
10.1.3 塊點陣圖 360
10.1.4 檔節點點陣圖 360
10.1.5 文件節點表 360
10.1.6 文件節點 360
10.1.7 檔日誌 362
10.2 LEXT3 363
10.2.1 LEXT3的數據結構 363
10.2.2 LEXT3的全域變數 371
10.2.3 LEXT3的API 372
10.2.4 LEXT3的實現 373
10.3 檔案系統日誌 397
10.3.1 日誌的數據結構 397
10.3.2 日誌的全域變數 405
10.3.3 日誌的API 405
10.3.4 日誌的實現 406

第11章 雜項 438
11.1 klibc 438
11.2 網路子系統 440
11.3 SIMPLE-KSHELL 440