基于有限狀態機的自動售貨機控制器

從圖中可以看出，自動售貨機控制器存在的狀態數量是比較多的，但是無論何時，自動售貨機總處于空閑、售貨、商品價格設置、時間設置、測試等諸多狀態之中的一個．這些狀態之間是互斥的。同時，上面列舉的所有狀態都包含子狀態，例如：狀態S2(時間設置狀態)包括日期設置、時分秒設置、星期設置等子狀態，而對于S3(日期設置狀態)又包括S4(日期顯示狀態)和S5(日期編輯狀態)兩個子狀態。因此，對于自動售貨機控制器這樣一個系統，其內部的狀態機是一種層次型狀態機。本文根據層次型狀態機的互斥與包含的雙重特性，提出層次型有限狀態機模型，并且用來實現自動售貨機控制器。模型使用樹結構來描述狀態集，包含其他狀態的狀態稱為“樹枝節點”，不包含其他狀態的狀態稱為“葉子節點”。為方便用單樹結構描述，總是設計一個狀態包含所有的狀態節點，稱為“根節點”，它是一個虛擬的節點，在系統中沒有狀態與其對應。狀態機只能停留在葉子節點，而不能停留在樹枝節點，每個樹枝節點需指定一個子節點為它的默認子節點，以便狀態機進入樹枝節點時能停留到葉子節點。

3 層次型有限狀態機模型
3．1 數據結構定義
HFSM模型采用樹結構實現有限狀態機，樹上的每一個節點都對應了自動售貨機狀態機的一個狀態。其中根節點是一個特殊的節點，它對應的是一個虛擬的并不存在的狀態，其目的是為了構造一棵單樹，而不是每一個功能對應一棵樹。節點的數據結構如下：

其中，id為狀態編號，每個狀態編號在整個系統狀態機中是唯一的；name為狀態名；enter_func為狀態進入操作；exit_func為狀態退出操作；event_table為事件表；sub_state_table為子狀態表。因為葉子節點沒有子狀態，而樹枝節點沒有狀態事件表，所以結構中的事件表與子狀態可以共享一段存儲空間。事件表中每個元素是另外一個結構FSM_STATE_EVENT，它有事件id(與事件源一一對應)、事件操作(func)和下一狀態編號(next_state_id)三個成員。圖2所示的狀態圖子集經過處理形成圖3所示的狀態樹，它是整個自動售貨機狀態樹的一部分。

3．2 狀態轉換算法
在有限狀態機中，是通過事件的驅動而進行狀態轉換的。狀態轉換算法的關鍵就在于查找下一狀態在狀態樹中的位置，也就是在狀態樹中查找下一狀態的時間復雜度的問題。與常規狀態機不同，層次型狀態機中的各個狀態不僅存在互斥關系，還存在包含關系，特別是當前狀態與下一狀態關系就更為緊密了，不僅存在局部相關性，而且在很多情況下，它們之間在狀態樹中表現為兄弟節點關系。因此，要在狀態樹查找下一狀態，需先查找當前節點的兄弟節點，再查找父節點的兄弟節點。如此循環，直到找到下一狀態或試圖查找根節點的兄弟節點(根節點沒有父節點，所以要查找的下一狀態是不存在的)。
狀態查找算法如下：

有限狀態機的一般狀態轉換過程是：系統首先執行exit_func退出當前狀態，然后執行驅動此次狀態轉換的事件操作func，最后執行enter_func進入新狀態。為了便于遍歷狀態樹，系統為層次型有限狀態機建立一個狀態堆棧，堆棧中記錄的數據是當前狀態在狀態樹中對應的節點路徑上所有節點(自身除外，因為沒有必要人棧)的地址。堆棧的初始狀態如圖4所示，此時系統處于空閑S1狀態，棧中只有根節點信息。在某個事件或一系列事件的驅動下(比如通過按鍵顯示系統的當前日期)，系統將要從空閑狀態轉換到日期顯示狀態S4。從圖3的自動售貨機狀態樹可以看出，系統需要經過S1一S2一S3一S4的過程，中間的S2和S3是不可停留的狀態。當按下管理鍵盤的“Time”鍵時，系統先執行exit_idle函數退出S1(空閑狀態)，然后根據空閑狀態的事件表得到下一狀態編號，再通過狀態查找算法搜索狀態樹，最后到達目的狀態S4。S2與S3是兩個中間狀態，但是這兩個狀態節點的地址需要入棧。