Linux編程之有限狀態(tài)機FSM的理解與實(shí)現

有限狀態(tài)機（finite state machine）簡(jiǎn)稱(chēng)FSM，表示有限個(gè)狀態(tài)及在這些狀態(tài)之間的轉移和動(dòng)作等行為的數學(xué)模型，在計算機領(lǐng)域有著(zhù)廣泛的應用。FSM是一種邏輯單元內部的一種高效編程方法，在服務(wù)器編程中，服務(wù)器可以根據不同狀態(tài)或者消息類(lèi)型進(jìn)行相應的處理邏輯，使得程序邏輯清晰易懂。

那有限狀態(tài)機通常在什么地方被用到？

處理程序語(yǔ)言或者自然語(yǔ)言的 tokenizer,自底向上解析語(yǔ)法的parser，
各種通信協(xié)議發(fā)送方和接受方傳遞數據對消息處理，游戲AI等都有應用場(chǎng)景。

狀態(tài)機有以下幾種實(shí)現方法，我將一一闡述它們的優(yōu)缺點(diǎn)。

使用if/else if語(yǔ)句是實(shí)現的FSM最簡(jiǎn)單最易懂的方法，我們只需要通過(guò)大量的if /else if語(yǔ)句來(lái)判斷狀態(tài)值來(lái)執行相應的邏輯處理。

看看下面的例子，我們使用了大量的if/else if語(yǔ)句實(shí)現了一個(gè)簡(jiǎn)單的狀態(tài)機，做到了根據狀態(tài)的不同執行相應的操作，并且實(shí)現了狀態(tài)的跳轉。

//比如我們定義了小明一天的狀態(tài)如下
enum
{
	GET_UP,
	GO_TO_SCHOOL,
	HAVE_LUNCH,
	GO_HOME,
	DO_HOMEWORK,
	SLEEP,
};int main()
{	int state = GET_UP;	//小明的一天	while (1)
	{		if (state == GET_UP)
		{
			GetUp(); //具體調用的函數			state = GO_TO_SCHOOL;  //狀態(tài)的轉移
		}		else if (state == GO_TO_SCHOOL)
		{
			Go2School();			state = HAVE_LUNCH;
		}		else if (state == HAVE_LUNCH)
		{
			HaveLunch();
		}
		...		else if (state == SLEEP)
		{
			Go2Bed();			state = GET_UP;
		}
	}	return 0;
}

看完上面的例子，大家有什么感受？是不是感覺(jué)程序雖然簡(jiǎn)單易懂，但是使用了大量的if判斷語(yǔ)句，使得代碼很低端，同時(shí)代碼膨脹的比較厲害。這個(gè)狀態(tài)機的狀態(tài)僅有幾個(gè)，代碼膨脹并不明顯，但是如果我們需要處理的狀態(tài)有數十個(gè)的話(huà)，該狀態(tài)機的代碼就不好讀了。

使用switch語(yǔ)句實(shí)現的FSM的結構變得更為清晰了，其缺點(diǎn)也是明顯的：這種設計方法雖然簡(jiǎn)單，通過(guò)一大堆判斷來(lái)處理，適合小規模的狀態(tài)切換流程，但如果規模擴大難以擴展和維護。

int main(){	int state = GET_UP;	//小明的一天
	while (1)
	{		switch(state)
		{		case GET_UP:
			GetUp(); //具體調用的函數
			state = GO_TO_SCHOOL;  //狀態(tài)的轉移
			break;		case GO_TO_SCHOOL:
			Go2School();
			state = HAVE_LUNCH;			break;		case HAVE_LUNCH:
			HaveLunch();
			state = GO_HOME;			break;
			...		default:			break;
	    }
	}	return 0;
}

使用函數指針實(shí)現FSM的思路：建立相應的狀態(tài)表和動(dòng)作查詢(xún)表，根據狀態(tài)表、事件、動(dòng)作表定位相應的動(dòng)作處理函數，執行完成后再進(jìn)行狀態(tài)的切換。

當然使用函數指針實(shí)現的FSM的過(guò)程還是比較費時(shí)費力，但是這一切都是值得的，因為當你的程序規模大時(shí)候，基于這種表結構的狀態(tài)機，維護程序起來(lái)也是得心應手。

下面給出一個(gè)使用函數指針實(shí)現的FSM的框架：

我們還是以“小明的一天”為例設計出該FSM。

先給出該FSM的狀態(tài)轉移圖：

下面講解關(guān)鍵部分代碼實(shí)現

首先我們定義出小明一天的活動(dòng)狀態(tài)

//比如我們定義了小明一天的狀態(tài)如下enum{
	GET_UP,
	GO_TO_SCHOOL,
	HAVE_LUNCH,
	DO_HOMEWORK,
	SLEEP,
};

我們也定義出會(huì )發(fā)生的事件

enum{
	EVENT1 = 1,
	EVENT2,
	EVENT3,
};

定義狀態(tài)表的數據結構

typedef struct FsmTable_s{
	int event;   //事件
	int CurState;  //當前狀態(tài)
	void (*eventActFun)();  //函數指針
	int NextState;  //下一個(gè)狀態(tài)}FsmTable_t;

接下來(lái)定義出最重要FSM的狀態(tài)表，我們整個(gè)FSM就是根據這個(gè)定義好的表來(lái)運轉的。

FsmTable_t XiaoMingTable[] =
{	//{到來(lái)的事件，當前的狀態(tài)，將要要執行的函數，下一個(gè)狀態(tài)}
	{ EVENT2,  SLEEP,           GetUp,        GET_UP },
	{ EVENT1,  GET_UP,          Go2School,    GO_TO_SCHOOL },
	{ EVENT2,  GO_TO_SCHOOL,    HaveLunch,    HAVE_LUNCH },
	{ EVENT3,  HAVE_LUNCH,      DoHomework,   DO_HOMEWORK },
	{ EVENT1,  DO_HOMEWORK,     Go2Bed,       SLEEP },	//add your codes here};

狀態(tài)機的注冊、狀態(tài)轉移、事件處理的動(dòng)作實(shí)現

/*狀態(tài)機注冊*/void FSM_Regist(FSM_t* pFsm, FsmTable_t* pTable){
	pFsm->FsmTable = pTable;
}/*狀態(tài)遷移*/void FSM_StateTransfer(FSM_t* pFsm, int state){
	pFsm->curState = state;
}/*事件處理*/void FSM_EventHandle(FSM_t* pFsm, int event){
	FsmTable_t* pActTable = pFsm->FsmTable;	void (*eventActFun)() = NULL;  //函數指針初始化為空
	int NextState;	int CurState = pFsm->curState;	int flag = 0; //標識是否滿(mǎn)足條件
	int i;	/*獲取當前動(dòng)作函數*/
	for (i = 0; i<g_max_num; i++)
	{		//當且僅當當前狀態(tài)下來(lái)個(gè)指定的事件，我才執行它
		if (event == pActTable[i].event && CurState == pActTable[i].CurState)
		{
			flag = 1;
			eventActFun = pActTable[i].eventActFun;
			NextState = pActTable[i].NextState;			break;
		}
	}	if (flag) //如果滿(mǎn)足條件了
	{		/*動(dòng)作執行*/
		if (eventActFun)
		{
			eventActFun();
		}		//跳轉到下一個(gè)狀態(tài)
		FSM_StateTransfer(pFsm, NextState);
	}	else
	{		// do nothing
	}
}

主函數我們這樣寫(xiě)，然后觀(guān)察狀態(tài)機的運轉情況

int main(){
	FSM_t fsm;
	InitFsm(&fsm);	int event = EVENT1; 
	//小明的一天,周而復始的一天又一天，進(jìn)行著(zhù)相同的活動(dòng)
	while (1)
	{
		printf("event %d is coming...\n", event);
		FSM_EventHandle(&fsm, event);
		printf("fsm current state %d\n", fsm.curState);
		test(&event); 
		sleep(1);  //休眠1秒，方便觀(guān)察
	}	return 0;
}

看一看該狀態(tài)機跑起來(lái)的狀態(tài)轉移情況：

上面的圖可以看出，當且僅當在指定的狀態(tài)下來(lái)了指定的事件才會(huì )發(fā)生函數的執行以及狀態(tài)的轉移，否則不會(huì )發(fā)生狀態(tài)的跳轉。這種機制使得這個(gè)狀態(tài)機不停地自動(dòng)運轉，有條不絮地完成任務(wù)。

與前兩種方法相比，使用函數指針實(shí)現FSM能很好用于大規模的切換流程，只要我們實(shí)現搭好了FSM框架，以后進(jìn)行擴展就很簡(jiǎn)單了（只要在狀態(tài)表里加一行來(lái)寫(xiě)入新的狀態(tài)處理就可以了）。

需要FSM完整代碼的童鞋請訪(fǎng)問(wèn)我的github