一个字节的奇妙之旅：白话计算机系统

本书作为一本初学编程者的入门书，帮助读者了解整个计算机系统背后的思想。全书共分为三部分：第一部分偏体系结构，主要讨论冯诺依曼体系架构下的CPU计算过程。第二部分偏操作系统，主要介绍同时运行多道程序的抽象。第三部分偏数据结构与计算理论，主要介绍红黑树与lambda表达式。

赵阳旻，笔名Yangmin，现就职于微软（Microsoft）M365部门，负责网络服务的开发与维护。毕业于复旦大学计算机专业，卡内基梅隆大学软件工程专业。

第 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

这是一个字节的奇妙之旅，也是初学编程者的入门书，它诞生在一个计算机蓬勃发展的伟大时代。计算机以惊人的生命力蔓延、侵入、扎根到每一个领域，并在智能制造、电子商务、直播视频、广告推荐这些领域做出了自己的卓越贡献。不仅如此，计算机本身的各分支也毫不削减自己的发展速度，如深度学习、分布式软件架构、网络安全、数据库的每个领域都同时在学术界与工业界吸引了最聪明的人才与最大笔的投资。在这个时代，凡人力所不能及之处，皆有计算机的身影。

在这背后支撑整个计算机世界的，就是程序员，也就是我们。从计算机学院教授到互联网公司员工，每一个从业者在他们各自职业身份之前，都是一名程序员。

很多人在涌入计算机行业，他们的第一道门槛就是编程。可惜的是，编程的学习曲线并不平缓。光面对Hello World编译报错，很多人可能就要浪费一整天时光。这本书的写作动机就是把编程讲得更简单些，让学习曲线不那么陡峭，最好再开阔一些视野，通过编程看到背后的思想，激发对计算机编程的热情。

为此，我虚设三个角色：计算机科学家、电子科学家、数学家，代表各自的领域知识，通过对话阐明计算机系统设计背后的动机。编程中的很多实践并不是拍脑袋决定的，其实需要计算机系统知识的支撑。想要知其所以然，常常需要从数学、电子科学的角度去理解。颜师古注《汉书》云：“穷波讨源”，就是设置三个角色的宗旨大纲。

编程是一门非常独特的技艺，它像是一个纯粹的形式逻辑游戏。数学系学生做数理逻辑证明题，哲学系学生做分析哲学论述，程序员则是把一些字符串变成另一些字符串。但如果这样看待计算机，其实写不出优秀的程序。这是计算机科学本身特点所决定的，程序员必须深入思考这门游戏的载体，计算机本身。不要“在数学中”编程，而是“在计算机体系结构中”编程。程序员需要先在脑海中构想软件架构、设计模式、数据结构、储存系统，通过多个层次的抽象控制复杂度，再运用编程技巧落实到软件中，使得计算过程变为一个个字节，运行在计算机中。

为了说明这些计算机科学中的伟大思想，我会与读者一道编程。本书所有程序都可以在Linux中编译运行，读者可以选择一个简单易用的Linux发行版本（我的选择是Ubuntu），搭建自己喜欢的编程环境。不过，关于本书代码需要说明两点：首先是代码的排版，毕竟出版物被印刷在纸上，所以不得不在螺蛳壳里做道场，代码排版只得辗转腾挪。还有就是代码逻辑，所有代码只运行Happy Path。这是因为书中代码都只作示例，不宜用于任何生产环境。

希望本书对读者学习计算机有所增益。但书中错谬在所难免，读者发现错误还请不要嘲笑，如不吝告知，则将不胜感激。

编者

2024年8月