狀态機的兩種寫法

有限狀态機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動作，

        case s2:                        //在s2狀态

并将狀态轉移到s0态；

                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)

        case s0:                        //觀察表1，在e1事件發生時，s1和s2處為

空

            執行a1動作;

            *nxt_state = s1;

//e2事件發生時，執行的函數

void e2_event_function(int * nxt_state)

        case s0:                        //觀察表1，在e2事件發生時，s2處為空

        case s1:

            執行a2動作;

            *nxt_state = s2;

    上面橫豎兩種寫法的代碼片段，實作的功能完全相同，但是，橫着寫的效果明顯好

于豎着寫的效果。理由如下：

    1、豎着寫隐含了優先級排序(其實各個事件是同優先級的)，排在前面的事件判斷将

毫無疑問地優先于排在後面的事件判斷。這種if/else if寫法上的限制将破壞事件間原

有的關系。而橫着寫不存在此問題。

    2、由于處在每個狀态時的事件數目不一緻，而且事件發生的時間是随機的，無法預

先确定，導緻豎着寫淪落為順序查詢方式，結構上的缺陷使得大量時間被浪費。對于橫

着寫，在某個時間點，狀态是唯一确定的，在事件裡查找狀态隻要使用switch語句，就

能一步定位到相應的狀态，延遲時間可以預先準确估算。而且在事件發生時，調用事件

函數，在函數裡查找唯一确定的狀态，并根據其執行動作和狀态轉移的思路清晰簡潔，

效率高，富有美感。

    總之，我個人認為，在軟體裡寫狀态機，使用橫着寫的方法比較妥帖。

    豎着寫的方法也不是完全不能使用，在一些小項目裡，邏輯不太複雜，功能精簡，

同時為了節約記憶體耗費，豎着寫的方法也不失為一種合适的選擇。

    在fpga類硬體設計中，以狀态為中心實作控制電路狀态機(豎着寫)似乎是唯一的選

擇，因為硬體不太可能靠事件驅動(橫着寫)。不過，在fpga裡有一個全局時鐘，在每次

上升沿時進行狀态切換，使得豎着寫的效率并不低。雖然在硬體裡豎着寫也要使用if/el

sif這類查詢語句(用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_proce

ss)。值得一提的是，在收包事件函數裡，在各個狀态裡判斷rst/syn/fin/ack/data等标

志(這些标志類似于事件)，看起來象豎着寫方式，其實，如果把標頭和資料看成一個整

體，那麼，rst/syn/fin/ack/data等标志就不必被看成獨立的事件，而是屬于同一個收

包事件裡的細節，這樣，就不會認為在狀态裡查找事件，而是總體上看，是在收包事件

裡查找狀态(橫着寫)。

    在ppp裡更是到處都能見到橫着寫的現象，有時間的話再細說。我個人感覺在實作pp

p架構協定前必須了解橫豎兩種寫法，而且隻有使用橫着寫的方式才能比較完美地實作pp

p。