有限状态机的一种实现框架_W

1、第 10 卷第 5 期 2003 年 10 月 工 程 设 计 学 报 Journa l of Eng ineer ing D es ignV o l. 10 N o. 5 O ct. 2003有限状态机的一种实现框架 徐小良, 汪乐宇, 周 泓 (浙江大学 数字技术及仪器研究所, 浙江 杭州 310027)摘 要: 有限状态机(F SM ) 是对反应式系统建模的一种强大工具 虽然一些高级特征和可视化状态图的引入, 使F SM 的表达能力更强, 但是其实现往往存在复用性差, 维护困难等问题 传统的 F SM 实现模式, 如结构化方法和State 模式, 由于软件结构简单, 与状态图不能有效匹配

2、, 难以解决这些问题 通过引入良好的数据结构和触发机制, 提出了一种面向对象的高度结构化的 F SM 实现框架, 并给出了触发转换的调度算法 新框架清晰地表达了F SM 中的所有主要元素及它们之间的关系, 并将行为部分与结构部分相分离, 不仅改善了软件的灵活性和重用性, 而且提高了系统的健壮性与可维护性关键词: 有限状态机; 反应式系统; 实现框架; 状态模式 中图分类号: T P 23; T P 311文献标识码: A文章编号: 10062754X (2003) 0520251205Im plem en ta t ion fram ework of f in ite sta te mach

3、in esXU X iao 2liang,W AN G L e2yu, ZHOU Hong( In stitu te of D igital T echno logy & A dvanced In strum entat ion, Zhejiang U n iversity, H angzhou 310027, Ch ina)Abstract: F in ite state m ach ines (F SM s) p rovide a pow erfu l w ay fo r m odeling reactive system s. A lthough F SMhas stronger exp

4、 ressio n ab ility after it is ex tended w ith m any advanced featu res and visual statechart diagram s, it s imp lem en ta t io n often suffers from bad reu sab ility and m ain te2 nance p rob lem s. T he t radit io nal w ays fo r F SM imp lem en ta t io n, such as structu re app roach andstate pat

5、tern, do no t address these p rob lem s becau se their sof tw are structu res are too sim p le to m atch the statechart diagram s. By p roviding m o re structu re and even t2triggered m echan ism , a new ob ject2o rien ted F SM im p lem en ta t io n fram ew o rk is p resen ted as w ell as the even t

6、2d isp atch ing algo rithm. T he new sof tw are fram ew o rk exp licit ly describes all the co re elem en ts and associa2 t io n s be tw een these elem en ts in the F SM and separates the behav io r from the structu re. T here2 fo re, no t on ly can th is fram ew o rk m ake the sof tw are m o re reu

7、 sab le and f lex ib le, bu t also can im 2 p rove the m ain tenance and robu stness.Key words: f in ite state m ach ines; reactive system s; im p lem en ta t io n fram ew o rk s; state pattern有限状态机(F SM ) 1 3 用于对系统的动态行为建模, 一般用状态图( statechart diagram ) 来可视化表示, 是对反应式系统建模的强大工具近 20 年来, F SM 和状态图的形式化机制得

8、到了很多扩展研究, 有效地支持了各种复杂行为的建模, 并应用于UM L 等面向对象建模方法中F SM 经扩展提供了很多高级特征, 如组合状 态、状态的进入动作和退出动作、转换动作、转换监护条件等, 这些高级特征虽然便于复杂行为的建模, 但是他们的实现往往存在复用性差, 维护困难等问题 4 传统的F SM 实现方法由于数据结构简单, 不能清晰地表达 F SM 中的所有元素及元素间的关系, 与状态图不能有效地形成映射机制, 难以解决这些问题 结构化方法由于本身的缺陷使得F SM实 收稿日期: 2003203210.作者简介: 徐小良(1976- ) , 男, 浙江东阳人, 博士生, 从事自动测试系

9、统软件建模与可视化编程技术研究, E2m ail: zjuxxl sohu. com ;汪乐宇(1945- ) , 男, 浙江海宁人, 教授, 博士生导师, 从事测试计量技术研究; 周 泓(1974- ) , 男, 浙江绍兴人, 副教授, 博士, 从事虚拟仪器技术研究第 5 期徐小良, 等: 有限状态机的一种实现框架 257现困难, 代码难以重用, 维护复杂; 典型的面向对象F SM 实现方法Sta te 模式 5 虽然解决了结构化方法中的一些不足, 但是仍然没有显式地表达F SM 中的所有元素, 而将、转换等元素都作为状态类的方法来表达, 实现与设计变化难以同步, 依然存在复用性差和维护困难

10、的问题近年来, 随着 F SM 的扩展研究及其在复杂反应式系统中的广泛应用, F SM 传统实现方法存在的问题日益突出, 因此必须基于面向对象技术研究提出一种更清晰的F SM 结构框架 6 , 建立与状态图更直接的映射机制 通过F SM 的形式化描述和对传统 F SM 实现方法的缺陷分析, 提出了一种面向对象的高度结构化的F SM 实现框架, 不仅实现了灵活的复用机制, 而且提高了系统的健壮性与可维护性 文中不仅给出了F SM 的实现框架, 而且给出了 触发转换的调度算法 7 1 FSM 的形式化描述文中定义的有限状态机F SM 由状态、 、转换和活动组成 每个状态有每个状态进入动作(en2

11、t ry act io n) 和 1 个状态退出动作(ex it act io n) , 每个转换有 1 个源状态和目标状态并且与 1 个 相关联当在源状态时, 该 发生且触发转换的监护条件为真, 则顺序执行下列一些动作: (1) 源状态的退出动作; ( 2) 转换动作; ( 3) 目标状态的进入动作 F SM 可以形式化表示为 1 个五元组:M = (Q , 2 , T , , q0 ) ,其中, Q 为有限状态集; 2 为有穷的输入集; T 为非空的转换集合; 为映射函数, = Q x 2 T ; q0 为初始状态, q0 Q.T 中的每个元素又可以表示为 1 个五元组, T= ( Sou

12、 rce- State, T arget- State, Inpu t- Even t, Con strain t, A ct io n) , 其中“So u rce- State”和“T ar2 get- State”分别表示 T 的初始状态和目标状态,“Inpu t- Even t”表示来自于 2 的输入或为空, “Co n strain t”表示监护条件及输入参数等约束, A ct ion 表示转换执行的动作2 传统的 FSM 实现2. 1过程模式过程模式是一种常用的实现F SM 的结构化方法, 它利用全局状态变量和嵌套的Case 语句来实现 外层Case 语句判断选择当前的状态, 里面

13、一层Case 语句判断在相应状态下发生的, 从而确定执行相应的转换动作举 1 个简单的例子 房间里的恒温器开始处于状态 Id le, 若房间温度偏低则进行加热并转换到状态H eating, 若偏高则进行降温并转换到状态Coo l2 ing; 在状态H eating, 若房间温度偏高则进行降温并转换到状态Coo ling, 若到达设定值则停止工作; 同理在状态Coo ling 下, 若房间温度偏低则进行加热并转换到状态H eating, 若到达设定值则停止工作 图 1 所示是恒温器的状态图, 描述了恒温器的状态转换情况图 1 恒温器状态图F ig. 1 Statechart diagram fo

14、 r the rm o stat恒温器F SM 面向过程的实现结构如下: sw itch ( state) case Id le:sw itch (even t) case tooCo ld (expectT em p ) : case tooHo t (expectT em p ) : defau lt:b reak; case H eating:sw itch (even t) case tooHo t (expectT em p ) : case atT em p:defau lt:b reak; case Coo ling:sw itch (even t) case tooCo ld

15、(expectT em p ) : case atT em p:defau lt:b reak; defau lt: 从上例可以看出, 代码可重用性差; 状态的退出和进入动作在多个转换中都需要重写, 当增加或改变一个状态时需要修改多个Case 语句和改变若干个操作, 可维护性差; 对于复杂系统, 由于存在很多状态和, 代码量庞大, 特别是存在组合状态时可能有很多层嵌套的Case 语句, 使得维护变得异常复杂2. 2状态模式State 模式是一种典型的实现F SM 的面向对象方法, 它将所有与一个特定的状态相关的行为都放入一个 State 对象中, 解决了上面过程模式中含有 庞大的多分支条件语句

16、的情况图 2 所示是恒温器F SM 的State 模式结构, 它解决了过程模式中存在的一些不足, 通过继承可以容易地增加一个新状态, 并在一定程度上实现了功能复用但是State 模式没有清晰地表达F SM 中的所有元素, 将和转换等元素隐含地作为State 类的方法来描述, 不仅使F SM 的设计变化与实现难以清晰地对应起来, 而且也使这些行为难以在其它状态和其它F SM 中得到重用 另外, 继承增加了类的数量, 破坏了类的封装性, 当增加一个或改变一个转换, 将影响到多个类因此, State 模式依然不能有效地解决复用性差和维护复杂的问题图 2 状态模式F ig. 2 State patte

17、rn3 高度结构化的 FSM 实现框架State 模式和过程模式的F SM 实现方法都没有清晰地表达F SM 中的所有元素及这些元素间的关系, 使得F SM 设计与实现难以直接映射起来, 维护比较困难, 也不能有效地实现功能复用和结构复用的框架为了克服传统 F SM 实现方法的上述问题, 提 框架的类图, 图中表达 7 个主要的类以及它们之间的关系F SM : F SM 的抽象类定义了F SM 的一些公共接口, 维护了一个指向当前状态对象的引用, 提供了F SM 实例化时执行的初始化方法, 设置状态变化的方法以及定义了一个处理接口 handleEven t (Even t3 even t) 出

18、了一种面向对象的高度结构化 该框架清ConcreteF SM : F SM 的子类定义了F SM 对象晰地表达了 F SM 中状态、转换、 及动作等元素, 使F SM 设计与实现建立直接的映射机制; 状态类和转换类将转换动作、状态退出动作和进入动作从结构中分离出来, 便于F SM 的实例化及行为在其它状态和 F SM 中的重用; 状态和转换对象的实现是基于接口写的, 所以实现上存在较少的依赖关系, 而且类和类继承层次会保持较小规模, 容易管理维护; F SM 中定义了一个状态转换表, 当到达时通过索引当前状态及 来方便地确定相应的转换反应式系统由多个反应式对象组成, 每个对象对应一个F SM

19、, 框架中引入了F SM 的抽象类及一个任务管理类, 很好地实现了F SM 的实例化和调度管理机制图 3 所示是反应式系统F SM 的实现 的状态集、集及状态转换表等F SM T ask: 任务管理类 负责F SM 的实例化、数据配置和调度管理等, 它定义了系统中F SM 的列表及指向当前 F SM 的指针,队列even tQ ueue, 函 数 w aitEven t( even tQ ueue) 通过操作系统的调用机制(W in32 的W aitFo rM u lt ip leO b jects) 对 队列中的 进行 Even t: 类 每个实例具有唯一的 ID 号, 并维护一个指向目标F

20、 SM 的指针, 提供派遣方法State: 状态类 每个状态实例具有唯一的 ID号, 还有一个状态进入和退出动作等 图 3 FSM 的实现框架类图F ig. 3 C lass diagram fo r the F SM im p lem entat io n fram ew o rkT ran sit io n: 转换类 每个转换实例对应一个目标状态, 有一个监护条件判断方法和执行转换动作的方法F SM A ct io n: F SM 所有动作的一个接口 F SM 中状态的进入和退出动作、转换动作及 F SM 初始化动作都通过调用这个接口来实现4 触发转换调度算法图 4 是反应式系统F SM

21、触发状态转换的一个简单顺序图, 它描述了 调度及F SM 顺序执行一系列动作( 源状态退出、转换动作、目标状态进入) 的交互情况图 4 FSM 触发转换的简单顺序图F ig. 4 A sim p le sequence diagram fo r event2triggered t ransit io n in F SM下面给出触发转换的调度算法F SM T ask 创建并初始化 F SM 对象, F SM 对象向 F SM T ask 注册要的, 步骤为 (1) ) F SM T ask 执行 函数w aitEven t(2) 若发生, 则函数调用的派遣方法, 发送到目标F SM 对象(3)

22、目标 F SM 对象执行处理函数 han2 dleEven t (even t) , 根据当前状态与在状态转换 表中查找相应的转换对象(4) 若找到相应的转换对象, 则往下执行, 否则忽略 并回到算法(2) (5) 执行转换对象的guard () 函数, 依次判断监护条件, 若返回为真则往下执行, 否则回到算法(2) (6) 依次执行当前状态的退出动作、相应的转换动作和目标状态的进入动作, 并将目标状态设为当前状态, 回到算法(2) 5 结论相对于传统的 F SM 实现方法, 文中提出的 F SM 实现框架具有如下特点:(1) 利用面向对象方法清晰地表达了状态、转换、动作等 F SM 中的主要

23、元素及它们之间的关系, 在 F SM 的设计与实现之间建立了直接的映射机制(2) 将结构与行为分离, 并通过对象组合技术代替类继承而提高了软件的复用性和维护性(3) 提供了任务管理以及 触发转换的调度算法, 非常适合于反应式系统的描述与实现(4) 具有良好的扩展性, 通过扩展可以支持组合状态、历史状态、并发状态等 F SM 高级特征的表达, 不过需要提出更复杂的 调度派遣算法参考文献: 1 JAM ES R um baugh, IVA R Jacobson, GRAD Y Booch.T he U n if ied M od eling L ang uag e R ef erence M an

24、ualM . Bo ston: A ddison W esley, 1999. 2 OM G. OM G U n if ied M od eling L ang uag e Sp ecif ica tion (A ction S em antics) EB ?OL . h t tp: ?www. om g. o rg, 2002. 3 HA R EL D. Statecharts: a visual fo rm alism fo r comp lex system sJ . S cience of C om p u ter P rog ramm ing , 1987, 8: 231- 274. 4 J ILL ES van Gurp, JAN Bo sch. O n the im p lem entat io n o