Linux編程之有限狀態(tài)機(jī)FSM的理解與實現(xiàn)

有限狀態(tài)機(jī)(finite state machine)簡稱FSM，表示有限個狀態(tài)及在這些狀態(tài)之間的轉(zhuǎn)移和動作等行為的數(shù)學(xué)模型，在計算機(jī)領(lǐng)域有著廣泛的應(yīng)用。FSM是一種邏輯單元內(nèi)部的一種高效編程方法，在服務(wù)器編程中，服務(wù)器可以根據(jù)不同狀態(tài)或者消息類型進(jìn)行相應(yīng)的處理邏輯，使得程序邏輯清晰易懂。

那有限狀態(tài)機(jī)通常在什么地方被用到?

處理程序語言或者自然語言的 tokenizer,自底向上解析語法的parser，

各種通信協(xié)議發(fā)送方和接受方傳遞數(shù)據(jù)對消息處理，游戲AI等都有應(yīng)用場景。

狀態(tài)機(jī)有以下幾種實現(xiàn)方法，我將一一闡述它們的優(yōu)缺點。

一、使用if/else if語句實現(xiàn)的FSM

使用if/else if語句是實現(xiàn)的FSM最簡單最易懂的方法，我們只需要通過大量的if /else if語句來判斷狀態(tài)值來執(zhí)行相應(yīng)的邏輯處理。

看看下面的例子，我們使用了大量的if/else if語句實現(xiàn)了一個簡單的狀態(tài)機(jī)，做到了根據(jù)狀態(tài)的不同執(zhí)行相應(yīng)的操作，并且實現(xiàn)了狀態(tài)的跳轉(zhuǎ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(); //具體調(diào)用的函數(shù) state = GO_TO_SCHOOL; //狀態(tài)的轉(zhuǎn)移 } 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)機(jī)的狀態(tài)僅有幾個，代碼膨脹并不明顯，但是如果我們需要處理的狀態(tài)有數(shù)十個的話，該狀態(tài)機(jī)的代碼就不好讀了。

二、使用switch實現(xiàn)FSM

使用switch語句實現(xiàn)的FSM的結(jié)構(gòu)變得更為清晰了，其缺點也是明顯的：這種設(shè)計方法雖然簡單，通過一大堆判斷來處理，適合小規(guī)模的狀態(tài)切換流程，但如果規(guī)模擴(kuò)大難以擴(kuò)展和維護(hù)。

int main(){ int state = GET_UP; //小明的一天 while (1) { switch(state) { case GET_UP: GetUp(); //具體調(diào)用的函數(shù) state = GO_TO_SCHOOL; //狀態(tài)的轉(zhuǎn)移 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的思路：建立相應(yīng)的狀態(tài)表和動作查詢表，根據(jù)狀態(tài)表、事件、動作表定位相應(yīng)的動作處理函數(shù)，執(zhí)行完成后再進(jìn)行狀態(tài)的切換。

當(dāng)然使用函數(shù)指針實現(xiàn)的FSM的過程還是比較費時費力，但是這一切都是值得的，因為當(dāng)你的程序規(guī)模大時候，基于這種表結(jié)構(gòu)的狀態(tài)機(jī)，維護(hù)程序起來也是得心應(yīng)手。

下面給出一個使用函數(shù)指針實現(xiàn)的FSM的框架：

我們還是以“小明的一天”為例設(shè)計出該FSM。

先給出該FSM的狀態(tài)轉(zhuǎn)移圖：

下面講解關(guān)鍵部分代碼實現(xiàn)

首先我們定義出小明一天的活動狀態(tài)

//比如我們定義了小明一天的狀態(tài)如下enum{ GET_UP, GO_TO_SCHOOL, HAVE_LUNCH, DO_HOMEWORK, SLEEP,};

我們也定義出會發(fā)生的事件

enum{ EVENT1 = 1, EVENT2, EVENT3,};

定義狀態(tài)表的數(shù)據(jù)結(jié)構(gòu)

typedef struct FsmTable_s{ int event; //事件 int CurState; //當(dāng)前狀態(tài) void (*eventActFun)(); //函數(shù)指針 int NextState; //下一個狀態(tài)}FsmTable_t;

接下來定義出最重要FSM的狀態(tài)表，我們整個FSM就是根據(jù)這個定義好的表來運轉(zhuǎn)的。

FsmTable_t XiaoMingTable[] ={ //{到來的事件，當(dāng)前的狀態(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)機(jī)的注冊、狀態(tài)轉(zhuǎn)移、事件處理的動作實現(xiàn)

/*狀態(tài)機(jī)注冊*/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; //標(biāo)識是否滿足條件 int i; /*獲取當(dāng)前動作函數(shù)*/ for (i = 0; i//當(dāng)且僅當(dāng)當(dāng)前狀態(tài)下來個指定的事件，我才執(zhí)行它 if (event == pActTable[i].event && CurState == pActTable[i].CurState) { flag = 1; eventActFun = pActTable[i].eventActFun; NextState = pActTable[i].NextState; break; } } if (flag) //如果滿足條件了 { /*動作執(zhí)行*/ if (eventActFun) { eventActFun(); } //跳轉(zhuǎn)到下一個狀態(tài) FSM_StateTransfer(pFsm, NextState); } else { // do nothing }}

主函數(shù)我們這樣寫，然后觀察狀態(tài)機(jī)的運轉(zhuǎn)情況

int main(){ FSM_t fsm; InitFsm(&fsm); int event = EVENT1; //小明的一天,周而復(fù)始的一天又一天，進(jìn)行著相同的活動 while (1) { printf("event %d is coming...n", event); FSM_EventHandle(&fsm, event); printf("fsm current state %dn", fsm.curState); test(&event); sleep(1); //休眠1秒，方便觀察 } return 0;}

看一看該狀態(tài)機(jī)跑起來的狀態(tài)轉(zhuǎn)移情況：

上面的圖可以看出，當(dāng)且僅當(dāng)在指定的狀態(tài)下來了指定的事件才會發(fā)生函數(shù)的執(zhí)行以及狀態(tài)的轉(zhuǎn)移，否則不會發(fā)生狀態(tài)的跳轉(zhuǎn)。這種機(jī)制使得這個狀態(tài)機(jī)不停地自動運轉(zhuǎn)，有條不絮地完成任務(wù)。

與前兩種方法相比，使用函數(shù)指針實現(xiàn)FSM能很好用于大規(guī)模的切換流程，只要我們實現(xiàn)搭好了FSM框架，以后進(jìn)行擴(kuò)展就很簡單了(只要在狀態(tài)表里加一行來寫入新的狀態(tài)處理就可以了)。