有限狀態(tài)機(jī)示意圖（Finite State Machines）圖片來(lái)源：flaviocopes.com

作者 | Peter Galan

“

獲取有關(guān)使用C語(yǔ)言為嵌入式系統(tǒng)的有限狀態(tài)機(jī)進(jìn)行編程的幫助。

”

有限狀態(tài)機(jī)（FSM）的定義是：描述特定（邏輯）過(guò)程的一系列事件和動(dòng)作的數(shù)學(xué)模型。在工程實(shí)踐中，你可以找到無(wú)數(shù)類似的過(guò)程，從簡(jiǎn)單的通過(guò)幾個(gè)按鈕控制電機(jī)的FSM， 到可以監(jiān)控非常復(fù)雜的生產(chǎn)制造過(guò)程或航天飛機(jī)的復(fù)雜FSM 系統(tǒng)。

我曾經(jīng)為廣泛應(yīng)用于光通信領(lǐng)域的摻鉺光纖放大器（EDFA）設(shè)計(jì)過(guò)固件。一個(gè)固件部分必須處理E DFA 的安全問(wèn)題，如果設(shè)計(jì)不當(dāng)，EDFA 可能會(huì)使用對(duì)人體有害的強(qiáng)激光。這似乎是一個(gè)常規(guī)的FSM 代碼設(shè)計(jì)，但其結(jié)果卻是一個(gè)非常復(fù)雜的、難以遵循和維護(hù)的冗長(zhǎng)過(guò)程。需要一種不同的方法來(lái)實(shí)施FSM，這可能會(huì)引起嵌入式代碼設(shè)計(jì)者的興趣。

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

根據(jù)有限狀態(tài)機(jī)理論，你可能會(huì)想起兩種類型的FSM 表示，一種是Mealy 有限狀態(tài)機(jī)，另一種是Moore 有限狀態(tài)機(jī)。這兩類FSM 都處理三組變量，一組輸入變量X（k）， 一組內(nèi)部狀態(tài)U（k）和一組輸出變量Y（k）。這兩類FSM 使用相同的轉(zhuǎn)換函數(shù)δ 來(lái)映射U x X

Mealy 和Moore FSM 的區(qū)別在于用于輸出狀態(tài)的第二個(gè)映射函數(shù)。Mealy 的輸出狀態(tài)映射函數(shù)λ 表示U x X Y 映射，而Mooreλ 表示一個(gè)更簡(jiǎn)單的映射，從U Y。從實(shí)現(xiàn)的角度來(lái)看，雖然Mo o re FSM 可能更簡(jiǎn)單，但Meal y FSM 也有其優(yōu)勢(shì)。例如， 與內(nèi)部狀態(tài)的數(shù)量相比，它可以有更多或不同的輸出狀態(tài)，而在Mo o re FSM 中，每個(gè)內(nèi)部狀態(tài)都與一個(gè)輸出狀態(tài)相關(guān)聯(lián)。

通用的Mealy FSM 可用下面的表格來(lái)表示：

其中u k 列表示當(dāng)前的內(nèi)部狀態(tài)，x k 行表示當(dāng)前的輸入狀態(tài)。表格顯示下一個(gè)內(nèi)部狀態(tài)（δ 映射）和相應(yīng)的輸出狀態(tài)（λ 映射）。

圖1 ：?jiǎn)渭?jí)EDFA 安全狀態(tài)圖。

圖1 顯示了FSM 另一種更常見(jiàn)的表達(dá)形式，即狀態(tài)圖。你可以看到一個(gè)完整的單級(jí)EDFA 安全序列狀態(tài)圖。

每個(gè)EDFA 使用一個(gè)或兩個(gè)（更常見(jiàn)的兩級(jí)EDFA）激光泵，將能量提供給EDFA 內(nèi)的特殊光纖線圈。通過(guò)放大器，該能量從上一個(gè)節(jié)點(diǎn)傳輸?shù)较乱粋€(gè)節(jié)點(diǎn)的光信號(hào)（光子） 放大。當(dāng)連接E D FA 和其它節(jié)點(diǎn)的光纖斷開(kāi)并且檢測(cè)到信號(hào)丟失（LO S）時(shí)，就會(huì)出現(xiàn)問(wèn)題。這種情況必須立即處理，激光功率必須降低或完全切斷。其它情況也需要立即關(guān)注。整個(gè)安全序列是E D FA 固件實(shí)施的一部分。

FSM 的基本實(shí)施

實(shí)現(xiàn)有限狀態(tài)機(jī)（通常用于嵌入式控制軟件），最好的編程語(yǔ)言是什么？答案可能是C 語(yǔ)言。還有許多其它更現(xiàn)代的、面向?qū)ο蟮木幊陶Z(yǔ)言，但C 語(yǔ)言就像嵌入式系統(tǒng)的“母語(yǔ)言”。一個(gè)經(jīng)驗(yàn)豐富的嵌入式軟件設(shè)計(jì)師， 如何在C 語(yǔ)言中實(shí)現(xiàn)這種FSM ？它很可能從這樣一個(gè)函數(shù)開(kāi)始：

如果查看上面的代碼，您可以看到條件（事件標(biāo)志組合）如何在滿足條件的情況下， 將c u r r State 變量從初始、禁用狀態(tài)移動(dòng)/ 更改為下一個(gè)狀態(tài)。每次這樣的內(nèi)部狀態(tài)變化，都會(huì)觸發(fā)一個(gè)特定動(dòng)作，在某些情況下， 輸出狀態(tài)會(huì)觸發(fā)多個(gè)動(dòng)作。

到目前為止一切都還正常進(jìn)行，但隨著整個(gè)過(guò)程變得更加復(fù)雜，i f- e l s e 決策語(yǔ)句也變得更加復(fù)雜（而且嵌套更深）。然后，如果需要修改任何if-else 決策語(yǔ)句，它可能會(huì)影響諸多其它語(yǔ)句。接下來(lái)，整個(gè)處理功能將需要反復(fù)測(cè)試。兩級(jí)E D FA 需要兩個(gè)類似的FSM 功能，再加上另一個(gè)控制A D FA 放大器的FSM 功能，需要做很多工作。

改進(jìn)FSM的實(shí)現(xiàn)

還有另一種方法來(lái)表達(dá)有限狀態(tài)機(jī)：通過(guò)狀態(tài)轉(zhuǎn)換表（STT） 來(lái)實(shí)現(xiàn)。STT 是Mealy FSM 描述的另一種形式。這樣的表通常有四列，行數(shù)根據(jù)需要確定。每行描述從當(dāng)前狀態(tài)到下一狀態(tài)的轉(zhuǎn)換。轉(zhuǎn)換由事件（一個(gè)或多個(gè)事件標(biāo)志的組合）觸發(fā)。該動(dòng)作描述了與轉(zhuǎn)換相關(guān)的所有動(dòng)作。例如，如下是一個(gè)STT（只是它的片段），對(duì)應(yīng)于圖中所示的狀態(tài)圖。

為什么這樣的表示比狀態(tài)圖更好？因?yàn)樗梢子趯?shí)現(xiàn)。下面，來(lái)看看如何用C 語(yǔ)言來(lái)實(shí)現(xiàn)。

一位經(jīng)驗(yàn)豐富的軟件設(shè)計(jì)師， 會(huì)將FSM 代碼拆分成幾個(gè)源文件， 并從FSM_ example.h 頭文件開(kāi)始，其中包含特殊類型的定義和所有函數(shù)的原型。下面是此類頭文件的一個(gè)示例。

對(duì)于經(jīng)驗(yàn)不足的程序員來(lái)說(shuō)，前兩個(gè)定義可能值得解釋。每個(gè)函數(shù)定義一個(gè)特定函數(shù)指針的名稱。在C# 中， 這些定義與使用delegate 關(guān)鍵字的定義相同。它們是C 語(yǔ)言編程中非常強(qiáng)大的工具，使C 程序能夠像使用C# 這樣面向?qū)ο蟮木幊陶Z(yǔ)言，更方便地編寫(xiě)程序。除了最后一個(gè)函數(shù)外，其它所有函數(shù)都應(yīng)該非常清楚。一類是F_FSM_EVENT_T 類型的函數(shù)，它們用于測(cè)試某些系統(tǒng)狀態(tài)（標(biāo)志），并返回true 或false。請(qǐng)注意IsLosON（） 和IsLosOFF（）等“成對(duì)”的函數(shù)。在這種特殊情況下，只需測(cè)試一個(gè)：通過(guò)硬件（H/W）報(bào)告的狀態(tài)/ 標(biāo)志， 來(lái)測(cè)試輸入信號(hào)的丟失。如果檢測(cè)到信號(hào)丟失，此函數(shù)將返回true，否則將返回false。第二個(gè)函數(shù)只是一種封裝器，它調(diào)用第一個(gè)函數(shù)并返回一個(gè)否定的結(jié)果。

這里定義的第二類函數(shù)是F_FSM_ACTION_T 類型。這是“動(dòng)作”功能，它們控制（打開(kāi)或關(guān)閉）微控制器所需的內(nèi)部/ 外部設(shè)備或一些H /W 電路，整個(gè)嵌入式系統(tǒng)由這些電路組成。

無(wú)論FSM 如何實(shí)現(xiàn)，都需要這兩類功能，例如“狀態(tài)圖”過(guò)程或STT 實(shí)現(xiàn)?，F(xiàn)在，F(xiàn)SM_sstKernel（） 函數(shù)是一個(gè)新功能。它取代了實(shí)現(xiàn)函數(shù)FSM_stage1（） 的“狀態(tài)圖”。它處理ST T 類型的數(shù)據(jù)。這些數(shù)據(jù)被定義為S_FSM_STT_T 類型，并作為FSM_sstKernel （）函數(shù)的參數(shù)。由于FSM_ s st Ke r n e l（）需要修改至少一個(gè)數(shù)據(jù)項(xiàng)，因此必須將其作為指向S _ FSM_ STT_ 類型數(shù)據(jù)的引用/ 指針。

圖2 ：?jiǎn)渭?jí)EDFA 安全狀態(tài)圖模擬。

FSM_sstKernel（）所做的事情非常簡(jiǎn)單。它在S _ FSM_ R OW_ T 類型的行（數(shù)組元素）中“循環(huán)”， 并查找presentState 與當(dāng)前內(nèi)部狀態(tài)currentState 相同的行。如果找到這樣的行，將調(diào)用其對(duì)應(yīng)的事件測(cè)試函數(shù)，并將它們的返回值“a n d – e d”放在一起，以確定是否滿足了移動(dòng)到下一個(gè)內(nèi)部狀態(tài)的條件。但有個(gè)限制，只能將兩個(gè)邏輯值“and-ed”加在一起。如果需要更多個(gè)，則需要通過(guò)另一個(gè)F _ FSM_ EVENT_T 類型的事件，來(lái)擴(kuò)展S_FSM_ROW_T 數(shù)據(jù)結(jié)構(gòu)。如果內(nèi)部狀態(tài)之間的轉(zhuǎn)換，必須將條件/ 事件“or-ed”放在在一起，那又如何處理呢？每個(gè)事件（或它們“and-ed”的組合）必須在單獨(dú)的、但在其它方面相同的行中提供。

然后，F(xiàn)SM_sstKernel（）繼續(xù)（如果瞬態(tài)條件滿足）啟動(dòng)在行數(shù)據(jù)中找到的動(dòng)作。最后，它將行的nextState 復(fù)制到stt 的currentState。

如果我想使用FS M _ s st Ke r n e l（） 來(lái)處理更多ST T 行數(shù)截然不同的FSM，該怎么辦？必須定義ROW_MAX 常量，以滿足最長(zhǎng)的STT，但最好的解決方案是用行的鏈接列表替換行數(shù)組。然后，每個(gè)S_FSM_STT_T 型數(shù)據(jù)， 將使用一個(gè)最佳內(nèi)存空間。然而，一些簡(jiǎn)單的嵌入式系統(tǒng)，不支持動(dòng)態(tài)分配內(nèi)存空間。

現(xiàn)在，在FS M _ s st Ke r n e l（）中取消對(duì)這兩個(gè)p r i n tf（）語(yǔ)句的注釋，可以看到FSM 是如何從當(dāng)前狀態(tài)發(fā)展到下一個(gè)狀態(tài)的。這顯然不適用于嵌入式系統(tǒng)， 但整個(gè)代碼可能會(huì)在P C 機(jī)上進(jìn)行測(cè)試， 例如在Microsoft Visual S tudio 中。

完成和編譯

一旦FSM _ exa m p l e . h 和 FSM _ example.c 完成后（甚至可以編譯它們并創(chuàng)建對(duì)應(yīng)的.o b j 文件），就可以將它們添加到應(yīng)用程序中。在另一個(gè)源文件中，需要?jiǎng)?chuàng)建STT 表。這意味著首先定義ST T 的每一行，最后定義STT 本身。然后可以調(diào)用FS M _ s st Ke r n e l（）函數(shù)。您很可能會(huì)在F/W 應(yīng)用程序的main（）函數(shù)中， 將其作為后臺(tái)任務(wù)之一調(diào)用。您可以定義更多這樣類似S_FSM_STT_T 變量，并調(diào)用FSM_sstKernel（）來(lái)引用它們。

為了更好地可視化， 請(qǐng)?jiān)贛S V i s u a l Studio 下的PC 上編寫(xiě)以下源文件：

在編譯和運(yùn)行程序（ 以及FSM_ example.h 和FSM_example.cpp）時(shí)，如果FSM_sstKernel（）中的兩個(gè)printf（） 語(yǔ)句并未注釋掉，您應(yīng)該會(huì)看到如圖2 所示的結(jié)果。

關(guān)鍵概念：

檢查有限狀態(tài)機(jī)的基本實(shí)現(xiàn)。

考察有限狀態(tài)機(jī)實(shí)現(xiàn)的改進(jìn)。

思考一下：

如果通過(guò)一種不同的方法來(lái)實(shí)施有限狀態(tài)機(jī)？