woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

函数指针构建状态机的经验

最近由于项目需要,开始研究状态机。其实原来就做过状态机相关的东西,毕竟在手机实时系统上状态是个很常见也很重要的东西。但是状态机的设计和实现的好坏直接影响整个系统的性能及可维护性。从设计上讲,无非是画状态图,理清各个状态之间的迁移关系;从编码上讲,对于非层次式有限状态自动机(FSM)一般有以下几种实现方法:

 

1、最简单的switch-case方法,设若干个变量保存当前状态,针对每个状态switch-case各种signal输入进行判断分别处理。说起来很容易理解,但是实际做起来却远不是这么简单。这种实现将所有状态的处理全部杂糅在一起,如果系统稍微复杂一些,那么维护起来将相当困难,我原来接触过的一个项目其中的主服务层的内部就有10多个变量标示各种不同类别的状态,十几层switch-caseif/else错综复杂,经常是一大段处理找不到他的输入signal在哪里,在什么情况下进行该处理。曾经安排我来维护这个,那个吐血...

 

2、状态表。以输入signal作索引,相应操作的函数指针和状态迁移作表元素,建立一个状态表。这样做的好处首先是速度快,完全避免了判断分支;所有状态迁移时的处理以独立函数的形式分离,在逻辑上比较清晰。但是该方法的缺点是即使可能某些状态并不接受某些signal输入,还是需要针对所有的signal输入和所有的状态列出所有可能的处理情况。并且由于c中没有现成的hash表,所以构造出的状态表通常是稀疏的,空间浪费比较大。另外由于将所有情况线性列举,如果对原状态图进行修改,在维护上也相对困难(需要在一个大的方阵中找出修改所影响的行列)。

 

3、状态模式。这个是基于面向对象的解决方法,基类中定义所有事件的处理接口,对于新状态通过派生基类的子类来扩展,在子类中重写该状态所涉及到的事件处理方法。这种方法可以很方便的扩展新状态,将不同状态处理独立开来,逻辑清晰。但是由于需要最大化基类接口数量,似乎不是很符合OO的设计原则,而且也需要枚举所有的signal输入,设计粒度太细。

 

4、不太好归纳该方法的名字,姑且叫综合方法吧。该方法综合了以上几种方法的优点,也是我比较欣赏的一种方法。该方法将着眼点从transition转移到state本身上来,以每个state作为粒度单位来设计。

定义一个状态管理变量currentState,保存当前状态处理的函数指针,同时定义init,destroy,trans等接口。对于新状态,只需新建一个状态处理函数,遵循接口

ret_value State1Handle( Signal )

{

    signal2:

        action2;

        trans(State2Handle);

    signal3:

        action3;

        trans(State3Handle);

    ....

}

trans中仅需要更改currentState的函数指针取值即可。

对于状态内的signal分发可以采用状态表(signal需可枚举)或简单的switch-case形式。

该方法避免了简单switch-case和状态表的处理堆叠的情况,状态转换非常高效(重新赋值状态处理指针),可以很方便的添加/删除/修改状态及处理(添加删除相应的状态处理函数及相关状态的处理即可),并且避免了signal处理接口的最大化,每个状态只处理所关心的signal输入。可以说这种方法最大限度的发挥了函数指针的灵活性。

 

以上所说的几种方法都针对非层次式状态机,也就是说对于某些共同的处理不能在宏观上加以综合,而只能在最小粒度上设计每个状态。而层次式状态机则允许有复合状态的出现,对于共通处理可以在父状态上进行而不必迁移到每一个子状态上。当子状态接收到一个共同处理时,可以将该处理throw给父状态,如果还不能处理就再次向上层throw。这种处理方法抽象程度更高,设计更加简洁。有一种量子模型是很好的层次式状态机的实现方式,不过由于此次项目尚未涉及层次式状态机,所以仅作了解。

 

越来越深的体会到了函数指针的强大了...

 

posted on 2009-03-21 14:50 肥仔 阅读(1196) 评论(1)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言

评论

# re: 函数指针构建状态机的经验  回复  更多评论   

用switch-case实现固定的状态机更好一点。
2009-03-21 23:16 | 陈梓瀚(vczh)

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理