有限状态机的一种实现框架
第 10 卷第 5 期
2003 年 10 月
工 程 设 计 学 报
Journal of Eng ineering D esign
Vol. 10 No. 5
O ct. 2003
收稿日期: 2003203210.
作者简介: 徐小良(1976- ) , 男, 浙江东阳人, 博士生, 从事自动测试系统软件建模与可视化编程技术研究,
E2m ail: zjuxxl@ sohu. com;
汪乐宇(1945- ) , 男, 浙江海宁人, 教授, 博士生导师, 从事测试计量技术研究;
周 泓(1974- ) , 男, 浙江绍兴人, 副教授, 博士, 从事虚拟仪器技术研究L
有限状态机的一种实现框架
徐小良, 汪乐宇, 周 泓
(浙江大学 数字技术及仪器研究所, 浙江 杭州 310027)
摘 要: 有限状态机(FSM ) 是对反应式系统建模的一种强大工具L 虽然一些高级特征和可视化状态图的引入, 使
FSM 的表达能力更强, 但是其实现往往存在复用性差, 维护困难等问题L 传统的 FSM 实现模式, 如结构化方法和
State 模式, 由于软件结构简单, 与状态图不能有效匹配, 难以解决这些问题L 通过引入良好的数据结构和事件触发
机制, 提出了一种面向对象的高度结构化的 FSM 实现框架, 并给出了事件触发转换的调度算法L 新框架清晰地表
达了 FSM 中的所有主要元素及它们之间的关系, 并将行为部分与结构部分相分离, 不仅改善了软件的灵活性和重
用性, 而且提高了系统的健壮性与可维护性L
关键词: 有限状态机; 反应式系统; 实现框架; 状态模式
中图分类号: TP23; TP311 文献标识码: A 文章编号: 10062754X (2003) 0520251205
Implemen tation framework of f in ite state machines
XU X iao2liang,WAN G L e2yu, ZHOU Hong
( Institute of D igital Techno logy & A dvanced Instrum entation, Zhejiang U niversity, Hangzhou 310027, China)
Abstract: F inite state m achines (FSM s) p rovide a pow erful w ay fo r modeling reactive system s.
A lthough FSM has stronger exp ression ability after it is extended w ith m any advanced features
and visual statechart diagram s, its imp lem entation often suffers from bad reusability and m ainte2
nance p roblem s. The traditional w ays fo r FSM imp lem entation, such as structure app roach and
state pattern, do no t address these p roblem s because their softw are structures are too simp le to
m atch the statechart diagram s. By p roviding mo re structure and event2triggered m echanism , a
new object2o riented FSM imp lem entation fram ewo rk is p resented as w ell as the event2dispatching
algo rithm. The new softw are fram ewo rk exp licitly describes all the co re elem ents and associa2
tions betw een these elem ents in the FSM and separates the behavio r from the structure. There2
fo re, no t only can this fram ewo rk m ake the softw are mo re reusable and flexible, but also can im 2
p rove the m aintenance and robustness.
Key words: finite state m achines; reactive system s; imp lem entation fram ewo rks; state pattern
有限状态机(FSM ) [1～ 3 ] 用于对系统的动态行为
建模, 一般用状态图 (statechart diagram ) 来可视化
表示, 是对反应式系统建模的强大工具L近 20 年来,
FSM 和状态图的形式化机制得到了很多扩展研究,
有效地支持了各种复杂行为的建模, 并应用于
UM L 等面向对象建模方法中L
FSM 经扩展提供了很多高级特征, 如组合状
态、状态的进入动作和退出动作、转换动作、转换监
护条件等, 这些高级特征虽然便于复杂行为的建模,
但是他们的实现往往存在复用性差, 维护困难等问
题[4 ]L 传统的 FSM 实现方法由于数据结构简单, 不
能清晰地表达 FSM 中的所有元素及元素间的关
系, 与状态图不能有效地形成映射机制, 难以解决这
些问题L 结构化方法由于本身的缺陷使得 FSM 实
现困难, 代码难以重用, 维护复杂; 典型的面向对象
FSM 实现方法——State 模式[5 ] 虽然解决了结构化
方法中的一些不足, 但是仍然没有显式地表达 FSM
中的所有元素, 而将事件、转换等元素都作为状态类
的方法来表达, 实现与设计变化难以同步, 依然存在
复用性差和维护困难的问题L
近年来, 随着 FSM 的扩展研究及其在复杂反
应式系统中的广泛应用, FSM 传统实现方法存在的
问题日益突出, 因此必须基于面向对象技术研究提
出一种更清晰的 FSM 结构框架[6 ] , 建立与状态图更
直接的映射机制L 通过 FSM 的形式化描述和对传
统 FSM 实现方法的缺陷分析, 提出了一种面向对
象的高度结构化的 FSM 实现框架, 不仅实现了灵
活的复用机制, 而且提高了系统的健壮性与可维护
性L 文中不仅给出了 FSM 的实现框架, 而且给出了
事件触发转换的调度算法[7 ]L
1 FSM 的形式化描述
文中定义的有限状态机 FSM 由状态、事件、转
换和活动组成L 每个状态有每个状态进入动作(en2
try action) 和 1 个状态退出动作(exit action) , 每个
转换有 1 个源状态和目标状态并且与 1 个事件相关
联L当在源状态时, 该事件发生且触发转换的监护条
件为真, 则顺序执行下列一些动作: (1) 源状态的退
出 动作; (2) 转换动作; (3) 目标状态的进入动作L
FSM 可以形式化表示为 1 个五元组:
M = (Q , 2 , T , D, q0) ,
其中,Q 为有限状态集; 2 为有穷的事件输入集; T
为非空的转换集合; D 为映射函数, D= Q x 2 →T ; q0
为初始状态, q0∈Q.
T 中的每个元素又可以表示为 1 个五元组, T
= ( Source- State, Target- State, Input- Event,
Constraint, A ction) , 其中“Source- State”和“Tar2
get- State”分别表示 T 的初始状态和目标状态,
“Input- Event”表示来自于 2 的输入事件或为空,
“Constraint”表示监护条件及输入事件参数等约束,
A ction 表示转换执行的动作L
2 传统的 FSM 实现
2. 1 过程模式
过程模式是一种常用的实现 FSM 的结构化方
法, 它利用全局状态变量和嵌套的 Case 语句来实
现L 外层 Case 语句判断选择当前的状态, 里面一层
Case 语句判断在相应状态下发生的事件, 从而确定
执行相应的转换动作L
举 1 个简单的例子L 房间里的恒温器开始处于
状态 Idle, 若房间温度偏低则进行加热并转换到状
态 H eating, 若偏高则进行降温并转换到状态 Coo l2
ing; 在状态 H eating, 若房间温度偏高则进行降温并
转换到状态 Coo ling, 若到达设定值则停止工作; 同
理在状态 Coo ling 下, 若房间温度偏低则进行加热
并转换到状态 H eating, 若到达设定值则停止工作L
图 1 所示是恒温器的状态图, 描述了恒温器的状态
转换情况L
图 1 恒温器状态图
F ig. 1 Statechart diagram fo r thermo stat
恒温器 FSM 面向过程的实现结构如下:
sw itch (state) {
case Idle:
sw itch (event) {
case tooCo ld (expectTemp): ?
case tooHo t (expectTemp): ?
default: ?
}
break;
case H eating:
sw itch (event) {
case tooHo t (expectTemp): ?
case atTemp: ?
default: ?
}
break;
case Coo ling:
sw itch (event) {
case tooCo ld (expectTemp): ?
case atTemp: ?
default: ?
}
break;
default: ?
}
·252· 工 程 设 计 学 报 第 10 卷
从上例可以看出, 代码可重用性差; 状态的退出
和进入动作在多个转换中都需要重写, 当增加或改
变一个状态时需要修改多个 Case 语句和改变若干
个操作, 可维护性差; 对于复杂系统, 由于存在很多
状态和事件, 代码量庞大, 特别是存在组合状态时可
能有很多层嵌套的 Case 语句, 使得维护变得异常
复杂L
2. 2 状态模式
State 模式是一种典型的实现 FSM 的面向对象
方法, 它将所有与一个特定的状态相关的行为都放
入一个 State 对象中, 解决了上面过程模式中含有
庞大的多分支条件语句的情况L
图 2 所示是恒温器 FSM 的 State 模式结构, 它
解决了过程模式中存在的一些不足, 通过继承可以
容易地增加一个新状态, 并在一定程度上实现了功
能复用L但是 State 模式没有清晰地表达 FSM 中的
所有元素, 将事件和转换等元素隐含地作为 State
类的方法来描述, 不仅使 FSM 的设计变化与实现
难以清晰地对应起来, 而且也使这些行为难以在其
它状态和其它 FSM 中得到重用L 另外, 继承增加了
类的数量, 破坏了类的封装性, 当增加一个事件或改
变一个转换, 将影响到多个类L因此, State 模式依然
不能有效地解决复用性差和维护复杂的问题L
图 2 状态模式
F ig. 2 State pattern
3 高度结构化的 FSM 实现框架
State 模式和过程模式的 FSM 实现方法都没有
清晰地表达 FSM 中的所有元素及这些元素间的关
系, 使得 FSM 设计与实现难以直接映射起来, 维护
比较困难, 也不能有效地实现功能复用和结构复用L
为了克服传统 FSM 实现方法的上述问题, 提
出了一种面向对象的高度结构化的框架L 该框架清
晰地表达了 FSM 中状态、转换、事件及动作等元
素, 使 FSM 设计与实现建立直接的映射机制; 状态
类和转换类将转换动作、状态退出动作和进入动作
从结构中分离出来, 便于 FSM 的实例化及行为在
其它状态和 FSM 中的重用; 状态和转换对象的实
现是基于接口写的, 所以实现上存在较少的依赖关
系, 而且类和类继承层次会保持较小规模, 容易管理
维护; FSM 中定义了一个状态转换表, 当事件到达
时通过索引当前状态及事件来方便地确定相应的转
换L反应式系统由多个反应式对象组成, 每个对象对
应一个 FSM , 框架中引入了 FSM 的抽象类及一个
任务管理类, 很好地实现了 FSM 的实例化和事件
调度管理机制L图 3 所示是反应式系统 FSM 的实现
框架的类图, 图中表达 7 个主要的类以及它们之间
的关系L
FSM : FSM 的抽象类L定义了 FSM 的一些公共
接口, 维护了一个指向当前状态对象的引用, 提供了
FSM 实例化时执行的初始化方法, 设置状态变化的
方法以及定义了一个事件处理接口 handleEvent
(Event3 event) L
ConcreteFSM : FSM 的子类L定义了 FSM 对象
的状态集、事件集及状态转换表等L
FSM Task: 任务管理类L 负责 FSM 的实例化、
数据配置和事件调度管理等, 它定义了系统中 FSM
的列表及指向当前 FSM 的指针, 监听事件队列
eventQ ueue, 事 件 监 听 函 数 w aitEvent
(eventQ ueue) 通过操作系统的调用机制 (W in32 的
W aitFo rM ultip leO bjects) 对事件队列中的事件进行
监听L
Event: 事件类L 每个事件实例具有唯一的 ID
号, 并维护一个指向目标 FSM 的指针, 提供事件派
遣方法L
State: 状态类L 每个状态实例具有唯一的 ID
号, 还有一个状态进入和退出动作等L
·352· 第 5 期 徐小良, 等: 有限状态机的一种实现框架
图 3 FSM 的实现框架类图
F ig. 3 C lass diagram fo r the FSM imp lem entation fram ewo rk
T ransition: 转换类L 每个转换实例对应一个目
标状态, 有一个监护条件判断方法和执行转换动作
的方法L
FSM A ction: FSM 所有动作的一个接口L FSM
中状态的进入和退出动作、转换动作及 FSM 初始
化动作都通过调用这个接口来实现L
4 事件触发转换调度算法
图 4 是反应式系统 FSM 事件触发状态转换的
一个简单顺序图, 它描述了事件调度及 FSM 顺序
执行一系列动作 (源状态退出、转换动作、目标状态
进入) 的交互情况L
图 4 FSM 事件触发转换的简单顺序图
F ig. 4 A simp le sequence diagram fo r event2triggered transition in FSM
下面给出事件触发转换的调度算法LFSM Task
创建并初始化 FSM 对象, FSM 对象向 FSM Task
注册要监听的事件, 步骤为
(1) FSM Task 执行监听函数w aitEvent (even2
tQ ueue) , 对事件队列中 eventQ ueue 中的事件进行
监听L
(2) 若事件发生, 则监听函数调用事件的派遣
方法, 发送事件到目标 FSM 对象L
(3) 目标 FSM 对象执行事件处理函数 han2
dleEvent (event) , 根据当前状态与事件在状态转换
·452· 工 程 设 计 学 报 第 10 卷
表中查找相应的转换对象L
(4) 若找到相应的转换对象, 则往下执行, 否则
忽略事件并回到算法(2) L
(5) 执行转换对象的 guard () 函数, 依次判断监
护条件, 若返回为真则往下执行, 否则回到算法(2) L
(6) 依次执行当前状态的退出动作、相应的转
换动作和目标状态的进入动作, 并将目标状态设为
当前状态, 回到算法(2) L
5 结 论
相对于传统的 FSM 实现方法, 文中提出的
FSM 实现框架具有如下特点:
(1) 利用面向对象方法清晰地表达了状态、转
换、事件、动作等 FSM 中的主要元素及它们之间的
关系, 在 FSM 的设计与实现之间建立了直接的映
射机制L
(2) 将结构与行为分离, 并通过对象组合技术
代替类继承而提高了软件的复用性和维护性L
(3) 提供了任务管理以及事件触发转换的调度
算法, 非常适合于反应式系统的描述与实现L
(4) 具有良好的扩展性, 通过扩展可以支持组
合状态、历史状态、并发状态等 FSM 高级特征的表
达, 不过需要提出更复杂的事件调度派遣算法L
参考文献:
[ 1 ] JAM ES Rum baugh, IVAR Jacobson, GRADY Booch.
T he U nif ied M odeling L anguage R ef erence M anual
[M ]. Bo ston: A ddison W esley, 1999.
[2 ] OM G. OM G U nif ied M odeling L anguage Sp ecif ication
(A ction S em antics) [EB?OL ]. http: ??www. om g. o rg,
2002.
[3 ] HAREL D. Statecharts: a visual fo rm alism fo r comp lex
system s[J ]. S cience of Comp uter P rog ramm ing , 1987,
8: 231- 274.
[4 ] J ILL ES van Gurp, JAN Bo sch. O n the imp lem entation
of finite state m achines[A ]. P roceed ings of the IA S T 2
ED International Conf erence, 3rd A nnual IA S T ED In2
ternational Conf erence S of tw are E ng ineering and A pp li2
cations[C ]. Sco ttsdale, A rizona: IA STED 1999.
[ 5 ] GAMMA E, HELM R, JOHN SON R , et al. D esign
P atterns2E lem ents of R eusable O bject O riented sof tw are
[M ]. Bo ston: A ddison W esley, 1995.
[ 6 ] ROBERTS D , JOHN SON R. Patterns fo r evo lving
fram ewo rks [A ]. P attern L anguages of P rog ram D e2
sign 3[C ]. Bo ston: A ddison W esley, 1998.
[7 ] SCHM IDT D C. Reacto r: an object behavio r pattern fo r
concurrent event dm ultip lexing and event handler dis2
patching [A ]. P roceed ings of the F irst P attern L an2
guages of P rog ram s conf erence [C ]. M onticello, Illi2
no is: A ddison2W esley, 1995.
·552· 第 5 期 徐小良, 等: 有限状态机的一种实现框架
有限状态机的一种实现框架.pdf
