C语言_有限状态机（Finite State Machine）
基本介绍
许多小型或复杂的应用程序都使用有限状态机 (FSM)，C 语言中的有限状态机是嵌入式系统的流行设计模式之一，有限状态机使开发变得容易和顺利。
有很多设备使用事件基态，如咖啡机、自动售货机、POS 设备、门锁系统等。一些 POS 设备使用事件表，在事件表中使用事件处理程序注册事件，通过相关条件触发事件的执行。
本文中，使用C语言创建一个简易的ATM状态机。 ATM 机的状态可以通过即将发生的事件进行更改。ATM状态机包含以下几个状态：
- Idle State
- Card Inserted State
- Pin entered State
- Option Selected State
- Amount Entered State
初始化时，ATM处于闲置状态，之后进入插卡状态，插卡处理完成之后需要用户输入密码，输入密码之后进行相关选项的操作，设置选项完成之后输入金额。创建一个状态机，按照以下步骤进行：
- Gather the information which the user wants.
- Analyze the all gather information and sketch the state transition diagram.
- create a code skeleton of the state machine.
- Make sure the transition (changing state) work properly
- Implement all the required information in the code skeleton of the state machine.
- Test the implemented state machine.
收集需求——>分析需求绘制状态图——>创建代码框架——>确认状态转换是否正确——>编写状态的具体动作——>测试状态机。
实现方法
在C语言中，有两种常用的方式实现基于事件的状态机：一种是通过嵌套的switch case（或者if else）实现，一种是look up table（查表）实现。
look up table 查表法实现有限状态机
结构体数组创建有限状态机是一种比较优雅的方式。状态机的状态和事件封装在一个结构中，并在适当的状态和事件上调用函数指针（事件处理程序），程序的可读性比较好。
#include <stdio.h>
//Different state of ATM machine
typedef enum
{Idle_State,Card_Inserted_State,Pin_Eentered_State,Option_Selected_State,Amount_Entered_State,last_State
} eSystemState;
//Different type events
typedef enum
{Card_Insert_Event,Pin_Enter_Event,Option_Selection_Event,Amount_Enter_Event,Amount_Dispatch_Event,last_Event
} eSystemEvent;
//typedef of function pointer
typedef eSystemState(*pfEventHandler)(void);
//structure of state and event with event handler
typedef struct
{eSystemState eStateMachine;eSystemEvent eStateMachineEvent;pfEventHandler pfStateMachineEvnentHandler;
} sStateMachine;
//function call to dispatch the amount and return the ideal state
eSystemState AmountDispatchHandler(void)
{return Idle_State;
}
//function call to Enter amount and return amount entered state
eSystemState EnterAmountHandler(void)
{return Amount_Entered_State;
}
//function call to option select and return the option selected state
eSystemState OptionSelectionHandler(void)
{return Option_Selected_State;
}
//function call to enter the pin and return pin entered state
eSystemState EnterPinHandler(void)
{return Pin_Eentered_State;
}
//function call to processing track data and return card inserted state
eSystemState InsertCardHandler(void)
{return Card_Inserted_State;
}
//Initialize array of structure with states and event with proper handler
sStateMachine asStateMachine[] =
{{ Idle_State, Card_Insert_Event, InsertCardHandler },{ Card_Inserted_State, Pin_Enter_Event, EnterPinHandler },{ Pin_Eentered_State, Option_Selection_Event, OptionSelectionHandler },{ Option_Selected_State, Amount_Enter_Event, EnterAmountHandler },{ Amount_Entered_State, Amount_Dispatch_Event, AmountDispatchHandler }
};
//main function
int main(int argc, char *argv[])
{eSystemState eNextState = Idle_State;while (1){//Api read the eventeSystemEvent eNewEvent = read_event();if ((eNextState < last_State) && (eNewEvent < last_Event) && (asStateMachine[eNextState].eStateMachineEvent == eNewEvent) && (asStateMachine[eNextState].pfStateMachineEvnentHandler != NULL)){// function call as per the state and event and return the next state of the finite state machineeNextState = (*asStateMachine[eNextState].pfStateMachineEvnentHandler)();}else{//Invalid}}return 0;
}
状态机结构体中包含状态，事件编号，执行状态的动作。执行动作将返回对应的状态值。填写状态机的结构体数组，状态、触发事件和即将执行的动作。状态机运行时，初始化状态机，实践中，通常从外部API读入实践触发动作的执行。执行状态机中的动作，返回下一个状态的状态编号。
switch case实现有限状态机
这是实现状态机的最简单方法。使用 if-else 或 switch case 来检查状态并触发事件。如果状态和触发事件的组合匹配，则执行事件处理程序并更新下一个状态。这取决于检查第一个状态或事件的要求。 在下面的示例代码中，首先验证状态，然后检查触发的事件。
#include <stdio.h>
//Different state of ATM machine
typedef enum
{Idle_State,Card_Inserted_State,Pin_Eentered_State,Option_Selected_State,Amount_Entered_State,
} eSystemState;
//Different type events
typedef enum
{Card_Insert_Event,Pin_Enter_Event,Option_Selection_Event,Amount_Enter_Event,Amount_Dispatch_Event
} eSystemEvent;
//Prototype of eventhandlers
eSystemState AmountDispatchHandler(void)
{return Idle_State;
}
eSystemState EnterAmountHandler(void)
{return Amount_Entered_State;
}
eSystemState OptionSelectionHandler(void)
{return Option_Selected_State;
}
eSystemState EnterPinHandler(void)
{return Pin_Eentered_State;
}
eSystemState InsertCardHandler(void)
{return Card_Inserted_State;
}
int main(int argc, char *argv[])
{eSystemState eNextState = Idle_State;eSystemEvent eNewEvent;while (1){//Read system EventseSystemEvent eNewEvent = ReadEvent();switch (eNextState){case Idle_State:{if (Card_Insert_Event == eNewEvent){eNextState = InsertCardHandler();}}break;case Card_Inserted_State:{if (Pin_Enter_Event == eNewEvent){eNextState = EnterPinHandler();}}break;case Pin_Eentered_State:{if (Option_Selection_Event == eNewEvent){eNextState = OptionSelectionHandler();}}break;case Option_Selected_State:{if (Amount_Enter_Event == eNewEvent){eNextState = EnterAmountHandler();}}break;case Amount_Entered_State:{if (Amount_Dispatch_Event == eNewEvent){eNextState = AmountDispatchHandler();}}break;default:break;}}return 0;
}
使用switch case 和if else实现上面的状态切换和动作执行，导致程序很长，不利于后期的维护和修改。可否对上面的程序进行优化，避免这种嵌套的结构呢？
使用二维数组指针精简switch case嵌套结构
答案是肯定得，我们在上面的程序中，首先是用switch case进行了状态的判断，然后使用if else判断是否有事件触发动作。那么相当于这段代码包含两层判断，第一层大的状态判断后面跟随着一层判断。基于这个认知，自然就想到，可否使用一个二维数组，行代表一层判断，列代表这一层判断下面的子状态判断呢！
下面，使用一个二维数组替代以上switch case的嵌套，实现代码的精简：
# include <stdio.h>
typedef enum
{Idle_State,Card_Inserted_State,Pin_Eentered_State,Option_Selected_State,Amount_Entered_State,last_State
} eSystemState;
//Different type events
typedef enum
{Card_Insert_Event,Pin_Enter_Event,Option_Selection_Event,Amount_Enter_Event,Amount_Dispatch_Event,last_Event
} eSystemEvent;
//typedef of 2d array
typedef eSystemState (*const afEventHandler[last_State][last_Event])(void);
//function call to dispatch the amount and return the ideal state
eSystemState AmountDispatchHandler(void)
{return Idle_State;
}
//function call to Enter amount and return amount enetered state
eSystemState EnterAmountHandler(void)
{return Amount_Entered_State;
}
//function call to option select and return the option selected state
eSystemState OptionSelectionHandler(void)
{return Option_Selected_State;
}
//function call to enter the pin and return pin entered state
eSystemState EnterPinHandler(void)
{return Pin_Eentered_State;
}
//function call to processing track data and return card inserted state
eSystemState InsertCardHandler(void)
{return Card_Inserted_State;
}
int main(int argc, char *argv[])
{eSystemState eNextState = Idle_State;eSystemEvent eNewEvent;// Table to define valid states and event of finite state machinestatic afEventHandler StateMachine ={[Idle_State] = { [Card_Insert_Event] = InsertCardHandler },[Card_Inserted_State] = { [Pin_Enter_Event] = EnterPinHandler },[Pin_Eentered_State] = { [Option_Selection_Event] = OptionSelectionHandler },[Option_Selected_State] = { [Amount_Enter_Event] = EnterAmountHandler },[Amount_Entered_State] = { [Amount_Dispatch_Event] = AmountDispatchHandler },};while (1){// assume api to read the next eventeSystemEvent eNewEvent = ReadEvent();//Check NULL pointer and array boundaryif ((eNextState < last_State) && (eNewEvent < last_Event) && StateMachine[eNextState][eNewEvent] != NULL){// function call as per the state and event and return the next state of the finite state machineeNextState = (*StateMachine[eNextState][eNewEvent])();}else{//Invalid}}return 0;
}
在上面这段代码中，使用typedef定义函数指针，返回值正是执行动作返回的状态值。二维数组返回event，是一个执行动作的过程。这样的话，在有限状态机的实现中，定义行为state，列里面我们放置event，每一列对应一个action，就可以实现根据前一次的state和event，执行当前与之对应的action，而返回当前执行动作的state，使状态机正确转移到下一个状态。
在上面的实现方法中，一个嵌套的 switch case 替换为一个指向函数的指针数组。 精简了代码，但是同时也并降低代码的可读性。 当状态很多，触发动作的条件也很多时，会造成内存大量的浪费，因为在二维数组中，每一行里面并非所有的event都是这一行的state必须的。
以上是状态机的常见实现方法，针对嵌入式的手写代码编程，常常希望有一种简单又不需要占用太多资源的方法，并且能够有效复用。这里推荐一种基于事件驱动的有限状态机框架，QEP框架，使用函数指针映射为状态，将状态机的描述进行标准化处理，接口简单，占用资源极少。
QEP有限状态机框架
博主会长期更新关于有限状态机设计的方法与思想，欢迎关注。
reference：
https://aticleworld.com/state-machine-using-c/
![NGUI插件] 收录最全的NGUI示例文档中文教程(更新版本3.0.5)](http://www.tasharen.com/ngui/icon.png){kind=icon}
