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