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

時(shí)間：2021-08-19 15:28:48

關(guān)鍵字：有限狀態(tài)機(jī) 編程

手機(jī)看文章

掃描二維碼
隨時(shí)隨地手機(jī)看文章

[導(dǎo)讀]關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容來(lái)源：https://www.cnblogs.com/skyfsm/p/7071386.html作者：Madcola有限狀態(tài)機(jī)（finitestatemachine）簡(jiǎn)稱FSM，表示有限個(gè)狀態(tài)及在這些狀態(tài)之間的轉(zhuǎn)移和動(dòng)作等行為的數(shù)學(xué)模型，在計(jì)算機(jī)領(lǐng)域...

關(guān)注、星標(biāo)公眾號(hào)，直達(dá)精彩內(nèi)容

來(lái)源：https://www.cnblogs.com/skyfsm/p/7071386.html

作者：Madcola

有限狀態(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)。

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 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ā)生的事件

{
? ?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
? ?{
? ? ? ?//當(dāng)且僅當(dāng)當(dāng)前狀態(tài)下來(lái)個(gè)指定的事件，我才執(zhí)行它
? ? ? ?if (event == pActTable[i].event


                
            欲知詳情，請(qǐng)下載word文檔 下載文檔

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

阿維塔、賽力斯已入股！華為引望可能成“中國(guó)博世”

Trianz與AWS達(dá)成戰(zhàn)略合作協(xié)議，徹底改變?cè)撇捎煤凸芾矸绞?/a>

人工智能驅(qū)動(dòng)工具SODA V將顛覆汽車市場(chǎng)，使汽車開(kāi)發(fā)時(shí)間和成本降低90%

從容應(yīng)對(duì)未知風(fēng)險(xiǎn)----解密亞馬遜云科技的韌性之道

中國(guó)游戲市場(chǎng)開(kāi)始復(fù)蘇！騰訊、網(wǎng)易等巨頭縮減在日本投資

獨(dú)立自主！華為董事：致力打造不依賴西方的技術(shù)

華為張平安：數(shù)字世界話語(yǔ)權(quán)最終由生態(tài)繁榮決定！

中國(guó)通信服務(wù)公布2024年中期業(yè)績(jī)

NVI技術(shù)創(chuàng)新聯(lián)盟成立！自主生態(tài)將帶動(dòng)產(chǎn)業(yè)鏈高速發(fā)展

軟通動(dòng)力與長(zhǎng)三角投資達(dá)成戰(zhàn)略合作共謀數(shù)字生態(tài)新發(fā)展

海南區(qū)6家凱悅系酒店與嵐圖達(dá)成戰(zhàn)略合作，共同推動(dòng)新能源出行體驗(yàn)

安嵐攜手妮可?巴菲特開(kāi)啟療愈之旅在秋日紅葉的浪漫中療愈身心

不懼美國(guó)封鎖！華為：我們給大家提供系統(tǒng)、存儲(chǔ)等

尼爾森IQ深耕中國(guó)四十載，共繪未來(lái)新篇章

第二十二屆跨盈年度B2B營(yíng)銷高管峰會(huì)2025聚焦"營(yíng)銷競(jìng)?cè)?，打破市?chǎng)內(nèi)卷實(shí)現(xiàn)認(rèn)知進(jìn)化"

恒久動(dòng)力馳騁天地美孚1號(hào)攜手周冠宇邀您縱擎馳騁，勁享駕趣體驗(yàn)

美通社母公司Cision發(fā)布CisionOne平臺(tái)，進(jìn)軍亞太地區(qū)媒體監(jiān)測(cè)市場(chǎng)

移遠(yuǎn)通信推出大模型解決方案，重塑千行百業(yè)智能邊界

高途公布2024年第二季度未經(jīng)審計(jì)業(yè)績(jī)

華為發(fā)布AI百校計(jì)劃：培養(yǎng)AI人才每年獲最高100萬(wàn)支持