[C++知识库]C语言_有限状态机（FSM）

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 event
		eSystemEvent 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 machine
			eNextState = (*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 Events
		eSystemEvent 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 machine
	static 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 event
		eSystemEvent eNewEvent = ReadEvent();
		//Check NULL pointer and array boundary
		if ((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 machine
			eNextState = (*StateMachine[eNextState][eNewEvent])();
		}
		else
		{
			//Invalid
		}
	}
	return 0;
}

在上面这段代码中，使用typedef定义函数指针，返回值正是执行动作返回的状态值。二维数组返回event，是一个执行动作的过程。这样的话，在有限状态机的实现中，定义行为state，列里面我们放置event，每一列对应一个action，就可以实现根据前一次的state和event，执行当前与之对应的action，而返回当前执行动作的state，使状态机正确转移到下一个状态。

在上面的实现方法中，一个嵌套的 switch case 替换为一个指向函数的指针数组。 精简了代码，但是同时也并降低代码的可读性。 当状态很多，触发动作的条件也很多时，会造成内存大量的浪费，因为在二维数组中，每一行里面并非所有的event都是这一行的state必须的。

reference：
https://aticleworld.com/state-machine-using-c/