一种多参数化的有限状态机的实现

一种多参数化的有限状态机的实现

有限体（fsd）用于系统的动态行为建模，通常使用图像表中的状态图（状态chartdiagram）进行可视化，这是系统建模的强大工具。近20年来,FSM和状态图的形式化机制得到了很多扩展研究,有效地支持了各种复杂行为的建模,并应用于UML等面向对象建模方法中。FSM经扩展提供了很多高级特征,如组合状态、状态的进入动作和退出动作、转换动作、转换监护条件等,这些高级特征虽然便于复杂行为的建模,但是他们的实现往往存在复用性差,维护困难等问题。传统的FSM实现方法由于数据结构简单,不能清晰地表达FSM中的所有元素及元素间的关系,与状态图不能有效地形成映射机制,难以解决这些问题。结构化方法由于本身的缺陷使得FSM实现困难,代码难以重用,维护复杂;典型的面向对象FSM实现方法——State模式虽然解决了结构化方法中的一些不足,但是仍然没有显式地表达FSM中的所有元素,而将事件、转换等元素都作为状态类的方法来表达,实现与设计变化难以同步,依然存在复用性差和维护困难的问题。近年来,随着FSM的扩展研究及其在复杂反应式系统中的广泛应用,FSM传统实现方法存在的问题日益突出,因此必须基于面向对象技术研究提出一种更清晰的FSM结构框架,建立与状态图更直接的映射机制。通过FSM的形式化描述和对传统FSM实现方法的缺陷分析,提出了一种面向对象的高度结构化的FSM实现框架,不仅实现了灵活的复用机制,而且提高了系统的健壮性与可维护性。文中不仅给出了FSM的实现框架,而且给出了事件触发转换的调度算法。1监护条件的fsm文中定义的有限状态机FSM由状态、事件、转换和活动组成。每个状态有每个状态进入动作(entryaction)和1个状态退出动作(exitaction),每个转换有1个源状态和目标状态并且与1个事件相关联。当在源状态时,该事件发生且触发转换的监护条件为真,则顺序执行下列一些动作:(1)源状态的退出动作;(2)转换动作;(3)目标状态的进入动作。FSM可以形式化表示为1个五元组:M=(Q,Σ,T,δ,q0),其中,Q为有限状态集;Σ为有穷的事件输入集;T为非空的转换集合;δ为映射函数,δ=QxΣ→T;q0为初始状态,q0∈Q.T中的每个元素又可以表示为1个五元组,T=(Source-State,Target-State,Input-Event,Constraint,Action),其中“Source-State”和“Target-State”分别表示T的初始状态和目标状态,“Input-Event”表示来自于Σ的输入事件或为空,“Constraint”表示监护条件及输入事件参数等约束,Action表示转换执行的动作。2fkm的传统实现2.1状态转换的fsm过程模式是一种常用的实现FSM的结构化方法,它利用全局状态变量和嵌套的Case语句来实现。外层Case语句判断选择当前的状态,里面一层Case语句判断在相应状态下发生的事件,从而确定执行相应的转换动作。举1个简单的例子。房间里的恒温器开始处于状态Idle,若房间温度偏低则进行加热并转换到状态Heating,若偏高则进行降温并转换到状态Cooling;在状态Heating,若房间温度偏高则进行降温并转换到状态Cooling,若到达设定值则停止工作;同理在状态Cooling下,若房间温度偏低则进行加热并转换到状态Heating,若到达设定值则停止工作。图1所示是恒温器的状态图,描述了恒温器的状态转换情况。恒温器FSM面向过程的实现结构如下:switch(state){caseIdle:switch(event){casetooCold(expectTemp):…casetooHot(expectTemp):…default:…}break;caseHeating:switch(event){casetooHot(expectTemp):…caseatTemp:…default:…}break;caseCooling:switch(event){casetooCold(expectTemp):…caseatTemp:…default:…}break;default:…}从上例可以看出,代码可重用性差;状态的退出和进入动作在多个转换中都需要重写,当增加或改变一个状态时需要修改多个Case语句和改变若干个操作,可维护性差;对于复杂系统,由于存在很多状态和事件,代码量庞大,特别是存在组合状态时可能有很多层嵌套的Case语句,使得维护变得异常复杂。2.2恒温器fsm的系统模式State模式是一种典型的实现FSM的面向对象方法,它将所有与一个特定的状态相关的行为都放入一个State对象中,解决了上面过程模式中含有庞大的多分支条件语句的情况。图2所示是恒温器FSM的State模式结构,它解决了过程模式中存在的一些不足,通过继承可以容易地增加一个新状态,并在一定程度上实现了功能复用。但是State模式没有清晰地表达FSM中的所有元素,将事件和转换等元素隐含地作为State类的方法来描述,不仅使FSM的设计变化与实现难以清晰地对应起来,而且也使这些行为难以在其它状态和其它FSM中得到重用。另外,继承增加了类的数量,破坏了类的封装性,当增加一个事件或改变一个转换,将影响到多个类。因此,State模式依然不能有效地解决复用性差和维护复杂的问题。3反应式系统fsm的实现和发展State模式和过程模式的FSM实现方法都没有清晰地表达FSM中的所有元素及这些元素间的关系,使得FSM设计与实现难以直接映射起来,维护比较困难,也不能有效地实现功能复用和结构复用。为了克服传统FSM实现方法的上述问题,提出了一种面向对象的高度结构化的框架。该框架清晰地表达了FSM中状态、转换、事件及动作等元素,使FSM设计与实现建立直接的映射机制;状态类和转换类将转换动作、状态退出动作和进入动作从结构中分离出来,便于FSM的实例化及行为在其它状态和FSM中的重用;状态和转换对象的实现是基于接口写的,所以实现上存在较少的依赖关系,而且类和类继承层次会保持较小规模,容易管理维护;FSM中定义了一个状态转换表,当事件到达时通过索引当前状态及事件来方便地确定相应的转换。反应式系统由多个反应式对象组成,每个对象对应一个FSM,框架中引入了FSM的抽象类及一个任务管理类,很好地实现了FSM的实例化和事件调度管理机制。图3所示是反应式系统FSM的实现框架的类图,图中表达7个主要的类以及它们之间的关系。FSM:FSM的抽象类。定义了FSM的一些公共接口,维护了一个指向当前状态对象的引用,提供了FSM实例化时执行的初始化方法,设置状态变化的方法以及定义了一个事件处理接口handleEvent(Event*event)。ConcreteFSM:FSM的子类。定义了FSM对象的状态集、事件集及状态转换表等。FSMTask:任务管理类。负责FSM的实例化、数据配置和事件调度管理等,它定义了系统中FSM的列表及指向当前FSM的指针,监听事件队列eventQueue,事件监听函数waitEvent(eventQueue)通过操作系统的调用机制(Win32的WaitForMultipleObjects)对事件队列中的事件进行监听。Event:事件类。每个事件实例具有唯一的ID号,并维护一个指向目标FSM的指针,提供事件派遣方法。State:状态类。每个状态实例具有唯一的ID号,还有一个状态进入和退出动作等。Transition:转换类。每个转换实例对应一个目标状态,有一个监护条件判断方法和执行转换动作的方法。FSMAction:FSM所有动作的一个接口。FSM中状态的进入和退出动作、转换动作及FSM初始化动作都通过调用这个接口来实现。4基于监听的fsm对象事件监听图4是反应式系统FSM事件触发状态转换的一个简单顺序图,它描述了事件调度及FSM顺序执行一系列动作(源状态退出、转换动作、目标状态进入)的交互情况。下面给出事件触发转换的调度算法。FSMTask创建并初始化FSM对象,FSM对象向FSMTask注册要监听的事件,步骤为(1)FSMTask执行监听函数waitEvent(eventQueue),对事件队列中eventQueue中的事件进行监听。(2)若事件发生,则监听函数调用事件的派遣方法,发送事件到目标FSM对象。(3)目标FSM对象执行事件处理函数handleEvent(event),根据当前状态与事件在状态转换表中查找相应的转换对象。(4)若找到相应的转换对象,则往下执行,否则忽略事件并回到算法(2)。(5)执行转换对象的guard()函数,依次判断监护条件,若返回为真则往下执行,否则回到算法(2)。(6)依次执行当前状态的退出动作、相应的转换动作和目标状态的进入动作,并将目标状态设为当前状态,回到算法(2)。5fsm的设计相对于传统的FSM实现方法,文中提出的FSM实现框架具有如下特点:(1)利用面向对象方法清晰地表达了状态、转换、