【原创+首发】[交流]从零开始的状态机漫谈(1)——万物之始的语言
(图片来在网络,侵删)
【说在前面的话】
也许从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状态机为例,介绍状态图的无脑翻译方式,尽情期待。 图片没显示出来 大佬,图片挂了 认真听大神讲课,状态机还有面向对象思维一直没切切实实学习和应用过,落后了… zyqcome 发表于 2020-5-14 21:26
大佬,图片挂了
OK,后面我会修复的。
搬凳子过来学习 好好学习大牛思维{:smile:} 大佬出品,必是精品 已经学习了,催更... 学习了,学了很多年了,感觉自己没学进去... 跟着大佬学习 有些看天书一般,云里雾里 搬板凳认真学习 大牛开课啦,赶紧搬凳子认真学习 出神入化状态机,每看一次都有收获。{:smile:} 虽然平时一直在用,但是看完还是有不少收获,且理解更加深刻。 68336016 发表于 2020-5-15 11:29
有些看天书一般,云里雾里
什么部分你觉得不太理解呢?我可以尝试做更多解释哈。 这个图是用啥软件画的那
谢谢分享 pxclihai 发表于 2020-5-19 12:05
这个图是用啥软件画的那
万能偷懒绘图软件——PPT 为什么简单的东西,看了你的讲解后,反而糊涂了呢?{:lol:}《MSP430系列单片机系统工程设计与实践》的状态机讲得清楚多了。 cheng-8yang 发表于 2020-5-28 16:48
为什么简单的东西,看了你的讲解后,反而糊涂了呢?《MSP430系列单片机系统工程设计与实践》的状态 ...
那实在是对不起了。 等待更新 Gorgon_Meducer 发表于 2020-5-30 04:14
那实在是对不起了。
前辈,别这么说,只是我没到那个层次,看不懂而已。肯定有很多其他朋友是喜欢你这种写作风格的。 cheng-8yang 发表于 2020-5-30 08:42
前辈,别这么说,只是我没到那个层次,看不懂而已。肯定有很多其他朋友是喜欢你这种写作风格的。 ...
开个玩笑,别介意。 大神终于又出山了,外面情况不好,泡沫消失殆尽,还是要回归技术本质。 TigerFish 发表于 2020-6-2 07:37
大神终于又出山了,外面情况不好,泡沫消失殆尽,还是要回归技术本质。
一直都在坚持做技术,只是因为疫情在家憋太久了……开始想写点东西…… 我是从15年以后,基本所有程序的框架都是状态机结构了,加上事件触发,开始摸到oop的皮毛。
不是软件专业的,思维限制真的很大。 Gorgon_Meducer 发表于 2020-6-3 20:15
一直都在坚持做技术,只是因为疫情在家憋太久了……开始想写点东西…… ...
现在的大学教育,感觉和实际应用脱节太多。
以实际应用项目为出发点,出一些讲座,观察下项目实现过程中各个细节解决的思路和方法,并最终能看到个成果。
目的是感兴趣的大学生买些开发板能快速入门,并把技巧迁移到其它项目中。
我理想中的大学生是动手实操能力很强,退可以保命,进可以更进一步搭建系统验证自己想法,解决更高层面,理论层面的东西。
我看野火,还有现在一些搞视觉识别,导航的都有相应的开发板。
这个是对大学教育不足的一个很好补充 simplorer 发表于 2020-6-4 08:14
我是从15年以后,基本所有程序的框架都是状态机结构了,加上事件触发,开始摸到oop的皮毛。
不是软件专业的 ...
不要迷信软件专业,他们很多也对OO一脸懵逼。
相信自己的同时,多看理论书籍,思考后尝试在工程中实践,你不会比别人差的。 TigerFish 发表于 2020-6-4 09:03
现在的大学教育,感觉和实际应用脱节太多。
以实际应用项目为出发点,出一些讲座,观察下项目实现过程中 ...
你这就是哪壶不开提哪壶了……现在实际情况是“好大学生不搞嵌入式”——也许有点夸张,但距离事实绝对不远。 半夜拜读傻孩子的大作。 Gorgon_Meducer 发表于 2020-6-5 04:59
你这就是哪壶不开提哪壶了……现在实际情况是“好大学生不搞嵌入式”——也许有点夸张,但距离事实绝对不 ...
那搞什么呢?
AI, 互联网,自动驾驶?
也没这么多需求量吧,下沉接点地气,安身立命的东西还是需要的吧。比如现在的地摊经济{:lol:} Gorgon_Meducer 发表于 2020-6-5 04:58
不要迷信软件专业,他们很多也对OO一脸懵逼。
相信自己的同时,多看理论书籍,思考后尝试在工程中实践, ...
从您帖子学了不少东西,在此表示感谢了。 大神的贴子,值得细品味 {:smile:}支持大神 支持大神 armok. 发表于 2020-6-5 05:22
半夜拜读傻孩子的大作。
谢谢莫老大提携。 傻孩子一路成长走来,分享心得体会更是难得,功德无量 状态在心中,无态也有态,感谢傻孩子的心得分享,获益很多 ziziy 发表于 2020-6-10 09:18
状态在心中,无态也有态,感谢傻孩子的心得分享,获益很多
后面很快会更新本文的第二篇。敬请期待。 期待后续!{:handshake:}{:lol:} 摩了个拜学了个习 学习了,期待后续文章! 听课 学习{:smile:} 感谢大神。
请教大神,有没有这种可能:子状态机结束后,父状态机根据子状态机执行结果,再次进入子状态机? future_wang 发表于 2020-9-8 17:20
感谢大神。
请教大神,有没有这种可能:子状态机结束后,父状态机根据子状态机执行结果,再次进入子状态机 ...
当然啦,根据应用逻辑,完全有这种可能性。 Gorgon_Meducer 发表于 2020-9-9 10:11
当然啦,根据应用逻辑,完全有这种可能性。
感谢大神。
再请教大神,在无操作系统下,通过IIC读写外设的时候,如何降低cpu等待时间?我目前尝试的方式是如下:(我个人理解是状态机)
1、写外设的时候,把要写的帧数据先放到缓存里,然后通过IIC中断发送出去
2、读外设的时候,同上
3、主函数定期去判断状态
虽然上述方式可行,但是代码写起来总感觉比较晕和乱,要判断很多状态。
之前那种死等外设操作完成后,直接执行下面的代码的编写方式思路很清晰,有串行的感觉。
现在用这种状态的编写方式,感觉相互是并行的,写外设需求地方置标志位,外设状态机里去操作,写起来感觉有点麻烦。
所以我想请教的是:
1、上述的需求用状态机实现是否是一个好的解决方法?
2、我的方式是否没有把状态机用好,所以才有比较乱的感受?该如何去写这个状态机?
以上,感谢!
future_wang 发表于 2020-9-9 12:00
感谢大神。
再请教大神,在无操作系统下,通过IIC读写外设的时候,如何降低cpu等待时间?我目前尝试的 ...
不把人绕晕,也好意思叫状态机
future_wang 发表于 2020-9-9 12:00
感谢大神。
再请教大神,在无操作系统下,通过IIC读写外设的时候,如何降低cpu等待时间?我目前尝试的 ...
你用的这个方法,在思路上是正确的,而且也并不复杂。
至于你说你的写起来比较复杂,可能是以下几个原因导致的:
1. 你本身的代码行不够,暂时对这种结构不熟悉
2. 可能你的模块封装的不是很好,或者接口设计的不是很干净,比如用了太多的全局flag来传递信息。
我自己的经验是:
状态机是程序员思路的翻译,如果状态机(以状态图来表示)比较复杂,或者说不够清晰,则很可能是你自己没有想清楚。
一般来说,一个状态图里面不应该超过10个状态,否则一定有办法通过拆分或者子状态机调用的方法进行简化。
一个设计良好的状态机,如果仍然看起来很复杂,那么很有可能这个逻辑本身已经复杂到普通线性编程无法简单实现等效逻辑的程度。
总结:先自己想清楚,画好图,一般来说你现在这个级别的应用,状态机不可能复杂到哪里去的。 chendaon 发表于 2020-9-9 20:38
不把人绕晕,也好意思叫状态机
实名反对你这句话。非常误导。
状态机配合状态图应该是非常清晰的,易懂的。
再好的语言工具,也可以由程序员写成一坨屎,再垃圾的编程语言也可以写出非常清晰的代码。
不要迷信状态机,也不要因为片面的原因诋毁状态机。
页:
[1]