【0到1的设计之路】计算机系统的状态机模型

Perface

在开始本文之前需要先介绍一下状态机的概念：

状态机不是实际机器设备，而是一个数学模型，通常体现为一个状态转换图。涉及到的相关概念是 State 状态，Event 事件，Action 动作，Transition 转换。状态机是计算机科学的重要基础概念之一，也可以说是一种总结归纳问题的思想，应用范围非常广泛。

状态机是有限状态自动机的简称，是现实事物运行规则抽象而成的一个数学模型。

状态机一般指有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机（英语：finite-state automaton，缩写：FSA），是表示有限个状态以及在这些状态之间的转移和动作等行为的数学计算模型。

有限状态机是在自动机理论和计算理论中研究的一类自动机。如下图所示，有限状态机归属于自动机理论范畴，从下面的自动机理论的领域分层图可以看出，越往外层，概念越复杂。

状态机中有几个术语：state(状态) 、transition(转移) 、action(动作) 、transition condition(转移条件) 。

• state(状态) ：将一个系统离散化，可以得到很多种状态，当然这些状态是有限的。例如：门禁闸机可以划分为开启状态、关闭状态；电扇可以划分为关、一档、二档、三档等状态。

• transition(转移) ：一个状态接收一个输入执行了某些动作到达了另外一个状态的过程就是一个transition(转移)。定义transition(转移)就是在定义状态机的转移流程。

• transition condition(转移条件) ：也叫做Event(事件)，在某一状态下，只有达到了transition condition(转移条件)，才会按照状态机的转移流程转移到下一状态，并执行相应的动作。

• action(动作)：在状态机的运转过程中会有很多种动作。如：进入动作(entry action)[在进入状态时进行]、退出动作(exit action)[在退出状态时进行]、转移动作[在进行特定转移时进行]。

如下图，就定义了一个只有opened 和closed两种状态的状态机。当系统处于opened状态，在收到输入“关闭事件”，达到了状态机转移条件，系统就转移到了closed状态，并执行相应的动作，此例有一个进入动作(entry action)，进入closed状态，会执行close door动作。

• 图片内容来自：橙子随记-什么是状态机？一篇文章就够了

状态机模型

一个不是特别严谨的定义

计算机系统都是状态机!

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

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

指令集体系（ISA）是规定处理器外在行为的一系列内容的统称，包括基本数据类型、指令、寄存器、寻址模式、存储体系、中断、异常以及外部I/O，规定了处理器的行为，是处理器的语言，是硅农和码农之间的桥梁，处理器的具体设计即ISA的硬件实现方式被称为微架构。

指令集体系结构（ISA）是计算机体系结构中的一部分，它规定了处理器可以执行的指令集合，以及每条指令所规定的操作数存放的地址空间、操作数类型、寻址方式和可访问地址空间的大小等内容。ISA是软件和硬件之间的接口，软件通过ISA来感知和使用硬件。

指令集体系结构包括以下部分：

• 指令集：处理器支持的可执行指令集合，包括基本数据类型、指令、寄存器、寻址模式、存储体系、异常事件处理和外部I/O等内容。
• 指令集编码：指令的字节级编码，不同的处理器家族有不同的指令集编码。
• 基本数据类型：处理器支持的基本数据类型，例如整数、浮点数、字符和指针等。
• 一组编程规范：为了使软件能够正确地使用处理器硬件，需要遵循一组编程规范，例如寄存器的使用方式、寻址模式的选择和异常事件的处理等。
• 寄存器：处理器内部的寄存器组，用于存储临时数据和执行计算。
• 寻址模式：指令获取操作数的方式，包括直接寻址、间接寻址和寄存器寻址等。
• 存储体系：处理器的存储体系结构，包括存储空间的大小和编址方式、操作数在存储空间存放时按照大端还是小端方式存放等。
• 异常事件处理：处理器在执行指令时可能遇到的异常事件，例如除以零、溢出和非法指令等，以及如何处理这些异常事件。
• 外部I/O：处理器与外部设备之间的数据传输方式，包括数据传输的协议和接口规范等。

不同的处理器家族有不同的指令集体系结构，例如Intel的IA32、IBM/Freescale的PowerPC和ARM的体系结构都有不同的ISA。不同的ISA可能会对处理器的性能和功能产生影响，因此选择适合特定应用的处理器类型是非常重要的。

程序是个状态机

大家眼中的C程序

C语言的组成

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

一个例子

int main() {
  int x = 1;
  int y = 2;
  int z = x + y;
  printf("z = %d\n", z);
  return 0;
}

C程序的状态机模型

x = (-b+sqrt(b*b-4*a*c))/(2*a);

如果执行的语句很复杂, 应该如何理解?

• 可以将复杂语句拆分成若干简单语句, 从简单语句理解状态转移
• 确实有工具做这件事: C Intermediate Language

C Intermediate Language：https://cil-project.github.io/cil/

语句的语义是谁说了算?

FM: C语言标准手册 ?

• 权威严谨, 但对新手来说不好读
• 追根溯源的唯一选择

C语言标准手册：https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

一看这个PPT就是理论扎实的学院派做的，如果对于集合和状态有点疑惑的，不要在意，现在想不通的问题，在未来的某一天你会想通的。

例: 真的是从main()第一条语句开始执行吗?

大家一定会觉得这是理所当然的, 至少很多C语言书籍都这么说

但怎么来动手验证一下呢?

要理解程序的动态行为, 当然是用trace工具!

$ cat a.c
int main() { return 0; }
$ gcc a.c
$ strace ./a.out

好像还有个exit_group(), 感觉从main()函数返回之后也有宝藏

调试器可以帮助我们更细致地理解这个问题

(gdb) starti

看看FM怎么说

5.1.2 Execution environments
Two execution environments are defined: freestanding and hosted. In both cases,
program startup occurs when a designated C function is called by the execution
environment...

有一个概念叫执行环境, 原来是它来调用一个专门的C函数

执行环境有两种: 独立环境(freestanding)和宿主环境(hosted)

5.1.2.1 Freestanding environment
1. In a freestanding environment (in which C program execution may take place
without any benefit of an operating system), the name and type of the function
called at program startup are implementation-defined.

在独立环境下, 这个专门的C函数由具体实现来决定

5.1.2.2 Hosted environments
5.1.2.2.1 Program startup
1. The function called at program startup is named main...

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

2. ...
— If the value of argc is greater than zero, the string pointed to by argv[0]
  represents the program name; ...
  If the value of argc is greater than one, the strings pointed to by argv[1]
  through argv[argc-1] represent the program parameters.

上次课提到的命令行参数=main()函数的参数, 原来是有手册依据的

5.1.2.3 Program execution
2. Accessing a volatile object, modifying an object, modifying a file, or calling
a function that does any of those operations are all side effects, which are
changes in the state of the execution environment...

一些语句的操作会引起副作用, 从而导致执行环境状态的变化

C程序确实是一个状态机

我们对C程序的行为建模, 从大方向来说符合手册

虽然main()函数不是真正的程序入口, 但足够用来理解状态机模型

RTFM

C语言标准手册精确定义了C语言的每一处细节

想了解一切细节发生的依据, RTFM是唯一正确的选择
大部分C语言的材料都没有覆盖到所有细节, 因此不要迷信书籍和博客

书籍和博客的作者对C语言的认识, 比不上C语言标准的制定者

正确的学习方法:

• 通过书籍入门
• 把书籍丢掉
• 通过手册成为专业人士

开放讨论: 公司不一定完全按标准来实现

从一个领域来看, 遵循标准有利于领域的稳定和繁荣

TCP/IP(网络), SQL(数据库), OpenGL(图形), 3GPP组织(通信), …

CPU是个状态机

CPU = 数字逻辑电路 = 状态机

CPU如何设计是微结构层次的话题

但无论怎么设计, 总归是一个数字逻辑电路

数字逻辑电路 = 组合逻辑电路 + 时序逻辑电路

• 状态集合
  • S={<时序逻辑元件的值>}
  • 具体包括寄存器, 存储器, 触发器等
• 激励事件E={组合逻辑}
• 状态转移规则next:S×E→S
  • 由设计中的组合逻辑电路决定
  • 依据: 架构师的设计文档
• 初始状态S0=<复位时时序逻辑元件的值>

例: Johnson计数器

// S = <A, B, C, D>
  S0 = <0, 0, 0, 0>
  S1 = <1, 0, 0, 0>
  S2 = <1, 1, 0, 0>
  S3 = <1, 1, 1, 0>
  S4 = <1, 1, 1, 1>
  S5 = <0, 1, 1, 1>
  S6 = <0, 0, 1, 1>
  S7 = <0, 0, 0, 1>
  S8 = <0, 0, 0, 0> = S0

从状态机的视角来说, CPU和这个计数器并没有本质上的区别

指令集也是个状态机

指令集是什么?

课本上通常会给一个抽象的定义, 例如

指令集是软件和硬件之间的接口

这句话本身是对的, 但对初学者来说没什么实际意义

你很可能还分不清软件和硬件的边界, 更别说它们之间的接口了

我们来进行这样的比喻: 指令集是一本手册规范, 使得

指令集手册定义了CPU执行指令的行为

就好比

C语言标准手册定义了C程序执行语句的行为

指令集和处理器是不同层次的概念

指令集和处理器都各自有3种知识产权模式

• 开放免费(Open & Free) - 不花钱就能用
• 可授权(Licensable) - 交钱就能用
• 封闭(Closed) - 有钱也不能用

关于RISC-V和开源处理器的一些解读：https://mp.weixin.qq.com/s/9PX5n_ZPjWM1OyqnijlIPw

正确理解开放指令集和开源处理器

• 封闭指令集不可能做出开源处理器(矩阵的左下三角)

• 开放指令集并不意味着做出的处理器必须开源(矩阵的右上三角)

• 过去只有可授权和封闭模式, 非专业人士大多只看到矩阵的对角线

  • 不易区分指令集和处理器

RISC-V好比处理器领域的马克思主义，RISC-V手册好比《共产党宣言》，全世界各国都可以获取（即使是被极限制裁的俄罗斯），关键是谁能实践好，也就是参照RISC-V手册做出高水平的处理器芯片，进而影响和主导RISC-V的后续演进。

自测题

• X86是一种指令集规范?

是的，X86是一种指令集规范。X86指令集是Intel处理器架构的基础，包括8086、80286、80386等。随着技术的发展，X86指令集也在不断扩展和改进，例如通过添加新的指令和扩展浮点运算等功能。

• 苹果M1牛是因为采用了ARM指令集?

不是，不过苹果M1芯片采用了ARM指令集。苹果M1芯片是基于ARM架构的处理器，而不是传统的x86架构。ARM架构通常用于移动设备和嵌入式系统等领域，而x86架构则广泛应用于PC和服务器等领域。苹果M1芯片的采用使得苹果能够在其Mac电脑中实现更加高效能、低功耗的处理器。

• 国产处理器的实现和国外还有差距?

是的，国产处理器的实现和国外还有一定的差距。虽然中国在处理器设计方面已经取得了一定的进展，但是与国际领先水平相比，还存在一定的差距。这主要是由于技术积累、人才储备和产业链等方面的不足所导致的。因此，中国还需要在处理器设计方面加强研发和投入，提高自主创新能力。

• 几个月就可以定义一个新指令集?

几个月就可以定义一个新指令集是不太可能的。定义一个新的指令集需要经过深思熟虑和充分验证，以确保其功能完备、性能优越且易于实现。这个过程通常需要较长的时间和大量的技术积累，因此几个月内完成是不太现实的。

• 根据指令集规范实现一个处理器不容易?

根据指令集规范实现一个处理器确实不容易。指令集体系结构（ISA）是计算机体系结构中的一部分，它规定了处理器可以执行的指令集合以及每条指令所规定的操作数存放的地址空间、操作数类型、寻址方式和可访问地址空间的大小等内容。为了实现一个处理器，需要遵循ISA的规定，同时还需要考虑处理器的实现细节，例如寄存器的设计、流水线结构、异常处理机制等。这个过程需要大量的技术积累和经验，因此实现一个处理器并不容易。

• 给定一个指令集只有一种处理器实现?

给定一个指令集并不是只有一种处理器实现。一种指令集可以有多种处理器实现，这些处理器实现可以具有不同的性能、功耗和成本等方面的特点。例如，对于RISC-V指令集，有多种处理器实现可以采用，这些处理器实现可以根据应用场景和需求进行选择。

• 可以给一个处理器实现换一个指令集?

是的，可以给一个处理器实现换一个指令集。不同的指令集具有不同的特点和适用场景，因此有时候需要根据需求改变一个处理器的指令集。这个过程需要重新设计和实现处理器的微架构，同时需要考虑与新指令集相关的性能、功耗和成本等方面的问题。因此，给一个处理器实现换一个指令集并不是一件容易的事情。

---

答案: Yes, No, Yes, Yes, Yes, No, Yes

• 《从技术的角度来看，RISC-V 能对芯片发展、科技自主起到哪些作用？》
• 《4年21份资料10万字：记录RISC-V在中国的一条轨迹》

RTFM学习指令集

We intend this slim book to work as both an introduction and a reference to RISC-V
for students and embedded systems programmers interested in writing RISC-V code.

我们打算将这本小书作为RISC-V的介绍和参考资料，供有兴趣编写RISC-V代码的学生和嵌入式系统程序员使用

《The RISC-V Reader》是一本科普读物, 并不是官方手册

《The RISC-V Reader》的作者(David Patterson & Andrew Waterman)也来自RISC-V团队, 书的质量并不低

书中介绍了很多软硬件协同工作的例子和指令集设计的考量

据翻译团队透露, 书籍的中文版已经重新排版, 正在出版中

书名修改成《RISC-V读本》

但这仍然不能替代真正的官方手册

正确做法:

• 通过《RISC-V读本》学习RISC-V
• 通过《The RISC-V Instruction Set Manual》了解所有最新的细节
  • 例如原子指令语义的定义

指令集手册也定义了一个状态机!

Q: RISC-V处理器的复位PC值是多少?

A: RTFM (《The RISC-V Reader》中找不到答案)

用C程序理解指令

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

指令并没有想象中的那么神秘

• 就是用来改变状态机状态的激励

指令的两种表示:

• 符号化表示 - 面向程序员
• 编码表示 - 面向电路设计

指令集手册不仅仅包含指令

全称: 指令集体系结构(Instruction Set Architecture, ISA), 还有

• 输入输出
• 系统状态
• 中断异常
• 虚存管理
• 内存模型

这些都可以用状态机模型来描述行为

指令集手册通过定义状态机进行状态转移的规则, 来从概念上描述一台抽象计算机所具备的, 程序可以使用的功能

使用计算机底层功能的用户(系统程序员)无需了解具体的电路设计

只需了解计算机的行为即可 -> 状态机模型

程序如何在计算机上运行

编译

汇编

• 汇编指令 = 指令的符号化表示
• 汇编程序 = 驱动指令集状态机的输入
  • 执行汇编程序 = 指令集状态机发生状态转移
• 汇编课 = RTFM(指令集手册)

CPU微结构设计

说人话: 抽象计算机执行一条指令后的状态, 与CPU在根据指令语义设计出的组合逻辑电路控制下的次态，语义上是等价的

到这里对于这个状态机有点感觉了

程序如何在计算机上运行

程序和指令集都没有实体, 计算机的实体是电路, 如何联系它们?

• 根据指令集手册的功能描述, 画一张CPU的电路图 -> 微结构设计
• 用RTL代码描述CPU电路图 -> RTL设计
• 根据RTL代码生成版图文件 -> 后端物理设计
• 根据版图文件生产芯片 -> 制造生产
• 编写程序 -> 软件编程
• 将程序翻译成指令集手册中描述的指令序列 -> 编译
• 程序在CPU上执行 = 指令序列控制CPU芯片电路进行状态转移
  • 三个状态机产生联系: Sc ~ Sisa ~ Scpu

一句话就能说清楚, 为什么搞那么复杂?

状态机模型是理解复杂系统的一种有效方法

有些概念和问题从状态机模型思考可以给我们带来新的启发

• Yanyan Jiang. The Hitchhiker’s Guide to Operating Systems. USENIX ATC 23, 929-943, 2023

一句话就能说清楚, 为什么搞那么复杂?(2)

不过最重要的是给大家传达一种观念:

机器永远是对的

这里的这句话应该这样理解：任何都不会随意产生，都是可追溯的。

计算机系统的行为是按照官方手册的描述精确发生的

• 每一次状态转移都有手册依据
• 如果你不理解计算机系统的行为, 很大概率是因为你不了解相关手册中的某些关键细节
• 这对初学者会有一定压力(哪都不太了解)
  • 但只有树立正确的观念, 才能解决问题
• “永远”的理解: 商业产品也会有bug(Intel奔腾的fdiv bug), 但你恰好遇上的概率很小

总结

计算机系统都是状态机

• 程序编译 = 将语句翻译成语义等价的指令序列

• 微结构设计 = 按照指令语义设计行为等价的电路

• 程序运行 = 指令序列驱动电路进行状态转移

• 机器永远是对的

• 通过RTFM了解细节成为专业人士, 不要迷信非官方材料

---

内容来自：一生一芯_余子濠_计算机系统的状态机模型