Linux编程之有限状态机FSM的理解与实现
有限状态机（finite state machine）简称fsm，表示有限个状态及在这些状态之间的转移和动作等行为的数学模型，在计算机领域有着广泛的应用。fsm是一种逻辑单元内部的一种高效编程方法，在服务器编程中，服务器可以根据不同状态或者消息类型进行相应的处理逻辑，使得程序逻辑清晰易懂。
那有限状态机通常在什么地方被用到？
处理程序语言或者自然语言的 tokenizer,自底向上解析语法的parser，
各种通信协议发送方和接受方传递数据对消息处理，游戏ai等都有应用场景。
状态机有以下几种实现方法，我将一一阐述它们的优缺点。
一、使用if/else if语句实现的fsm
使用if/else if语句是实现的fsm最简单最易懂的方法，我们只需要通过大量的if /else if语句来判断状态值来执行相应的逻辑处理。
看看下面的例子，我们使用了大量的if/else if语句实现了一个简单的状态机，做到了根据状态的不同执行相应的操作，并且实现了状态的跳转。
//比如我们定义了小明一天的状态如下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; //状态的转移 } 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;}
看完上面的例子，大家有什么感受？是不是感觉程序虽然简单易懂，但是使用了大量的if判断语句，使得代码很低端，同时代码膨胀的比较厉害。这个状态机的状态仅有几个，代码膨胀并不明显，但是如果我们需要处理的状态有数十个的话，该状态机的代码就不好读了。
二、使用switch实现fsm
使用switch语句实现的fsm的结构变得更为清晰了，其缺点也是明显的：这种设计方法虽然简单，通过一大堆判断来处理，适合小规模的状态切换流程，但如果规模扩大难以扩展和维护。
int main(){ int state = get_up; //小明的一天 while (1) { switch(state) { case get_up: getup(); //具体调用的函数 state = go_to_school; //状态的转移 break; case go_to_school: go2school(); state = have_lunch; break; case have_lunch: havelunch(); state = go_home; break; ... default: break; } } return 0;}
三、使用函数指针实现fsm
使用函数指针实现fsm的思路：建立相应的状态表和动作查询表，根据状态表、事件、动作表定位相应的动作处理函数，执行完成后再进行状态的切换。
当然使用函数指针实现的fsm的过程还是比较费时费力，但是这一切都是值得的，因为当你的程序规模大时候，基于这种表结构的状态机，维护程序起来也是得心应手。
下面给出一个使用函数指针实现的fsm的框架：
我们还是以“小明的一天”为例设计出该fsm。
先给出该fsm的状态转移图：
下面讲解关键部分代码实现
首先我们定义出小明一天的活动状态
//比如我们定义了小明一天的状态如下enum{ get_up, go_to_school, have_lunch, do_homework, sleep,};
我们也定义出会发生的事件
enum{ event1 = 1, event2, event3,};
定义状态表的数据结构
typedef struct fsmtable_s{ int event; //事件 int curstate; //当前状态 void (*eventactfun)(); //函数指针 int nextstate; //下一个状态}fsmtable_t;
接下来定义出最重要fsm的状态表，我们整个fsm就是根据这个定义好的表来运转的。
fsmtable_t xiaomingtable[] ={ //{到来的事件，当前的状态，将要要执行的函数，下一个状态} { 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};
状态机的注册、状态转移、事件处理的动作实现
/*状态机注册*/void fsm_regist(fsm_t* pfsm, fsmtable_t* ptable){ pfsm->fsmtable = ptable;}/*状态迁移*/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; //标识是否满足条件 int i; /*获取当前动作函数*/ for (i = 0; i//当且仅当当前状态下来个指定的事件，我才执行它 if (event == pacttable[i].event && curstate == pacttable[i].curstate) { flag = 1; eventactfun = pacttable[i].eventactfun; nextstate = pacttable[i].nextstate; break; } } if (flag) //如果满足条件了 { /*动作执行*/ if (eventactfun) { eventactfun(); } //跳转到下一个状态 fsm_statetransfer(pfsm, nextstate); } else { // do nothing }}
主函数我们这样写，然后观察状态机的运转情况
int main(){ fsm_t fsm; initfsm(&fsm); int event = event1; //小明的一天,周而复始的一天又一天，进行着相同的活动 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;}
看一看该状态机跑起来的状态转移情况：
上面的图可以看出，当且仅当在指定的状态下来了指定的事件才会发生函数的执行以及状态的转移，否则不会发生状态的跳转。这种机制使得这个状态机不停地自动运转，有条不絮地完成任务。
与前两种方法相比，使用函数指针实现fsm能很好用于大规模的切换流程，只要我们实现搭好了fsm框架，以后进行扩展就很简单了（只要在状态表里加一行来写入新的状态处理就可以了）。
区块链用于食品供应链中，供应链运输中的任何时候能够监控和检查货物
基于SoPC的参数化TFT-LCD控制器IP核设计
智能电话机器人的优势是什么
每日分享：光纤布线小技巧
MP3采购注意事项
Linux编程之有限状态机FSM的理解与实现
智能手表的功能及用途_智能手表用处大不大
地磁传感器到底是什么？有什么样的应用
微压差传感器工作原理_微压差传感器安装
用于无线鼠标的无接触供电电路
戴森成就专业造型无限可能，先锋科技引领行业
电流反馈型OPA SC7508，压摆率5500V/μs，兼容AD8009
如何消除电磁干扰
5G版开启了下一个时代 接下来苹果该怎么继续增长？
魅族首款搭载后置三摄的手机魅族16Xs正式发布
基于各种用户自定义的测试数据序列来评估RF-DAC多频带发射器线性性能
32亿美元工业可穿戴设备市场，国产XR设备将大显身手
谁才是车上的“文艺青年”
区块链 打造新的创富神话
小米6最新真机配置曝光, 米5降至冰点价, 等新还是买旧?
那有限状态机通常在什么地方被用到？
处理程序语言或者自然语言的 tokenizer,自底向上解析语法的parser，
各种通信协议发送方和接受方传递数据对消息处理，游戏ai等都有应用场景。
状态机有以下几种实现方法，我将一一阐述它们的优缺点。
一、使用if/else if语句实现的fsm
使用if/else if语句是实现的fsm最简单最易懂的方法，我们只需要通过大量的if /else if语句来判断状态值来执行相应的逻辑处理。
看看下面的例子，我们使用了大量的if/else if语句实现了一个简单的状态机，做到了根据状态的不同执行相应的操作，并且实现了状态的跳转。
//比如我们定义了小明一天的状态如下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; //状态的转移 } 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;}
看完上面的例子，大家有什么感受？是不是感觉程序虽然简单易懂，但是使用了大量的if判断语句，使得代码很低端，同时代码膨胀的比较厉害。这个状态机的状态仅有几个，代码膨胀并不明显，但是如果我们需要处理的状态有数十个的话，该状态机的代码就不好读了。
二、使用switch实现fsm
使用switch语句实现的fsm的结构变得更为清晰了，其缺点也是明显的：这种设计方法虽然简单，通过一大堆判断来处理，适合小规模的状态切换流程，但如果规模扩大难以扩展和维护。
int main(){ int state = get_up; //小明的一天 while (1) { switch(state) { case get_up: getup(); //具体调用的函数 state = go_to_school; //状态的转移 break; case go_to_school: go2school(); state = have_lunch; break; case have_lunch: havelunch(); state = go_home; break; ... default: break; } } return 0;}
三、使用函数指针实现fsm
使用函数指针实现fsm的思路：建立相应的状态表和动作查询表，根据状态表、事件、动作表定位相应的动作处理函数，执行完成后再进行状态的切换。
当然使用函数指针实现的fsm的过程还是比较费时费力，但是这一切都是值得的，因为当你的程序规模大时候，基于这种表结构的状态机，维护程序起来也是得心应手。
下面给出一个使用函数指针实现的fsm的框架：
我们还是以“小明的一天”为例设计出该fsm。
先给出该fsm的状态转移图：
下面讲解关键部分代码实现
首先我们定义出小明一天的活动状态
//比如我们定义了小明一天的状态如下enum{ get_up, go_to_school, have_lunch, do_homework, sleep,};
我们也定义出会发生的事件
enum{ event1 = 1, event2, event3,};
定义状态表的数据结构
typedef struct fsmtable_s{ int event; //事件 int curstate; //当前状态 void (*eventactfun)(); //函数指针 int nextstate; //下一个状态}fsmtable_t;
接下来定义出最重要fsm的状态表，我们整个fsm就是根据这个定义好的表来运转的。
fsmtable_t xiaomingtable[] ={ //{到来的事件，当前的状态，将要要执行的函数，下一个状态} { 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};
状态机的注册、状态转移、事件处理的动作实现
/*状态机注册*/void fsm_regist(fsm_t* pfsm, fsmtable_t* ptable){ pfsm->fsmtable = ptable;}/*状态迁移*/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; //标识是否满足条件 int i; /*获取当前动作函数*/ for (i = 0; i//当且仅当当前状态下来个指定的事件，我才执行它 if (event == pacttable[i].event && curstate == pacttable[i].curstate) { flag = 1; eventactfun = pacttable[i].eventactfun; nextstate = pacttable[i].nextstate; break; } } if (flag) //如果满足条件了 { /*动作执行*/ if (eventactfun) { eventactfun(); } //跳转到下一个状态 fsm_statetransfer(pfsm, nextstate); } else { // do nothing }}
主函数我们这样写，然后观察状态机的运转情况
int main(){ fsm_t fsm; initfsm(&fsm); int event = event1; //小明的一天,周而复始的一天又一天，进行着相同的活动 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;}
看一看该状态机跑起来的状态转移情况：
上面的图可以看出，当且仅当在指定的状态下来了指定的事件才会发生函数的执行以及状态的转移，否则不会发生状态的跳转。这种机制使得这个状态机不停地自动运转，有条不絮地完成任务。
与前两种方法相比，使用函数指针实现fsm能很好用于大规模的切换流程，只要我们实现搭好了fsm框架，以后进行扩展就很简单了（只要在状态表里加一行来写入新的状态处理就可以了）。
区块链用于食品供应链中，供应链运输中的任何时候能够监控和检查货物
基于SoPC的参数化TFT-LCD控制器IP核设计
智能电话机器人的优势是什么
每日分享：光纤布线小技巧
MP3采购注意事项
Linux编程之有限状态机FSM的理解与实现
智能手表的功能及用途_智能手表用处大不大
地磁传感器到底是什么？有什么样的应用
微压差传感器工作原理_微压差传感器安装
用于无线鼠标的无接触供电电路
戴森成就专业造型无限可能，先锋科技引领行业
电流反馈型OPA SC7508，压摆率5500V/μs，兼容AD8009
如何消除电磁干扰
5G版开启了下一个时代 接下来苹果该怎么继续增长？
魅族首款搭载后置三摄的手机魅族16Xs正式发布
基于各种用户自定义的测试数据序列来评估RF-DAC多频带发射器线性性能
32亿美元工业可穿戴设备市场，国产XR设备将大显身手
谁才是车上的“文艺青年”
区块链 打造新的创富神话
小米6最新真机配置曝光, 米5降至冰点价, 等新还是买旧?