有限状态机FSM思想广泛应用于硬件控制电路设计,也是软件上常用的一种处理方法(软 件上称为FMM--有限消息机)。它把复杂的控制逻辑分解成有限个稳定状态,在每个状态
上判断事件,变连续处理为离散数字处理,符合计算机的工作特点。同时,因为有限状 态机具有有限个状态,所以可以在实际的工程上实现。但这并不意味着其只能进行有限
次的处理,相反,有限状态机是闭环系统,有限无穷,可以用有限的状态,处理无穷的 事务。
有限状态机的工作原理如图1所示,发生事件(event)后,根据当前状态(cur_state) ,决定执行的动作(action),并设置下一个状态号(nxt_state)。
-------------
|
|-------->执行动作action
发生事件event ----->| cur_state
|
|
|-------->设置下一状态号nxt_state
-------------
当前状态
图1 有限状态机工作原理
e0/a0
--->--
| |
-------->----------
e0/a0 |
| S0 |-----
| -<------------
| e1/a1
| | e2/a2
V
----------
----------
| S2 |-----<-----|
S1 |
---------- e2/a2 ----------
图2 一个有限状态机实例
--------------------------------------------
当前状态 s0
s1 s2
| 事件
--------------------------------------------
a0/s0 --
a0/s0 | e0
--------------------------------------------
a1/s1 --
-- | e1
--------------------------------------------
a2/s2 a2/s2
-- | e2
--------------------------------------------
表1 图2状态机实例的二维表格表示(动作/下一状态)
图2为一个状态机实例的状态转移图,它的含义是:
在s0状态,如果发生e0事件,那么就执行a0动作,并保持状态不变;
如果发生e1事件,那么就执行a1动作,并将状态转移到s1态;
如果发生e2事件,那么就执行a2动作,并将状态转移到s2态;
在s1状态,如果发生e2事件,那么就执行a2动作,并将状态转移到s2态;
在s2状态,如果发生e0事件,那么就执行a0动作,并将状态转移到s0态;
有限状态机不仅能够用状态转移图表示,还可以用二维的表格代表。一般将当前状 态号写在横行上,将事件写在纵列上,如表1所示。其中“--”表示空(不执行动作,也
不进行状态转移),“an/sn”表示执行动作an,同时将下一状态设置为sn。表1和图2表示 的含义是完全相同的。
观察表1可知,状态机可以用两种方法实现:竖着写(在状态中判断事件)和横着写( 在事件中判断状态)。这两种实现在本质上是完全等效的,但在实际操作中,效果却截然
不同。
==================================
竖着写(在状态中判断事件)C代码片段
==================================
cur_state = nxt_state;
switch(cur_state){
//在当前状态中判断事件
case s0:
//在s0状态
if(e0_event){
//如果发生e0事件,那么就执行a0动作,
并保持状态不变;
执行a0动作;
//nxt_state = s0;
//因为状态号是自身,所以可以删除此句
,以提高运行速度。
}
else if(e1_event){
//如果发生e1事件,那么就执行a1动作,
并将状态转移到s1态;
执行a1动作;
nxt_state = s1;
}
else if(e2_event){
//如果发生e2事件,那么就执行a2动作,
并将状态转移到s2态;
执行a2动作;
nxt_state = s2;
}
break;
case s1:
//在s1状态
if(e2_event){
//如果发生e2事件,那么就执行a2动作,
并将状态转移到s2态;
执行a2动作;
nxt_state = s2;
}
break;
case s2:
//在s2状态
if(e0_event){
//如果发生e0事件,那么就执行a0动作,
并将状态转移到s0态;
执行a0动作;
nxt_state = s0;
}
}
==================================
横着写(在事件中判断状态)C代码片段
==================================
//e0事件发生时,执行的函数
void e0_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0:
//观察表1,在e0事件发生时,s1处为空
case s2:
执行a0动作;
*nxt_state = s0;
}
}
//e1事件发生时,执行的函数
void e1_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0:
//观察表1,在e1事件发生时,s1和s2处为
空
执行a1动作;
*nxt_state = s1;
}
}
//e2事件发生时,执行的函数
void e2_event_function(int * nxt_state)
{
int cur_state;
cur_state = *nxt_state;
switch(cur_state){
case s0:
//观察表1,在e2事件发生时,s2处为空
case s1:
执行a2动作;
*nxt_state = s2;
}
}
上面横竖两种写法的代码片段,实现的功能完全相同,但是,横着写的效果明显好于竖着写的效果。理由如下:
1、竖着写隐含了优先级排序(其实各个事件是同优先级的),排在前面的事件判断将毫无疑问地优先于排在后面的事件判断。这种if/else
if写法上的限制将破坏事件间原有的关系。而横着写不存在此问题。
2、由于处在每个状态时的事件数目不一致,而且事件发生的时间是随机的,无法预 先确定,导致竖着写沦落为顺序查询方式,结构上的缺陷使得大量时间被浪费。对于横
着写,在某个时间点,状态是唯一确定的,在事件里查找状态只要使用switch语句,就 能一步定位到相应的状态,延迟时间可以预先准确估算。而且在事件发生时,调用事件
函数,在函数里查找唯一确定的状态,并根据其执行动作和状态转移的思路清晰简洁, 效率高,富有美感。
总之,我个人认为,在软件里写状态机,使用横着写的方法比较妥帖。
竖着写的方法也不是完全不能使用,在一些小项目里,逻辑不太复杂,功能精简,同时为了节约内存耗费,竖着写的方法也不失为一种合适的选择。
在FPGA类硬件设计中,以状态为中心实现控制电路状态机(竖着写)似乎是唯一的选择,因为硬件不太可能靠事件驱动(横着写)。不过,在FPGA里有一个
全局时钟,在每次上升沿时进行状态切换,使得竖着写的效率并不低。虽然在硬件里竖着写也要使用IF/ELSIF这类查询语句(用VHDL开发),但他们映
射到硬件上是组合逻辑,查询只会引起门级延迟(ns量级),而且硬件是真正并行工作的,这样竖着写在硬件里就没有负面影响。因此,在硬件设计里,使用竖着
写的方式成为必然的选择。这也是为什么很多搞硬件的工程师在设计软件状态机时下意识地只使用竖着写方式的原因,盖思维定势使然也。
TCP和PPP框架协议里都使用了有限状态机,这类软件状态机最好使用横着写的方式实现。以某TCP协议为例,见图3,有三种类型的事件:上层下达的命令事件;下层到达的标志和数据的收包事件;超时定时器超时事件。
上层命令(open,close)事件
-----------------------------------
--------------------
| TCP
| <----------超时事件timeout
--------------------
RST/SYN/FIN/ACK/DATA等收包事件
图3 三大类TCP状态机事件
图
3可知,此TCP协议栈采用横着写方式实现,有3种事件处理函数,上层命令处理函数(如tcp_close);超时事件处理函数(tmr_slow);下
层收包事件处理函数(tcp_process)。值得一提的是,在收包事件函数里,在各个状态里判断RST/SYN/FIN/ACK/DATA等标志(这
些标志类似于事件),看起来象竖着写方式,其实,如果把包头和数据看成一个整体,那么,RST/SYN/FIN/ACK/DATA等标志就不必被看成独立
的事件,而是属于同一个收包事件里的细节,这样,就不会认为在状态里查找事件,而是总体上看,是在收包事件里查找状态(横着写)。
在PPP里更是到处都能见到横着写的现象,有时间的话再细说。我个人感觉在实现PPP框架协议前必须了解横竖两种写法,而且只有使用横着写的方式才能比较完美地实现PPP。
相关推荐
说到单片机编程,不得不说到状态机,状态机做为软件编程的主要架构已经在各种语言中应用,当然包括C语言,在一个思路清晰而且高效的程序中,必然有状态机的身影浮现。灵活的应用状态机不仅是程序更高效,而且可读性...
verilog有限状态机实验报告(附源代码).pdfverilog有限状态机实验报告(附源代码).pdfverilog有限状态机实验报告(附源代码).pdfverilog有限状态机实验报告(附源代码).pdfverilog有限状态机实验报告(附源代码)....
1、资源内容:Java工程示例的SMC - 状态机的基本格式说明及使用示例; 2、应用场景:SMC可以通过一个配置文件,生成有限状态机所需的所有状态类以及状态机类,同时还包括了所有的状态间的转换逻辑。 3、参考链接:...
同步状态机的原理、结构和设计.ppt 实验三:状态机编程 (1).pdf 实验三:状态机编程.pdf 操作系统课程设计报告-基于时间片的轮转调度算法.doc 时间片轮转法进行CPU调度.doc 时间片轮转法进行CPU调度算法实验....
有限状态机有限状态机有限状态机有限状态机有限状态机有限状态机
在LabVIEW中进行程序框架设计,似乎只见到过一种框架,那就是状态机,(并行的算不算?)还有“主/从设计模式”、“生产/消费模式”之类的,但好像也是建立在状态机的基础上的。如果真是这样的话,状态机就成了唯一...
前言 背景 内外事件 事件数据 状态转变 状态机模块 电机实例 外部事件 州数 状态函数 状态图 状态机对象 过渡图 新的状态机步骤 状态引擎 生成事件 不使用堆 离心机测试实例 多线程安全
Python实现,根据状态表生成C代码的【层次状态机】,亦可退化成【平面状态机】。使用C模拟C++的一些特性。 2009.12.3: 里面有readme,在研究之前先读一下。 对于号称“专业研究。。。”的fazai001(无激发)同学,...
现在大家比较统一的观点是,状态机的写法应该是用三段式写法,即第一部分说明初始状态,current_state,第二部分是状态机的状态转化的描述,第三部分是每一步状态的组合逻辑的描述。这样写调理更加清晰,也更加利于...
通用有限状态机(FSM: Finite-state machine)自动代码生成器. 可以根据配置文件,自动生成状态机代码(C++)。配置文件中只需要定义状态,跃迁条件。然后完善每个状态的动作即可。省去开发过程中手写状态机的麻烦。...
在8051单片机内实现列表型的状态机。如果你需要更多的状态转移,你只需要将任务函数加入到列表里面即可。里面还附带了电路图
二段式状态机,状态转换,还是有毛刺的。
qt中,关于并发状态机,满足两个子状态都结束才能向父状态的下一个状态切换的实例,本人亲测有效。 在用qt状态机的时候,往往会遇到一个问题,就是在实际任务执行中,我们不希望两个并行的任务,其中一个结束,就...
有限状态机VHDL模板 FPGA开发实用模板
通过按键状态机方式实现多个按键扫描,具有短按,长按,释放检测功能
状态机是计算机网络通信的重要内容,想要对tcp-ip协议栈加深了解的朋友尤其需要重点掌握,状态机的使用,统计字符串中单词的个数
状态机简介 函数指针实现FSM 代码实现步骤 附代码 测试程序 总结
本程序使用定时器,运用状态机的思想,实现了单按键的单击长按操作。 代码简洁规范,可读性强,移植性强。 实验器材: 自制开发板,STM32F03C8T6平台 实验目的: 学习定时器中断、按键使用。实现单击双击长按操作 ...
如何在verdi中直接查看状态机的状态名 同样适用于debussy
管理订单状态,该上状态机吗?轻量级状态机COLA StateMachine保姆级入门教程.doc