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

作者 | Peter Galan

“

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

”

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

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

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

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

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

通用的Mealy FSM 可用下面的表格來表示：

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

圖1 ：單級EDFA 安全狀態(tài)圖。

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

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

FSM 的基本實施

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

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

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

改進FSM的實現(xiàn)

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

為什么這樣的表示比狀態(tài)圖更好？因為它可易于實現(xiàn)。下面，來看看如何用C 語言來實現(xiàn)。

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

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

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

無論FSM 如何實現(xiàn)，都需要這兩類功能，例如“狀態(tài)圖”過程或STT 實現(xiàn)?，F(xiàn)在，F(xiàn)SM_sstKernel（） 函數(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（）需要修改至少一個數(shù)據(jù)項，因此必須將其作為指向S _ FSM_ STT_ 類型數(shù)據(jù)的引用/ 指針。

圖2 ：單級EDFA 安全狀態(tài)圖模擬。

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

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

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

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

完成和編譯

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

為了更好地可視化， 請在MS V i s u a l Studio 下的PC 上編寫以下源文件：

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

關鍵概念：

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

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

思考一下：

如果通過一種不同的方法來實施有限狀態(tài)機？