狀態機編程

轉載正文1有限狀態機FSM思想廣泛應用于硬件控制電路設計，也是軟件上常用的一種處理方法(軟件上稱為FMM--有限消息機)。它把復雜的控制邏輯分解成有限個穩定狀態，在每個狀態上判斷事件，變連續處理為離散數字處理，符合計算機的工作特點。同時，因為有限狀態機具有有限個狀態，所以可以在實際的工程上實現。但這并不意味著其只能進行有限次的處理，相反，有限狀態機是閉環系統，有限無窮，可以用有限的狀態，處理無窮的事務。有限狀態機的工作原理如圖1所示，發生事件(event)后，根據當前狀態(cur_state)，決定執行的動作(action)，并設置下一個狀態號(nxt_state)。-------------||-------->執行動作action發生事件event ----->| cur_state |||-------->設置下一狀態號nxt_state-------------當前狀態圖1 有限狀態機工作原理e0/a0--->--||-------->----------e0/a0 ||S0|-----|-<------------| e1/a1|| e2/a2V--------------------|S2|-----<-----|S1|----------e2/a2----------圖2 一個有限狀態機實例--------------------------------------------當前狀態s0s1s2| 事件--------------------------------------------a0/s0--a0/s0|e0--------------------------------------------a1/s1----|e1--------------------------------------------a2/s2a2/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。

				
            

				
					
					
				
			
                
			
							

                
			            

                            	              		              		上一頁
              		1
              		              			              		              	              				              				2
              					              						              						              				下一頁