状态机的两种写法

r囧r小猫 2022-08-25 11:54 223阅读 0赞

状态机的两种写法  
                        2004/12/26  www.armecos.com  asdjf@163.com  
  
yy20041226-1v1  
  
    有限状态机FSM思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法(软件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变连续处理为离散数字处理，符合计算机的工作特点。同时，因为有限状态机具有有限个状态，所以可以在实际的工程上实现。但这并不意味着其只能进行有限次的处理，相反，有限状态机是闭环系统，有限无穷，可以用有限的状态，处理无穷的事务。  
    有限状态机的工作原理如图1所示，发生事件(event)后，根据当前状态(cur\_state)，决定执行的动作(action)，并设置下一个状态号(nxt\_state)。  
  
                         -------------  
                         |           |-------->执行动作action  
     发生事件event ----->| cur\_state |  
                         |           |-------->设置下一状态号nxt\_state  
                         -------------  
                            当前状态  
                      图1 有限状态机工作原理  
  
  
                               e0/a0  
                              --->--  
                              |    |  
                   -------->----------  
             e0/a0 |        |   S0   |-----  
                   |    -<------------    | e1/a1  
                   |    | e2/a2           V  
                 ----------           ----------  
                 |   S2   |-----<-----|   S1   |  
                 ----------   e2/a2   ----------  
                       图2 一个有限状态机实例  
  
              --------------------------------------------  
              当前状态   s0        s1        s2     | 事件  
              --------------------------------------------  
                       a0/s0      --       a0/s0   |  e0  
              --------------------------------------------  
                       a1/s1      --        --     |  e1  
              --------------------------------------------  
                       a2/s2     a2/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。

发表评论取消回复

表情：

评论列表（有 0 条评论，223人围观）

还没有评论，来说两句吧...

相关阅读

相关 php冒泡排序的两种写法

第一种： function bubbleSort($arr) { foreach ($arr as $i => &$a) {

谁践踏了优雅/ 2022年10月23日 08:13/ 0 赞/ 204 阅读

相关整理：状态机的两种写法

　　有限状态机FSM思想广泛应用于硬件控制电路设计，也是软件上常用的一种处理方法（软件上称为FMM有限消息机）。它把复杂的控制逻辑分解成有限个稳定状态，在每个状态上判断事件，变

缺乏、安全感/ 2022年09月24日 10:27/ 0 赞/ 184 阅读

相关整理：状态机的两种写法对比

状态机可以用两种方法实现：竖着写(在状态中判断事件)和横着写(在事件中判断状态)。这两种实现在本质上是完全等效的，但在实际操作中，效果却截然不同。 =========

Myth丶恋晨/ 2022年09月24日 10:26/ 0 赞/ 172 阅读

相关 vue的两种写法

<!DOCTYPE html> <html> <head> <meta charset="utf-8" /> <ti

旧城等待，/ 2022年09月10日 12:11/ 0 赞/ 251 阅读

相关状态机的两种写法

状态机的两种写法 2004/12/26 www.armecos.com asdjf@163.com yy200

r囧r小猫/ 2022年08月25日 11:54/ 0 赞/ 224 阅读

相关 iOS关于model的两种写法

前言今天和大家说一说model的一些问题。model相信大家都不默生，因为对于OC来说（其他语言都应该是一样的），MVC这个模式应该都是最基本的。只要用刀MVC那么你就

蔚落/ 2022年08月19日 11:25/ 0 赞/ 281 阅读

相关 response重定向的两种写法

protected void doGet(HttpServletRequest request, HttpServletResponse response) throw

港控/mmm°/ 2022年08月12日 01:08/ 0 赞/ 203 阅读

相关两种Ajax写法

Ajax:(Asynchronous Javascript And XML)简称为异步的js和xml js中有两种写法： //原生js写法 functio

﹏ヽ暗。殇╰゛Y/ 2022年03月28日 15:11/ 0 赞/ 297 阅读

相关 ajax的两种写法

一、原生ajax的实现 1.什么是ajax？ ajax是异步的javas和xml（ Asynchronous JavaScript And XML）。通过在后台与服务器

古城微笑少年丶/ 2022年03月27日 05:37/ 0 赞/ 357 阅读

相关 animate两种写法

animate.css <image class="logo animate__animated " :class="{ animate_

绝地灬酷狼/ 2021年07月25日 17:33/ 0 赞/ 529 阅读