基于有限狀態(tài)機(jī)的自動(dòng)售貨機(jī)控制器

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

3 層次型有限狀態(tài)機(jī)模型
3．1 數(shù)據(jù)結(jié)構(gòu)定義
HFSM模型采用樹結(jié)構(gòu)實(shí)現(xiàn)有限狀態(tài)機(jī)，樹上的每一個(gè)節(jié)點(diǎn)都對(duì)應(yīng)了自動(dòng)售貨機(jī)狀態(tài)機(jī)的一個(gè)狀態(tài)。其中根節(jié)點(diǎn)是一個(gè)特殊的節(jié)點(diǎn)，它對(duì)應(yīng)的是一個(gè)虛擬的并不存在的狀態(tài)，其目的是為了構(gòu)造一棵單樹，而不是每一個(gè)功能對(duì)應(yīng)一棵樹。節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：

其中，id為狀態(tài)編號(hào)，每個(gè)狀態(tài)編號(hào)在整個(gè)系統(tǒng)狀態(tài)機(jī)中是唯一的；name為狀態(tài)名；enter_func為狀態(tài)進(jìn)入操作；exit_func為狀態(tài)退出操作；event_table為事件表；sub_state_table為子狀態(tài)表。因?yàn)槿~子節(jié)點(diǎn)沒有子狀態(tài)，而樹枝節(jié)點(diǎn)沒有狀態(tài)事件表，所以結(jié)構(gòu)中的事件表與子狀態(tài)可以共享一段存儲(chǔ)空間。事件表中每個(gè)元素是另外一個(gè)結(jié)構(gòu)FSM_STATE_EVENT，它有事件id(與事件源一一對(duì)應(yīng))、事件操作(func)和下一狀態(tài)編號(hào)(next_state_id)三個(gè)成員。圖2所示的狀態(tài)圖子集經(jīng)過處理形成圖3所示的狀態(tài)樹，它是整個(gè)自動(dòng)售貨機(jī)狀態(tài)樹的一部分。

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

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