911
狀態機的兩種寫法
有限狀態機FSM思想廣泛應用於硬件控製電路設計，也是軟件上常用的一種處理方法(軟件上稱為FMM--有限消息機)。它把複雜的控製邏輯分解成有限個穩定狀態，在每個狀態上判斷事件，變連續處理為離散數字處理，符合計算機的工作特點。同時，因為有限狀態機具有有限個狀態，所以可以在實際的工程上實現。但這並不意味著其隻能進行有限次的處理，相反，有限狀態機是閉環係統，有限無窮，可以用有限的狀態，處理無窮的事務。有限狀態機的工作原理如圖1所示，發生事件(event)後，根據當前狀態(cur_state)，決定執行的動作(action)，並設置下一個狀態號(nxt_state)。
-------------
| |-------->執行動作action
發生事件event ----->| cur_state |
| |-------->設置下一狀態號nxt_state
-------------
當前狀態
圖1 有限狀態機工作原理
e0/a0
--->--
| |
-------->----------
e0/a0 | | S0 |-----
| -<------------ | e1/a1
| | e2/a2 V
---------- ----------
| S2 |-----<-----| S1 |
---------- e2/a2 ----------
圖2 一個有限狀態機實例
--------------------------------------------
當前狀態 s0 s1 s2 | 事件
--------------------------------------------
a0/s0 -- a0/s0 | e0
--------------------------------------------
a1/s1 -- -- | e1
--------------------------------------------
a2/s2 a2/s2 -- | e2
--------------------------------------------
表1 圖2狀態機實例的二維表格表示(動作/下一狀態)
圖2為一個狀態機實例的狀態轉移圖，它的含義是：
在s0狀態，如果發生e0事件，那麼就執行a0動作，並保持狀態不變；
如果發生e1事件，那麼就執行a1動作，並將狀態轉移到s1態；
如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
在s1狀態，如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
在s2狀態，如果發生e0事件，那麼就執行a0動作，並將狀態轉移到s0態；
有限狀態機不僅能夠用狀態轉移圖表示，還可以用二維的表格代表。一般將當前狀態號寫在橫行上，將事件寫在縱列上，如表1所示。其中“--”表示空(不執行動作，也不進行狀態轉移)，“an/sn”表示執行動作an,同時將下一狀態設置為sn。表1和圖2表示的含義是完全相同的。
觀察表1可知，狀態機可以用兩種方法實現：豎著寫(在狀態中判斷事件)和橫著寫(在事件中判斷狀態)。這兩種實現在本質上是完全等效的，但在實際操作中，效果卻截然不同。
==================================
豎著寫(在狀態中判斷事件)C代碼片段
==================================
cur_state = nxt_state;
switch(cur_state){ //在當前狀態中判斷事件
case s0: //在s0狀態
if(e0_event){ //如果發生e0事件，那麼就執行a0動作，並保持狀態不變；
執行a0動作;
//nxt_state = s0; //因為狀態號是自身，所以可以刪除此句，以提高運行速度。
}
else if(e1_event){ //如果發生e1事件，那麼就執行a1動作，並將狀態轉移到s1態；
執行a1動作;
nxt_state = s1;
}
else if(e2_event){ //如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
執行a2動作;
nxt_state = s2;
}
break;
case s1: //在s1狀態
if(e2_event){ //如果發生e2事件，那麼就執行a2動作，並將狀態轉移到s2態；
執行a2動作;
nxt_state = s2;
}
break;
case s2: //在s2狀態
if(e0_event){ //如果發生e0事件，那麼就執行a0動作，並將狀態轉移到s0態；
執行a0動作;
nxt_state = s0;
}
}
==================================
橫著寫(在事件中判斷狀態)C代碼片段
==================================
//e0事件發生時，執行的函數
void e0_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //觀察表1，在e0事件發生時，s1處為空
case s2:
執行a0動作;
*nxt_state = s0;
}
}
//e1事件發生時，執行的函數
void e1_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //觀察表1，在e1事件發生時，s1和s2處為空
執行a1動作;
*nxt_state = s1;
}
}
//e2事件發生時，執行的函數
void e2_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0: //觀察表1，在e2事件發生時，s2處為空
case s1:
執行a2動作;
*nxt_state = s2;
}
}
上麵橫豎兩種寫法的代碼片段，實現的功能完全相同，但是，橫著寫的效果明顯好於豎著寫的效果。理由如下：
1、豎著寫隱含了優先級排序(其實各個事件是同優先級的)，排在前麵的事件判斷將毫無疑問地優先於排在後麵的事件判斷。這種if/else if寫法上的限製將破壞事件間原有的關係。而橫著寫不存在此問題。
2、由於處在每個狀態時的事件數目不一致，而且事件發生的時間是隨機的，無法預先確定，導致豎著寫淪落為順序查詢方式，結構上的缺陷使得大量時間被浪費。對於橫著寫，在某個時間點，狀態是唯一確定的，在事件裏查找狀態隻要使用switch語句，就能一步定位到相應的狀態，延遲時間可以預先準確估算。而且在事件發生時，調用事件函數，在函數裏查找唯一確定的狀態，並根據其執行動作和狀態轉移的思路清晰簡潔，效率高，富有美感。
總之，我個人認為，在軟件裏寫狀態機，使用橫著寫的方法比較妥帖。
豎著寫的方法也不是完全不能使用，在一些小項目裏，邏輯不太複雜，功能精簡，同時為了節約內存耗費，豎著寫的方法也不失為一種合適的選擇。
在FPGA類硬件設計中，以狀態為中心實現控製電路狀態機(豎著寫)似乎是唯一的選擇，因為硬件不太可能靠事件驅動(橫著寫)。不過，在FPGA裏有一個全局時鍾，在每次上升沿時進行狀態切換，使得豎著寫的效率並不低。雖然在硬件裏豎著寫也要使用IF/ELSIF這類查詢語句(用VHDL開發)，但他們映射到硬件上是組合邏輯，查詢隻會引起門級延遲(ns量級)，而且硬件是真正並行工作的，這樣豎著寫在硬件裏就沒有負麵影響。因此，在硬件設計裏，使用豎著寫的方式成為必然的選擇。這也是為什麼很多搞硬件的工程師在設計軟件狀態機時下意識地隻使用豎著寫方式的原因，蓋思維定勢使然也。
TCP和PPP框架協議裏都使用了有限狀態機，這類軟件狀態機最好使用橫著寫的方式實現。以某TCP協議為例，見圖3，有三種類型的事件：上層下達的命令事件；下層到達的標誌和數據的收包事件；超時定時器超時事件。
上層命令(open,close)事件
-----------------------------------
--------------------
| TCP | <----------超時事件timeout
--------------------
-----------------------------------
RST/SYN/FIN/ACK/DATA等收包事件
圖3 三大類TCP狀態機事件
由圖3可知，此TCP協議棧采用橫著寫方式實現，有3種事件處理函數，上層命令處理函數(如tcp_close)；超時事件處理函數(tmr_slow)；下層收包事件處理函數(tcp_process)。值得一提的是，在收包事件函數裏，在各個狀態裏判斷RST/SYN/FIN/ACK/DATA等標誌(這些標誌類似於事件)，看起來象豎著寫方式，其實，如果把包頭和數據看成一個整體，那麼，RST/SYN/FIN/ACK/DATA等標誌就不必被看成獨立的事件，而是屬於同一個收包事件裏的細節，這樣，就不會認為在狀態裏查找事件，而是總體上看，是在收包事件裏查找狀態(橫著寫)。
在PPP裏更是到處都能見到橫著寫的現象，有時間的話再細說。我個人感覺在實現PPP框架協議前必須了解橫豎兩種寫法，而且隻有使用橫著寫的方式才能比較完美地實現PPP。
最後更新：2017-04-02 00:06:25