F4 计算机系统的状态机模型

Created on September 22, 2026

2026   ·   notes   osoc   ·   notes   imported

处理器的组成和工作原理

指令及其编码

处理器的指令由“操作码”(opcode)+“操作数”(operand)两个字段组成。

操作码：指令中来指定用何种方式处理数据的字段；操作数：指令中来指定处理哪些数据的字段。

数据处理的中间数据用寄存器保存，多个寄存器组成寄存器组（Register Set）或寄存器堆(Register File).，这些处理一般数据的寄存器组被称为通用寄存器（General Purpose Register, GPR）。

例如, 某简单处理器有4个GPR, 支持3种指令, 其中2种如下:

 7  6 5  4 3   2 1   0
+----+----+-----+-----+
| 00 | rd | rs1 | rs2 | R[rd]=R[rs1]+R[rs2]    add指令, 寄存器相加
+----+----+-----+-----+
| 10 | rd |    imm    | R[rd]=imm              li指令, 装入立即数, 高位补0
+----+----+-----+-----+

关于操作数, 因为GPR只有4个, 因此可以用2位来指定一个GPR的地址(00, 01, 10, 11). 操作数据的来源称为”源寄存器”, 上述的add指令需要从两个源寄存器中获取加数, 两个源寄存器的地址分别记为rs1和rs2, 分别用R[rs1]和R[rs2]来表示GPR中存放的内容; 操作需要写入的目的称为”目的寄存器”, 一般记为rd. 其中, 第2条li指令的操作数稍有不同, 其源操作数不再是GPR, 而是直接将指令中的imm字段解析成一个二进制数来使用, 这种操作数称为”立即数”。

存储程序

在计算器中指示当前指令执行到哪条指令的部件叫做程序计数器(Program Counter, PC)。所以我们只需要重复执行以下步骤：从PC指示的存储器中取指令->执行指令->更新PC。这就是当前主流计算机存储程序的思想。

扩展一下，既然PC存储了当前执行指令的位置, 那PC也应该是一个寄存器, 这样的话, 我们还可以设计相应的指令来修改它, 从而增加程序执行过程的灵活性. 例如, 我们可以在上文提到的2条指令的基础上, 再添加第3条指令:

 7  6 5         2 1  0
+----+---- -----+-----+
| 11 |   addr   | rs2 | if (R[0]!=R[rs2]) PC=addr bner0指令, 若不等于R[0]则跳转
+----+----------+-----+

这条bner0指令十分特殊, 它是Branch if Not Equal r0的缩写, 如果执行这条指令的时候R[rs2]与R[0]不相等, 则将PC寄存器更新为addr, 即让PC指向addr处的指令. 不过, PC寄存器并不是用于处理一般数据, 因此它不属于GPR。

一个数列求和的例子

用指令来计算1+2+...+10这一数列的和. 为了方便理解, 先不采用0和1来表示指令. 用r0, r1, r2和r3分别指代4个GPR, 并且用逗号来分隔指令的操作数. 假设以下指令序列存放在存储器中, 用于计算上述数列之和, 其中:前的数字表示PC, #及其后的文字表示注释:

0: li r0, 10   # 这里是十进制的10
1: li r1, 0
2: li r2, 0
3: li r3, 1
4: add r1, r1, r3  # r1 = r1 + r3
5: add r2, r2, r1
6: bner0 r1, 4   # 如果`R[r1]`与`4`不相等, 则将PC寄存器更新为 4 .
7: bner0 r3, 7

模仿处理器执行指令：

PC r0 r1 r2 r3
(0, 0, 0, 0, 0)   # 初始状态
(1, 10, 0, 0, 0)  # 执行PC为0的指令后, r0更新为10, PC更新为下一条指令的位置
(2, 10, 0, 0, 0)  # 执行PC为1的指令后, r1更新为0, PC更新为下一条指令的位置
(3, 10, 0, 0, 0)  # 执行PC为2的指令后, r2更新为0, PC更新为下一条指令的位置
(4, 10, 0, 0, 1)  # 执行PC为3的指令后, r3更新为1, PC更新为下一条指令的位置
(5, 10, 1, 0, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 1, 1, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 1, 1, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4
(5, 10, 2, 1, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 2, 3, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 2, 3, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 3, 3, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 3, 6, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 3, 6, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 4, 6, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 4, 10, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 4, 10, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 5, 10, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 5, 15, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 5, 15, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 6, 15, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 6, 21, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 6, 21, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 7, 21, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 7, 28, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 7, 28, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 8, 28, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 8, 36, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 8, 36, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 9, 36, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 9, 45, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 9, 45, 1)  # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4

(5, 10, 10, 45, 1)  # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 10, 55, 1)  # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 10, 10, 1)  # 执行PC为6的指令后, 因r1等于r0, 故PC更新为7

(4, 10, 10, 10, 1)  # 执行PC为6的指令后, 因r1等于r0, 故PC更新为7
循环....

由分析可见，执行到最后，程序循环在PC=7的这条指令，数列求和的结果保存在寄存器r2当中。

计算10以内的奇数之和

尝试用上述指令编写一个程序, 求出10以内的奇数之和, 即计算1+3+5+7+9.

0: li r0, 9
1: li r1, 1
2: li r2, 0
3: li r3, 2
4: add r1, r1, r3
5: add r2, r2, r1
6: bner0 r1, 4
7: bner0 r3, 7

指令集架构的状态机模型

上文介绍的GPR, PC, 存储器, 指令及其执行过程, 都属于指令集架构(Instruction Set Architecture, 缩写为ISA, 也简称指令集)的范畴，常用的ISA有x86, ARM, RISC-V，ISA的本质是一系列规范, 这些规范通常记录在相应的手册中， 它们定义了一台（只存在于思维中的）模型机的功能和行为，通过数字电路将其实现出来, 我们才得到一台真正的计算机。

  • 状态集合 $S = {S_1, S_2, \cdots}$
  • 激励事件集合 $E$
  • 状态转移规则 $\operatorname{next}: S \times E \to S$
    • 描述每个状态在不同激励事件下的次态（next state），即二元函数 $\operatorname{next}(S, E)$ 给出了在状态 $S$ 下接收到激励事件 $E$ 后的次态
  • 初始状态 $S_0 \in S$

C程序入门

本人有c语言基础，这部分跳过。

数字电路的状态机模型

上文介绍的GPR, PC, 存储器, 指令及其执行过程, 在计算机领域中属于指令集架构(Instruction Set Architecture, 缩写为ISA, 也简称指令集)的范畴。ISA的本质是一系列规范, 这些规范通常记录在相应的手册中, 它们定义了一台模型机的功能和行为。所谓的模型机就是一台只存在于思维中的机器, 我们只讨论其具备的功能和行为, 而不讨论其具体实现。

从状态机的视角去理解ISA:

  • 状态集合. 回忆时序逻辑电路的相关内容, 状态是那些可以稳定存储信息的元素. 对这个含义进行引申, 在ISA中, 状态应该包含PC, GPR和内存. 也即, ISA中的一个状态是一组具体的PC, GPR和内存, 而全体状态的集合则是PC, GPR和内存所有取值的组合.在数字电路中, 只有时序逻辑电路才能存储信息, 因此一个状态是时序逻辑元件所存储的具体信息, 而全体状态的集合则是时序逻辑元件所能存储信息的所有组合.
  • 激励事件集合. 在ISA中, 执行指令会改变状态, 因此执行指令就是这个状态机的激励事件；既然时序逻辑元件表征了数字电路的状态, 而时序逻辑元件的内部状态可以通过其输入端改变(例如可以通过输入端将数据写入D触发器),我们可以将数字电路看成以下模型:
  •   +------------------+
+-->| Sequential Logic |----+
|   +------------------+    |
| next state                | current state
|                           |
|  +---------------------+  |
+--| Combinational Logic |<-+
   +---------------------+
  • 也即, 让时序逻辑元件的状态发生变化的, 其实是组合逻辑电路输出的信号, 因此组合逻辑电路就是这个状态机的激励事件.
  • 状态转移规则. 按照定义, 在ISA中, 状态转移规则用于描述“在某个状态下执行某指令后的次态”, 也即指令的语义, 它约定了执行某指令后, 状态应该发生怎么样的变化, 从而从一个状态转移到另一个；时序逻辑元件的状态具体应如何变化, 是由组合逻辑电路的具体逻辑决定的.
  • 初始状态. 在未执行任何指令之前的状态.即电路在复位时, 时序逻辑元件的状态.

编译 = 将C程序翻译成指令序列

CPU设计 = 根据ISA设计数字电路

  ISA 数字电路
状态 ${PC,R,M}$ 时序逻辑电路
激励事件 执行指令 处理组合逻辑
状态转移规则 指令的语义 组合逻辑电路的逻辑

CPU设计的工作就是用数字电路的状态机实现ISA的状态机。

对比两个状态机后可以得知, CPU设计需要完成以下工作:

  • 用数字电路的状态实现ISA的状态, 也即, 用时序逻辑电路实现PC, GPR和内存
  • 用数字电路的状态转移规则实现ISA的状态转移规则, 也即, 用组合逻辑电路实现指令的功能

程序, ISA和CPU之间的联系

到此, 我们可以来简单梳理程序, ISA和CPU之间的联系:

  1. 根据ISA手册的功能描述, 画一张CPU的结构图 -> 处理器微结构设计
  2. 根据结构图设计具体的电路 -> 逻辑设计
  3. 开发程序 -> 软件编程
  4. 将程序翻译成ISA手册中描述的指令序列 -> 编译
  5. 在CPU上执行程序 = 用程序编译出的指令序列控制CPU电路进行状态转移
    • 此时, 三个状态机产生联系

Hugoz’s Lab

全站搜索

支持正文与模糊搜索 · 使用 ↑ ↓ 选择，Enter 跳转到命中位置