Linux 編程之有限狀態機 FSM 的理解與實現
有限狀態機（finite state machine）簡稱 FSM，表示有限個狀態及在這些狀態之間的轉移和動作等行爲的數學模型，在計算機領域有着廣泛的應用。FSM 是一種邏輯單元內部的一種高效編程方法，在服務器編程中，服務器可以根據不同狀態或者消息類型進行相應的處理邏輯，使得程序邏輯清晰易懂。
那有限狀態機通常在什麼地方被用到？
處理程序語言或者自然語言的 tokenizer, 自底向上解析語法的 parser，
各種通信協議發送方和接受方傳遞數據對消息處理，遊戲 AI 等都有應用場景。
狀態機有以下幾種實現方法，我將一一闡述它們的優缺點。
一、使用 if/else if 語句實現的 FSM
使用 if/else if 語句是實現的 FSM 最簡單最易懂的方法，我們只需要通過大量的 if /else if 語句來判斷狀態值來執行相應的邏輯處理。
看看下面的例子，我們使用了大量的 if/else if 語句實現了一個簡單的狀態機，做到了根據狀態的不同執行相應的操作，並且實現了狀態的跳轉。
看完上面的例子，大家有什麼感受？是不是感覺程序雖然簡單易懂，但是使用了大量的 if 判斷語句，使得代碼很低端，同時代碼膨脹的比較厲害。這個狀態機的狀態僅有幾個，代碼膨脹並不明顯，但是如果我們需要處理的狀態有數十個的話，該狀態機的代碼就不好讀了。
二、使用 switch 實現 FSM
使用 switch 語句實現的 FSM 的結構變得更爲清晰了，其缺點也是明顯的：這種設計方法雖然簡單，通過一大堆判斷來處理，適合小規模的狀態切換流程，但如果規模擴大難以擴展和維護。
三、使用函數指針實現 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; i<g_max_num; i++)
{
//當且僅當當前狀態下來個指定的事件，我才執行它
if (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 框架，以後進行擴展就很簡單了（只要在狀態表里加一行來寫入新的狀態處理就可以了）。
作者：Madcola
原文地址：http://www.cnblogs.com/skyfsm/p/7071386.html
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/bTSR1mu6etApkbsxGqKvKA