从零开始的状态机漫谈（1）——万物之始的语言

时间：2021-03-10 09:52:03

关键字：状态机有限自动机

手机看文章

扫描二维码
随时随地手机看文章

[导读]也许从12年前我第一次开始分享状态机编写心得开始，“状态机”就像标签一样紧紧的贴在了“傻孩子”这个网络昵称的额头上——真是抠都扣不下来。

（图片来在网络，侵删）

【说在前面的话】

也许从12年前我第一次开始分享状态机编写心得开始，“状态机”就像标签一样紧紧的贴在了“傻孩子”这个网络昵称的额头上——真是抠都扣不下来。不得不坦白的是，从一开始我介绍状态机更多只注重状态机这一语言的表现形式，而故意偷懒避开了状态机开发思维的系统性介绍——也许刚开始真的是没什么自信，觉得自己也没有能真正领会状态机的所谓精髓，所以不敢瞎说；后来慢慢的掌握了所谓的状态机思维模式以后，就是真正的懒惰了。在过去的5年间，尽管那些毛遂自荐参加过我免费远程培训的人或多或少都学习到了一系列使用状态机进行开发的思维方式，但毕竟人数太少。由阿莫论坛改为付费订阅模式为契机，我也有机会仔细回看、思考之前所写过的内容。说实话，它们中的很多实在谈不上“深入浅出”。作为公众号复更的开端，我觉得有必要系统性的整理我那些所谓的“理论”、把它们写下来—— 让更多的人得以获得一个讨论和交流的起点。虽然我后面要写的内容既不是什么教条、也不是什么标准答案更不会是“金科玉律”，但一定是一个非常好的出发点——如果能引起大家的思考和讨论，真正掌握状态机开发，甚至能发展出自己的理论和风格，那就再好不过了。

(图片来源：https://en.wikipedia.org/wiki/Finite-state_machine)

【正文】

说来你不信，有限自动机（Finite State Machine），又叫状态机是整个计算机学科倒数第二层的基石；倒数第一层就是大家所熟悉的组合逻辑（Combinational logic）——如果说组合逻辑是没啥灵魂的细胞的话，有限自动机就是第一种“能够任意描述思维逻辑”的神兽大乌龟——整个计算机学科都驮在它的背上。

然而，如同组合逻辑电路如同“阿米巴”一样的简单，掌握状态机的难度跟“幼稚园”差不了多少。不相信的话，我们先从几个简单的概念说起：

怎么理解状态？如何才算一个状态

很多小伙伴都曾抱怨说“字面意思我都懂”，但“实际中如何理解什么是状态”？、 “怎样才算一个状态呢？ ”——我不是第一次遇到这种问题了。答案其实很直接：
【第一种情况】 ：假设我们尝试去做一件事情，但这件事情不是每次去做就一定会成功，而且每次去尝试都有可能产生至少2种以上的结果，那么针对这件事情的尝试就应该单独划分一个状态。举个例子：

extern bool serial_out(uint8_t chByte);

函数serial_out()可以用来向某个串行外设发送一个字符，比如UART。如果成功了就返回true，如果设备正忙导致本次发送失败则立即返回false。由于外设的发送速度相对CPU的运行频率来说差了好几个数量级——在CPU眼中外设慢得跟蜗牛一样，所以每次通过serial_out() 发送字符不一定是成功——很可能外设还在努力“消化”上一次的字符。这种情况下，如果我们要在状态机中描述发送字符这样的行为，就值得为其单独分配一个状态，因为它满足了我们前面说的条件：1）一件事情你要不停的尝试才有可能成功，而且2）每次做都可能会产生2个以上的结果。习惯上，我们会用图示的方法来描述状态，以发送字符'H'为例：

从图中很容易注意到：

我们用圆圈来表示一个状态；
圆圈中心我们会写一些注释性质的内容用来帮助人们理解这个状态是做什么的；
图中有三个箭头，最左上角单纯“指向”状态的箭头表示从别的什么地方“跃迁”到了当前状态——我们称为“扇入”；下方从当前状态指向别的什么地方的箭头表示从当前状态离开；——我们成为“扇出”；右上角从当前状态“扇出”后又“返回到”当前状态的情况，我们称之为“自返”——也就是返回自己的意思。是不是特别简单。

实际使用的时候，如果单凭一个状态圆圈里面的注释文字，我们仍然不能理解这个状态实际做了什么事情；或者说我们非常好奇这个状态实际尝试做了什么动作，就可以通过以下的标注方法追加更多的信息，比如：

你看，是不是更加清晰了？同样的情况还可以推广到“调用一个函数而函数有多个不同的返回值”的情况；或者是“我们通过调用函数做了一件事情，虽然函数没有返回值，但是我们可以通过多种其它手段来获得这件事情的多个不同结果”的情况等等——领会精神，以此类推。

【第二种情况】：假设我们只是单纯的在等待某一个事情发生；或者等待某个一结果——这个结果由2个以上的返回值组成等等，那么这个等待行为就需要分配一个独立的状态。举个例子：

int32_t get_sensor_voltage(void);

函数get_sensor_volatage()可以返回某个传感器的电压值；我们设置了上下两个门限，一旦电压超过了任何一个门限，我们就切换到其它状态，对应的状态图示如下：

在这里，HIGH_THRESHOLD和LOW_THRESHOLD是两个宏表示上下两个门限。可以看到，这个状态表示：如果传感器的电压值在两个门限之间，我们就留在当前状态（通过自返回）；如果任意门限被超过，我们就相应的跳转到别的状态去。

所有的神奇都在状态跃迁上

在前面的图示中，所有的箭头我们都称之为“ 跃迁”，表示 从当前状态跳转到箭头所指向的目标状态（自返的跃迁就是自己跳回自己）。 跃迁不是无条件的，也不允许无条件——换句话说， 每个跃迁都必须有一个条件：例如第一个例子中的 true和 false就是对应跃迁的条件；后面例子中与门限值的比较也是对应的条件。需要特别强调的是： 1）一个状态所有的跃迁条件必须是彼此“互斥”的、唯一的；2）所有的跃迁必须能覆盖一个状态机所有可能的情况——绝不允许出现漏网之鱼，否则 一旦没有被覆盖的情况出现就有可能导致整个状态机的行为存在“不确定性”——如果状态机描述的是一个机器人的行为的话，这就是导致机器人逻辑故障的严重 Bug； 3）跃迁是个瞬间的行为，你只能认为当条件满足时跃迁的行为就像白驹过隙一样一下就做完了——这点很重要，我们马上就要细说。前面说过，当某个跃迁的条件得到了满足，我们就要沿着箭头的方向从当前状态调转到箭头所指向的目标状态。实际上，在跃迁的过程中我们还可以执行一些动作。需要注意的是，正如前面 3）说的那样， “跃迁是个瞬间行为”，所以这里的 动作也只会被执行一次。习惯上，如果某个跃迁存在动作，我们就在跃迁的条件下面加一个横线，并在横线的下方按顺序列举所有要执行的动作。
比如，我们可以通过一个专门的状态来实现一个计数器延时的效果：

在这个例子中，我们注意到：

虽然左上角扇入Delay状态的跃迁条件我们并不知道，但在此时复位计数器s_wCounter是再好不过了。所以我们空出了跃迁条件，并在横线的下方写下了计数器的初始化代码；
右上角的跃迁条件是：“如果计数器的值小于延时1s所需的最大值”，那么对应的动作就是让计数器自增；
右下角跃迁的条件是：“计数器的值超过了规定的最大值”，因此直接跳到目标状态而无需做其它动作。

状态机的起点和终点

一个状态机可以没有终点，但一定有一个起点，我们称之为 start。图示上，习惯用一个实心小圆点来表示。 start 不仅是状态机的起点，由一个跃迁来连接它和第一个状态； start 还是“兼任” 这一跃迁的条件，例如：

容易看出，这里 start 不仅是整个状态机的起点，还兼任了扇入Delay状态的跃迁的条件——从图上来看，很容易理解成：“当状态机开始时复位计数器s_wCounter”——可谓一目了然。

与 start 类似，状态机的终点也是一个实心小圆点，以 cpl 来标记； cpl 是 complete的缩写。值得强调的是，虽然每个状态机只有一个 start点，但却可以拥有 0个或多个 cpl点。 一旦状态机跃迁到了 cpl 点，这就意味着当前状态机结束了，下次再执行状态机就自动从 start 点开始了。

状态机有多简单

至此，借助前面介绍的概念和图式方法，我们已经可以轻松的绘制一个状态机（图）了。其实前面的例子中，我们已经看到了一个完整的 Delay状态机，尽管它只有一个状态但已麻雀虽小五脏俱全。接下来，我们再展示一个更直接的例子——如何使用 serial_out()发送字符串“ hello”：

还有另外一种更为通用的方法：

“不要问，问就是子状态机”

如果状态机不能调用子状态机，那它跟咸鱼有什么两样？那么如何用图示表示子状态机呢？废话少说，直接上图：

如图所示：

子状态机是被圆角矩形包裹的
子状态机的右上角有一个自反的状态迁移，条件是“on going”意味子状态机正在执行，还未得出一个结果；
子状态机的右下角（或者别的什么位置）需要有一个标记有cpl条件的状态迁移，表示当子状态机内部达到了终点cpl以后，子状态机从这里退出并跃迁到指定的状态；
子状态机有一个标题栏，里面分别列举了状态机的名称以及传递给当前子状态机的形参列表。（状态机的返回值只能是类似cpl, on-going这样的状态，所以不需要特别标记）

通过子状态机调用，我们很容易用已有的状态机实现搭积木的功能，比如假设我们将此前Delay的状态机也做成子状态机，配合这个已有的print_hello子状态机，就可以轻松实现一个“打印hello然后延时1秒”的状态机：

（这里需要注意，当子状态机被调用时，它使用圆角矩形替代了普通状态的圆圈。）

考虑到任何一个状态机其实都可以在未来被其它状态机调用，我们实际操作上会把每一个状态机都按照子状态机的格式进行绘制，因此上面的状态机正确的画法应该是：

怎么样，是不是很简单？

【后记】

请不要怀疑， 状态机本身是一种编程语言；状态图是描述状态机的最常见方式之一；绘制状态图的图例规范有很多种，比如 UML规范等等。本文以及后续其它文章使用的是一种笔者自己结合状态机的常见画法并针对嵌入式软件开发习惯简化后的图例规范， 简单、明确、有效，并且可以毫无歧义的严格且无脑的翻译成包括switch状态机在内的多种C语言实现。在下一篇文章里，我们将以 switch状态机为例，介绍状态图的无脑翻译方式，尽情期待。