背景

机器人主控程序考虑使用QP框架1编写处理逻辑,可以通过编辑好的图形状态机生成C/C++代码,在这里补充一些状态机相关的知识。QP里面的状态机是statechart和flowchart的结合,其中的差别可以参考Wikipedia2。更详细的QP教程可以到官网下载电子书3

UML状态机速成

事件

事件的定义

事件是发生的影响系统的事情。严格来说,在 UML 规范中,[1] 术语事件是指事件的类型,而不是该事件的任何具体实例。例如,Keystroke 是键盘的一个事件,但每次按下一个键都不是一个事件,而是 Keystroke 事件的一个具体实例。另一个对键盘感兴趣的事件可能是 Power-on,但明天 10:05:36 打开电源只是 Power-on 事件的一个实例。

一个事件可以有关联的参数,允许事件实例不仅传达一些有趣事件的发生,而且还传达有关该事件的定量信息。例如,通过按下计算机键盘上的键生成的 Keystroke 事件具有相关的参数,这些参数传达字符扫描代码以及 Shift、Ctrl 和 Alt 键的状态。

一个事件实例比生成它的瞬时事件的寿命更长,并且可能将此事件传递给一个或多个状态机。一旦生成,事件实例就会经历一个处理生命周期,该生命周期最多可包含三个阶段。首先,事件实例在被接受并等待处理时被接收(例如,它被放置在事件队列中)。然后,事件实例被分派到状态机,此时它成为当前事件。最后,当状态机完成对事件实例的处理时,它会被消耗掉。已消费的事件实例不再可用于处理。

事件的类型

UML规范里面定义了四种事件,具体为:

  • SignalEvent: 代表特定的(异步)信号,格式为:signal_name(v1,v2…)。
  • TimeEvent: 对一个特定的最后期限建模。格式为:after 时间表达式
  • CallEvent: 代表同步调用请求。格式为:func_name(v1,v2…)
  • ChangeEvent: 对一个明确的boolean表达式为真的事件建模。格式为: when 表达式

在经典的FSM只有SignalEvent

事件的推迟

有时候,一个事件,在一个状态机正在某个状态中从而不能处理这个事件这种特别不方便的时刻到达。在很多情况下,事件的本性是它可以被(有限度的)推迟,直到系统进入到另一个状态,在那里它被更好的准备去处理这个原来的事件。

UML状态机提供了一个特定的机制,用来在状态里延迟事件。在每一个状态,你能包含一个deferred/[event list]。如果在当前状态的延迟事件列表中的一个事件出现,这个事件会被保留(延迟)给将来处理,直到进入到一个没有把它放在自己的延迟事件列表中的状态。在进入这种状态时,UML状态机将自动的恢复任何被保留的事件,不再延迟它们,而像它们刚刚到达一样处理它们。

有点类似像析构函数处理的异步操作

状态

每个状态机都有一个状态,它控制状态机对事件的反应。例如,当您敲击键盘上的键时,生成的字符代码将是大写或小写字符,具体取决于 Caps Lock 是否处于活动状态。因此,键盘的行为可以分为两种状态:“默认”状态和“caps_locked”状态。 (大多数键盘包含一个 LED,指示键盘处于“caps_locked”状态。)键盘的行为仅取决于其历史的某些方面,即是否按下了 Caps Lock 键,但不取决于,例如,关于之前按下了多少个以及确切地按下了哪些其他键。状态可以抽象出所有可能的(但不相关的)事件序列并仅捕获相关的事件序列。

在软件状态机(尤其是经典 FSM)的上下文中,状态一词通常被理解为单个状态变量,它只能假设有限数量的先验确定值(例如,在键盘的情况下为两个值,或更多通常-在许多编程语言中具有枚举类型的某种变量)。状态变量(和经典 FSM 模型)的思想是状态变量的值完全定义了系统在任何给定时间的当前状态。状态的概念将代码中识别执行上下文的问题简化为只测试状态变量而不是很多变量,从而省去了很多条件逻辑。

分层嵌套状态

FSM状态机

FSM状态机

HSM状态机

HSM状态机

UML状态机相对于传统FSM最重要的创新是引入了分层嵌套状态(这就是为什么状态图也称为分层状态机或HSM)。与状态嵌套相关的语义如下(见图 3): 如果一个系统处于嵌套状态,例如“result”(称为子状态),它也(隐含地)处于周围状态“on”(称为超级状态)。此状态机将尝试处理子状态上下文中的任何事件,从概念上讲,该子状态位于层次结构的较低级别。但是,如果子状态“result”没有规定如何处理事件,则事件不会像传统的“扁平”状态机那样被悄悄丢弃;相反,它是在超状态“on”的更高级别上下文中自动处理的。这就是系统处于“result”和“on”状态的含义。当然,状态嵌套不仅限于一级,事件处理的简单规则递归地适用于任何一级的嵌套。

包含其他状态的状态称为复合状态;相反,没有内部结构的状态称为简单状态。当嵌套状态不被任何其他状态包含时,它被称为直接子状态;否则,它被称为传递嵌套子状态。

因为复合状态的内部结构可以任意复杂,任何分层状态机都可以被视为某些(更高级别)复合状态的内部结构。将一个复合状态定义为状态机层次结构的最终根在概念上很方便。在UML规范中,每个状态机都有一个顶级状态(每个状态机层次结构的抽象根),它包含整个状态机的所有其他元素。 这种全封闭顶部状态的图形呈现是可选的。

扩展状态

然而,在实践中,将状态机的整个状态解释为单个状态变量很快就变得不切实际,除了非常简单的状态机之外的所有状态机。事实上,即使我们的机器状态中有一个32位整数,它也可能导致超过40亿种不同的状态——并且会导致过早的状态爆炸。这种解释是不切实际的,因此在UML状态机中,状态机的整个状态通常分为 (a)可枚举状态变量和 (b)所有其他变量,这些变量被命名为扩展状态。另一种看待它的方式是将可枚举状态变量解释为定性方面,将扩展状态解释为整个状态的定量方面。在这种解释中,变量的变化并不总是意味着系统行为的质量方面的变化,因此不会导致状态的变化。

以扩展状态变量为补充的状态机称为扩展状态机,UML状态机属于这一类。扩展状态机可以将底层形式主义应用于比实际复杂得多的问题,而不包括扩展状态变量。例如,如果我们必须在 FSM 中实现某种限制(例如,将键盘上的击键次数限制为1000),如果没有扩展状态,我们将需要创建和处理1000个状态——这是不切实际的;但是,通过扩展状态机,我们可以引入一个key_count变量,该变量被初始化为1000,并在每次击键时递减而不改变状态变量。

例如:

状态图

FSM有一个叫状态图 (state diagram) 的图型表达方法。这些图是有向图,节点代表状态,连接线代表状态转换。

在 UML 里,状态表示为圆角矩形,标签是状态名。转换被表示为箭头,标签是触发事件,它后面是可选需执行动作的列表。初始转换 (initial transistion) 从一个实心圆点出发,确定了当系统在最初开始时的启动状态。每个状态图必须有一个这样的转换,它不能带标签,因为这样的转换不需事件触发。初始转换能够带有关联的动作。

监护条件

监护条件(Guard conditions)(或简称监护)是基于扩展状态变量和事件参数的值动态评估的布尔表达式。 保护条件通过仅在评估为TRUE时启用操作或转换并在评估为FALSE时禁用它们来影响状态机的行为。 在UML表示法中,保护条件显示在方括号中(例如,图中的[key_count == 0])。

动作和过渡

(Actions and transitions)。当一个事件实例被分派时,状态机通过执行动作来响应,例如改变一个变量、执行 I/O、调用一个函数、生成另一个事件实例或改变到另一个状态。与当前事件相关的任何参数值都可用于由该事件直接引起的所有操作。

从一种状态切换到另一种状态称为状态转换,导致它的事件称为触发事件,或简称为触发器。在键盘示例中,如果按下CapsLock键时键盘处于“默认”状态,则键盘将进入“caps_locked”状态。但是,如果键盘已经处于“caps_locked”状态,按下CapsLock将导致不同的转换——从“caps_locked”状态到“默认”状态。在这两种情况下,按下CapsLock都是触发事件。

在扩展状态机中,转换可以有一个监护,这意味着只有当监护评估为TRUE时,转换才能“触发”。一个状态可以有许多响应于同一个触发器的转换,只要它们有不重叠的保护;然而,当共同触发发生时,这种情况可能会在警卫的评估顺序中产生问题。 UML 规范有意不规定任何特定的顺序;更确切地说,UML让设计人员承担了设计监护的责任,使得它们的评估顺序无关紧要。实际上,这意味着监护表达式应该没有副作用,至少不会改变对具有相同触发器的其他监护的评估。

运行到完成的执行模型

(Run-to-completion execution model)。所有的状态机体系,包括每个事件的处理。这个执行模型被称为运行-到-完成,或RTC。在RTC模型里,系统在分散的不可分割的RTC步骤里处理事件。新到的事件不能中断当前事件的处理,而且必须被存储(通常是存储在一个事件队列里),直到状态机又变成空闲。这些语义完全避免了在一个单一的状态机里的任何内部并发问题。 RTC模型也克服了处理和转换相关联的动作时的概念性问题,因为状态机在动作过程中没有处于一个明确定义的状态(在两个状态之间)。 在处理事件时,系统没有响应(不可观测性),因此在那个时段这种不清楚的状态没有实际的意义。然而请注意,RTC不意味着状态机必须独占CPU直到RTC步骤被完成。可抢占性约束只适用状态机在忙于处理事件的任务上下文的情况。在一个多任务处理环境里,其他(和繁忙的状态机的任务上下文无关的)任务也可以运行,可能抢占当前执行的状态机。只要其他状态机互相间不共享变量或其他资源,就不会有并发性的危险。 RTC处理的关键优点是简单。它最大的不利条件是状态机的响应由它最长的RTC步骤决定。为实现较短的RTC步骤常常会明显的让实时设计复杂化。

参考

其他资料

  1. https://en.wikipedia.org/wiki/UML_state_machine
  2. Harel statechart

  1. https://www.state-machine.com/↩︎

  2. https://en.wikipedia.org/wiki/State_diagram#State_diagrams_versus_flowcharts↩︎

  3. https://www.state-machine.com/psicc2↩︎