应用视角的操作系统
1. 程序：解释与编译
1.1. 单步解释执行 C 程序
C 解释执行器
虽然我们不大费周章去实现一个 SimpleC 的解释器 (烧一些 tokens 完全也可以做到)，但我们可以在 gdb 中模拟这个效果：我们可以主动把程序改写成 SimpleC 的形式，在 gdb 中单步，就收集到了程序运行的状态和迁移，从而反过来 “看” 解释器是如何执行的。
理解计算机程序：函数调用
Tower of Hanoi: C++ 课的噩梦
- 第一次领教了计算机里的 “函数” 不是数学里的 “函数”
- 总有一种 “搞懂了，又没完全搞懂” 的感觉
- 有多少同学自信能不借助 AI 写对一个非递归的版本？
- 后悔没有选修 SICP 了 (里面讲了函数式编程呢)
汉诺塔
汉诺塔是递归和分治的经典问题，而同学们也曾经在理解这个程序的时候遇到困难。遇到困难是正常的：C/C++ 中的 “函数” 和数学的函数很不一样，例如我们可以把 Fibonacci 数列的递归写成
int x = f(n - 1);
int y = f(n - 2);
// 也可以 return y + x;
return x + y;
或是任意调换函数调用的次序，但汉诺塔不行。
不行的根本原因在于汉诺塔中的 printf 会带来全局的副作用。但 C/C++ 遵循 “顺序执行” 的原则，函数的执行有 “先后” (不像数学的函数，先后是无关的)，按照不同顺序调用会导致程序输出不同的结果。实际上，C 标准中 return f(n - 1) + f(n - 2); 甚至不保证从左到右的调用顺序。(但现代编译器为了防止产生难以理解的执行，通常按照自然顺序调用、不做激进优化。)
1.2. 编译器
RISC-V 处理器模拟器
C 语言实现的 single-header RISC-V32IMA 系统模拟器 (项目源自mini-rv32ima)。因为有 M-Mode，这个模拟器可以运行几乎 “任意复杂” 的程序——甚至是没有 MMU 的 Linux。我们稍稍修改了这份代码，更好地体现《操作系统》课程的教学目标。
什么是编译器
“编译器是一种将高级语言转换为低级语言的程序。” 这个定义不错；但到底什么是 “编译正确”？编译正确意味着对于任何输入，编译后程序的执行结果都和执行 C 语言形式语义的结果等价 (包括输出和终止)。这个定义其实给了编译器很多优化的空间——例如，所有最终 “用不上” 的计算都可以抹去。现在的编译器为了确保编译正确性，能做的优化相对有限，一个著名的论断是 “编译器不能把冒泡排序优化成快速排序”——虽然在今天也许不再是这样了。
1. 操作系统上的最小程序
最小可执行文件
为了理解操作系统上的程序，我们的目标是构造一个能直接被操作系统加载且打印 Hello World 的指令序列。如果你能想到这一点，剩下的一切都可以让 AI 帮助你。
2. 操作系统上的应用世界
2.1. 各式各样的应用程序
操作系统上的应用程序
天天说操作系统，但我们其实是感知不到操作系统存在的
- 能感受到的是操作系统上运行的程序 (进程)
2.2. 应用程序是什么
我的第一次二进制逆向 (~2000)
¥5 一张盗版游戏光盘的时代……
- 人畜无害的《大富翁 4》，却藏了一个神秘的文件夹
- 大家知道 “Elf”？(不是 a.out 的 Elf)
- 可是难度实在太高了 😭
- GAME.SAV 里有一串神秘的 0x00 0x00 0x01 0x00 0x00 代表了解锁 CG 的 “进度”
2.3. 用正确的工具 “打开” 应用程序
Takeaways
程序 = 状态机 (变量 + 栈)，通过指令/语句不断迁移状态。操作系统提供了一组抽象和 API：进程管理 (fork, execve, exit)、文件/设备管理：(open, close, read, write)、存储管理：(mmap, brk)……通过 strace 观察程序的行为，我们确认了 “真实” 的应用程序确实只是计算 + 系统调用实现的。
阅读材料
本次课没有书本阅读材料；但你可以花一些时间和 AI 对话，了解一下 GNU Coreutils, Binutils，建立 “手边有哪些可用的命令行工具” 的一些印象，并且让 AI 带着你玩一玩这些应用。你还可以浏览 gdb 文档的目录，找到你感兴趣的章节了解，例如——“Reverse Execution”、“TUI: GDB Text User Interface”……对于你有兴趣的命令行工具，可以参考 busybox 和 toybox 项目中与之对应的简化实现。Toybox 现在已经成为了 Android 自带的命令行工具集。