一、状态机描述
状态机理论最初的发展在数字电路设计领域。在数字电路方面,根据输出是否与输入信号有关,状态机可以划分为Mealy型和Moore型状态机;根据输出是否与输入信号同步,状态机可以划分为异步和同步状态机。而在软件设计领域,状态机设计的理论俨然已经自成一体。Moore型状态机的输出只和当前状态有关,和输入无关,如果在软件设计领域设计出这种类型的状态机,则该状态机接受的事件都是无内蕴信息的事件(输入)。Mealy型状态机的输入是由当前状态和输入共同决定,对应到软件设计领域,则该状态机接收的事件含有内蕴信息,并且影响状态机的输出。显然,这种划分在软件设计领域毫无意义。虽然软件设计领域的状态机也有同步和异步的划分,但和数字电路方面的同步异步已经不同。
除了《数字电路》,涉及到状态机的课程就是《编译原理》了(本人属计算机专业,其它专业是否涉及到状态机就不清楚了)。下面简单回顾一下《编译原理》里有关有限状态机的描述。在编译原理课程里面,对有限状态机的描述仅限在编译领域,特定状态,针对输入字符,发生状态改变,没有额外的行为,另编译原理里有限状态机的构成要素,还包含唯一的初始状态和一个终态集。数学语言描述如下:一个有限状态机M是一个五元组,M=(K,E,T,S,Z)。其中(1)K是一个有穷集,其中的每个元素称为状态(2)E是一个有穷字母表,它的每个元素称为一个输入字符(3)T是转换函数,是K×E->K上的映射(4)S是K中的元素,是唯一的一个初态(5)
Z是K的一个子集,是一个终态集,或者叫结束集。很明显,状态机在编译原理里的讲解已经特化,输入被定位为字符集,状态改变的时候没有额外动作发生。
与编译原理中的状态机不同,软件设计领域中通用状态机的输入不是字符集,而是被称作事件的结构(可以是结构体,也可以是类对象),并且特定的状态下,针对发生的事件,不仅发生状态改变,而且产生动作。借鉴编译原理中状态机的初始状态和终态,通用状态机的数学语言描述如下:一个通用有限状态机M是一个七元组,M={K,E,T,M,F,S,Z}。其中(1)K是一个有穷集,其中的每个元素称为状态(2)E是一个有穷集,它的每个元素称为一个事件(3)T是转换函数,是K×E->K上的映射(4)M是一个有穷集,它的每个元素称为动作(5)F是动作映射函数,是K×E->M上的映射(6)S是K中的元素,是唯一的一个初态(7)
Z是K的一个子集,是一个终态集,或者叫结束集。实用的状态机可以做进一步的优化,首先,可以把 (3)(5)整合在一起,做一个K×E->{K,M}的映射,其次从实用性的角度出发,禁止状态接收空事件(无输入的情况下,状态发生改变),作为弥补,为每个状态增加进入动作和离开动作,第三,鉴于定时器在系统中,尤其是在状态机中的重要性,可以为每个状态增加定时器以及超时后的状态转换。本文后面的讲述以及实现暂不考虑把定时器特化,如果需要,可以在状态的进入动作中初始化定时器(另:关于定时器,以后会写文章《系统设计之 定时器》)。
二、状态机分类(后文中如无特别说明,则状态机指软件设计领域的通用有限状态机)
依据状态之间是否有包含关系,分以下两种
(1)常规状态机。状态机中的所有状态是不相交的、互斥的。
(2)层次状态机。状态机中的状态之间要么是互斥的,要么是真包含的,可以用树性结构来描述这些状态集,包含其它状态的状态称为枝节点,不包含其它状态的状态称为叶节点,为方便单树描述,总是设计一个状态包含所有的状态节点,称为根节点。状态机的状态只能停留在叶节点,而不能停留在枝节点,每个枝节点需要指定一个子节点为它的默认子节点,以便状态机进入枝节点的时候能够停留到叶节点。
三、状态机实现
(1)switch/case if/else方式实现。用于少量状态(3个及其以下)的时候,不需要引入专门的状态机模块。这种方式不能编写通用的状态机模块,不再多说。
(2)面向过程方式:宏是实现面向过程方式的通用方式。虽然在状态机层面还是可以用面向对象的方式封装,这里还是把它称为面向过程的方式。
1.常规状态机模块实现。这个状态机涉及到机构由上而下为:
- 顶层结构是状态机:当前状态id,缺省操作,状态表,
- 状态表:状态数组
- 状态结构:状态id,状态名,进入操作,退出操作,缺省操作,状态事件表(数组)
- 状态事件结构:操作,事件,下一状态的id
状态机的算法是由状态机的结构决定的。实现如下:
#defineSINGLE_STATE_MAX_EVENT10
typedefintFSM_EVENT_ID;
typedefstructevent_param_st
{
FSM_EVENT_IDid;
union{
inti;
}data;
}FSM_EVENT;
typedefintFSM_STATE_ID;
typedefvoid(*FSM_FUNC)(FSM_EVENT*);
typedefstructstate_event_st
{
FSM_FUNCfunc;
FSM_EVENT_IDevent;
FSM_STATE_IDstate;
}FSM_STATE_EVENT;
typedefstructstate_st
{
FSM_STATE_IDid;
char*name;
FSM_FUNCenter_func;
FSM_FUNCexit_func;
FSM_FUNCdefault_func;
FSM_STATE_EVENTevent_table[SINGLE_STATE_MAX_EVENT];
}FSM_STATE;
typedefFSM_STATESTATE_TABLE[];
typedefFSM_STATE*PTR_STATE_TABLE;
#defineEND_EVENT_ID-1
#defineEND_STATE_ID-1
#defineBEGIN_FSM_STATE_TABLE(state_stable)staticSTATE_TABLEstate_stable={
#defineBEGIN_STATE(id,name,enter_func,exit_func,default_func){id,name,enter_func,exit_func,default_func,{
#defineSTATE_EVENT_ITEM(func,event,state){func,event,state},
#defineEND_STATE(id){NULL,END_EVENT_ID,END_STATE_ID}}},
#defineEND_FSM_STATE_TABLE(state_stable){END_STATE_ID,NULL,NULL,NULL,NULL,NULL}};
typedefstructfsm_st
{
FSM_STATE_IDstate_id;
FSM_FUNCdefault_func;
PTR_STATE_TABLEstate_tables;
}FSM;
voidfsm_do_event(FSM&fsm,FSM_EVENT&event)
{
FSM_STATE*state=&(fsm.state_tables[fsm.state_id]);
inti=0;
while(state->event_table[i].event!=END_EVENT_ID)
{
if(state->event_table[i].event==event.id)
break;
i++;
}
if(state->event_table[i].event!=END_EVENT_ID)
{
if(state->id!=state->event_table[i].state)
{
if(state->exit_func)
state->exit_func(&event);
}
if(state->event_table[i].func)
state->event_table[i].func(&event);
if(state->id!=state->event_table[i].state)
{
if(fsm.state_tables[state->event_table[i].state].enter_func)
fsm.state_tables[state->event_table[i].state].enter_func(&event);
fsm.state_id=state->event_table[i].state;
}
}
else
{
if(state->default_func)
state->default_func(&event);
else
{
if(fsm.default_func)
fsm.default_func(&event);
}
}
}
以上说明实现原理,有特殊需要的话可以自己定制状态机,比如上面的状态事件表数组的上限取的是单个状态中事件项的最大值,也可以定义为所有事件的个数,这样的话事件也不需要查询,可以象状态样直接定位,只是状态事件表会浪费一些存储空间。上面的FSM_EVENT仅仅是个例子,实际开发根据需要定义不同的union。上面的算法也是假定状态表的状态定义是从0开始,顺序递增的。
对外部调用而言,最后的状态机结构和事件执行的方法可以封装为对象。下面举例说明状态机的定义(事件和状态都应该是enum类型,这里直接使用数字,仅为说明问题而已)。
BEGIN_FSM_STATE_TABLE(my_state_table)
BEGIN_STATE(0,"first",enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm,1,1)
STATE_EVENT_ITEM(func_fsm,2,2)
END_STATE(0)
BEGIN_STATE(1,"second",enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm,1,2)
STATE_EVENT_ITEM(func_fsm,2,0)
END_STATE(1)
BEGIN_STATE(2,"third",enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm,1,0)
STATE_EVENT_ITEM(func_fsm,2,1)
END_STATE(2)
END_FSM_STATE_TABLE(my_state_table)
voidenter_fsm(FSM_EVENT*event)
{
printf("enterme\n");
}
voidexit_fsm(FSM_EVENT*event)
{
printf("exitme\n");
}
voiddefualt_fsm(FSM_EVENT*event)
{
printf("iamdefualt_fsm\n");
}
voidfunc_fsm(FSM_EVENT*event)
{
printf("iamfunc_fsm\n");
}
intmain()
{
printf("iammain\n");
FSMfsm={0,defualt_fsm,my_state_table};
printf("state[%d],name[%s]\n",fsm.state_id,fsm.state_tables[fsm.state_id].name);
FSM_EVENTevent;
event.id=1;
event.data.i=1;
fsm_do_event(fsm,event);
printf("state[%d],name[%s]\n",fsm.state_id,fsm.state_tables[fsm.state_id].name);
}
分享到:
相关推荐
我们在看程序设计相关书籍的时候,经常会看见:...最近在写一个单词解析的练习题,刚好是使用了函数指针来达到隔离变化,降低耦合的目的,本文将是对学习知识的一个记录,同时分享给每一个需要学习函数指针的同学们。
有关状态机设计方面的书籍,我这里隆重推荐一本:《Practical Statecharts in C/C++ Quantum Programming for Embedded Systems》,中文名叫做《嵌入式系统的微模块化程序设计-实用状态图C/C++实现》,北航出版的,...
Ragel是个有限状态机编译器,它将基于正则表达式的状态机编译成传统语言(C,C++,D,Java,Ruby等)的解析器。
2. 状态机解析HTTP请求 3. 心跳机制 4. 简易日志系统 主要内容: 1. 使用 socket 实现服务器和浏览器客户端的通信; 2. 用 epoll 事件检测技术实现 IO 多路复用,提高运行效率; 3. 采用模拟 Proacto r的事件处理...
(2)使用状态机解析HTTP请求报文,支持解析GET和POST请求; (3)访问服务器数据库实现web端用户注册、登录功能,可以请求播放服务器图片和视频文件; (4)实现同步/异步日志系统,记录服务器运行状态
Ragel是个有限状态机编译器,它将基于正则表达式的状态机编译成传统语言(C,C++,D,Java,Ruby等)的解析器。Ragel不仅仅可以用来解析字节流,它实际上可以解析任何可以用正则表达式表达出来的内容。而且可以很...
3.使用主从状态机作为逻辑单元解析HTTP请求报文; 4.使用定时器链表检测非活跃连接; 5.使用Webbench压力测试,可实现上万的并发连接数据交换; 代码基本上关键部分都加上了备注,源代码是参考的...
为了解析和验证JSON数据,使用了状态机(某种)。 主要思想很简单,但是这里的主要问题-状态机本身。 尽管有片刻,解析器仍满足所有(几乎)要求。 数据以其类型的字符串形式存储在对象中(以手动将它们转换为适当...
Bencode一个Bencode的非标准的C++实现。特点引入null值(使用'n'表示)以状态机方式实现解析提供基于流的接口
有限状态机实现。 实现的思考过程参考:http://blog.csdn.net/stevenkylelee/article/details/38309147
使用状态机解析HTTP请求报文,支持解析GET和POST请求 访问服务器数据库实现web端用户注册、登录功能,可以请求服务器图片和视频文件 实现同步/异步日志系统,记录服务器运行状态 经Webbench压力测试可以实现上万的...
ARP (Address Resolution Protocol)(地址解析協議) 12.IP地址的编码分为哪俩部分? IP地址由两部分组成,网络号和主机号。不过是要和“子网掩码”按位与上之后才能区分哪些是网络位哪些是主机位。 13.用户输入...
Visual C++程序开发范例宝典配套光盘,因大小受限,所以分成8部分上传,必须全部下载才能正常解压! 第1章 窗体与界面设计 1.1 菜单应用实例 实例001 在系统菜单中添加菜单项 实例002 带图标的程序菜单 实例003...
项目 4:端口扫描器。 实施者:Puneet Loya(用户名:ploya)和 Suprith Chandrashekharachar(用户名:suprchan) 该项目是在 C++11 中实现的。... Jobs.cpp:维护作业状态和作业队列的文件。 所需文件: CommonUtili
工业现场总线详解包含EtherCAT和CANopen等,详细介绍了PDO,SDO,状态机的机制。第一部
使用Qt C++ 开发的计算器小程序,采用解析器、状态机两种模式, 是个人学习设计模式后的总结,希望有所帮助。
Ragel是个有限状态机编译器,它将基于正则表达式的状态机编译成传统语言(C,C++,D,Java,Ruby等)的解析器。Ragel不仅仅可以用来解析字节流,它实际上可以解析任何可以用正则表达式表达出来的内容。而且可以很...
cc实例115 彩票抽奖机 3.12 OpenGL程序设计 cc实例116 制作OpenGL动画 cc实例117 利用OpenGL绘制立体模型 cc实例118 利用OpenGL绘制NURBS曲线 第4章 多媒体技术 4.1 动画 cc实例...
cc实例114 网络五子棋 cc实例115 彩票抽奖机 3.12 OpenGL程序设计 cc实例116 制作OpenGL动画 cc实例117 利用OpenGL绘制立体模型 cc实例118 利用OpenGL绘制NURBS曲线 第4章 多媒体技术 4.1 动画 cc...
状态机解析HTTP请求,目前支持 HTTP GET、HEAD方法 添加定时器支持HTTP长连接,定时回调handler处理超时连接 使用 priority queue 实现的最小堆结构管理定时器,使用标记删除,以支持惰性删除,提高性能 使用...