1.应用视角的操作系统

操作系统有三条主线：“软件 (应用)”、“硬件 (计算机)”、“操作系统 (软件直接访问硬件带来麻烦太多而引入的中间件)”。想要理解操作系统，对操作系统的服务对象 (应用程序) 有精确的理解是必不可少的。

指令序列和高级语言的状态机模型；回答以下问题：

  • 如何在操作系统上构造最小/一般/图形界面应用程序？

  • 什么是软件 (程序)，如何理解程序？

  • 什么是编译器？编译器的工作原理，编译器把一段程序翻译成什么样的指令序列才算 “正确”？

1. 构造一个最小的程序

操作系统服务程序，以一个最简单的程序为例子，看看是如何被操作系统服务的。但是什么样才是最简单的呢？

第一个 c 语言程序

vscode 终端命令行工具都是操作系统的程序，要更深刻的理解什么是操作系统里的程序。写一个最小的程序。如何定义小？

#include <stdio.h>
int main()
{
    printf("Hello world\n");
}

足够小，甚至没有 return 0 ，为了让这个代码跑起来，一些工具和命令：

  • gcc a.c -o a.out 编译

  • file a.out 查看文件类型，猜文件是什么类型

  • ls -l a.out 可以看到文件大小

  • objdump -d a.out | less 看看到底大不大，一个工具 objdump。来看一个可执行程序的二进制代码。

  • --verbose 查看所有的选项

我们看汇编代码，甚至发现没有 printf ，在反汇编里，看到编译器把 printf 优化成了 puts，省了一个换行，最重要的，puts 的代码在这个文件里也没有，它真正的实现在libc里，所以这个程序看起来小，实际一点都不小。

  • gcc hello.c -static 静态链接 libc

  • objdump -d a.out | wc --lines 看看有多少行 ，149488

静态链接编译出来的可执行文件巨大，因此，这个程序一点也不小。不小的原因？编译器到底做了什么？这个事情也是可以知道的，我们想看更多的细节，看gcc的日志，以及所有的编译选项：

  • gcc hello.c -static --verbose

输出也有很多可以研究的东西，比如为什么出来的是x86的程序，我们可以看到所有默认的选项的东西、默认的命令行的参数。看到include的path，。我们还可以看更多的东西，看二进制文件是怎么连接出来的

  • gcc hello.c -static -Wl,--verbose

可以看到每个section，c语言可以用end的符号代表数据区的结尾，不需要定义。

手动链接控制程序大小

强行编译 + 链接：gcc -c + ld。

c语言的编译过程，强行手动走一遍编译流程。直接不包含 stdio.h

int main()
{
    printf("Hello world\n");
}

  • gcc -E hello.c -o hello.i

  • gcc -c hello.i -o hello.o

有警告但是不要紧，这个hello.o真的是最小的。

  • ld hello.o

报错了

ld: warning: cannot find entry symbol _start; defaulting to 0000000000401000
ld: hello.o: in function `main':
hello.c:(.text+0x10): undefined reference to `puts'
ld: 警告: 无法找到项目符号 _start; 缺省为 0000000000401000
ld: a.o: in function `main':
5-1.c:(.text+0x13): undefined reference to `puts'

有个警告没有 _start ，此外引用了一个没有定义的符号 puts 这在初学C的时候经常遇到，编译不会报错但链接会，那么删除printf好了。

int main()
{
}

再次手动操作，ld 有个警告，手动处理。

  • ld hello.o -e main 指定 main为入口

或者把函数名改成 _start 绕过 warning，

int _start()
{
}

这是一个最小的C程序。但是如果运行的话会报一个segmentation错误 [1] 4532 segmentation fault (core dumped) ./a.out。为什么呢？

如果加一个死循环。

int main()
{
    while(1);
}

2024 ，请求 gpt 的帮助，很有可能能给出合适的回答。许多底层开发者会遇到问题、学过的东西会以某种形式存放在互联网上，吸收了天地精华的大语言模型能够给出一些正确的回答。gpt 的出现会给学习方式带来变化，最重要的是问出好的问题。

加了以后就可以运行了，说明这个循环直接在操作系统上运行了。虽然不完美，但是离最小的程序比较近了。但是不管怎么说，这个程序很小 size a.out 可以看到只有90多个byte。这时候需要尝试观测程序的运行状态。用 gdb 调试器。

我们到现在，希望调试他，并且希望在程序的第一条指令停下来，然后单布执行。所以，在学习计算机或者编程的时候，只要能问出正确的问题，就离解决不远了。搜索引擎都能帮助我们找到，所以距离计算机专家的距离并不远，就是问出正确的问题。

"gdb如何在第一条指令前停下来"

去问google，stackoverflow，甚至chatgpt可以给出相当具体的步骤。当 ai 的潮流来临时，问出问题，就是人与人之间最大的差别。
>gdb a.out
(gdb)starti 
(gdb)layout asm
(gdb)info registers
(gdb)p $rsp

这个程序在刚加载时，是非常干净的状态，所有寄存器都是0，唯一比较奇怪的是栈指针，所以返回的时候出问题了。

单步运行，发现到了一条 ret 的指令出错了，既然出错了，我们还是从状态机的角度去理解。来看ret的行为，

  • rip <- m[rsp]

  • rsp = rsp + 8

所以，如果这条指令出错，要么是rsp不合法，要么是ip不对。

通过这个例子，也有一些更本质的思考，计算机系统本质上是个状态机。CPU 是个无情的执行指令的机器，因此推论mov 指令 ret 指令都是计算，即改内存或者改寄存器的状态，那么也就是说，程序停不下来，程序无法自己退出自己。而且，指令集里没有一条关闭计算机的指令，但是点了关机选项计算机却能关闭。

这些事情是由操作系统实现的。关机实际上是操作系统和硬件协作实现的。那么如何让程序退出？

因此必须设计一条指令让他停下来。这就是 syscall，约定好一些参数放到指定的寄存器里，执行 syscall ，操作系统就接管了。

#include <sys/syscall.h>

int main()
{
	syscall(SYS_exit, 42);
}

在终端去查看返回值 echo $?，没问题，正常返回了。同样去调试。发现调用了一个库函数 syscall@plt，后面会说。如果追踪下去，最终这段函数就是给各种寄存器赋值，然后执行 syscall 指令。实际上是准备好了系统调用的参数，然后把自己完全交给操作系统，请求销毁自己。

最小的程序

程序本身唯一能做的是计算，把打印的字符计算出来，然后找操作系统帮忙。

一个成功的实现。如果我们也想实现这样的代码，也完全可以做到。

#include <sys/syscall.h>

.globl _start
_start:
  movq $SYS_write, %rax   // write(
  movq $1,         %rdi   //   fd=1,
  movq $st,        %rsi   //   buf=st,
  movq $(ed - st), %rdx   //   count=ed-st
  syscall                 // );

  movq $SYS_exit,  %rax   // exit(
  movq $1,         %rdi   //   status=1
  syscall                 // );

st:
  .ascii "\033[01;31mHello, OS World\033[0m\n"
ed:

首先生成可重定位文件 gcc -c a.S -o a.o 然后手动链接 ld a.o，就有了可执行文件。

这段代码用了gcc编译，.S 和编译器生成的不太一样，用了include还有宏，这段代码是经过了gcc的预编译。

C 语言特性，有些头文件可以暴露给汇编。ASSEMBLER 区分

系统调用的神秘数字从哪里知道的呢？，查看手册

syscall (2), syscalls (2) -- RTFM & RTFSC 东西就在这里，如何找到他。

从哪里知道这些代码的呢？手册 man syscall ，关于函数怎么用，甚至还有每个体系结构是如何调用的。 x86-64 是用 syscall 实现的，i386 使用 int $0x80 实现的。手册里也给出了约定好的使用的寄存器。

所以，神秘代码并不神秘，神秘数字也是有来源的。

这个红色的字体，使用ANSI ESCAPE CODE 实现。

有了这个东西，就可以在终端上搞出任何东西。
- telnet towel.blinkenlights.nl
  - 电影 ctrl + ] 输入q退出
- dialog --msgbox 'test' 8 32
  - 打印出对话框
- ssh sshtron.zachlatta.com

程序是状态机，状态是 gdb 里可以看到的内存和寄存器。初始状态由 ABI 规定，状态迁移分两类

  • 随便一条什么计算指令(寄存器到寄存器，内存到寄存器，寄存器到内存)

  • syscall 指令

程序是个状态机

这个最小的程序里就已经包含了操作系统。在他的眼里，操作系统就是 syscall

到这里，提前放出后面的内容：状态机视角的程序

  • 程序 = 计算 -> syscall-> 计算 -> syscall

2. 操作系统上的程序

所有的程序，和刚刚的最小程序没有本质区别。程序 = 计算 -> syscall -> ...

汇编和C没什么区别，就差了个编译器。

操作系统收编了所有的硬件/软件资源，操作系统说你行就行，不行就不行。只能用操作系统允许的方式来访问操作系统中的对象，从而实现操作系统的霸主地位。

举个例子

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>

void try_open(const char *fname) {
  int fd = open(fname, O_RDWR);
  printf("open(\"%s\") returns %d\n", fname, fd);
  if (fd < 0) {
    perror("  FAIL");
  } else {
    printf("  SUCCESS!\n");
    close(fd);
  }
}

int main() {
  try_open("/something/not/exist");
  try_open("/dev/sda"); // hard drive
}
open("/something/not/exist") returns -1
  FAIL: No such file or directory
open("/dev/sda") returns -1
  FAIL: Permission denied

可以看到，操作系统拒绝我了。所以操作系统在应用程序眼里，就是个 syscall ，操作系统里面有很多对象，syscall 是个API，通过这个东西可以访问所有东西。

可执行文件和普通文件也没什么区别。二进制文件和文本文件一样，可以直接vim打开，也可以直接用二进制编辑文件修改 :%!xxd。

所有的程序都是状态机。这个理解还有更深层次的内涵，一个人畜无害的问题：一个 hello world 程序的第一条指令在哪里？用 gdb 试试

0x00007ffff7fe32b0 in _start () from /lib64/ld-linux-x86-64.so.2

可以看到，第一条指令去找一个文件，那么为什么是这个文件呢？必须是这个文件吗？

在gdb里info proc mapping还可以看到其他的在内存里的东西。程序是状态机，那么总有个初始状态，这个问题等价于，操作系统给的初始状态是什么？答案就是gdb告诉的一个so.2的文件。

main之前发生了什么？加载器，加载了libc，完成了一些初始化，这是个很复杂的过程，后面会学习到。

理解了这些东西就可以去解释一些有意思的程序，比如说

#include <stdio.h>

__attribute__((constructor)) void hello() {
  printf("Hello, World\n");
}

// See also: atexit(3)
__attribute__((destructor)) void goodbye() {
  printf("Goodbye, Cruel OS World!\n");
}

int main() {
}

main完全是空的，但是可以设置constructor这样一个东西，这是如何实现的？main的开始结束并不是整个程序的开始和结束。

接着追问，还有更多有意思的东西。那么为什么是这个so.2文件呢？必须是这个文件吗？当然可以是其他的，比如说 rtfm.so

直接用vim编辑a.out，替换字符，:%!xxd查看二进制文件，修改以后:%!xxd -r写回去。直接把可执行文件的原数据改掉了。

  • R 替换模式

  • ln -s ld-linux-x86-64.so.2 rtfm.so 软链接，相当于快捷方式

在使用gdb调试，就是我们自己的东西了。

所以所有计算机的东西都不存在玄学，所有东西都有解释。状态机是一个非常严谨的数学对象，数学的含义是所有东西都被严格定义。C代码汇编还是二进制代码，都有严格定义，整个计算机世界都是这样的，所有东西都有解释。

一个不知道的bug，只要能复现，就有信心能调对。

如果再问，这个a.out执行的时候，发生了哪些系统调用？所有的东西都建立在确定的机制上，这个问题应该是可以回答的。所以有个工具 strace

In general, trace refers to the process of following anything from the beginning to the end. For example, the traceroute command follows each of the network hops as your computer connects to another computer.

strace ./a.out

可以看到所有的系统调用。

每个系统调用就对应了一个 syscall 指令，完全对应。一些关注的小点

  • 所有程序都是被操作系统加载的，通过另一个进程执行 execve 设置为初始状态

  • 状态机执行使用各种各样的系统调用

    • fork, execve, exit

    • open, close, read, write

    • mmap, brk

  • 直到 _exit(exit_group)

所有的东西，包括浏览器游戏杀毒软件病毒。

比如果，编译器这个东西，看看他是怎么使用操作系统的 strace -f gcc test.c

太长了，把输出丢到vim里面 strace -f gcc test.c |& vim -

  • 管道给编辑器

  • 编辑器里还可以grep

想看看gcc启动了什么进程，在vim里调用 :%!grep execve，为了看的更清除可以:set nowrap

对于失败的，可以 :%! grep -v ENOENT 反向(reversed)过滤掉不需要的，还有些技巧比如 :%s /, /\r /g，用一点点命令行工具，用一些自动化的脚本，就可以看到gcc调用的所有的东西。

所以操作系统是一个确定的东西。

甚至可以看看图形界面发生了什么 strace xedit， 这是个单进程的，原则上，理解这个，就理解所有的图形界面如何工作，背后的基本原理是类似的。这个小程序做的事情就是各种发消息，收消息。

平时用的时候，操作系统是个完整的应用生态。一层层叠起来的。比如 grep ls sh 最最基本的操作系统核心工具；在核心工具往上 有一些命令行工具如 gcc python ；再往上有各种 app

这些程序和 minimal.S 没有区别。

修改二进制可执行文件，简单的 hack，如果这个事可以做，那么同样的方式可以修改 windows 的二进制可执行文件。该游戏存档，调试游戏程序，在运行时观察哪里变化了，简单的逆向工程。

需要合适的工具来理解复杂的程序的工作原理是否和 minimal 一样。

apt 是 dpkg 的套壳。

strace 工具，理解程序是如何和操作系统交互的。观测状态机里执行的 syscall。这是一个很有力的工具。

strace ./minimal

可以看到调用了 exevce write exit 等。同样的可以观察更复杂的程序，任何一个程序都能，。

任何程序都和这个最小的程序是一样的，

  • 从被操作系统加载开始

    • 另一个进程执行 execve 设置为初始状态

  • 经历状态机执行(计算 + syscall)

    • 进行管理 fork execve exit ...

    • 文件/设备管理 open close read write ...

    • 存储管理 mmap brk ...

  • 最终调用 _exit 退出

任何复杂的事情都是，做计算，算出系统调用的参数，然后躺平交给操作系统。

一些实际的例子

strace -f gcc hello.c -o hello # -f 跟踪 gcc 创建的所有子进程
strace -f gcc hello.c -o hello | vim - # 编辑器里 %!grep

出来的东西很多，可以问出问题：

  • ld 脚本在哪里

  • include 的东西在哪里

  • ld 是 gcc 内嵌的还是调用的 这些答案都能在输出日志里找到。事实上 gcc 是调用外部的 ld

还有一个实际的例子，图形界面程序。

strace xedit

同样导出查看strace日志，查看后可以看到自己不绘制任何界面，只是在内存里计算出(想好)需要显示什么东西，然后把所有的东西以数据的形式通过操作系统送给了另外一个程序(窗口管理器)。窗口管理器管理一些东西然后写到 fb0 这个文件里去即可。

操作系统的职责：提供让应用程序舒服的抽象(对象 + API)

  • 比如进程，文件 fb ，就是对象

  • 系统调用

任务管理器的实现，pstree，看 C 语言源码。

3. 如何正确的理解程序？

前面观察的程序是二进制的，指令序列+syscall，但是写的程序最起码也是 C 语言的代码。C 代码是一定要编译成 bin 的。

  • 为什么(通常)没在 C 代码里看到 syscall

  • C 代码如何变成二进制文件

  • 编译器能做什么样的优化，不能做什么样的优化(非传统操作系统课程内容)

C 与汇编

一个问题：什么是 C 语言程序，C 程序是不是个状态机。能否写一个 C 语言的解释器。

gdb 是比较像是 C 语言解释器的，gdb就有点像解释器，一步一步执行语句，功能类似解释器，在layout src视角下。 gdb 里的 C 每一步执行的是一条语句，变量是状态。所有 C 语言也是状态机。

两个状态机的关系

  • C 语言变量 对应 汇编的 reg + mem

能不能写一个输入 C 源代码的东西，然后一条一条执行，像 gdb 一样可以打印变量。python 解释器，C 解释器。

在此之前，看一个程序

递归和非递归

这里使用一个稍微简单的类似的思路的例子，写一个非递归的汉诺塔。

事实上，非递归的这个例子并不简单，第一次看的话，甚至连个思路都不容易有，什么是非递归呢？不如问问chatgpt，一个更简单的例子，给一个表达式的字符串，分析运算的优先级，计算出表达式的结果。

汉诺塔是学习程序设计的一个经典的例子，用来讲递归思想的，重新拿出来复习一下

void hanoi(int n, char from, char to, char via) 
{
  if (n == 1) 
  {
    printf("%c -> %c\n", from, to);
  }
  else 
  {
    hanoi(n - 1, from, via, to);
    hanoi(1,     from, to,  via);
    hanoi(n - 1, via,  to,  from);
  }
}
void hanoi(int n, char from, char to, char via) {
  if (n == 1) printf("%c -> %c\n", from, to);
  else {
    hanoi(n - 1, from, via, to);
    hanoi(1,     from, to,  via);
    hanoi(n - 1, via,  to,  from);
  }
  return;
}

我们需要调用一下

#include <stdio.h>
#include "3-1.mmm"

int main()
{
	hanoi(3,'A','B','C');
}

这里可以看出，include可以包含任何东西，预处理阶段的东西，形式语义就是复制和粘贴，找这个文件，把内容粘贴过来，仅此而已。

C语言的形式语义，什么是C语言对应的状态机，一个很抽象的状态机

看起来很抽象，事实上，用 gdb 工具运行起来，就已经在状态机视角了。

黑色的条代表当前的语句，当前的状态，每次step都可以看到栈帧

(gdb)layout src #源代码视角
(gdb)start #源代码视角
(gdb)s #单步
(gdb)info frame #看栈帧

C语言程序是个状态机，这是对程序的正确理解。但是这还是“粗浅”的理解，还不到位。

把理解落实成可执行的代码，这才叫理解了。

比如计算机系统基础，什么是指令集，什么是计算机。

写一个全系统模拟器，才算真正理解了。

对于C语言程序是个状态机的理解，可以去写一个C语言解释器。

C语言程序的状态有些什么呢？这就有点复杂了，

  • 全局变量肯定是状态的一部分

  • 函数调用是什么？

    • push frame(frame.PC=入口)

  • 函数返回是什么？

    • pop frame

整个内存里所有的东西是C语言的状态，每执行一条语句，状态就变一下。然后我们是不是可以不以为每一种语句都写出精确的程序执行一步是什么样的行为，这就可以实现一个C语言的解释器了。

C语言程序的一个状态机模型：list of stack frame

这个思路的一个应用：把任何递归程序转换为非递归程序

用递归实现，不用递归实现

非递归，如何实现呢？思路是去模拟栈，

/* 一个栈帧，pc+所有的参数 */
typedef struct {
  int pc, n;
  char from, to, via;
} Frame;

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

/* 栈顶pop */
#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);
    }
  }
}

这看起来，好像和递归的也差不多，调用的部分也差不多，但是这个程序可以工作，这个程序展示的是

编程语言也是个状态机，C也是状态机，当我们谈论C语言的状态机的状态是什么的时候，要想到这个程序。

写不出非递归的程序，原因是不清楚函数的调用。

函数调用就是在栈帧的顶上加一个栈帧。函数的返回就是把顶上的栈帧抹掉。

这些就是C语言的形式语义。理解了这些，我们可以把任何C语言改写成只有if和goto的形式，这就相当于实现了一个编译器。这就是编译器。

程序是状态机，每次走一小步，从一个状态变成下一个状态。重要的是要理解什么是状态。能写出代码来。

这样的非递归代码告诉我们，可以写任何非递归代码，包括C解释器。

甚至是A调用B，B调用A的递归。

当我们有了一个好的视角，有一段好的代码之后，就可以有个全新的认识。

所以 C 语言程序也是状态机。

程序也是状态机

数字电路系统本身是状态机，所有的程序都是运行在数字电路上的，所以程序本身也是状态机。

那么什么是C程序的状态？

  • 状态 = 堆 + 栈

  • 初始状态 = main

  • 状态迁移 = gdb 里面调试可以看到

C程序执行一条语句，那么堆栈里的东西在变化，这就是状态。

C 解释器

总是可以把一个 C 代码写成每次只干一件事，simple c，一行代码就像一个指令。

唯一不好实现的，函数调用，比如 main 函数递归调用自己。

C ：高级汇编语言

存在 C 代码到指令集的直接对应关系，状态机和迁移都可以直译，看到 C 就能想到背后的东西，内存分布式什么。

高级汇编的特点，因为在任何体系结构上都会有 C 编译器，C 就变成了一个特别好的移植兼容层，只要是用标准 c 写的，没有奇怪的依赖，那么几乎就可以在任何的机器上运行。

既是高级汇编，又去掉了对架构的依赖，。

甚至可以直接在 C 语言里内嵌汇编。

底层的理解

汇编代码，

计算机=数字电路=状态机

任何复杂的程序最终都会变为上面的样子。

那可执行程序和源代码又有什么样的关系呢？

不太像源程序的模型了，而是更像一个数字电路的状态机模型。

任意一个指令集，不管是RSIC还是X86，我们有一些内存，还有寄存器，也可以理解为内存这就是一个程序的基本状态。程序在CPU上执行，写模拟器带来的好处就是对CPU特别理解。取得指令，译码执行，然后生成新的状态。

gdb同样可以调试，切换到调试汇编代码的模式

(gdb)layout asm
(gdb)info reg

gdb是非常神奇的软件，可以在两种视角切换。

当理解了程序都是状态机以后，就可以研究一些有意思的事情了。

程序有初始状态，假设操作系统给的初始状态是确定的，没有任何的随机性。如果程序没有任何输入的话，指令永远是从PC这个位置出来的，那么状态机就是一条直线，永远是相同的结果，完全确定的系统。

事实上，有一些好玩的指令，是可以生成随机数的。

(gdb)wa $rax

这就意味着，状态机产生了分叉。也就意味着，在生成随机数的这个位置有 2642^{64} 个状态，这个图不可能被画出来，但是在概念上是存在的。这个状态机继续执行，有可能回到原来的状态。

这个模型有个非常有意思的性质，这个计算停不下来，假设指令都合法，停不下来的。如果所有的指令都只有运算的话，能做的事情很有限

没办法退出自己，没办法用printf输出东西

而我们的程序，最终都是运行在操作系统上，而且可以退出的，这个时候，就要有一条非常特别的指令 syscall

程序是个状态机，绝大多数指令都是纯计算，从 (M,R)(M,R) 里面算出 (M′,R′)(M',R') ，但是 syscall 把当前正在运行程序的所有东西无条件的全部交给操作系统，操作系统可以执行很长代码，决定下一个返回的 (M′,R′)(M',R') 。

读写文件，改变进程(运行中的状态机)的状态，结束自己。

程序还是状态机，这个程序还是内存和寄存器，每次也是执行指令，但是指令有两种，一种是计算，一种是 syscall ，所以的程序，浏览器，播放器，本质还是计算，但是算好，要想显示出来，需要交给操作系统来实现。

也即，程序 = 计算 + syscall

4. 编译器与优化

我们理解了程序，汇编和C，两种状态机。编译器做二者的转化，那么什么是编译正确？

非递归汉诺塔，如何看待程序是个状态机。然后用二进制代码，也是指令的状态机。

既然有两种状态机，一种是C的状态机，一种是汇编的状态机。这两种状态机当然是有关联的，他们之间的关联是什么呢？绝大部分时候都是在写C代码，然后通过一个程序生成汇编代码。编译器在做的一个事情：状态机之间的转换。

Code=Compile(Source)\text{Code} = Compile(\text{Source})

编译(优化)的正确性，什么样的编译是正确的？举个例子，没用的赋值，可以直接删掉。直接return了。S与C的可观测行为完全一致。

状态机视角给了一个简明的解释，C代码的状态机和汇编代码的状态机。

C里面有些东西是不可优化的比如 asm , volatile 。

正确的编译，就是所有不可优化的部分被正确的翻译到了汇编上。不可优化的部分，语义是对应的，此外其他的所有的东西都是可以优化的。

一个显然正确的低效的实现：解释执行。直接翻译Source的语义。观测一致性。

编译器在保证观测一致性的前提下改写代码(rewriting)

  • 内联函数，

extern int g;
void foo()
{
  g++;
  g++;
}
extern int g;
void foo(int x)
{
  g++;
  asm volatile("nop" : : "r"(x));
  g++;
}

不可优化的部分，可以来回挪动。

如何做一个完全不可优化的，compiler barrier，不可跨越的障碍

extern int g;
void foo(int x)
{
  g++;
  asm volatile("nop" : : "r"(x):"memory");
  g++;
}

还有另一种在后面并发的时候讲。

这里的状态机，最主要的内容实际上是定义了什么是正确的编译。

其实今天的编译器，远远达不到令人满意的程度。未来可能编译器还能发生很大的变化。本质上一个编译器满足上面的等价的要求就可以，所以为什么不能先理解代码的含义呢？再给一个等价的实现。

“编译器不可能把冒泡排序优化成快速排序”，将来有没有可能实现呢？如果能证明程序的等价性，现在有了AI，有github里海量的代码，为何不可以替换成等价但是跑得更快的呢》

当谈编译器的正确性时，就进入了PL(programming language)的领域。这里的人倾向用数学化的语言定义和理解一切。PL的一些paper，用数学证明一个编译器可以输出正确的代码，虽然这样的编译器性能不高，但是航天器上的代码，如果编译器有个BUG，后果没人可以承担。

https://xavierleroy.org/publi/compcert-backend.pdf

需要一些数理逻辑基础。

虽然但是，背后的直觉依然是个system/sofware

总结

什么是程序？

  • 程序 = 状态机

    • 源代码 Source ： 状态迁移 = 执行语句

    • 二进制代码 Code ： 状态迁移 = 执行指令

    • 编译器

  • 应用视角的操作系统

    • 一条 syscall指令

计算机系统没有玄学，一切都建立在确定的机制上。

  • 理解操作系统重要的工具

    • gcc

    • gdb

    • strace

    • binutils

上一页0.绪论下一页2.硬件视角的操作系统

最后更新于