狀態(tài)機的三種實現方法

嵌入式大雜燴

關注「嵌入式大雜燴」，選擇「星標公眾號」一起進步！


作者 | Alicedodo
狀態(tài)機的實現無非就是 3 個要素：狀態(tài)、事件、響應。轉換成具體的行為就 3 句話。

發(fā)生了什么事？

現在系統處在什么狀態(tài)？

在這樣的狀態(tài)下發(fā)生了這樣的事，系統要干什么？用 C 語言實現狀態(tài)機主要有 3 種方法：switch—case 法、表格驅動法、函數指針法。
switch—case 法狀態(tài)用 switch—case 組織起來， 將事件也用switch—case 組織起來， 然后讓其中一個 switch—case 整體插入到另一個 switch—case 的每一個 case 項中  。
「程序清單 List4  ：」
switch(StateVal)
{
    case S0:
  switch(EvntID)
  {
   case E1:
    action_S0_E1(); /*S0 狀態(tài)下 E1 事件的響應*/
    StateVal = new state value;/*狀態(tài)遷移，不遷移則沒有此行*/
    break;
   case E2:
    action_S0_E2(); /*S0 狀態(tài)下 E2 事件的響應*/
    StateVal = new state value;
    break;
   ......
   case Em:
    action_S0_Em(); /*S0 狀態(tài)下 Em 事件的響應*/
    StateVal = new state value;
    break;
   default:
    break;
  }
  break;
    case S1:
  ......
  break;
    ......
    case Sn:
  ......
  break;
    default:
  break;
}
上面的偽代碼示例只是通用的情況，實際應用遠沒有這么復雜。雖然一個系統中事件可能有很多種，但在實際應用中，許多事件可能對某個狀態(tài)是沒有意義的。
例如在程序清單 List4中，如果 E2、······ Em 對處在 S0 狀態(tài)下的系統沒有意義，那么在 S0 的 case 下有關事件E2、······ Em 的代碼根本沒有必要寫,狀態(tài) S0 只需要考慮事件 E1 的處理就行了。
既然是兩個 switch—case 之間的嵌套， 那么就有一個誰嵌套誰的問題， 所以說 switch—case法有兩種寫法：狀態(tài)嵌套事件和事件嵌套狀態(tài)。這兩種寫法都可以， 各有利弊， 至于到底選用哪種方式就留給設計人員根據具體情況自行決斷吧。
關于 switch—case 法還有最后一點要說明， 因為 switch—case 的原理是從上到下挨個比較，越靠后，查找耗費的時間就越長，所以要注意狀態(tài)和事件在各自的 switch 語句中的安排順序，不推薦程序清單 List4 那樣按順序號排布的方式。出現頻率高或者實時性要求高的狀態(tài)和事件的位置應該盡量靠前。
表格驅動法如果說 switch—case 法是線性的，那么表格驅動法則是平面的。表格驅動法的實質就是將狀態(tài)和事件之間的關系固化到一張二維表格里， 把事件當做縱軸，把狀態(tài)當做橫軸，交點[Sn , Em]則是系統在 Sn 狀態(tài)下對事件 Em 的響應  。

如圖 4， 我把表格中的 Node_SnEm 叫做狀態(tài)機節(jié)點， 狀態(tài)機節(jié)點 Node_SnEm 是系統在 Sn狀態(tài)下對事件 Em 的響應。這里所說的響應包含兩個方面：輸出動作和狀態(tài)遷移。狀態(tài)機節(jié)點一般是一個類似程序清單 List5 中的結構體變量 。
struct fsm_node
{
    void (*fpAction)(void* pEvnt);
    INT8U u8NxtStat;
};
程序清單 List5 中的這個結構體有兩個成員：fpAction 和 u8NxtStat。fpAction 是一個函數指針， 指向一個形式為 void func(void * pEvnt)的函數， func 這個函數是對狀態(tài)轉移中動作序列的標準化封裝。
也就是說， 狀態(tài)機在狀態(tài)遷移的時候， 不管輸出多少個動作、操作多少個變量、調用多少個函數，這些行為統統放到函數 func 中去做。
把動作封裝好了之后，再把封裝函數 func 的地址交給函數指針 fpAction，這樣，想要輸出動作，只需要調用函數指針 fpAction 就行了。
再看看上面的 func 函數，會發(fā)現函數有一個形參 pEvnt，這是一個類型為 void * 的指針， 在程序實際運行時指向一個能存儲事件的變量，通過這個指針我們就能獲知關于事件的全部信息，這個形參是很有必要的。事件一般包括兩個屬性：事件的類型和事件的內容。
例如一次按鍵事件，我們不僅要知道這是一個按鍵事件，還要知道按下的到底是哪個鍵。事件的類型和狀態(tài)機當前的狀態(tài)可以讓我們在圖 4 的表格中迅速定位，確定該調用哪個動作封裝函數， 但是動作封裝函數要正確響應事件還需要知道事件的內容是什么， 這也就是形參pEvnt 的意義。
由于事件的多樣性，存儲事件內容的數據格式不一定一樣，所以就把 pEvnt 定義成了 void * 型，以增加靈活性。有關 fpAction 的最后一個問題：如果事件 Em 對狀態(tài) Sn 沒有意義，那么狀態(tài)機節(jié)點Node_SnEm 中的 fpAction 該怎么辦？我的答案是：那就讓它指向一個空函數唄！前面不是說過么，什么也不干也叫響應。
u8NxtStat 存儲的是狀態(tài)機的一個狀態(tài)值。我們知道， 狀態(tài)機響應事件要輸出動作， 也就是調用函數指針 fpAction 所指向的那個封裝函數， 函數調用完畢后程序返回主調函數， 狀態(tài)機對事件的響應就算結束了， 下一步就要考慮狀態(tài)遷移的問題了。
可能要保持本狀態(tài)不變， 也可能要遷移到一個新的狀態(tài)，該如何抉擇呢？u8NxtStat 存儲的狀態(tài)就是狀態(tài)機想要的答案！
圖 4 的這張表格反映在 C 語言代碼里就是一個二維數組，第 1 維就是狀態(tài)機的狀態(tài)，第 2維就是統一分類的事件，而數組的元素則是程序清單 List5 中的結構體常量。如果程序中使用表格驅動法，還需要注意一些特別的事項。要將狀態(tài)當做表格的橫軸，那么就要求狀態(tài)值集合必須滿足以下條件：
(1) 該集合是一個遞增的等差整數數列
(2) 該數列初值為 0
(3) 該數列等差值為 1
“事件” 作為縱軸，其特點和要求與用來做橫軸的“狀態(tài)” 完全一致。在 C 語言提供的數據類型中， 沒有比枚舉更符合以上要求的可選項了， 極力推薦將狀態(tài)集合和事件類型集合做成枚舉常量。表格驅動法的優(yōu)點：調用接口統一 ，定位快速。
表格驅動法屏蔽了不同狀態(tài)下處理各個事件的差異性，因此可以將處理過程中的共性部分提煉出來，做成標準統一的框架式代碼，形成統一的調用接口。根據程序清單 List5 中的狀態(tài)機節(jié)點結構體，做成的框架代碼如程序清單 List6 所示。
表格驅動法查找目標實際上就是一次二維數組的尋址操作，所以它的平均效率要遠高于switch—case 法。
「程序清單 List6  ：」
extern struct fsm_node g_arFsmDrvTbl[][]; /*狀態(tài)機驅動表格*/
INT8U u8CurStat = 0; /*狀態(tài)暫存*/
INT8U u8EvntTyp = 0; /*事件類型暫存*/
void* pEvnt = NULL; /*事件變量地址暫存*/
struct fsm_node stNodeTmp = {NULL, 0}; /*狀態(tài)機節(jié)點暫存*/
u8CurStat = get_cur_state(); /*讀取當前狀態(tài)*/
u8EvntTyp = get_cur_evnt_typ(); /*讀取當前觸發(fā)事件類型*/
pEvnt = (void*)get_cur_evnt_ptr(); /*讀取事件變量地址*/
stNodeTmp = g_arFsmDrvTbl[u8CurStat ][u8EvntTyp ];/*定位狀態(tài)機節(jié)點*/
stNodeTmp.fpAction(pEvnt ); /*動作響應*/
set_cur_state(stNodeTmp.u8NxtStat); /*狀態(tài)遷移*/
.....
表格驅動法好則好矣，但用它寫出來的程序還有點兒小問題，我們先來看看按照表格驅動法寫出來的程序有什么特點 。
前面說過，表格驅動法可以把狀態(tài)機調度的部分做成標準統一的框架代碼，這個框架適用性極強， 不管用狀態(tài)機來實現什么樣的應用， 框架代碼都不需要做改動， 我們只需要根據實際應用場合規(guī)劃好狀態(tài)轉換圖，然后將圖中的各個要素(狀態(tài)、事件、動作、遷移，有關“條件”要素一會兒再說)用代碼實現就行了，我把這部分代碼稱作應用代碼。
在應用代碼的.c 文件中， 你會看到一個聲明為 const 的二維數組， 也就是圖 4 所示的狀態(tài)驅動表格， 還會看到許多彼此之間毫無關聯的函數， 也就是前面提到的動作封裝函數。這樣的一份代碼， 如果手頭上沒有一張狀態(tài)轉換圖， 讓誰看了也會一頭霧水， 這樣的格式直接帶來了代碼可讀性差的問題。
如果我們想給狀態(tài)機再添加一個狀態(tài)，反映到代碼上就是給驅動表格再加一列內容，同時也要新添加若干個動作封裝函數。如果驅動表格很大， 做這些工作是很費事兒的， 而且容易出錯。如果不小心在數組中填錯了位置， 那么程序跑起來就和設計者的意圖南轅北轍了，
遠沒有在 switch—case 法中改動來得方便、安全。上面說的只是小瑕疵， 其實最讓我不爽的是表格驅動法不能使用干貨 | 嵌入式之狀態(tài)機編程 中 g_stFSM那樣的 Extended State Machine(對這個詞組還有印象吧？)！Extended State Machine 的最大特點就是狀態(tài)機響應事件之前先判斷條件，根據判定結果選擇執(zhí)行哪些動作，轉向哪個狀態(tài)。
也就是說，系統在狀態(tài) Sn 下發(fā)生了事件 Em 后，轉向的狀態(tài)不一定是唯一的，這種靈活性是 Extended State Machine 的最有價值的優(yōu)點。
回過頭來看看程序清單 List5 中給出的狀態(tài)機節(jié)點結構體，如果系統在狀態(tài) Sn 下發(fā)生了事件 Em， 狀態(tài)機執(zhí)行完 fpAction 所給出的動作響應之后， 必須轉到 u8NxtStat 指定的狀態(tài)。
表格驅動法的這個特性直接杜絕了 Extended State Machine 在表格驅動法中應用的可能性， 所以表格驅動法的代碼實現中不存在“條件” 這個狀態(tài)機要素。ESM，你是如此的優(yōu)秀，我怎么舍得拋棄你 ？！
再看圖 4 所示的表格驅動法示例圖，如果我們把表格中的代表事件的縱軸去掉，只留下代表狀態(tài)的橫軸，將一列合并成一格，前文提到的問題是不是能得到解決呢？不錯！這就是失傳江湖多年的《葵花寶典》 ——閹割版表格驅動法 ！！
閹割版表格驅動法，又名壓縮表格驅動法，一維狀態(tài)表格與事件 switch—case 的合體。壓縮表格驅動法使用了一維數組作為驅動表格，數組的下標即是狀態(tài)機的各個狀態(tài)。
表格中的元素叫做壓縮狀態(tài)機節(jié)點， 節(jié)點的主要內容還是一個指向動作封裝函數的函數指針， 只不過這個動作封裝函數不是為某個特定事件準備的， 而是對所有的事件都有效的。
節(jié)點中不再強制指定狀態(tài)機輸出動作完畢后所轉向的狀態(tài)， 而是讓動作封裝函數返回一個狀態(tài)， 并把這個狀態(tài)作為狀態(tài)機新的狀態(tài)。
壓縮表格驅動法的這個特點， 完美的解決了 Extended State Machine 不能在表格驅動法中使用的問題 。
程序清單 List7 中的示例代碼包含了壓縮狀態(tài)機節(jié)點結構體和狀態(tài)機調用的框架代碼。
「程序清單 List7：」
struct fsm_node /*壓縮狀態(tài)機節(jié)點結構體*/
{
INT8U (*fpAction)(void* pEvnt); /*事件處理函數指針*/
INT8U u8StatChk; /*狀態(tài)校驗*/
};
......
u8CurStat = get_cur_state(); /*讀取當前狀態(tài)*/
......
if(stNodeTmp.u8StatChk == u8CurStat )
{
u8CurStat = stNodeTmp.fpAction(pEvnt ); /*事件處理*/
set_cur_state(u8CurStat ); /*狀態(tài)遷移*/
}
else
{
state_crash(u8CurStat ); /*非法狀態(tài)處理*/
}
.....
對照程序清單 List5，就會發(fā)現程序清單 List7 中 struct fsm_node 結構體的改動之處。首先， fpAction 所指向函數的函數形式變了，動作封裝函數 func 的模樣成了這樣的了：
INT8U func(void * pEvnt);
現在的動作封裝函數 func 是要返回類型為 INT8U 的返回值的，這個返回值就是狀態(tài)機要轉向的狀態(tài)， 也就是說， 壓縮表格驅動法中的狀態(tài)機節(jié)點不負責狀態(tài)機新狀態(tài)的確定， 而把這項任務交給了動作封裝函數 func， func 返回哪個狀態(tài)， 狀態(tài)機就轉向哪個狀態(tài)。
新狀態(tài)由原來的常量變成了現在的變量，自然要靈活許多。上面說到現在的動作封裝函數 func 要對當前發(fā)生的所有的事件都要負責， 那么 func 怎么會知道到底是哪個事件觸發(fā)了它呢？看一下 func 的形參 void * pEvnt 。
在程序清單 List5 中我們提到過，這個形參是用來向動作封裝函數傳遞事件內容的，但是從前文的敘述中我們知道， pEvnt 所指向的內存包含了事件的所有信息， 包括事件類型和事件內容 ， 所以通過形參 pEvnt ， 動作封裝函數 func 照樣可以知道事件的類型。
程序清單 List7 中 struct fsm_node 結構體還有一個成員 u8StatChk ， 這里面存儲的是狀態(tài)機 的一個狀態(tài)，干什么用的呢？玩 C 語言數組的人都知道，要嚴防數組尋址越界。
要知道，壓縮表格驅動法的驅動表格是一個以狀態(tài)值為下標的一維數組， 數組元素里面最重要的部分就是一個個動作封裝函數的地址。
函數地址在單片機看來無非就是一段二進制數據， 和內存中其它的二進制數據沒什么兩樣，不管程序往單片機 PC 寄存器里塞什么值，單片機都沒意見。假設程序由于某種意外而改動了存儲狀態(tài)機當前狀態(tài)的變量，使變量值變成了一個非法狀態(tài)。
再發(fā)生事件時， 程序就會用這個非法的狀態(tài)值在驅動表格中尋址， 這時候就會發(fā)生內存泄露，程序拿泄露內存中的未知數據當函數地址跳轉，不跑飛才怪！
為了防止這種現象的發(fā)生， 壓縮狀態(tài)機節(jié)點結構體中又添加了成員 u8StatChk 。u8StatChk中存儲的是壓縮狀態(tài)機節(jié)點在一維驅動表格的位置， 例如某節(jié)點是表格中的第 7 個元素， 那么這個節(jié)點的成員 u8StatChk 值就是 6。
看一下程序清單 List7 中的框架代碼示例， 程序在引用函數指針 fpAction 之前， 先檢查當前狀態(tài)和當前節(jié)點成員 u8CurStat 的值是否一致，一致則認為狀態(tài)合法，事件正常響應，如果不一致，則認為當前狀態(tài)非法，轉至意外處理，最大限度保證程序運行的安全。當然，如果泄露內存中的數據恰好和 u8CurStat 一致，那么這種方法真的就回天乏力了。
還有一個方法也可以防止狀態(tài)機跑飛，如果狀態(tài)變量是枚舉，那么框架代碼就可以獲知狀態(tài)值的最大值， 在調用動作封裝函數之前判斷一下當前狀態(tài)值是否在合法的范圍之內， 同樣能保證狀態(tài)機的安全運行。
壓縮表格驅動法中動作封裝函數的定義形式我們已經知道了，函數里面到底是什么樣子的呢？程序清單 List8 是一個標準的示例。
「程序清單List8：」
INT8U action_S0(void* pEvnt)
{
INT8U u8NxtStat = 0;
INT8U u8EvntTyp = get_evnt_typ(pEvnt);
switch(u8EvntTyp )
{
  case E1:
   action_S0_E1(); /*事件 E1 的動作響應*/
   u8NxtStat = new state value; /*狀態(tài)遷移，不遷移也必須有本行*/
   break;
   ......
  case Em:
   action_S0_Em(); /*事件 Em 的動作響應*/
   u8NxtStat = new state value; /*狀態(tài)遷移，不遷移也必須有本行*/
   break;
  default:
   ; /*不相關事件處理*/
   break;
}
return u8NxtStat ; /*返回新狀態(tài)*/
}
從程序清單 List8 可以看出， 動作封裝函數其實就是事件 switch—case 的具體實現。函數根據形參 pEvnt 獲知事件類型， 并根據事件類型選擇動作響應， 確定狀態(tài)機遷移狀態(tài)， 最后將新的狀態(tài)作為執(zhí)行結果返回給框架代碼。
有了這樣的動作封裝函數， Extended State Machine 的應用就可以完全不受限制了！到此，有關壓縮表格驅動法的介紹就結束了。
個人認為壓縮表格驅動法是相當優(yōu)秀的，它既有表格驅動法的簡潔、高效、標準，又有 switch—case 法的直白、靈活、多變，相互取長補短，相得益彰。
函數指針法上面說過，用 C 語言實現狀態(tài)機主要有 3 種方法(switch—case 法、表格驅動法、函數指針法)， 其中函數指針法是最難理解的， 它的實質就是把動作封裝函數的函數地址作為狀態(tài)來看待。不過，有了之前壓縮表格驅動法的鋪墊，函數指針法就變得好理解了，因為兩者本質上是相同的。
壓縮表格驅動法的實質就是一個整數值(狀態(tài)機的一個狀態(tài))到一個函數地址(動作封裝函數)的一對一映射， 壓縮表格驅動法的驅動表格就是全部映射關系的直接載體。在驅動表格中通過狀態(tài)值就能找到函數地址，通過函數地址同樣能反向找到狀態(tài)值。
我們用一個全局的整型變量來記錄狀態(tài)值，然后再查驅動表格找函數地址，那干脆直接用一個全局的函數指針來記錄狀態(tài)得了，還費那勞什子勁干嗎？！這就是函數指針法的前世今生。
用函數指針法寫出來的動作封裝函數和程序清單 List8 的示例函數是很相近的， 只不過函數的返回值不再是整型的狀態(tài)值， 而是下一個動作封裝函數的函數地址， 函數返回后， 框架代碼再把這個函數地址存儲到全局函數指針變量中。
相比壓縮表格驅動法，在函數指針法中狀態(tài)機的安全運行是個大問題，我們很難找出一種機制來檢查全局函數指針變量中的函數地址是不是合法值。如果放任不管， 一旦函數指針變量中的數據被篡改，程序跑飛幾乎就不可避免了。
小節(jié)有關狀態(tài)機的東西說了那么多，相信大家都已經感受到了這種工具的優(yōu)越性，狀態(tài)機真的是太好用了！其實我們至始至終講的都是有限狀態(tài)機(Finite State Machine 現在知道為什么前面的代碼中老是有 fsm 這個縮寫了吧！)， 還有一種比有限狀態(tài)機更 NB 更復雜的狀態(tài)機， 那就是層次狀態(tài)機(Hierarchical State Machine 一般簡寫為 HSM)。
通俗的說，系統中只存在一個狀態(tài)機的叫做有限狀態(tài)機，同時存在多個狀態(tài)機的叫做層次狀態(tài)機(其實這樣解釋層次狀態(tài)機有些不嚴謹， 并行狀態(tài)機也有多個狀態(tài)機， 但層次狀態(tài)機各個狀態(tài)機之間是上下級關系，而并行狀態(tài)機各個狀態(tài)機之間是平級關系)。
層次狀態(tài)機是一種父狀態(tài)機包含子狀態(tài)機的多狀態(tài)機結構，里面包含了許多與面向對象相似的思想， 所以它的功能也要比有限狀態(tài)機更加強大， 當一個問題用有限狀態(tài)機解決起來有些吃力的時候， 就需要層次狀態(tài)機出馬了。
層次狀態(tài)機理論我理解得也不透徹， 就不在這里班門弄斧了，大家可以找一些有關狀態(tài)機理論的專業(yè)書籍來讀一讀。要掌握狀態(tài)機編程，理解狀態(tài)機(主要指有限狀態(tài)機)只是第一步，也是最簡單的一步，更重要的技能是能用狀態(tài)機這個工具去分析解剖實際問題：劃分狀態(tài)、 提取事件、 確定轉換關系、規(guī)定動作等等，形成一張完整的狀態(tài)轉換圖，最后還要對轉換圖進行優(yōu)化，達到最佳。
把實際問題變成了狀態(tài)轉換圖， 工作的一大半就算完成了， 這個是具有架構師氣質的任務，剩下的問題就是按照狀態(tài)圖編程寫代碼了，這個是具有代碼工特色的工作。
本文來源網絡，版權歸原作者所有。如涉及作品版權問題，請聯系我進行刪除。
猜你喜歡：
WiFi6+藍牙+星閃，三合一開發(fā)板，真香！
Github上熱門 C 語言項目匯總！
嵌入式，可測試性軟件設計！
一些低功耗軟件設計的要點！
嵌入式 C 保護結構體的方式
實用 | 10分鐘教你通過網頁點燈
談談嵌入式軟件的兼容性！
分享一個嵌入式代碼生成器設計思路！
點擊閱讀原文，查看更多分享。