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

更新時間：2017年06月27日 10:58:31 作者：Madcola

這篇文章主要幫助大家理解與實現(xiàn)Linux有限狀態(tài)機FSM，具有一定的參考價值，感興趣的小伙伴們可以參考一下

有限狀態(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)的跳轉。

//比如我們定義了小明一天的狀態(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)的轉移
    }
    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 main()
{
  int state = GET_UP;
  //小明的一天
  while (1)
  {

    switch(state)
    {
    case GET_UP:
      GetUp(); //具體調(diào)用的函數(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ā)生的事件

enum
{
  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<g_max_num; i++)
  {
    //當且僅當當前狀態(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();
    }

    //跳轉到下一個狀態(tài)
    FSM_StateTransfer(pFsm, NextState);
  }
  else
  {
    // do nothing
  }
}

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

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

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