操作系统的本质：一个程序，用于管理硬件资源供其他程序调用
那问题就到了程序本身：程序应该如何定义？这引出了程序的状态机模型：
状态机
这东西我们在数电中接触过，硬件基础就是一堆触发器（RS、JK等）。状态就是寄存器保存的值，初始状态即寄存器初始值，迁移就是组合逻辑电路计算寄存器下一周期的值。
下面是一个寄存器的模拟程序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #define REGS_FOREACH(_) _(X) _(Y)
#define RUN_LOGIC X1 = !X && Y; \
Y1 = !X && !Y;
#define DEFINE(X) static int X, X##1;
#define UPDATE(X) X = X##1;
#define PRINT(X) printf(#X " = %d; ", X);
int main() {
REGS_FOREACH(DEFINE);
while (1) {
RUN_LOGIC;
REGS_FOREACH(PRINT);
REGS_FOREACH(UPDATE);
putchar('\n');
sleep(1);
}
}
|
程序的定义
源码视角
程序就是状态机。对于C程序而言，它的状态机模型如下：
1
2
3
4
5
| 状态=栈帧+全局变量
初始状态=main
迁移=执行栈顶的语句并转到下一条指令
函数调用=入栈
函数返回=出栈
|
这定义有很多应用，比如将任何递归程序就地转为非递归。虽然实际上递归就是这么实现的（一层递归建立一层函数栈、跳转地址压栈）。例如，下面就是手写函数栈展开递归：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <assert.h>
typedef struct {
int pc, n;
char from, to, via;
} Frame;
#define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })
#define ret() ({ top--; })
#define goto(loc) ({ f->pc = (loc) - 1; }
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); goto(4); } 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: assert(0);
}
}
}
|
二进制视角
实际上就是汇编视角。汇编程序分为几个段：数据段、代码段和栈段。加载程序就是加载初始状态，状态转移就是改变寄存器的值，转移方式就是执行指令。
这两个视角都可以用gdb来查看。
但是，操作系统又不是普通程序。因为操作系统不光处理计算任务，还需要能够暂停、退出程序等等。
在Linux中，有一条叫做systemcall（系统调用）的指令。它不负责计算，它把当前进程的状态交给操作系统，也就是允许操作系统任意更改程序。这使得进程可以和操作系统中的其他对象交互。
也就是说，对于程序而言，操作系统就是一个程序。参数就是应用程序本身的状态，输出就是程序要访问的资源。C程序main函数最后的return;就是这样的，它实质上是借助了syscall()，将程序状态变为某特定状态，再交给系统去处理。这就好比准备好要传递的参数，然后去调用函数一样。
回到主题。从二进制/操作系统的视角看来，程序是一个不停计算，并会穿插执行systemcall的状态机。
什么是编译器
编译器将源代码编译为二进制程序。从汇编状态机/C程序状态机的视角来看，实际上就是将后者翻译成了前者。编译（优化）的正确性（Soundness）就是在确保二者的可观测行为完全一致。
而关于编译器优化，我们可以使用compiler barrier来阻止优化：
1
2
3
4
5
6
7
| extern int g;
void foo(int x){
g++;
asm volatile("nop" : : "r(x)" : "memory");
g++;
}
|
上面的代码借助objdump查看反编译代码，可以看出，这两条g++并没有被-O2编译优化。
1
2
3
4
5
6
7
8
9
10
11
12
13
| $ gcc -O2 -c a.c && objdump -d a.o
a.o: file format elf64-x86-64
Disassembly of section .text:
0000000000000000 <foo>:
0: f3 0f 1e fa endbr64
4: 83 05 00 00 00 00 01 addl $0x1,0x0(%rip)
b: 90 nop
c: 83 05 00 00 00 00 01 addl $0x1,0x0(%rip)
13: c3 retq
|
除此之外，还有一种更强的barrier：__sync_synchronize();
观察编译器
使用strace，我们可以看到一个程序所有的系统调用。借助下面几个工具的组合，我们可以看到gcc如何编译程序：
1
2
3
4
5
6
7
8
|
#include <stdio.h>
int main(void){
printf("Hello, OS!");
return 0;
}
|
保存上面的文件后，执行下面的指令：
1
| strace -f gcc a.c |& vim -
|
我们可以在Vim中看到下面的输出
![[Pasted image 20230128215947.png]]
稍微修改后（:%!grep execve留下系统调用的行，:%!grep -v ENOENT删除失败的行，:%s/, /\r /g将参数换行显示，提高结果可读性），可以分析得到下面的结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| 1 execve("/usr/bin/gcc"
2 ["gcc"
3 "a.c"]
4 0x7ffd181ca900 /* 30 vars */) = 0
5 [pid 212] execve("/usr/lib/gcc/x86_64-linux-gnu/9/cc1"
6 ["/usr/lib/gcc/x86_64-linux-gnu/9/"...
7 "-quiet"
8 "-imultiarch"
9 "x86_64-linux-gnu"
10 "a.c"
11 "-quiet"
12 "-dumpbase"
13 "a.c"
14 "-mtune=generic"
15 "-march=x86-64"
16 "-auxbase"
17 "a"
18 "-fasynchronous-unwind-tables"
19 "-fstack-protector-strong"
20 "-Wformat"
21 "-Wformat-security"
22 "-fstack-clash-protection"
23 "-fcf-protection"
24 "-o"
25 "/tmp/ccf8oz38.s"]
26 0x251bbd0 /* 35 vars */ <unfinished ...>
...
|
上面就是gcc编译这个程序的全流程，以及全部的参数。这些系统调用都能看得到。也就证明了前面的结论：程序=系统调用+计算。我们写的算法题就几乎属于纯计算（只有最后的return 0;算个系统调用），平时使用的各种程序就属于系统调用+计算的类型。