状态机

计算机系统都是状态机

一个简单的计算机系统：程序直接在 CPU 上运行(无操作系统)

这三个抽象层次(程序、指令集、CPU) 都可以用状态机来理解。

程序是个状态机：

C 语言的组成：

变量：计算的对象
语句：计算的操作流程
输入输出函数：让变量与外界交互

C 程序的状态机模型

状态集合：$S={< V, PC >}$
V = $\{v1, v2, v3, …\} = 程序中所有变量的取值(包括全局变量和局部变量)$
PC = 程序计数器 = 当前执行的语句位置
激励事件 $E = \{语句\}$
执行 PC 指向的语句
状态转移规则：
$next: S \times E -> S$
语句的语义$(semantics)$
初始状态 $S_0=< V_0,~ main 函数的第一条语句 >$

/* 1 **/ int main() {
/* 2 **/	int x = 1;
/* 3 **/	int y = 2;
/* 4 **/	int z = x + y;
/* 5 **/	printf("z = %d\n", z);
/* 6 **/	return 0;
/* 7 **/ }

对于的状态转移

S = <x, y, z, PC>
S0 = <?, ?, ?, 2> // '?' 表示未初始化
S0 = <1, ?, ?, 3>
S0 = <1, 2, ?, 4>
S0 = <1, 2, 3, 5>
S0 = <1, 2, 3, 6> // 输出 "z = 3"
S0 = <1, 2, 3, 结束>

C 程序真的是从 $main()$ 第一条语句开始执行吗？

理解程序的动态行为 -> trace 工具

1	int main(){return 0;}

再用 strace 工具

1 2	gcc a.c strace ./1.out

我们发现它执行了许多操作，但事实上，这段代码只有简单的一行，并且直接 return 0; 如果真的从 main 函数开始执行，那么应该直接退出。所以我们猜测这些操作要么是在 main 函数执行之前做的，要么是在返回之后。
1.c 中我们加入死循环。

1	int main(){while(1); return 0;}

我们发现程序卡在了这里。说明是在 main 函数之前输出的

说明了不是从 main() 函数第一条语句开始执行。

观察最初的 1.c
我们发现退出程序后还有一个 $exit\_group()$
实际上，程序并不是在 $return~0$ 之后结束，它还会执行一些额外的操作。

我们使用 gdb 调试工具。

1 2	gdb 1 starti

发现程序马上停在程序的开始。

同时，这个 _start() 函数并不在我们 1.c 文件中，在别的地方，也说明不是从 main() 开始。

查看 ISO/IEC 9899:201x:

执行环境调用一个专门的 C 函数。
执行环境有两种：独立环境 freestanding 和宿主环境 hosted

Freestanding environment

在独立环境下，这个专门的 C 函数由具体实现来决定。用它去调用 main 函数。

Hosted environment

在宿主环境下，这个专门的 C 函数名称为 main

手册定义了这个函数在宿主环境下叫 main

Program execution

可以看出一些语句的执行会引起副作用，导致执行环境的状态变化。由此可见，C 程序确实是一个状态机。

CPU 是个状态机

CPU = 数字逻辑电路 = 状态机
数字逻辑电路 = 组合逻辑电路 + 时序逻辑电路
状态集合：$S = \{< 时序逻辑元件的值 >\}$
具体包括寄存器、存储器、触发器等
激励事件 $E = \{ 组合逻辑 \}$
状态转移规则：
$next: S \times E -> S$
由设计中的组合逻辑电路决定
依据：架构师的设计文档
初始状态 $S_0 = < 复位时时序逻辑元件的值 >$

指令集是个状态机

指令集是软件和硬件之间的接口。
指令集是一本手册规范，定义了 CPU 执行指令的行为。
状态集合：$S = \{< R, M >\}$
$R = \{PC, x_0, x_1, x_2, …\}$
PC = 程序计数器 = 当前执行的指令位置
M = 内存
激励事件 $E = \{ 指令 \}$
执行 PC 指向的指令
状态转移规则：
$next: S \times E -> S$
指令的语义$(semantics)$
初始状态 $S_0 = < R_0, M_0 >$

用 C 程序理解指令

计算 1+2+…+100 的指令序列

// PC: instruction      | label: statement    
    0: li    x1,0       |   pc0: x1 = 0;
    1: li    x2,0       |   pc1: x2 = 0;
    2: li    x3,100     |   pc2: x3 = 100;
    3: addi  x2,x2,1    |   pc3: x2 = x2+1;
    4: add   x1,x1,x2   |   pc4: x1 = x1+x2;
    5: blt   x2,x3,3    |   pc5: if(x2 < x3) goto pc3; // branch if less than
    6: j     6          |   pc6: goto pc6;