状态机的三种实现方法

发表于： 2023-07-25 分类于： Programming

字数：676 阅读：≈ 4分钟浏览：

这次我们一起来学习C语言实现状态机的三种方法解析。

状态机的实现无非就是 3 个要素：状态、事件、响应。转换成具体的行为就 3 句话。

发生了什么事？
现在系统处在什么状态？
在这样的状态下发生了这样的事，系统要干什么？

用 C 语言实现状态机主要有 3 种方法：switch—case 法、表格驱动法、函数指针法。

switch—case 法

状态用 switch—case 组织起来，将事件也用switch—case 组织起来，然后让其中一个 switch—case 整体插入到另一个 switch—case 的每一个 case 项中。

「程序清单 List4 ：」

switch (StateVal) {
case S0:
    switch (EvntID) {
    case E1:
        action_S0_E1();         /*S0 状态下 E1 事件的响应 */
        StateVal = new state value;     /*状态迁移，不迁移则没有此行 */
        break;
    case E2:
        action_S0_E2();         /*S0 状态下 E2 事件的响应 */
        StateVal = new state value;
        break;
    ... ... case Em:
        action_S0_Em();         /*S0 状态下 Em 事件的响应 */
        StateVal = new state value;
        break;
    default:
        break;
    }
    break;
case S1:
    ... ... break;
... ... case Sn:
    ... ... break;
default:
    break;
}

上面的伪代码示例只是通用的情况，实际应用远没有这么复杂。虽然一个系统中事件可能有很多种，但在实际应用中，许多事件可能对某个状态是没有意义的。

例如在程序清单 List4中，如果 E2、······ Em 对处在 S0 状态下的系统没有意义，那么在 S0 的 case 下有关事件E2、······ Em 的代码根本没有必要写,状态 S0 只需要考虑事件 E1 的处理就行了。

既然是两个 switch—case 之间的嵌套，那么就有一个谁嵌套谁的问题，所以说 switch—case法有两种写法：状态嵌套事件和事件嵌套状态。这两种写法都可以，各有利弊，至于到底选用哪种方式就留给设计人员根据具体情况自行决断吧。

关于 switch—case 法还有最后一点要说明，因为 switch—case 的原理是从上到下挨个比较，越靠后，查找耗费的时间就越长，所以要注意状态和事件在各自的 switch 语句中的安排顺序，不推荐程序清单 List4 那样按顺序号排布的方式。出现频率高或者实时性要求高的状态和事件的位置应该尽量靠前。

表格驱动法

如果说 switch—case 法是线性的，那么表格驱动法则是平面的。表格驱动法的实质就是将状态和事件之间的关系固化到一张二维表格里，把事件当做纵轴，把状态当做横轴，交点[Sn , Em]则是系统在 Sn 状态下对事件 Em 的响应。

State Machine

如图 4，我把表格中的 Node_SnEm 叫做状态机节点，状态机节点 Node_SnEm 是系统在 Sn状态下对事件 Em 的响应。这里所说的响应包含两个方面：输出动作和状态迁移。状态机节点一般是一个类似程序清单 List5 中的结构体变量。

struct fsm_node
{
    void (*fpAction)(void* pEvnt);
    INT8U u8NxtStat;
};

程序清单 List5 中的这个结构体有两个成员：fpAction 和 u8NxtStat。fpAction 是一个函数指针，指向一个形式为 void func(void * pEvnt)的函数， func 这个函数是对状态转移中动作序列的标准化封装。

也就是说，状态机在状态迁移的时候，不管输出多少个动作、操作多少个变量、调用多少个函数，这些行为统统放到函数 func 中去做。

把动作封装好了之后，再把封装函数 func 的地址交给函数指针 fpAction，这样，想要输出动作，只需要调用函数指针 fpAction 就行了。

再看看上面的 func 函数，会发现函数有一个形参 pEvnt，这是一个类型为 void * 的指针，在程序实际运行时指向一个能存储事件的变量，通过这个指针我们就能获知关于事件的全部信息，这个形参是很有必要的。事件一般包括两个属性：事件的类型和事件的内容。

例如一次按键事件，我们不仅要知道这是一个按键事件，还要知道按下的到底是哪个键。事件的类型和状态机当前的状态可以让我们在图 4 的表格中迅速定位，确定该调用哪个动作封装函数，但是动作封装函数要正确响应事件还需要知道事件的内容是什么，这也就是形参pEvnt 的意义。

由于事件的多样性，存储事件内容的数据格式不一定一样，所以就把 pEvnt 定义成了 void * 型，以增加灵活性。有关 fpAction 的最后一个问题：如果事件 Em 对状态 Sn 没有意义，那么状态机节点Node_SnEm 中的 fpAction 该怎么办？我的答案是：那就让它指向一个空函数呗！前面不是说过么，什么也不干也叫响应。

u8NxtStat 存储的是状态机的一个状态值。我们知道，状态机响应事件要输出动作，也就是调用函数指针 fpAction 所指向的那个封装函数，函数调用完毕后程序返回主调函数，状态机对事件的响应就算结束了，下一步就要考虑状态迁移的问题了。

可能要保持本状态不变，也可能要迁移到一个新的状态，该如何抉择呢？u8NxtStat 存储的状态就是状态机想要的答案！

图 4 的这张表格反映在 C 语言代码里就是一个二维数组，第 1 维就是状态机的状态，第 2维就是统一分类的事件，而数组的元素则是程序清单 List5 中的结构体常量。如果程序中使用表格驱动法，还需要注意一些特别的事项。要将状态当做表格的横轴，那么就要求状态值集合必须满足以下条件：

(1) 该集合是一个递增的等差整数数列

(2) 该数列初值为 0

(3) 该数列等差值为 1

“事件” 作为纵轴，其特点和要求与用来做横轴的“状态” 完全一致。在 C 语言提供的数据类型中，没有比枚举更符合以上要求的可选项了，极力推荐将状态集合和事件类型集合做成枚举常量。表格驱动法的优点：调用接口统一，定位快速。

表格驱动法屏蔽了不同状态下处理各个事件的差异性，因此可以将处理过程中的共性部分提炼出来，做成标准统一的框架式代码，形成统一的调用接口。根据程序清单 List5 中的状态机节点结构体，做成的框架代码如程序清单 List6 所示。

表格驱动法查找目标实际上就是一次二维数组的寻址操作，所以它的平均效率要远高于switch—case 法。

###「程序清单 List6 ：」

extern struct fsm_node g_arFsmDrvTbl[][]; /*状态机驱动表格*/
INT8U u8CurStat = 0; /*状态暂存*/
INT8U u8EvntTyp = 0; /*事件类型暂存*/
void* pEvnt = NULL; /*事件变量地址暂存*/
struct fsm_node stNodeTmp = {NULL, 0}; /*状态机节点暂存*/
u8CurStat = get_cur_state(); /*读取当前状态*/
u8EvntTyp = get_cur_evnt_typ(); /*读取当前触发事件类型*/
pEvnt = (void*)get_cur_evnt_ptr(); /*读取事件变量地址*/
stNodeTmp = g_arFsmDrvTbl[u8CurStat ][u8EvntTyp ];/*定位状态机节点*/
stNodeTmp.fpAction(pEvnt ); /*动作响应*/
set_cur_state(stNodeTmp.u8NxtStat); /*状态迁移*/
.....

表格驱动法好则好矣，但用它写出来的程序还有点儿小问题，我们先来看看按照表格驱动法写出来的程序有什么特点。

前面说过，表格驱动法可以把状态机调度的部分做成标准统一的框架代码，这个框架适用性极强，不管用状态机来实现什么样的应用，框架代码都不需要做改动，我们只需要根据实际应用场合规划好状态转换图，然后将图中的各个要素(状态、事件、动作、迁移，有关“条件”要素一会儿再说)用代码实现就行了，我把这部分代码称作应用代码。

在应用代码的.c 文件中，你会看到一个声明为 const 的二维数组，也就是图 4 所示的状态驱动表格，还会看到许多彼此之间毫无关联的函数，也就是前面提到的动作封装函数。这样的一份代码，如果手头上没有一张状态转换图，让谁看了也会一头雾水，这样的格式直接带来了代码可读性差的问题。

如果我们想给状态机再添加一个状态，反映到代码上就是给驱动表格再加一列内容，同时也要新添加若干个动作封装函数。如果驱动表格很大，做这些工作是很费事儿的，而且容易出错。如果不小心在数组中填错了位置，那么程序跑起来就和设计者的意图南辕北辙了，

远没有在 switch—case 法中改动来得方便、安全。上面说的只是小瑕疵，其实最让我不爽的是表格驱动法不能使用Extended State Machine(对这个词组还有印象吧？)！Extended State Machine 的最大特点就是状态机响应事件之前先判断条件，根据判定结果选择执行哪些动作，转向哪个状态。

也就是说，系统在状态 Sn 下发生了事件 Em 后，转向的状态不一定是唯一的，这种灵活性是 Extended State Machine 的最有价值的优点。

回过头来看看程序清单 List5 中给出的状态机节点结构体，如果系统在状态 Sn 下发生了事件 Em，状态机执行完 fpAction 所给出的动作响应之后，必须转到 u8NxtStat 指定的状态。

表格驱动法的这个特性直接杜绝了 Extended State Machine 在表格驱动法中应用的可能性，所以表格驱动法的代码实现中不存在“条件” 这个状态机要素。ESM，你是如此的优秀，我怎么舍得抛弃你？！

再看图 4 所示的表格驱动法示例图，如果我们把表格中的代表事件的纵轴去掉，只留下代表状态的横轴，将一列合并成一格，前文提到的问题是不是能得到解决呢？不错！这就是失传江湖多年的《葵花宝典》 ——阉割版表格驱动法！！

阉割版表格驱动法，又名压缩表格驱动法，一维状态表格与事件 switch—case 的合体。压缩表格驱动法使用了一维数组作为驱动表格，数组的下标即是状态机的各个状态。

表格中的元素叫做压缩状态机节点，节点的主要内容还是一个指向动作封装函数的函数指针，只不过这个动作封装函数不是为某个特定事件准备的，而是对所有的事件都有效的。

节点中不再强制指定状态机输出动作完毕后所转向的状态，而是让动作封装函数返回一个状态，并把这个状态作为状态机新的状态。

压缩表格驱动法的这个特点，完美的解决了 Extended State Machine 不能在表格驱动法中使用的问题。

程序清单 List7 中的示例代码包含了压缩状态机节点结构体和状态机调用的框架代码。

「程序清单 List7：」

struct fsm_node /*压缩状态机节点结构体*/
{
 INT8U (*fpAction)(void* pEvnt); /*事件处理函数指针*/
 INT8U u8StatChk; /*状态校验*/
};
......
u8CurStat = get_cur_state(); /*读取当前状态*/
......
if(stNodeTmp.u8StatChk == u8CurStat )
{
 u8CurStat = stNodeTmp.fpAction(pEvnt ); /*事件处理*/
 set_cur_state(u8CurStat ); /*状态迁移*/
}
else
{
 state_crash(u8CurStat ); /*非法状态处理*/
}
.....

对照程序清单 List5，就会发现程序清单 List7 中 struct fsm_node 结构体的改动之处。首先， fpAction 所指向函数的函数形式变了，动作封装函数 func 的模样成了这样的了：

INT8U func(void * pEvnt);

现在的动作封装函数 func 是要返回类型为 INT8U 的返回值的，这个返回值就是状态机要转向的状态，也就是说，压缩表格驱动法中的状态机节点不负责状态机新状态的确定，而把这项任务交给了动作封装函数 func， func 返回哪个状态，状态机就转向哪个状态。

新状态由原来的常量变成了现在的变量，自然要灵活许多。上面说到现在的动作封装函数 func 要对当前发生的所有的事件都要负责，那么 func 怎么会知道到底是哪个事件触发了它呢？看一下 func 的形参 void * pEvnt 。

在程序清单 List5 中我们提到过，这个形参是用来向动作封装函数传递事件内容的，但是从前文的叙述中我们知道， pEvnt 所指向的内存包含了事件的所有信息，包括事件类型和事件内容，所以通过形参 pEvnt ，动作封装函数 func 照样可以知道事件的类型。

程序清单 List7 中 struct fsm_node 结构体还有一个成员 u8StatChk ，这里面存储的是状态机的一个状态，干什么用的呢？玩 C 语言数组的人都知道，要严防数组寻址越界。

要知道，压缩表格驱动法的驱动表格是一个以状态值为下标的一维数组，数组元素里面最重要的部分就是一个个动作封装函数的地址。

函数地址在单片机看来无非就是一段二进制数据，和内存中其它的二进制数据没什么两样，不管程序往单片机 PC 寄存器里塞什么值，单片机都没意见。假设程序由于某种意外而改动了存储状态机当前状态的变量，使变量值变成了一个非法状态。

再发生事件时，程序就会用这个非法的状态值在驱动表格中寻址，这时候就会发生内存泄露，程序拿泄露内存中的未知数据当函数地址跳转，不跑飞才怪！

为了防止这种现象的发生，压缩状态机节点结构体中又添加了成员 u8StatChk 。u8StatChk中存储的是压缩状态机节点在一维驱动表格的位置，例如某节点是表格中的第 7 个元素，那么这个节点的成员 u8StatChk 值就是 6。

看一下程序清单 List7 中的框架代码示例，程序在引用函数指针 fpAction 之前，先检查当前状态和当前节点成员 u8CurStat 的值是否一致，一致则认为状态合法，事件正常响应，如果不一致，则认为当前状态非法，转至意外处理，最大限度保证程序运行的安全。当然，如果泄露内存中的数据恰好和 u8CurStat 一致，那么这种方法真的就回天乏力了。

还有一个方法也可以防止状态机跑飞，如果状态变量是枚举，那么框架代码就可以获知状态值的最大值，在调用动作封装函数之前判断一下当前状态值是否在合法的范围之内，同样能保证状态机的安全运行。

压缩表格驱动法中动作封装函数的定义形式我们已经知道了，函数里面到底是什么样子的呢？程序清单 List8 是一个标准的示例。

「程序清单List8：」

INT8U action_S0(void* pEvnt)
{
 INT8U u8NxtStat = 0;
 INT8U u8EvntTyp = get_evnt_typ(pEvnt);
 switch(u8EvntTyp )
 {
  case E1:
   action_S0_E1(); /*事件 E1 的动作响应*/
   u8NxtStat = new state value; /*状态迁移，不迁移也必须有本行*/
   break;
   ......
  case Em:
   action_S0_Em(); /*事件 Em 的动作响应*/
   u8NxtStat = new state value; /*状态迁移，不迁移也必须有本行*/
   break;
  default:
   ; /*不相关事件处理*/
   break;
 }
 return u8NxtStat ; /*返回新状态*/
}

从程序清单 List8 可以看出，动作封装函数其实就是事件 switch—case 的具体实现。函数根据形参 pEvnt 获知事件类型，并根据事件类型选择动作响应，确定状态机迁移状态，最后将新的状态作为执行结果返回给框架代码。

有了这样的动作封装函数， Extended State Machine 的应用就可以完全不受限制了！到此，有关压缩表格驱动法的介绍就结束了。

个人认为压缩表格驱动法是相当优秀的，它既有表格驱动法的简洁、高效、标准，又有 switch—case 法的直白、灵活、多变，相互取长补短，相得益彰。

函数指针法

上面说过，用 C 语言实现状态机主要有 3 种方法(switch—case 法、表格驱动法、函数指针法)，其中函数指针法是最难理解的，它的实质就是把动作封装函数的函数地址作为状态来看待。不过，有了之前压缩表格驱动法的铺垫，函数指针法就变得好理解了，因为两者本质上是相同的。

压缩表格驱动法的实质就是一个整数值(状态机的一个状态)到一个函数地址(动作封装函数)的一对一映射，压缩表格驱动法的驱动表格就是全部映射关系的直接载体。在驱动表格中通过状态值就能找到函数地址，通过函数地址同样能反向找到状态值。

我们用一个全局的整型变量来记录状态值，然后再查驱动表格找函数地址，那干脆直接用一个全局的函数指针来记录状态得了，还费那劳什子劲干吗？！这就是函数指针法的前世今生。

用函数指针法写出来的动作封装函数和程序清单 List8 的示例函数是很相近的，只不过函数的返回值不再是整型的状态值，而是下一个动作封装函数的函数地址，函数返回后，框架代码再把这个函数地址存储到全局函数指针变量中。

相比压缩表格驱动法，在函数指针法中状态机的安全运行是个大问题，我们很难找出一种机制来检查全局函数指针变量中的函数地址是不是合法值。如果放任不管，一旦函数指针变量中的数据被篡改，程序跑飞几乎就不可避免了。

小节

有关状态机的东西说了那么多，相信大家都已经感受到了这种工具的优越性，状态机真的是太好用了！其实我们至始至终讲的都是有限状态机(Finite State Machine 现在知道为什么前面的代码中老是有 fsm 这个缩写了吧！)，还有一种比有限状态机更 NB 更复杂的状态机，那就是层次状态机(Hierarchical State Machine 一般简写为 HSM)。

通俗的说，系统中只存在一个状态机的叫做有限状态机，同时存在多个状态机的叫做层次状态机(其实这样解释层次状态机有些不严谨，并行状态机也有多个状态机，但层次状态机各个状态机之间是上下级关系，而并行状态机各个状态机之间是平级关系)。

层次状态机是一种父状态机包含子状态机的多状态机结构，里面包含了许多与面向对象相似的思想，所以它的功能也要比有限状态机更加强大，当一个问题用有限状态机解决起来有些吃力的时候，就需要层次状态机出马了。

层次状态机理论我理解得也不透彻，就不在这里班门弄斧了，大家可以找一些有关状态机理论的专业书籍来读一读。要掌握状态机编程，理解状态机(主要指有限状态机)只是第一步，也是最简单的一步，更重要的技能是能用状态机这个工具去分析解剖实际问题：划分状态、提取事件、确定转换关系、规定动作等等，形成一张完整的状态转换图，最后还要对转换图进行优化，达到最佳。

把实际问题变成了状态转换图，工作的一大半就算完成了，这个是具有架构师气质的任务，剩下的问题就是按照状态图编程写代码了，这个是具有代码工特色的工作。