-------------
| |-------->执行动作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/EL SIF这类查询语句(用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_proce ss)。值得一提的是,在收包事件函数里,在各个状态里判断RST/SYN/FIN/ACK/DATA等标 志(这些标志类似于事件),看起来象竖着写方式,其实,如果把包头和数据看成一个整 体,那么,RST/SYN/FIN/ACK/DATA等标志就不必被看成独立的事件,而是属于同一个收 包事件里的细节,这样,就不会认为在状态里查找事件,而是总体上看,是在收包事件 里查找状态(横着写)。在PPP里更是到处都能见到横着写的现象,有时间的话再细说。我个人感觉在实现PP
P框架协议前必须了解横竖两种写法,而且只有使用横着写的方式才能比较完美地实现PP P。版权声明:本文为博主原创文章,未经博主允许不得转载。