嵌入式开发工程师必备有限状态机

　　有限状态机示意图（Finite State Machines）图片来源：flaviocopes.com
　　作者 |  Peter Galan
　　＂
　　获取有关使用C语言为嵌入式系统的有限状态机进行编程的帮助。
　　＂
　　有限状态机（FSM）的定义是：描述特定（逻辑）过程的一系列事件和动作的数学模型。在工程实践中，你可以找到无数类似的过程，从简单的通过几个按钮控制电机的FSM， 到可以监控非常复杂的生产制造过程或航天飞机的复杂FSM 系统。
　　我曾经为广泛应用于光通信领域的掺铒光纤放大器（EDFA）设计过固件。一个固件部分必须处理E DFA 的安全问题，如果设计不当，EDFA 可能会使用对人体有害的强激光。这似乎是一个常规的FSM 代码设计，但其结果却是一个非常复杂的、难以遵循和维护的冗长过程。需要一种不同的方法来实施FSM，这可能会引起嵌入式代码设计者的兴趣。
　　有限状态机理论
　　根据有限状态机理论，你可能会想起两种类型的FSM 表示，一种是Mealy 有限状态机，另一种是Moore 有限状态机。这两类FSM 都处理三组变量，一组输入变量X（k）， 一组内部状态U（k）和一组输出变量Y（k）。这两类FSM 使用相同的转换函数δ 来映射U x X
　　Mealy 和Moore FSM 的区别在于用于输出状态的第二个映射函数。Mealy 的输出状态映射函数λ 表示U x X   Y 映射，而Mooreλ 表示一个更简单的映射，从U   Y。从实现的角度来看，虽然Mo o re FSM 可能更简单，但Meal y FSM 也有其优势。例如， 与内部状态的数量相比，它可以有更多或不同的输出状态，而在Mo o re FSM 中，每个内部状态都与一个输出状态相关联。
　　通用的Mealy FSM 可用下面的表格来表示：
　　其中u k 列表示当前的内部状态，x k 行表示当前的输入状态。表格显示下一个内部状态（δ 映射）和相应的输出状态（λ 映射）。
　　图1 ：单级EDFA 安全状态图。
　　图1 显示了FSM 另一种更常见的表达形式，即状态图。你可以看到一个完整的单级EDFA 安全序列状态图。
　　每个EDFA 使用一个或两个（更常见的两级EDFA）激光泵，将能量提供给EDFA 内的特殊光纤线圈。通过放大器，该能量从上一个节点传输到下一个节点的光信号（光子） 放大。当连接E D FA 和其它节点的光纤断开并且检测到信号丢失（LO S）时，就会出现问题。这种情况必须立即处理，激光功率必须降低或完全切断。其它情况也需要立即关注。整个安全序列是E D FA 固件实施的一部分。
　　FSM 的基本实施
　　实现有限状态机（通常用于嵌入式控制软件），最好的编程语言是什么？答案可能是C 语言。还有许多其它更现代的、面向对象的编程语言，但C 语言就像嵌入式系统的＂母语言＂。一个经验丰富的嵌入式软件设计师， 如何在C 语言中实现这种FSM ？它很可能从这样一个函数开始：
　　如果查看上面的代码，您可以看到条件（事件标志组合）如何在满足条件的情况下， 将c u r r State 变量从初始、禁用状态移动/ 更改为下一个状态。每次这样的内部状态变化，都会触发一个特定动作，在某些情况下， 输出状态会触发多个动作。
　　到目前为止一切都还正常进行，但随着整个过程变得更加复杂，i f- e l s e 决策语句也变得更加复杂（而且嵌套更深）。然后，如果需要修改任何if-else 决策语句，它可能会影响诸多其它语句。接下来，整个处理功能将需要反复测试。两级E D FA 需要两个类似的FSM 功能，再加上另一个控制A D FA 放大器的FSM 功能，需要做很多工作。
　　改进FSM的实现
　　还有另一种方法来表达有限状态机：通过状态转换表（STT） 来实现。STT 是Mealy FSM 描述的另一种形式。这样的表通常有四列，行数根据需要确定。每行描述从当前状态到下一状态的转换。转换由事件（一个或多个事件标志的组合）触发。该动作描述了与转换相关的所有动作。例如，如下是一个STT（只是它的片段），对应于图中所示的状态图。
　　为什么这样的表示比状态图更好？因为它可易于实现。下面，来看看如何用C 语言来实现。
　　一位经验丰富的软件设计师， 会将FSM 代码拆分成几个源文件， 并从FSM_ example.h 头文件开始，其中包含特殊类型的定义和所有函数的原型。下面是此类头文件的一个示例。
　　对于经验不足的程序员来说，前两个定义可能值得解释。每个函数定义一个特定函数指针的名称。在C# 中， 这些定义与使用delegate 关键字的定义相同。它们是C 语言编程中非常强大的工具，使C 程序能够像使用C# 这样面向对象的编程语言，更方便地编写程序。除了最后一个函数外，其它所有函数都应该非常清楚。一类是F_FSM_EVENT_T 类型的函数，它们用于测试某些系统状态（标志），并返回true 或false。请注意IsLosON（） 和IsLosOFF（）等＂成对＂的函数。在这种特殊情况下，只需测试一个：通过硬件（H/W）报告的状态/ 标志， 来测试输入信号的丢失。如果检测到信号丢失，此函数将返回true，否则将返回false。第二个函数只是一种封装器，它调用第一个函数并返回一个否定的结果。
　　这里定义的第二类函数是F_FSM_ACTION_T 类型。这是＂动作＂功能，它们控制（打开或关闭）微控制器所需的内部/ 外部设备或一些H /W 电路，整个嵌入式系统由这些电路组成。
　　无论FSM 如何实现，都需要这两类功能，例如＂状态图＂过程或STT 实现。现在，FSM_sstKernel（） 函数是一个新功能。它取代了实现函数FSM_stage1（） 的＂状态图＂。它处理ST T 类型的数据。这些数据被定义为S_FSM_STT_T 类型，并作为FSM_sstKernel （）函数的参数。由于FSM_ s st Ke r n e l（）需要修改至少一个数据项，因此必须将其作为指向S _ FSM_ STT_ 类型数据的引用/ 指针。
　　图2 ：单级EDFA 安全状态图模拟。
　　FSM_sstKernel（）所做的事情非常简单。它在S _ FSM_ R OW_ T 类型的行（数组元素）中＂循环＂， 并查找presentState 与当前内部状态currentState 相同的行。如果找到这样的行，将调用其对应的事件测试函数，并将它们的返回值＂a n d - e d＂放在一起，以确定是否满足了移动到下一个内部状态的条件。但有个限制，只能将两个逻辑值＂and-ed＂加在一起。如果需要更多个，则需要通过另一个F _ FSM_ EVENT_T 类型的事件，来扩展S_FSM_ROW_T 数据结构。如果内部状态之间的转换，必须将条件/ 事件＂or-ed＂放在在一起，那又如何处理呢？每个事件（或它们＂and-ed＂的组合）必须在单独的、但在其它方面相同的行中提供。
　　然后，FSM_sstKernel（）继续（如果瞬态条件满足）启动在行数据中找到的动作。最后，它将行的nextState 复制到stt 的currentState。
　　如果我想使用FS M _ s st Ke r n e l（） 来处理更多ST T 行数截然不同的FSM，该怎么办？必须定义ROW_MAX 常量，以满足最长的STT，但最好的解决方案是用行的链接列表替换行数组。然后，每个S_FSM_STT_T 型数据， 将使用一个最佳内存空间。然而，一些简单的嵌入式系统，不支持动态分配内存空间。
　　现在，在FS M _ s st Ke r n e l（）中取消对这两个p r i n tf（）语句的注释，可以看到FSM 是如何从当前状态发展到下一个状态的。这显然不适用于嵌入式系统， 但整个代码可能会在P C 机上进行测试， 例如在Microsoft Visual S tudio 中。
　　完成和编译
　　一旦FSM _ exa m p l e . h 和 FSM _ example.c 完成后（甚至可以编译它们并创建对应的.o b j 文件），就可以将它们添加到应用程序中。在另一个源文件中，需要创建STT 表。这意味着首先定义ST T 的每一行，最后定义STT 本身。然后可以调用FS M _ s st Ke r n e l（）函数。您很可能会在F/W 应用程序的main（）函数中， 将其作为后台任务之一调用。您可以定义更多这样类似S_FSM_STT_T 变量，并调用FSM_sstKernel（）来引用它们。
　　为了更好地可视化， 请在MS V i s u a l Studio 下的PC 上编写以下源文件：
　　在编译和运行程序（ 以及FSM_ example.h 和FSM_example.cpp）时，如果FSM_sstKernel（）中的两个printf（） 语句并未注释掉，您应该会看到如图2 所示的结果。
　　关键概念：
　　检查有限状态机的基本实现。
　　考察有限状态机实现的改进。
　　思考一下：
　　如果通过一种不同的方法来实施有限状态机？