一個字節的奇妙之旅：白話電腦系統

目   錄

第 1 部分 馮·諾依曼機器的雛形

第 1 章 電容器中的數據   3

1.1 電容器與晶體管  3

1.2 整數類型  9

1.3 字符與字符串  29

1.4 閱讀材料 36

第 2 章 指令計算的藝術  37

2.1 指令即數據 38

2.2 URM：一種理論電腦  42

2.3 RISC-V 解釋器 45

2.4 讀取指令：IF  48

2.5 指令解碼：ID  55

2.6 執行指令：EX  62

2.7 訪問內存：MEM  69

2.8 寫回寄存器：WB  72

2.9 解釋執行樣例程序 74

2.10 閱讀材料 79

第 3 章 過程調用的魔法  80

3.1 控制轉移與返回  80

3.2 棧：表達式求值器 86

3.3 Prologue 與 Epilogue  91

3.4 分配局部變量. 97

3.5 參數傳遞與返回值 99

3.6 返回值  104

3.7 遞歸函數 106

3.8 閱讀材料 119

第 4 章 容量與速度的均衡 120

4.1 多層次儲存 120

4.2 偉大的洞見：局部性原理 124

4.3 組相聯式映射  126

4.4 查找緩存行 127

4.5 緩存行的狀態  132

4.6 淘汰策略：LRU  135

4.7 緩存中的 Load/Store  137

4.8 計數器分析 140

4.9 矩陣轉置問題  142

4.10 線程級並行中的緩存一致性 146

4.11 閱讀材料 154

第 2 部分 系統與應用的對話

第 5 章 虛擬與物理的內存 159

5.1 從源代碼到進程  159

5.2 進程的虛擬地址空間 164

5.3 多級頁表：虛擬地址映射 168

5.4 共享頁：寫時復制的詭計 182

5.5 頁錯誤處理程序  184

5.6 按需分配/分頁  186

5.7 頁回收機制 187

5.8 反向映射：從 PPN 到 PTE  194

5.9 TLB：緩存. 197

5.10 閱讀材料 199

第 6 章 同時運行多道程序 200

6.1 進程的幻覺 200

6.2 進程控制塊 202

6.3 中斷與異常 207

6.4 內核棧與 Trap frame  214

6.5 切換虛擬內存  217

6.6 Fork 系統調用 220

6.7 閱讀材料 225

第 3 部分 精彩紛呈的程序

第 7 章 紅黑樹索引. 229

7.1 從 VMA 開始  229

7.2 二叉搜索樹 230

7.3 AVL 樹. 233

7.4 紅黑樹的平衡性  235

7.5 紅黑樹的結構體  237

7.6 鏈表的插入與刪除 239

7.7 紅黑樹的插入操作 242

7.8 紅黑樹的旋轉  245

7.9 紅黑樹的刪除操作 249

7.10 處理雙黑結點  254

7.11 區間查詢 258

7.12 紅黑樹索引程序 260

7.13 閱讀材料 266

第 8 章 λ 表達式求值器 267

8.1 λ 表達式  267

8.2 抽象語法樹 271

8.3 α 歸約與約束變量 272

8.4 β 歸約與二叉樹操作 276

8.5 β 範式與歸約策略 279

8.6 實現 λ 表達式求值器 285

8.7 常見的 λ 表達式. 292

8.8 遞歸函數與不動點組合子 295

8.9 閱讀材料 300

附錄 A 常用的 C 語言標準庫函數 302

附錄 B RISC-V 指令釋義 307

參考書目 311