基于層次型有限狀態(tài)機(jī)模型實(shí)現(xiàn)自動(dòng)售貨機(jī)的控制系統(tǒng)設(shè)計(jì)

引言

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

1 有限狀態(tài)機(jī)

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

有限狀態(tài)機(jī)一般有2種表示方式：狀態(tài)轉(zhuǎn)移表和狀態(tài)轉(zhuǎn)移圖。通常用有向圖來(lái)表示有限狀態(tài)機(jī)，其節(jié)點(diǎn)代表狀態(tài)。如圖1所示，若在狀態(tài)SO接收到某個(gè)輸入事件 e1后轉(zhuǎn)向S1狀態(tài)，就在圖中畫一條從SO到Sl的帶箭頭的弧線，并在弧線上標(biāo)記e1。

2 基本思想

2．1 必要性分析

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

2．2 實(shí)現(xiàn)方式

根據(jù)系統(tǒng)中各個(gè)狀態(tài)之間是否存在包含關(guān)系，有限狀態(tài)機(jī)可以分為常規(guī)狀態(tài)機(jī)與層次型狀態(tài)機(jī)（hierarchicalstate machine）。對(duì)于前者，系統(tǒng)中各個(gè)狀態(tài)是獨(dú)立的、互斥的，適合應(yīng)用于那些存在狀態(tài)數(shù)量不多的簡(jiǎn)單系統(tǒng)；而對(duì)于后者，系統(tǒng)中的狀態(tài)除了互斥關(guān)系以外，還存在真包含的關(guān)系。

分析自動(dòng)售貨機(jī)這樣一個(gè)狀態(tài)機(jī)，圖2為自動(dòng)售貨機(jī)的狀態(tài)圖（不完整）。

從圖中可以看出，自動(dòng)售貨機(jī)控制器存在的狀態(tài)數(shù)量是比較多的，但是無(wú)論何時(shí)，自動(dòng)售貨機(jī)總處于空閑、售貨、商品價(jià)格設(shè)置、時(shí)間設(shè)置、測(cè)試等諸多狀態(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ī)模型，并且用來(lái)實(shí)現(xiàn)自動(dòng)售貨機(jī)控制器。模型使用樹結(jié)構(gòu)來(lái)描述狀態(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)過(guò)處理形成圖3所示的狀態(tài)樹，它是整個(gè)自動(dòng)售貨機(jī)狀態(tài)樹的一部分。

3．2 狀態(tài)轉(zhuǎn)換算法

在有限狀態(tài)機(jī)中，是通過(guò)事件的驅(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)換過(guò)程是：系統(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)下（比如通過(guò)按鍵顯示系統(tǒng)的當(dāng)前日期），系統(tǒng)將要從空閑狀態(tài)轉(zhuǎn)換到日期顯示狀態(tài)S4。從圖3的自動(dòng)售貨機(jī)狀態(tài)樹可以看出，系統(tǒng)需要經(jīng)過(guò)S1一S2一S3 一S4的過(guò)程，中間的S2和S3是不可停留的狀態(tài)。當(dāng)按下管理鍵盤的“Time”鍵時(shí)，系統(tǒng)先執(zhí)行exit_idle函數(shù)退出S1（空閑狀態(tài)），然后根據(jù)空閑狀態(tài)的事件表得到下一狀態(tài)編號(hào)，再通過(guò)狀態(tài)查找算法搜索狀態(tài)樹，最后到達(dá)目的狀態(tài)S4。S2與S3是兩個(gè)中間狀態(tài)，但是這兩個(gè)狀態(tài)節(jié)點(diǎn)的地址需要入棧。

3．3 模型評(píng)價(jià)

（1）擴(kuò)展性

為層次型有限狀態(tài)機(jī)模型增加新功能，只需在其根節(jié)點(diǎn)下增加一個(gè)子節(jié)點(diǎn)，因?yàn)樾碌淖庸?jié)點(diǎn)與其他兄弟節(jié)點(diǎn)是互斥的，所以模型可以很方便地進(jìn)行系統(tǒng)功能擴(kuò)展。

（2）查找算法時(shí)間復(fù)雜度

假設(shè)系統(tǒng)中存在的狀態(tài)數(shù)量為n。如果不采用層次型有限狀態(tài)機(jī)模型，那么系統(tǒng)中的各個(gè)狀態(tài)都是相互獨(dú)立、互斥的，相當(dāng)于所有的狀態(tài)都是一個(gè)虛擬根節(jié)點(diǎn)的子節(jié)點(diǎn)。這樣的話，查找下一狀態(tài)的時(shí)間復(fù)雜度為：

然而，上面的情況忽略了狀態(tài)之間的相關(guān)性，很有可能當(dāng)前狀態(tài)與下一狀態(tài)是兄弟關(guān)系，此時(shí)的比較次數(shù)就會(huì)明顯減少。如果采用層次型狀態(tài)機(jī)，假設(shè)系統(tǒng)子功能數(shù)目為m（m》1），那么平均每個(gè)子功能的狀態(tài)數(shù)目為n／m，當(dāng)前狀態(tài)與下一狀態(tài)為兄弟節(jié)點(diǎn)的概率為p（0

其中，t1為當(dāng)前狀態(tài)與下一狀態(tài)不是兄弟節(jié)點(diǎn)的查找時(shí)間，與狀態(tài)樹的平均深度^有關(guān)。但是由于存在局部相關(guān)性，并且這種相關(guān)性越大（即p值越大），平均時(shí)間復(fù)雜度就越集中在前面部分（p·n）／（m·2），后面的表達(dá)式值可以忽略不計(jì)，即：

顯然，T（n）2

結(jié)語(yǔ)

通過(guò)建立層次型有限狀態(tài)機(jī)模型，并應(yīng)用改進(jìn)的數(shù)據(jù)結(jié)構(gòu)與狀態(tài)轉(zhuǎn)換算法，自動(dòng)售貨機(jī)控制器的程序結(jié)構(gòu)更為清晰。原來(lái)存在于程序中的諸多標(biāo)志變量，由狀態(tài)機(jī)的各個(gè)狀態(tài)所取代，使系統(tǒng)具有更好的擴(kuò)展性；并且模型很好地利用了狀態(tài)的相關(guān)性，縮短了查找所花費(fèi)的時(shí)間。但是，該模型也存在一定的局限性。比如，很大數(shù)量在構(gòu)造狀態(tài)樹時(shí)需要的存儲(chǔ)空間給一般嵌入式系統(tǒng)的成本帶來(lái)了挑戰(zhàn)，不過(guò)可以試圖通過(guò)讓所有的狀態(tài)共享內(nèi)存空間的方法來(lái)解決這個(gè)問題。因此，層次型有限狀態(tài)機(jī)模型應(yīng)用于較為復(fù)雜的嵌入式系統(tǒng)具有更普遍的意義。

責(zé)任編輯：gt