源代码程序是状态机

  • 状态 = 堆 + 栈
  • 初始状态 = main 的第一条语句
  • 迁移 = 执行一条简单语句
    • 任何 C 程序都可以改写成 “非复合语句” 的 C 代码

C程序的语义

  • 状态 = stack frame 的列表 (每个 frame 有 PC) + 全局变量
  • 初始状态 = main(argc, argv), 全局变量初始化
  • 迁移 = 执行 top stack frame PC 的语句; PC++
    • 函数调用 = push frame (frame.PC = 入口)
    • 函数返回 = pop frame

非递归汉诺塔：switch模拟状态机，把不同状态的frame放入call中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef struct {
  u32 pc, n;
  char from, to, via;
} Frame;

#define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })
#define ret()     ({ top--; })

void hanoi(int n, char from, char to, char via) {
  Frame stk[64], *top = stk - 1;
  call(n, from, to, via);
  for (Frame *f; (f = top) >= stk; f->pc++) {
    switch (f->pc) {
      case 0: if (f->n == 1) printf("%c -> %c\n", f->from, f->to), f->pc = 3; break;
      case 1: call(f->n - 1, f->from, f->via, f->to);   break;
      case 2: call(       1, f->from, f->to,  f->via);  break;
      case 3: call(f->n - 1, f->via,  f->to,  f->from); break;
      case 4: ret();                                    break;
      default: panic();
    }
  }
}

二进制程序是状态机

  • 状态 = 内存  + 寄存器
  • 初始状态 = (稍后回答)
  • 迁移 = 执行一条指令

操作系统上的程序

所有的指令都只能计算

  • deterministic: mov, add, sub, call, …
  • non-deterministic: rdrand, …
  • 但这些指令甚至都无法使程序停下来

特殊指令：syscall

  • 把内存M、寄存器R完全交给操作系统，任其修改

  • 实现与操作系统中的其他对象交互

    • 读写文件/操作系统状态 (例如把文件内容写入M )
    • 改变进程 (运行中状态机) 的状态，例如创建进程/销毁自己

程序 = 计算 + syscall

在程序的两个视角之间切换

“状态机” 顺便解决了一个非常重要的基本问题：什么是编译器？

编译器：源代码S (状态机) → 二进制代码C (状态机)

编译 (优化) 的正确性 (Soundness):

  • S与C的可观测行为严格一致
    • system calls; volatile variable loads/stores; termination
  • Trivially 正确 (但低效) 的实现
    • 解释执行/直接翻译S的语义

操作系统中的一般程序

操作系统收编了所有的硬件/软件资源

  • 只能用操作系统允许的方式访问操作系统中的对象
    • 从而实现操作系统的 “霸主” 地位
  • 这是为 “管理多个状态机” 所必须的
    • 不能打架，谁有权限就给他

二进制程序状态机的初始/结束状态

  • main() 的开始/结束并不是整个程序的开始/结束

gdb info proc {mappings,...} - 打印进程内存