首页

系统教程

LINUX

Linux 编程之有限状态机 FSM 的理解与实现

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Feb 05, 2024 am 11:30 AM

linuxlinux教程linux系统服务器编程linux命令外壳脚本typedef嵌入式linux良好的许可证linux入门linux学习

有限状态机 (Finite State Machine，简称FSM) 是指由有限个状态以及在这些状态之间的转移和动作等行为组成的数学模型，在计算机领域得到了广泛的应用。FSM 是一种高效的编程方法，用于在逻辑单元内部实现程序的处理逻辑，特别是在服务器编程中，通过基于不同的状态或消息类型进行相应的处理，可以使程序的逻辑更加清晰易懂。

那么，有限状态机通常在哪些地方被使用呢？

它可以应用于处理程序语言或自然语言的分词器 (tokenizer)，通过自底向上的语法解析器 (parser) 实现语法的解析和分析，在各种通信协议中，发送方和接收方之间通过传递数据来处理消息，在游戏人工智能中等等。

对于有限状态机的实现，一般有以下几种方法，我将逐一介绍它们的优缺点。

一、使用 if/else if 语句实现的有限状态机

使用 if/else if 语句实现有限状态机是最简单、易于理解的方法。只需要使用大量的 if/else if 语句来判断当前的状态，并执行相应的逻辑处理。

下面是一个简单的状态机示例，我们使用了大量的 if/else if 语句来实现，根据不同的状态执行相应的操作，并实现状态的转换。

enum

{

    GET_UP,

    GO_TO_SCHOOL,

    HAVE_LUNCH,

    GO_HOME,

    DO_HOMEWORK,

    SLEEP,

};





int
 main()

{

    
int
 state = GET_UP;

    
//小明的一天

    
while
 (
1
)

    {

        
if
 (state == GET_UP)

        {

            
GetUp
(); 
//具体调用的函数

            state = GO_TO_SCHOOL;  
//状态的转移

        }

        
else
 
if
 (state == GO_TO_SCHOOL)

        {

            
Go2School
();

            state = HAVE_LUNCH;

        }

        
else
 
if
 (state == HAVE_LUNCH)

        {

            
HaveLunch
();

        }

        ...

        
else
 
if
 (state == SLEEP)

        {

            
Go2Bed
();

            state = GET_UP;

        }

    }



    
return
 
0
;

}

看完上面的例子，大家有什么感受？是不是感觉程序虽然简单易懂，但是使用了大量的 if 判断语句，使得代码很低端，同时代码膨胀的比较厉害。这个状态机的状态仅有几个，代码膨胀并不明显，但是如果我们需要处理的状态有数十个的话，该状态机的代码就不好读了。

二、使用 switch 实现 FSM

使用 switch 语句实现的 FSM 的结构变得更为清晰了，其缺点也是明显的：这种设计方法虽然简单，通过一大堆判断来处理，适合小规模的状态切换流程，但如果规模扩大难以扩展和维护。

   
int
 state = GET_UP;

    
//小明的一天

    
while
 (
1
)

    {



        
switch
(state)

        {

        
case
 GET_UP:

            
GetUp
(); 
//具体调用的函数

            state = GO_TO_SCHOOL;  
//状态的转移

            
break
;

        
case
 GO_TO_SCHOOL:

            
Go2School
();

            state = HAVE_LUNCH;

            
break
;

        
case
 HAVE_LUNCH:

            
HaveLunch
();

            state = GO_HOME;

            
break
;

            ...

        
default
:

            
break
;

        }

    }



    
return
 
0
;

}

三、使用函数指针实现 FSM

使用函数指针实现 FSM 的思路：建立相应的状态表和动作查询表，根据状态表、事件、动作表定位相应的动作处理函数，执行完成后再进行状态的切换。

当然使用函数指针实现的 FSM 的过程还是比较费时费力，但是这一切都是值得的，因为当你的程序规模大时候，基于这种表结构的状态机，维护程序起来也是得心应手。

下面给出一个使用函数指针实现的 FSM 的框架：

我们还是以 “小明的一天” 为例设计出该 FSM。

先给出该 FSM 的状态转移图：

下面讲解关键部分代码实现

首先我们定义出小明一天的活动状态：

//比如我们定义了小明一天的状态如下

enum

{

    GET_UP,

    GO_TO_SCHOOL,

    HAVE_LUNCH,

    DO_HOMEWORK,

    SLEEP,

};

我们也定义出会发生的事件

{

    EVENT1 = 
1
,

    EVENT2,

    EVENT3,

};

定义状态表的数据结构

typedef
 
struct
 
FsmTable_s

{

    
int
 
event
;   
//事件

    
int
 
CurState
;  
//当前状态

    
void
 (*eventActFun)();  
//函数指针

    
int
 
NextState
;  
//下一个状态

}
FsmTable_t
;

接下来定义出最重要 FSM 的状态表，我们整个 FSM 就是根据这个定义好的表来运转的。

FsmTable_t
 
XiaoMingTable
[] =

{

    
//{到来的事件，当前的状态，将要要执行的函数，下一个状态}

    { EVENT1,  SLEEP,           
GetUp
,        GET_UP },

    { EVENT2,  GET_UP,          
Go2School
,    GO_TO_SCHOOL },

    { EVENT3,  GO_TO_SCHOOL,    
HaveLunch
,    HAVE_LUNCH },

    { EVENT1,  HAVE_LUNCH,      
DoHomework
,   DO_HOMEWORK },

    { EVENT2,  DO_HOMEWORK,     
Go2Bed
,       SLEEP },



    
//add your codes here

};

状态机的注册、状态转移、事件处理的动作实现

/*状态机注册*/

void
 FSM_Regist(
FSM_t
* pFsm, 
FsmTable_t
* pTable)

{

    pFsm->
FsmTable
 = pTable;

}



/*状态迁移*/

void
 FSM_StateTransfer(
FSM_t
* pFsm, 
int
 state)

{

    pFsm->curState = state;

}



/*事件处理*/

void
 FSM_EventHandle(
FSM_t
* pFsm, 
int
 
event
)

{

    
FsmTable_t
* pActTable = pFsm->
FsmTable
;

    
void
 (*eventActFun)() = NULL;  
//函数指针初始化为空

    
int
 
NextState
;

    
int
 
CurState
 = pFsm->curState;

    
int
 flag = 
0
; 
//标识是否满足条件

    
int
 i;



    
/*获取当前动作函数*/

    
for
 (i = 
0
; iif
 (
event
 == pActTable[i].
event
 && 
CurState
 == pActTable[i].
CurState
)

        {

            flag = 
1
;

            eventActFun = pActTable[i].eventActFun;

            
NextState
 = pActTable[i].
NextState
;

            
break
;

        }

    }





    
if
 (flag) 
//如果满足条件了

    {

        
/*动作执行*/

        
if
 (eventActFun)

        {

            eventActFun();

        }



        
//跳转到下一个状态

        FSM_StateTransfer(pFsm, 
NextState
);

    }

    
else

    {

        
// do nothing

    }

}

主函数我们这样写，然后观察状态机的运转情况。

int
 main()

{

    
FSM_t
 fsm;

    
InitFsm
(&fsm);

    
int
 
event
 = EVENT1;

    
//小明的一天,周而复始的一天又一天，进行着相同的活动

    
while
 (
1
)

    {

        printf(
"event %d is coming...\n"
, 
event
);

        FSM_EventHandle(&fsm, 
event
);

        printf(
"fsm current state %d\n"
, fsm.curState);

        test(&
event
);

        sleep(
1
);  
//休眠1秒，方便观察

    }



    
return
 
0
;

}

看一看该状态机跑起来的状态转移情况：