Linux 編程之有限狀態機 FSM 的理解與實現

有限狀態機 (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
;

}

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

上面的图可以看出，当且仅当在指定的状态下来了指定的事件才会发生函数的执行以及状态的转移，否则不会发生状态的跳转。这种机制使得这个状态机不停地自动运转，有条不絮地完成任务。

与前两种方法相比，使用函数指针实现 FSM 能很好用于大规模的切换流程，只要我们实现搭好了 FSM 框架，以后进行扩展就很简单了（只要在状态表里加一行来写入新的状态处理就可以了）。

以上是Linux 編程之有限狀態機 FSM 的理解與實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！