谁能给我们讲解下状态机的应用阿~

只看该作者 · 2007-12-29 20:59

..发现写程序的时候很多地方都用到类似的概念..
但不能把模型抽象出来.. 糊里糊涂的..

哪位大虾能比较全面的说说状态机的软件实现呢..

:)

只看该作者 · 2007-12-29 22:08

                                   状态机的两种写法
                        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。

1万 · 2008-1-5 13:43

     看看小时候玩的5块钱那种最简单的电子表。只有2个按钮就能操作。
     暂且称为按钮A和按钮B
     现给出一个完整的功能文字描述：
     在显示时间时按A，屏幕显示变成日期
     在显示日期时按A，屏幕显示变成秒钟
     在显示秒钟时按A，屏幕显示变成时间
     在显示秒钟时按B，秒钟归0
     在显示时间时按B，屏幕时间、日期交替显示。
     在时间、日期交替显示时按B，屏幕“时”闪烁
     在“时”闪烁时按B，屏幕“时”加1，超过23回0
     在“时”闪烁时按A，屏幕“分”闪烁
     在“分”闪烁时按B，屏幕“分”加1，超过59回0
     在“分”闪烁时按A，屏幕“月”闪烁
     在“月”闪烁时按B，屏幕“月”加1，超过12回0
     在“月”闪烁时按A，屏幕“日”闪烁
     在“日”闪烁时按B，屏幕“日”加1，超过31回0
     在“日”闪烁时按A，屏幕回到时间显示

    如果按照新手的思路，尝试去画流程图，很快就会陷入一头雾水：你会发现实现这个功能的程序根本就没有“确定的流程”。因为程序实际流程是根据人的操作而变化的。程序运行到什么地方，完全取决于两个键的次序，有无数种次序组合，根本不可能画出流程图来。
    但是我们会发现，这个电子表功能的“语言描述”在语法上似乎有某种规律，就是：
    当系统处于某状态（S1）时，如果发生了什么事情(E)，就执行某功能(F)，然后系统变成新状态（S2）
    只要能用上面这句话描述的系统，都可以用一种状态跳转机制很方便的实现
，并且一句话其实就是一个if(...)，无论有多少多复杂的功能，只要能用上面这句话描述，都可以通过状态机编程实现。

我们将它们抽象。整个系统中有2个事件分别是：A按下，B按下

    A按下(可以是中断)时执行：
{
     if(Status==TIME)  //当显示时间时按下A键
     {
        Status=DATE    //变成显示日期
     }
     if(Status==DATE)  //当显示日期时按下A键
     {
        Status=SEC     //变成显示秒钟
     }
     if(Status==SEC)  //当显示秒钟时按下A键
     {
        Status=TIME     //变成显示时间
     }
     if(Status==SET_HOUR)  //当设置“小时”时按下A键
     {
        Status=SET_MINUT        //变成设置“分钟”
     }
     if(Status==SET_MINUT)  //当设置“分钟”时按下A键
     {
        Status=SET_MONTH        //变成设置“月”
     }
     .....
     .....
}


    B按下(可以是中断)时执行：
{
      if(Status==SEC)  //当显示秒钟时按下B键
     {
        Secound=0     //秒归0
     }
     if(Status==TIME)  //当显示时间时按下B键
     {
        Status=TIMEDATE    //变成时间日期交替显示
     }
     if(Status==TIMEDATE)  //当日期交替显示时按下B键
     {
        Status=SET_HOUR    //变成设置“时”（时闪烁）
     }
     if(Status==SET_HOUR)  //当设置“时”时按下B键
     {
        Status=Hour++      //时加1
        if(Hour>23) Hour=0;
     }

     .....
     .....
}

     和语言描述完全一致，很快就能写完程序。这就是最简单的状态机思想。
     当然，上述一大堆if可以用switch case来实现
     实际中，大量的并发过程都可以表述为状态跳转关系，从而将CPU从过程中解放出来，只需处理状态关系，因为真正需要CPU的是状态变化的时刻，而不是过程中大量的等待，这样大量的并发过程都可以并行处理。

只看该作者 · 2008-1-9 22:04

状态机很复杂怎么办, 最有效的办法是把状态机按照分层和并发的方法来分解.
分层的意思是指: 状态机有些状态里包含有若干个小状态机, 但如果离开这个状态的话,这个状态里面所包含的状态机全部会变为无效, 这种状态叫做复合状态, 这样就可以把很复杂的状态机需求分解为如顶层状态机, 第二层, 第三层, ...这是一种非常行之有效的方法, 在化解复杂性的同时体现了状态机的生命周期, 但如果要重用就不是其所长了.

并发的意思是指:在执行一个动作或过程的同时还要能够照常响应其他事件, 或者同一个事件会引起不同状态机不同的动作, 比如在空闲的时候可能有若干个并行的状态机在运行, 但可能只有一个(主)状态机是真正在响应空闲时的事件的, 其他状态机可能只是在空转, 但如果(主)状态机如果接受某个事件而变迁到另一个状态, 可能会激活空闲时空转的那些并行状态机运行, 也切换到另一个状态, 这样相互合作从而完成一系列有效预定的任务. 并发不但能增强实时性, 降低复杂性, 而且能够达到状态机重用的目的, 如果你有若干复合状态都会执行同样的动作,不妨把他作为一个并发的模块来处理, 当然不可滥用, 因为并发的引入同样会引入状态机之间的同步等问题,可能使在某种情况下会带入不可预测的结果.

状态机之间的交互最常见和有效的就是信号和事件(消息), 信号一般会在发出后立即执行响应这个信号的状态机, 而事件发出后可能并不会马上执行, 可能进入事件队列然后执行其他任务等待下一个事件分发时时才真正执行, 当然这个根据具体实现会有所差别罗.

关于这些知识大家可以看visual state的user manual, 上面还是说得很清楚的
对MDD(模型驱动开发)有兴趣的可参考UML和rhapsody.

只看该作者 · 2008-1-12 11:42

状态图的实现有三种方式：
1、switch
2、查表
3、函数指针

如果编译器支持函数指针，最好用指针。有些编编译器的函数指针，编译完代码会较长。如果不支持，只能用SWITCH.
    switch做层次式状态机会麻烦一些。
    在状态机中，事件队列还是比较重要的。

void Fsm_dispatch(Fsm *me)
{
    State  s = me->State__;
    (*s)(me);
    if (me->Sig_ == (Signal)0) {

        me->Sig_ = (Signal)EXIT_SIG;
        (*s)(me);               //源状态执行退出动作 */

        me->Sig_ = (Signal)ENTRY_SIG;
        (*me->State__)(me);     //目标状态执行进入动作 */
    }
}

1万 · 2007-12-29 21:08

switch (state) {
case STATE1:
  ......
  state = STATE2;  // 改变到下一个状态
  break;
case STATE2:
  ......
  state = STATE3;  // 改变到下一个状态
  break;

default:
.....
}

2万 · 2007-12-29 21:17

3万 · 2007-12-29 21:34

只看该作者 · 2007-12-30 08:18

只看该作者 · 2007-12-30 10:38

5楼的那个**我看过.,.

网上也就艘到那一篇容易懂点的.不过很多都是用函数指针什么实现的.

...想多了解些

只看该作者 · 2007-12-30 15:09

最初级：
if（）
else

高点：switch

再高：事件驱动

第三层的武功好像就靠意会了

2万 · 2007-12-30 15:37

建议档主自己找个课题练练就会有感觉了，你可以设计让单片机控制4个继电器分别按各自的定时值执行开合动作，普通的方式肯定很麻烦，而用状态机却很容易实现。

2万 · 2007-12-30 15:44

程序根据状态编码的序号将程序引导到下次程序应该到的运行路径~~~

哈哈~~~这样就简化了程序设计和减少了程序分支~~~提高了编程效率.

如果下次程序没运行到预定的程序状态都将视为非法~~~
相关链接:https://bbs.21ic.com/club/bbs/list.asp?boardid=27&t=2809345

2万 · 2007-12-30 16:50

只看该作者 · 2007-12-30 19:03

楼上好舒服..
我查了查.好象没有系统讲这方面的...
我比较想知道的是如何把一个工程问题转换成状态机的思路去解决.
还不是一开始就if else switch case...

只看该作者 · 2007-12-30 21:13

可以得到关于状态机的比较系统的技术支持。
EasyARM2200和SmartARM2200增值软件合集第二版

只看该作者 · 2007-12-30 21:21

我看过他以前利用状态机写一个处理几个任务的状态程序。

只看该作者 · 2008-1-2 16:25

只看该作者 · 2008-1-2 17:39

armecos写得这么详细的东西，:)

只看该作者 · 2008-1-3 10:30

#include    <intrins.h>
#include    ".headCPU32.h"
#include    ".headdefine.h"
#include    ".headglobal.h"

static    bit    DLTReadDataApp(void);
static    bit    DLTReadAgainApp(void);
static    bit    DLTReadRestDataApp(void);
static    bit    DLTWriteDataApp(void);
static    bit    DLTBreadTimeApp(void);
static    bit    DLTWriteDeviceApp(void);
static    bit    DLTChangeBaudRateApp(void);
static    bit    DLTChangePasswordApp(void);
static    bit    DLTChangeMaxNeedApp(void);

typedef struct EnCodeDLTCommand
    {
        unsigned char DLTCommandWord;        //DLT645 command word.
        unsigned char DLTcommandLength;        //DLT645 data length.
        bit    (*DLTCommandProPtr)(void);        //Enable DLT645 command application.
    } EnCodeDLTCommand;

EnCodeDLTCommand code    EncodeCommandUnit[] =
    {
        { 0x01,0x02,&DLTReadDataApp},
        { 0x02,0x02,&DLTReadRestDataApp},
        { 0x03,0x00,&DLTReadAgainApp},
        { 0x04,0x02,&DLTWriteDataApp},
        { 0x08,0x06,&DLTBreadTimeApp},
        { 0x0A,0x06,&DLTWriteDeviceApp},
        { 0x0C,0x01,&DLTChangeBaudRateApp},
        { 0x0F,0x08,&DLTChangePasswordApp},
        { 0x10,0x04,&DLTChangeMaxNeedApp}
    };

static    bit    DLTReadDataApp(void)            //0
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTReadAgainApp(void)            //1
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTReadRestDataApp(void)        //2
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTWriteDataApp(void)            //3
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTBreadTimeApp(void)            //4
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTWriteDeviceApp(void)            //5
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTChangeBaudRateApp(void)        //6
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTChangePasswordApp(void)        //7
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}
static    bit    DLTChangeMaxNeedApp(void)        //8
{
    //do some judgement and return success or false
    _nop_();
    _nop_();
    //debug:
    return    1;
}

void    main(void)
{

    unsigned char     DLTControlWordInx    =    0x00;        //debug

    bit    FgNeedToAnswer;
    FgNeedToAnswer =   (*EncodeCommandUnit[DLTControlWordInx].DLTCommandProPtr)();

    while(1)
    {
    }
}

只看该作者 · 2008-1-3 10:36

不叫状态机，叫命令解释程序。
不过遇到同行了，呵呵。

1万 · 2008-1-3 10:58

很多编译器在编译switch case时用的就是18楼的这个方法，但比你这个效率还高，这是因为编译器作了更好的优化。

只看该作者 · 2008-1-3 11:38

看看PC编程的原理。

谁能给我们讲解下状态机的应用阿~

相关下载

相关帖子

状态机的两种写法

我来给个实际的状态机编程思想例子

状态机的分层, 并发和交互

状态图的实现有三种方式

用一个变量记录状态，用switch case执行操作

俺一直记得小x有个状态机的红外解码例子

状态迁移图没搞好没搞全也是一个麻烦——一旦程序大了

楼上如果是转贴的应该注明

~~呵呵.

很多层次

5楼讲得还不错

状态机实际就是编程事先设置好的程序状态的路径~~~

~~，躺椅舒服中……

呵.

购买《ecos增值包》的用户，

请老农讲讲吧

不用switch case,通過查表運行某個序號的程序并返回

真是有心人

用switch case效率太低了，看我的

楼上这个没有状态

用switch case效率并不低，主要看编译器的效率

状态机进一步，就是事件驱动。

核心会员奖章

常驻人口

奔腾之江水

技术高手奖章

终身成就奖章

坚毅之洋流

十世金身

技术领袖奖章

荣誉元老奖章

以坛为家

精英会员奖章

技术奇才奖章

突出贡献奖章

湍急之河流