引言

售貨機上除基本自動售貨功能外，增加了諸多功能，如GPRS短信模塊以加強安全監控，在售貨機上播放視頻廣告以提高運營商的經濟效益等。這就使得存在于售貨機內部的控制器（Vencling Machine Controller，VMC）的復雜程度也迅速增加，先前的一套用于小規模嵌入式系統的分析設計方法、應用程序結構、運行效率與易維護程度在當前的售貨機需求面前顯得有些力不從心了。有限狀態機理論在計算機應用領域有著廣泛的應用，狀態機對處理一些復雜情況也大有裨益。在設計階段，開發人員可以利用狀態機模型來描述復雜的系統，從而大大縮短項目的開發周期，且系統易于維護。魏先民提出了有限狀態機在嵌入式領域應用的一個基本框架，但是在這個框架中，系統中的所有狀態都是互斥的關系，盡管有些狀態之間存在著緊密的關系。V．Ayvazyan等論述了狀態之間不僅存在互斥關系，還存在包含關系（父狀態與子狀態）。本文應用有限狀態機的這些特性，提出一個層次型有限狀態機（Hierarchical FSM，HFSM）模型，對售貨機控制器（VMC）進行改進。

1 有限狀態機

有限狀態機是一種具有離散輸入輸出系統的模型，在任何時刻都處于一個特定的狀態。對于事件驅動的程序設計，它是非常有用的設計模型。在某一個狀態下有事件發生時，根據當前狀態和輸入事件的不同，選擇如何處理該事件以及是否需要轉換到下一個狀態。一個有限狀態機（FSM）是一個五元組，M=（K，E，T，S，Z）。其中，K是一個有限的狀態集合，它的每個元素稱為“狀態”；E表示該系統能接收的所有事件的集合，它的每個元素稱為一個“事件”；T是狀態轉換函數，是K×E→K上的映射；S 是系統的一個特殊狀態，一般是系統啟動時的初始狀態；Z是K的一個子集，是一個終態集。

有限狀態機一般有2種表示方式：狀態轉移表和狀態轉移圖。通常用有向圖來表示有限狀態機，其節點代表狀態。如圖1所示，若在狀態SO接收到某個輸入事件 e1后轉向S1狀態，就在圖中畫一條從SO到Sl的帶箭頭的弧線，并在弧線上標記e1。

2 基本思想

2．1 必要性分析

有限狀態機是通過事件來觸發狀態的轉變的，其事件來源主要有2個：其一是外部觸發事件，如響應用戶鍵盤的輸入；其二是內部觸發事件，如系統所發出來的各種命令。有限狀態機這種事件驅動的特性具有良好的開放性，可以根據用戶的要求方便地增加相應的狀態與事件，完成系統功能的擴展。本文所研究的自動售貨機配有1個5×5的管理鍵盤和1個3×7用戶鍵盤，二者復用了部分的鍵盤掃描線；另外有37個外部事件源，加上幾條內部命令，可能觸發的事件達45 個。如此多的事件，當某個事件發生時，如果采用if…else或switch…case語句進行一一判斷，將非常復雜。而采用有限狀態機，每個狀態維護一張事件表，無需比較，大大提高了響應速度；并且就擴展需求較為頻繁的自動售貨機而言，有限狀態機也是便于維護的。

2．2 實現方式

根據系統中各個狀態之間是否存在包含關系，有限狀態機可以分為常規狀態機與層次型狀態機（hierarchicalstate machine）。對于前者，系統中各個狀態是獨立的、互斥的，適合應用于那些存在狀態數量不多的簡單系統；而對于后者，系統中的狀態除了互斥關系以外，還存在真包含的關系。

分析自動售貨機這樣一個狀態機，圖2為自動售貨機的狀態圖（不完整）。

從圖中可以看出，自動售貨機控制器存在的狀態數量是比較多的，但是無論何時，自動售貨機總處于空閑、售貨、商品價格設置、時間設置、測試等諸多狀態之中的一個．這些狀態之間是互斥的。同時，上面列舉的所有狀態都包含子狀態，例如：狀態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是兩個中間狀態，但是這兩個狀態節點的地址需要入棧。

3．3 模型評價

（1）擴展性

為層次型有限狀態機模型增加新功能，只需在其根節點下增加一個子節點，因為新的子節點與其他兄弟節點是互斥的，所以模型可以很方便地進行系統功能擴展。

（2）查找算法時間復雜度

假設系統中存在的狀態數量為n。如果不采用層次型有限狀態機模型，那么系統中的各個狀態都是相互獨立、互斥的，相當于所有的狀態都是一個虛擬根節點的子節點。這樣的話，查找下一狀態的時間復雜度為：

然而，上面的情況忽略了狀態之間的相關性，很有可能當前狀態與下一狀態是兄弟關系，此時的比較次數就會明顯減少。如果采用層次型狀態機，假設系統子功能數目為m（m》1），那么平均每個子功能的狀態數目為n／m，當前狀態與下一狀態為兄弟節點的概率為p（0

其中，t1為當前狀態與下一狀態不是兄弟節點的查找時間，與狀態樹的平均深度^有關。但是由于存在局部相關性，并且這種相關性越大（即p值越大），平均時間復雜度就越集中在前面部分（p·n）／（m·2），后面的表達式值可以忽略不計，即：

顯然，T（n）2

結語

通過建立層次型有限狀態機模型，并應用改進的數據結構與狀態轉換算法，自動售貨機控制器的程序結構更為清晰。原來存在于程序中的諸多標志變量，由狀態機的各個狀態所取代，使系統具有更好的擴展性；并且模型很好地利用了狀態的相關性，縮短了查找所花費的時間。但是，該模型也存在一定的局限性。比如，很大數量在構造狀態樹時需要的存儲空間給一般嵌入式系統的成本帶來了挑戰，不過可以試圖通過讓所有的狀態共享內存空間的方法來解決這個問題。因此，層次型有限狀態機模型應用于較為復雜的嵌入式系統具有更普遍的意義。

責任編輯：gt