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

3．3 模型評價
(1)擴展性
為層次型有限狀態機模型增加新功能，只需在其根節點下增加一個子節點，因為新的子節點與其他兄弟節點是互斥的，所以模型可以很方便地進行系統功能擴展。
(2)查找算法時間復雜度
假設系統中存在的狀態數量為n。如果不采用層次型有限狀態機模型，那么系統中的各個狀態都是相互獨立、互斥的，相當于所有的狀態都是一個虛擬根節點的子節點。這樣的話，查找下一狀態的時間復雜度為：

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

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

顯然，T(n)2T(n)1。因此，該模型對于查找下一狀態在時間復雜度上也是有優勢的。

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