Linux?編程之有限狀態(tài)機?FSM?的理解與實現(xiàn)
[導讀]關注、星標公眾號，直達精彩內(nèi)容來源：https://www.cnblogs.com/skyfsm/p/7071386.html作者：Madcola有限狀態(tài)機（finitestatemachine）簡稱FSM，表示有限個狀態(tài)及在這些狀態(tài)之間的轉移和動作等行為的數(shù)學模型，在計算機領域...
關注、星標公眾號，直達精彩內(nèi)容來源：https://www.cnblogs.com/skyfsm/p/7071386.html作者：Madcola
有限狀態(tài)機（finite state machine）簡稱 FSM，表示有限個狀態(tài)及在這些狀態(tài)之間的轉移和動作等行為的數(shù)學模型，在計算機領域有著廣泛的應用。FSM 是一種邏輯單元內(nèi)部的一種高效編程方法，在服務器編程中，服務器可以根據(jù)不同狀態(tài)或者消息類型進行相應的處理邏輯，使得程序邏輯清晰易懂。
那有限狀態(tài)機通常在什么地方被用到？
處理程序語言或者自然語言的 tokenizer, 自底向上解析語法的 parser，各種通信協(xié)議發(fā)送方和接受方傳遞數(shù)據(jù)對消息處理，游戲 AI 等都有應用場景。
狀態(tài)機有以下幾種實現(xiàn)方法，我將一一闡述它們的優(yōu)缺點。
一、使用 if/else if 語句實現(xiàn)的 FSM
使用 if/else if 語句是實現(xiàn)的 FSM 最簡單最易懂的方法，我們只需要通過大量的 if /else if 語句來判斷狀態(tài)值來執(zhí)行相應的邏輯處理。
看看下面的例子，我們使用了大量的 if/else if 語句實現(xiàn)了一個簡單的狀態(tài)機，做到了根據(jù)狀態(tài)的不同執(zhí)行相應的操作，并且實現(xiàn)了狀態(tài)的跳轉。
????看完上面的例子，大家有什么感受？是不是感覺程序雖然簡單易懂，但是使用了大量的 if 判斷語句，使得代碼很低端，同時代碼膨脹的比較厲害。這個狀態(tài)機的狀態(tài)僅有幾個，代碼膨脹并不明顯，但是如果我們需要處理的狀態(tài)有數(shù)十個的話，該狀態(tài)機的代碼就不好讀了。
二、使用 switch 實現(xiàn) FSM
使用 switch 語句實現(xiàn)的 FSM 的結構變得更為清晰了，其缺點也是明顯的：這種設計方法雖然簡單，通過一大堆判斷來處理，適合小規(guī)模的狀態(tài)切換流程，但如果規(guī)模擴大難以擴展和維護。
三、使用函數(shù)指針實現(xiàn) FSM
使用函數(shù)指針實現(xiàn) FSM 的思路：建立相應的狀態(tài)表和動作查詢表，根據(jù)狀態(tài)表、事件、動作表定位相應的動作處理函數(shù)，執(zhí)行完成后再進行狀態(tài)的切換。
當然使用函數(shù)指針實現(xiàn)的 FSM 的過程還是比較費時費力，但是這一切都是值得的，因為當你的程序規(guī)模大時候，基于這種表結構的狀態(tài)機，維護程序起來也是得心應手。
下面給出一個使用函數(shù)指針實現(xiàn)的 FSM 的框架：
我們還是以 “小明的一天” 為例設計出該 FSM。
先給出該 FSM 的狀態(tài)轉移圖：
下面講解關鍵部分代碼實現(xiàn)
首先我們定義出小明一天的活動狀態(tài)：
//比如我們定義了小明一天的狀態(tài)如下
我們也定義出會發(fā)生的事件
定義狀態(tài)表的數(shù)據(jù)結構
接下來定義出最重要 FSM 的狀態(tài)表，我們整個 FSM 就是根據(jù)這個定義好的表來運轉的。
狀態(tài)機的注冊、狀態(tài)轉移、事件處理的動作實現(xiàn)
有限狀態(tài)機（finite state machine）簡稱 FSM，表示有限個狀態(tài)及在這些狀態(tài)之間的轉移和動作等行為的數(shù)學模型，在計算機領域有著廣泛的應用。FSM 是一種邏輯單元內(nèi)部的一種高效編程方法，在服務器編程中，服務器可以根據(jù)不同狀態(tài)或者消息類型進行相應的處理邏輯，使得程序邏輯清晰易懂。
那有限狀態(tài)機通常在什么地方被用到？
處理程序語言或者自然語言的 tokenizer, 自底向上解析語法的 parser，各種通信協(xié)議發(fā)送方和接受方傳遞數(shù)據(jù)對消息處理，游戲 AI 等都有應用場景。
狀態(tài)機有以下幾種實現(xiàn)方法，我將一一闡述它們的優(yōu)缺點。
一、使用 if/else if 語句實現(xiàn)的 FSM
使用 if/else if 語句是實現(xiàn)的 FSM 最簡單最易懂的方法，我們只需要通過大量的 if /else if 語句來判斷狀態(tài)值來執(zhí)行相應的邏輯處理。
看看下面的例子，我們使用了大量的 if/else if 語句實現(xiàn)了一個簡單的狀態(tài)機，做到了根據(jù)狀態(tài)的不同執(zhí)行相應的操作，并且實現(xiàn)了狀態(tài)的跳轉。
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(); //具體調用的函數(shù)? ? ? ? ? ?state = GO_TO_SCHOOL; ?//狀態(tài)的轉移? ? ? ?}? ? ? ?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 判斷語句，使得代碼很低端，同時代碼膨脹的比較厲害。這個狀態(tài)機的狀態(tài)僅有幾個，代碼膨脹并不明顯，但是如果我們需要處理的狀態(tài)有數(shù)十個的話，該狀態(tài)機的代碼就不好讀了。
二、使用 switch 實現(xiàn) FSM
使用 switch 語句實現(xiàn)的 FSM 的結構變得更為清晰了，其缺點也是明顯的：這種設計方法雖然簡單，通過一大堆判斷來處理，適合小規(guī)模的狀態(tài)切換流程，但如果規(guī)模擴大難以擴展和維護。
{? ?int state = GET_UP;? ?//小明的一天? ?while (1)? ?{? ? ? ?switch(state)? ? ? ?{? ? ? ?case GET_UP:? ? ? ? ? ?GetUp(); //具體調用的函數(shù)? ? ? ? ? ?state = GO_TO_SCHOOL; ?//狀態(tài)的轉移? ? ? ? ? ?break;? ? ? ?case GO_TO_SCHOOL:? ? ? ? ? ?Go2School();? ? ? ? ? ?state = HAVE_LUNCH;? ? ? ? ? ?break;? ? ? ?case HAVE_LUNCH:? ? ? ? ? ?HaveLunch();? ? ? ? ? ?state = GO_HOME;? ? ? ? ? ?break;? ? ? ? ? ?...? ? ? ?default:? ? ? ? ? ?break;? ? ? ?}? ?}? ?return 0;}
三、使用函數(shù)指針實現(xiàn) FSM
使用函數(shù)指針實現(xiàn) FSM 的思路：建立相應的狀態(tài)表和動作查詢表，根據(jù)狀態(tài)表、事件、動作表定位相應的動作處理函數(shù)，執(zhí)行完成后再進行狀態(tài)的切換。
當然使用函數(shù)指針實現(xiàn)的 FSM 的過程還是比較費時費力，但是這一切都是值得的，因為當你的程序規(guī)模大時候，基于這種表結構的狀態(tài)機，維護程序起來也是得心應手。
下面給出一個使用函數(shù)指針實現(xiàn)的 FSM 的框架：
我們還是以 “小明的一天” 為例設計出該 FSM。
先給出該 FSM 的狀態(tài)轉移圖：
下面講解關鍵部分代碼實現(xiàn)
首先我們定義出小明一天的活動狀態(tài)：
//比如我們定義了小明一天的狀態(tài)如下
enum{? ?GET_UP,? ?GO_TO_SCHOOL,? ?HAVE_LUNCH,? ?DO_HOMEWORK,? ?SLEEP,};
我們也定義出會發(fā)生的事件
{? ?EVENT1 = 1,? ?EVENT2,? ?EVENT3,};
定義狀態(tài)表的數(shù)據(jù)結構
typedef struct FsmTable_s{? ?int event; ? //事件? ?int CurState; ?//當前狀態(tài)? ?void (*eventActFun)(); ?//函數(shù)指針? ?int NextState; ?//下一個狀態(tài)}FsmTable_t;
接下來定義出最重要 FSM 的狀態(tài)表，我們整個 FSM 就是根據(jù)這個定義好的表來運轉的。
FsmTable_t XiaoMingTable[] ={? ?//{到來的事件，當前的狀態(tài)，將要要執(zhí)行的函數(shù)，下一個狀態(tài)}? ?{ 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};
狀態(tài)機的注冊、狀態(tài)轉移、事件處理的動作實現(xiàn)
/*狀態(tài)機注冊*/void FSM_Regist(FSM_t* pFsm, FsmTable_t* pTable){? ?pFsm->FsmTable = pTable;}/*狀態(tài)遷移*/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; ?//函數(shù)指針初始化為空? ?int NextState;? ?int CurState = pFsm->curState;? ?int flag = 0; //標識是否滿足條件? ?int i;? ?/*獲取當前動作函數(shù)*/? ?for (i = 0; i? ?{? ? ? ?//當且僅當當前狀態(tài)下來個指定的事件，我才執(zhí)行它? ? ? ?if (event == pActTable[i].event
下載文檔
