状态机编程

小程序无所谓，工程稍微一大，情况一多，这种方法就比较实用

转载正文1有限状态机FSM思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。有限状态机的工作原理如图1所示，发生事件(event)后，根据当前状态(cur_state)，决定执行的动作(action)，并设置下一个状态号(nxt_state)。-------------||-------->执行动作action发生事件event ----->| cur_state |||-------->设置下一状态号nxt_state-------------当前状态图1 有限状态机工作原理e0/a0--->--||-------->----------e0/a0 ||S0|-----|-<------------| e1/a1|| e2/a2V--------------------|S2|-----<-----|S1|----------e2/a2----------图2 一个有限状态机实例--------------------------------------------当前状态s0s1s2| 事件--------------------------------------------a0/s0--a0/s0|e0--------------------------------------------a1/s1----|e1--------------------------------------------a2/s2a2/s2--|e2--------------------------------------------表1 图2状态机实例的二维表格表示(动作/下一状态)图2为一个状态机实例的状态转移图，它的含义是：在s0状态，如果发生e0事件，那么就执行a0动作，并保持状态不变；如果发生e1事件，那么就执行a1动作，并将状态转移到s1态；如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；在s1状态，如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；在s2状态，如果发生e0事件，那么就执行a0动作，并将状态转移到s0态；有限状态机不仅能够用状态转移图表示，还可以用二维的表格代表。一般将当前状态号写在横行上，将事件写在纵列上，如表1所示。其中“--”表示空 (不执行动作，也不进行状态转移)，“an/sn”表示执行动作an,同时将下一状态设置为sn。表1和图2表示的含义是完全相同的。观察表1可知，状态机可以用两种方法实现：竖着写(在状态中判断事件)和横着写(在事件中判断状态)。这两种实现在本质上是完全等效的，但在实际操作中，效果却截然不同。==================================竖着写(在状态中判断事件)C代码片段==================================cur_state = nxt_state;switch(cur_state){//在当前状态中判断事件case s0://在s0状态if(e0_event){//如果发生e0事件，那么就执行a0动作，并保持状态不变；执行a0动作;//nxt_state = s0;//因为状态号是自身，所以可以删除此句，以提高运行速度。}else if(e1_event){//如果发生e1事件，那么就执行a1动作，并将状态转移到s1态；执行a1动作;nxt_state = s1;}else if(e2_event){//如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；执行a2动作;nxt_state = s2;}break;case s1://在s1状态if(e2_event){//如果发生e2事件，那么就执行a2动作，并将状态转移到s2态；执行a2动作;nxt_state = s2;}break;case s2://在s2状态if(e0_event){//如果发生e0事件，那么就执行a0动作，并将状态转移到s0态；执行a0动作;nxt_state = s0;}}==================================横着写(在事件中判断状态)C代码片段==================================//e0事件发生时，执行的函数void e0_event_function(int * nxt_state){int cur_state;cur_state = *nxt_state;switch(cur_state){case s0://观察表1，在e0事件发生时，s1处为空case s2:执行a0动作;*nxt_state = s0;}}//e1事件发生时，执行的函数void e1_event_function(int * nxt_state){int cur_state;cur_state = *nxt_state;switch(cur_state){case s0://观察表1，在e1事件发生时，s1和s2处为空执行a1动作;*nxt_state = s1;}}//e2事件发生时，执行的函数void e2_event_function(int * nxt_state){int cur_state;cur_state = *nxt_state;switch(cur_state){case s0://观察表1，在e2事件发生时，s2处为空case s1:执行a2动作;*nxt_state = s2;}}上面横竖两种写法的代码片段，实现的功能完全相同，但是，横着写的效果明显好于竖着写的效果。理由如下：1、竖着写隐含了优先级排序(其实各个事件是同优先级的)，排在前面的事件判断将毫无疑问地优先于排在后面的事件判断。这种if/else if写法上的限制将破坏事件间原有的关系。而横着写不存在此问题。2、由于处在每个状态时的事件数目不一致，而且事件发生的时间是随机的，无法预先确定，导致竖着写沦落为顺序查询方式，结构上的缺陷使得大量时间被浪费。对于横着写，在某个时间点，状态是唯一确定的，在事件里查找状态只要使用switch语句，就能一步定位到相应的状态，延迟时间可以预先准确估算。而且在事件发生时，调用事件函数，在函数里查找唯一确定的状态，并根据其执行动作和状态转移的思路清晰简洁，效率高，富有美感。总之，我个人认为，在软件里写状态机，使用横着写的方法比较妥帖。竖着写的方法也不是完全不能使用，在一些小项目里，逻辑不太复杂，功能精简，同时为了节约内存耗费，竖着写的方法也不失为一种合适的选择。在FPGA类硬件设计中，以状态为中心实现控制电路状态机(竖着写)似乎是唯一的选择，因为硬件不太可能靠事件驱动(横着写)。不过，在FPGA 里有一个全局时钟，在每次上升沿时进行状态切换，使得竖着写的效率并不低。虽然在硬件里竖着写也要使用IF/ELSIF这类查询语句(用VHDL开发)，但他们映射到硬件上是组合逻辑，查询只会引起门级延迟(ns量级)，而且硬件是真正并行工作的，这样竖着写在硬件里就没有负面影响。因此，在硬件设计里，使用竖着写的方式成为必然的选择。这也是为什么很多搞硬件的工程师在设计软件状态机时下意识地只使用竖着写方式的原因，盖思维定势使然也。TCP和PPP框架协议里都使用了有限状态机，这类软件状态机最好使用横着写的方式实现。以某TCP协议为例，见图3，有三种类型的事件：上层下达的命令事件；下层到达的标志和数据的收包事件；超时定时器超时事件。上层命令(open,close)事件-------------------------------------------------------|TCP|<----------超时事件timeout-------------------------------------------------------RST/SYN/FIN/ACK/DATA等收包事件图3 三大类TCP状态机事件由图3可知，此TCP协议栈采用横着写方式实现，有3种事件处理函数，上层命令处理函数(如tcp_close)；超时事件处理函数 (tmr_slow)；下层收包事件处理函数(tcp_process)。值得一提的是，在收包事件函数里，在各个状态里判断RST/SYN/FIN/ACK/DATA等标志(这些标志类似于事件)，看起来象竖着写方式，其实，如果把包头和数据看成一个整体，那么，RST/SYN/FIN/ACK/DATA等标志就不必被看成独立的事件，而是属于同一个收包事件里的细节，这样，就不会认为在状态里查找事件，而是总体上看，是在收包事件里查找状态(横着写)。在PPP里更是到处都能见到横着写的现象，有时间的话再细说。我个人感觉在实现PPP框架协议前必须了解横竖两种写法，而且只有使用横着写的方式才能比较完美地实现PPP。

转载正文2

状态机思路在单片机程序设计中的应用状态机的概念状态机是软件编程中的一个重要概念。比这个概念更重要的是对它的灵活应用。在一个思路清晰而且高效的程序中，必然有状态机的身影浮现。比如说一个按键命令解析程序，就可以被看做状态机：本来在A状态下，触发一个按键后切换到了B状态；再触发另一个键后切换到C状态，或者返回到A状态。这就是最简单的按键状态机例子。实际的按键解析程序会比这更复杂些，但这不影响我们对状态机的认识。进一步看，击键动作本身也可以看做一个状态机。一个细小的击键动作包含了：释放、抖动、闭合、抖动和重新释放等状态。同样，一个串行通信的时序（不管它是遵循何种协议，标准串口也好、I2C也好；也不管它是有线的、还是红外的、无线的）也都可以看做由一系列有限的状态构成。显示扫描程序也是状态机；通信命令解析程序也是状态机；甚至连继电器的吸合/释放控制、发光管（LED）的亮/灭控制又何尝不是个状态机。当我们打开思路，把状态机作为一种思想导入到程序中去时，就会找到解决问题的一条有效的捷径。有时候用状态机的思维去思考程序该干什么，比用控制流程的思维去思考，可能会更有效。这样一来状态机便有了更实际的功用。程序其实就是状态机。也许你还不理解上面这句话。请想想看，计算机的大厦不就是建立在“0”和“1”两个基本状态的地基之上么？

状态机的要素状态机可归纳为4个要素，即现态、条件、动作、次态。这样的归纳，主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因，“动作”和“次态”是果。详解如下：①现态：是指当前所处的状态。②条件：又称为“事件”。当一个条件被满足，将会触发一个动作，或者执行一次状态的迁移。③动作：条件满足后执行的动作。动作执行完毕后，可以迁移到新的状态，也可以仍旧保持原状态。动作不是必需的，当条件满足后，也可以不执行任何动作，直接迁移到新状态。④次态：条件满足后要迁往的新状态。“次态”是相对于“现态”而言的，“次态”一旦被激活，就转变成新的“现态”了。如果我们进一步归纳，把“现态”和“次态”统一起来，而把“动作”忽略（降格处理），则只剩下两个最关键的要素，即：状态、迁移条件。状态机的表示方法有许多种，我们可以用文字、图形或表格的形式来表示一个状态机。纯粹用文字描述是很低效的，所以就不介绍了。接下来先介绍图形的方式。

状态迁移图（STD）状态迁移图（STD），是一种描述系统的状态、以及相互转化关系的图形方式。状态迁移图的画法有许多种，不过一般都大同小异。我们结合一个例子来说明一下它的画法，如图1所示。

图1 状态迁移图 ①状态框：用方框表示状态，包括所谓的“现态”和“次态”。 ②条件及迁移箭头：用箭头表示状态迁移的方向，并在该箭头上标注触发条件。 ③节点圆圈：当多个箭头指向一个状态时，可以用节点符号（小圆圈）连接汇总。 ④动作框：用椭圆框表示。 ⑤附加条件判断框：用六角菱形框表示。 状态迁移图和我们常见的流程图相比有着本质的区别，具体体现为：在流程图中，箭头代表了程序PC指针的跳转；而在状态迁移图中，箭头代表的是状态的改变。 我们会发现，这种状态迁移图比普通程序流程图更简练、直观、易懂。这正是我们需要达到的目的。 状态迁移表 除了状态迁移图，我们还可以用表格的形式来表示状态之间的关系。这种表一般称为状态迁移表。 表1就是前面介绍的那张状态迁移图的另一种描述形式。 表1 状态迁移表 ①采用表格方式来描述状态机，优点是可容纳更多的文字信息。例如，我们不但可以在状态迁移表中描述状态的迁移关系，还可以把每个状态的特征描述也包含在内。 ②如果表格内容较多，过于臃肿不利于阅读，我们也可以将状态迁移表进行拆分。经过拆分后的表格根据其具体内容，表格名称也有所变化。 ③比如，我们可以把状态特征和迁移关系分开列表。被单独拆分出来的描述状态特征的表格，也可以称为“状态真值表”。这其中比较常见的就是把每个状态的显示内容单独列表。这种描述每个状态显示内容的表称之为“显示真值表”。同样，我们把单独表述基于按键的状态迁移表称为“按键功能真值表”。另外，如果每一个状态包含的信息量过多，我们也可以把每个状态单独列表。 ④由此可见，状态迁移表作为状态迁移图的有益补充，它的表现形式是灵活的。 ⑤状态迁移表优点是信息涵盖面大，缺点是视觉上不够直观，因此它并不能取代状态迁移图。比较理想的是将图形和表格结合应用。用图形展现宏观，用表格说明细节。二者互为参照，相得益彰。

用状态机思路实现一个时钟程序接下来，我将就状态机的应用，结合流程图、状态迁移图和状态迁移，举一个实际例子。下面这张图是一个时钟程序的状态迁移图，如图2所示。

图2 时钟程序状态迁移图 把这张图稍做归纳，就可以得到它的另一种表现形式——状态迁移表，如表2所示。 表2 时钟程序状态迁移表 状态机应用的注意事项 基于状态机的程序调度机制，其应用的难点并不在于对状态机概念的理解，而在于对系统工作状态的合理划分。 初学者往往会把某个“程序动作”当作是一种“状态”来处理。我称之为“伪态”。那么如何区分“动作”和“状态”。本匠人的心得是看二者的本质：“动作”是不稳定的，即使没有条件的触发，“动作”一旦执行完毕就结束了；而“状态”是相对稳定的，如果没有外部条件的触发，一个状态会一直持续下去。 初学者的另一种比较致命的错误，就是在状态划分时漏掉一些状态。我称之为“漏态”。 “伪态”和“漏态”这两种错误的存在，将会导致程序结构的涣散。因此要特别小心避免。 更复杂的状态机 前面介绍的是一种简单的状态结构。它只有一级，并且只有一维，如图3所示。 图3 线性状态机结构 如果有必要，我们可以建立更复杂的状态机模型。 1 多级状态结构 状态机可以是多级的。在分层的多级状态机系统里面，一个“父状态”下可以划分多个“子状态”，这些子状态共同拥有上级父状态的某些共性，同时又各自拥有自己的一些个性。 在某些状态下，还可以进一步划分子状态。比如，我们可以把前面的时钟例子修改如下： 把所有和时钟功能有关的状态，合并成1个一级状态。在这个状态下，又可以划分出3个二级子状态，分别为显示时间、设置小时、设置分钟； 同样，我们也可以把所有和闹钟功能有关的状态，合并成1个一级状态。在这个状态下，再划分出4个二级子状态，分别为显示闹钟、设置“时”、设置“分”、设置鸣叫时间。 我们需要用另一个状态变量（寄存器）来表示这些子状态。 子状态下面当然还可以有更低一级的孙状态（子子孙孙无穷尽也），从而将整个状态体系变成了树状多级状态结构，如图4所示。 图4 树状多级状态结构 2 多维状态结构 状态结构也可以是多维的。从不同的角度对系统进行状态的划分，这些状态的某些特性是交叉的。比如，在按照按键和显示划分状态的同时，又按照系统的工作进程做出另一种状态划分。这两种状态划分同时存在，相互交叉，从而构成了二维的状态结构空间。 举一个这方面的例子，如：空调遥控器，如图5所示。 图5 多维状态机结构 同样，我们也可以构建三维、四维甚至更多维的状态结构。每一维的状态都需要用一个状态变量（寄存器）来表示。 无论多级状态结构和多维状态结构看上去多么迷人，匠人的忠告是：我们依然要尽可能地简化状态结构，能用单级、单维的结构，就不要给自己找事，去玩那噩梦般的复杂结构。 简单的才是最有效的。 结束语 对状态机的理解需要一个由浅入深的过程。这个过程应该是与实践应用和具体案例思考相结合的。当一种良好的思路成为设计的习惯，它就能给设计者带来回报。愿这篇手记里介绍的基于状态机的编程思路能给新手们带来一些启迪，帮助大家找到“程序设计”的感觉。