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

2024-09-01 13:52:12

字體：大中小

來源：轉載

供稿：網友

有限狀態機（finite state machine）簡稱FSM，表示有限個狀態及在這些狀態之間的轉移和動作等行為的數學模型，在計算機領域有著廣泛的應用。FSM是一種邏輯單元內部的一種高效編程方法，在服務器編程中，服務器可以根據不同狀態或者消息類型進行相應的處理邏輯，使得程序邏輯清晰易懂。

那有限狀態機通常在什么地方被用到？

處理程序語言或者自然語言的 tokenizer,自底向上解析語法的parser，
各種通信協議發送方和接受方傳遞數據對消息處理，游戲AI等都有應用場景。

狀態機有以下幾種實現方法，我將一一闡述它們的優缺點。

一、使用if/else if語句實現的FSM
使用if/else if語句是實現的FSM最簡單最易懂的方法，我們只需要通過大量的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 main(){  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的狀態轉移圖：

Linux,有限狀態機,FSM

下面講解關鍵部分代碼實現

首先我們定義出小明一天的活動狀態

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

我們也定義出會發生的事件

enum{  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;}

看一看該狀態機跑起來的狀態轉移情況：

Linux,有限狀態機,FSM