Linux有限狀態(tài)機(jī)FSM的理解與實(shí)現(xiàn)
有限狀態(tài)機(jī)(finite state machine)簡(jiǎn)稱FSM,表示有限個(gè)狀態(tài)及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型,在計(jì)算機(jī)領(lǐng)域有著廣泛的應(yīng)用。FSM是一種邏輯單元內(nèi)部的一種高效編程方法,在服務(wù)器編程中,服務(wù)器可以根據(jù)不同狀態(tài)或者消息類型進(jìn)行相應(yīng)的處理邏輯,使得程序邏輯清晰易懂。
那有限狀態(tài)機(jī)通常在什么地方被用到?
處理程序語(yǔ)言或者自然語(yǔ)言的 tokenizer,自底向上解析語(yǔ)法的parser,
各種通信協(xié)議發(fā)送方和接受方傳遞數(shù)據(jù)對(duì)消息處理,游戲AI等都有應(yīng)用場(chǎng)景。
狀態(tài)機(jī)有以下幾種實(shí)現(xiàn)方法,我將一一闡述它們的優(yōu)缺點(diǎn)。
一、使用if/else if語(yǔ)句實(shí)現(xiàn)的FSM
使用if/else if語(yǔ)句是實(shí)現(xiàn)的FSM最簡(jiǎn)單最易懂的方法,我們只需要通過(guò)大量的if /else if語(yǔ)句來(lái)判斷狀態(tài)值來(lái)執(zhí)行相應(yīng)的邏輯處理。
看看下面的例子,我們使用了大量的if/else if語(yǔ)句實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的狀態(tài)機(jī),做到了根據(jù)狀態(tài)的不同執(zhí)行相應(yīng)的操作,并且實(shí)現(xiàn)了狀態(tài)的跳轉(zhuǎn)。
//比如我們定義了小明一天的狀態(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(); //具體調(diào)用的函數(shù)
state = GO_TO_SCHOOL; //狀態(tài)的轉(zhuǎn)移
}
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)機(jī)的狀態(tài)僅有幾個(gè),代碼膨脹并不明顯,但是如果我們需要處理的狀態(tài)有數(shù)十個(gè)的話,該狀態(tài)機(jī)的代碼就不好讀了。
二、使用switch實(shí)現(xiàn)FSM
使用switch語(yǔ)句實(shí)現(xiàn)的FSM的結(jié)構(gòu)變得更為清晰了,其缺點(diǎn)也是明顯的:這種設(shè)計(jì)方法雖然簡(jiǎn)單,通過(guò)一大堆判斷來(lái)處理,適合小規(guī)模的狀態(tài)切換流程,但如果規(guī)模擴(kuò)大難以擴(kuò)展和維護(hù)。
int main()
{
int state = GET_UP;
//小明的一天
while (1)
{
switch(state)
{
case GET_UP:
GetUp(); //具體調(diào)用的函數(shù)
state = GO_TO_SCHOOL; //狀態(tài)的轉(zhuǎn)移
break;
case GO_TO_SCHOOL:
Go2School();
state = HAVE_LUNCH;
break;
case HAVE_LUNCH:
HaveLunch();
state = GO_HOME;
break;
...
default:
break;
}
}
return 0;
}
三、使用函數(shù)指針實(shí)現(xiàn)FSM
使用函數(shù)指針實(shí)現(xiàn)FSM的思路:建立相應(yīng)的狀態(tài)表和動(dòng)作查詢表,根據(jù)狀態(tài)表、事件、動(dòng)作表定位相應(yīng)的動(dòng)作處理函數(shù),執(zhí)行完成后再進(jìn)行狀態(tài)的切換。
當(dāng)然使用函數(shù)指針實(shí)現(xiàn)的FSM的過(guò)程還是比較費(fèi)時(shí)費(fèi)力,但是這一切都是值得的,因?yàn)楫?dāng)你的程序規(guī)模大時(shí)候,基于這種表結(jié)構(gòu)的狀態(tài)機(jī),維護(hù)程序起來(lái)也是得心應(yīng)手。
下面給出一個(gè)使用函數(shù)指針實(shí)現(xiàn)的FSM的框架:
我們還是以“小明的一天”為例設(shè)計(jì)出該FSM。
先給出該FSM的狀態(tài)轉(zhuǎn)移圖:

下面講解關(guān)鍵部分代碼實(shí)現(xiàn)
首先我們定義出小明一天的活動(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)表的數(shù)據(jù)結(jié)構(gòu)
typedef struct FsmTable_s
{
int event; //事件
int CurState; //當(dāng)前狀態(tài)
void (*eventActFun)(); //函數(shù)指針
int NextState; //下一個(gè)狀態(tài)
}FsmTable_t;
接下來(lái)定義出最重要FSM的狀態(tài)表,我們整個(gè)FSM就是根據(jù)這個(gè)定義好的表來(lái)運(yùn)轉(zhuǎn)的。
FsmTable_t XiaoMingTable[] =
{
//{到來(lái)的事件,當(dāng)前的狀態(tài),將要要執(zhí)行的函數(shù),下一個(gè)狀態(tài)}
{ EVENT1, SLEEP, GetUp, GET_UP },
{ EVENT2, GET_UP, Go2School, GO_TO_SCHOOL },
{ EVENT3, GO_TO_SCHOOL, HaveLunch, HAVE_LUNCH },
{ EVENT1, HAVE_LUNCH, DoHomework, DO_HOMEWORK },
{ EVENT2, DO_HOMEWORK, Go2Bed, SLEEP },
//add your codes here
};
狀態(tài)機(jī)的注冊(cè)、狀態(tài)轉(zhuǎn)移、事件處理的動(dòng)作實(shí)現(xiàn)
/*狀態(tài)機(jī)注冊(cè)*/
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; //函數(shù)指針初始化為空
int NextState;
int CurState = pFsm->curState;
int flag = 0; //標(biāo)識(shí)是否滿足條件
int i;
/*獲取當(dāng)前動(dòng)作函數(shù)*/
for (i = 0; i<g_max_num; i++)
{
//當(dāng)且僅當(dāng)當(dāng)前狀態(tài)下來(lái)個(gè)指定的事件,我才執(zhí)行它
if (event == pActTable[i].event && CurState == pActTable[i].CurState)
{
flag = 1;
eventActFun = pActTable[i].eventActFun;
NextState = pActTable[i].NextState;
break;
}
}
if (flag) //如果滿足條件了
{
/*動(dòng)作執(zhí)行*/
if (eventActFun)
{
eventActFun();
}
//跳轉(zhuǎn)到下一個(gè)狀態(tài)
FSM_StateTransfer(pFsm, NextState);
}
else
{
// do nothing
}
}
主函數(shù)我們這樣寫,然后觀察狀態(tài)機(jī)的運(yùn)轉(zhuǎn)情況
int main()
{
FSM_t fsm;
InitFsm(&fsm);
int event = EVENT1;
//小明的一天,周而復(fù)始的一天又一天,進(jìn)行著相同的活動(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秒,方便觀察
}
return 0;
}
看一看該狀態(tài)機(jī)跑起來(lái)的狀態(tài)轉(zhuǎn)移情況:

上面的圖可以看出,當(dāng)且僅當(dāng)在指定的狀態(tài)下來(lái)了指定的事件才會(huì)發(fā)生函數(shù)的執(zhí)行以及狀態(tài)的轉(zhuǎn)移,否則不會(huì)發(fā)生狀態(tài)的跳轉(zhuǎn)。這種機(jī)制使得這個(gè)狀態(tài)機(jī)不停地自動(dòng)運(yùn)轉(zhuǎn),有條不絮地完成任務(wù)。
與前兩種方法相比,使用函數(shù)指針實(shí)現(xiàn)FSM能很好用于大規(guī)模的切換流程,只要我們實(shí)現(xiàn)搭好了FSM框架,以后進(jìn)行擴(kuò)展就很簡(jiǎn)單了(只要在狀態(tài)表里加一行來(lái)寫入新的狀態(tài)處理就可以了)。
需要FSM完整代碼的童鞋請(qǐng)?jiān)L問(wèn)我的github
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
linux下查看本機(jī)和遠(yuǎn)程服務(wù)器的端口是否連通的方法
今天小編就為大家分享一篇linux下查看本機(jī)和遠(yuǎn)程服務(wù)器的端口是否連通的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2019-07-07
ubuntu下安裝Python多版本的方法及注意事項(xiàng)
倒霉的今天我居然把ubuntu系統(tǒng)給完壞了,因?yàn)槲野裵ython3卸載了,然后就哦了,下面小編給大家分享下ubuntu下管理python的多個(gè)版本的方法,本文給大家介紹的非常詳細(xì),感興趣的朋友一起看下吧2016-10-10
谷歌云Google Cloud 啟用Ubuntu的SSH服務(wù)
默認(rèn)情況下,當(dāng) Ubuntu 最初被安裝的時(shí)候,通過(guò) SSH 進(jìn)行遠(yuǎn)程訪問(wèn)是不被允許的,在 Ubuntu 上啟用 SSH 非常的簡(jiǎn)單直接,需要的朋友可以參考下2023-12-12
虛擬機(jī)ubuntu16.04無(wú)法連網(wǎng)的解決方法
這篇文章主要為大家詳細(xì)介紹了虛擬機(jī)ubuntu16.04無(wú)法連網(wǎng)的解決方法,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-03-03
Apache限制IP并發(fā)數(shù)和流量控制的方法
這篇文章主要介紹了Apache限制IP并發(fā)數(shù)和流量控制的方法,需要的朋友可以參考下2014-12-12

