下载掌阅APP，畅读海量书库
立即打开
1.状态机
状态机是描述系统状态与状态转换的一种形式化方法，是计算机科学的理论基础，也是一种强大的建模方法。在计算机科学中，状态机的使用非常普遍，尤其是在通信协议及实时嵌入式软件的建模及验证领域。
通常来说，一个系统的行为可以归为以下三种类型：
·简单行为：对于特定输入，系统总是确切地以同一种方式做出响应，与系统历史无关。
·连续行为：系统的当前状态依赖于历史，而且无法标识一个单独的状态。
·基于状态的行为：系统的当前状态依赖于历史，并且能够与其他系统状态清晰地区别开。
由于实时嵌入式软件大多基于状态，而有限状态机模型用触发事件和状态迁移描述系统的行为，因此适用于一般实时嵌入式软件的开发和测试的形式化描述。
传统的状态机是展示状态与状态转换的图，由状态、转换、事件、活动和动作5个部分组成：
·状态：表示一个模型在其生存期内的状况，如满足某些条件、执行某些操作或等待某些事件。一个状态的生存期是有限的时间段。
·转换：表示两个不同状态之间的联系，事件可以触发状态之间的转换。
·事件：在某个时间产生，可以触发状态转换，如信号、对象的创建和销毁以及超时和条件的改变等。
·活动：在状态机中进行的一个非原子的执行，由一系列动作组成。
·动作：一个可执行的原子计算，导致状态的变更或返回一个值。
利用状态机可以精确地描述对象的行为：从对象的初始状态起，开始响应事件并执行某些动作，这些事件引起状态的转换，对象在新的状态下又开始响应状态和执行动作，如此连续进行直到终结。在计算机科学中，状态机的使用非常普遍：在编译技术中，通常用有限状态机描述词法分析过程；在操作系统进程调度中，通常用状态机描述进程各个状态之间的转化关系；在面向对象分析与设计中，对象的状态、状态的转换、触发状态转换的事件、对象对事件的响应都可以用状态机来描述。
2.有限状态机
有限状态机（FSM）是状态机的一种，有限状态机模型是形式化模型的一种。一个有限状态机可以表示为一个六元组(S,S 0 ,δ,λ,I,O)：
·S：有限状态的集合。
·S 0 ：状态中的一种，是所有状态的初态。
·δ：状态转换函数。
·λ：输出函数。
·I：有限输入字符集。
·O：有限输出字符集。
按照FSM的性质，可具体划分如下：
·完全（Complete）有限状态机：对于一个FSM，如果对每一个状态和每一个输入，δ和λ都有定义，那么称为完全FSM，否则称为不完全（Incomplete）FSM。
·可重置（Reset Capacity）有限状态机：对于一个FSM，如果存在一个输入，对于任何一个状态，都能使该FSM转换至初始状态，则该FSM具有重置功能。
·初始化连通（Initially Connected）有限状态机：如果一个FSM可以从初始状态到达每一个状态，则称该FSM是初始化连通的。
·强连通（Strongly Connected）有限状态机：如果对于FSM中的每一对状态(S i ,S j )，都存在一个输入序列使得状态S i 可迁移到状态S j ，则称该FSM是强连通的。
按是否使用输入信号，有限状态机可以划分为：
·Mealy机：输出信号不仅与当前状态有关，而且还与所有的输入信号有关，即可以把Mealy型有限状态机的输出看成当前状态和所有输入信号的函数。
·Moore机：输出信号仅与当前状态有关，即可以把Moore型有限状态机的输出看成当前状态的函数。
按转换状态和输出是否确定，有限状态机可以划分为：
·DFSM：对于特定的输入和所有的状态，转换状态和输出是确定的。
·NFSM：对于特定的输出和已经存在的状态，转换状态和输出是不确定的。
有限状态机的表示法主要有三种：图形法、表格法和矩阵法，其中图形法较为常用。
有限状态机的优点是相对简单、可预测、易于实现和易于测试。有限状态机的缺点是：①处理复杂问题时，有可能发生状态空间爆炸；②在多有限状态机系统中，系统的状态为所有有限状态机状态的笛卡儿积，系统的状态数具有状态组合复杂性问题，且会出现死锁；③有限状态机可以较好地描述状态间的迁移特性，但不能很好地描述输入、输出间的变换特性（即数据的变换特性）；④有限状态机只反映了协议事件和协议状态之间的关系，不能表达其他协议元素，如协议变量、协议行为、谓词等。
3.扩展有限状态机
对有限状态机进行扩展的主要目的是增强有限状态机的描述能力并简化描述，使各状态之间的变化清晰化，最终提高对局部以致整个模型的描述与分析能力，可作为工具用于后续开发者的描述和解决方案。常见的扩展有限状态机模型有以下四种：NFSM（Non-deterministic FSM）、CFSM（Communicating FSM）、EFSM（Extended FSM）、CEFSM（Communicating EFSM）、PFSM（Probability FSM）。模型扩展的演变过程如图3-5所示。
图3-5 几种常见的FSM扩展模型
其中，EFSM是软件测试中相对较为常用的一种。一个EFSM可以表示为一个六元组<S,S 0 ,I,O,T,V>：
·S：非空的有限状态的集合。
·S 0 ：状态中的一种，是所有状态的初态。
·I：非空的输入消息集合。
·O：非空的输出消息集合。
·T：非空的状态迁移集合，且有t∈T，且t=<Head(t),I(t),P(t),operation/O(t),Tail(t)>。其中，Head(t)是迁移t的出发状态；I(t)是输入集I中包含的EFSM的输入消息，它可以为空；P(t)是迁移t执行的前置条件，它可以为空；operation是状态迁移过程中进行的操作，它一般由一系列的变量赋值语句或输出语句组成；O(t)是输出集O中包含的消息输出，它可以为空；Tail(t)是迁移t的到达状态。
·V：变量的集合，可表示为V=<IV,CV,OV>。其中，IV代表输入变量集合，输入变量可以由测试人员控制；OV代表输出变量集合；CV代表环境变量集合，环境变量可以是局部变量或全局变量，既不是输入变量也不是输出变量的变量都可以归为环境变量。CV和OV是不受测试人员控制的，它们的值由状态迁移的操作来确定。
由EFSM的定义可见，它在FSM模型的基础上增加了变量、操作、迁移的前置条件等。EFSM有存储功能，它的每个状态都有默认的重置（Reset）功能，即δ(S i ,r)=S 0 。通过EFSM模型，可更加精确地描述软件系统的行为，因此可广泛应用于面向对象软件系统中对象的行为以及对象之间的交互。EFSM较好地克服了上述FSM缺点中的后两点，但还没有解决一致性、可达性、同步等问题，并且引入了新的问题——不确定性问题。