为Linux应用构造有限状态机方法

为Linux应用构造有限状态机方法

有 限自动机（Finite Automata Machine）是计算机科学的重要基石，它在软件开发领域内通常被称作有限状态机（Finite State Machine），是一种应用非常广泛的软件设计模式（Design Pattern）。本文介绍如何构建基于状态机的软件系统，以及如何利用Linux下的工具来自动生成实用的状态机框架。

一、什么是状态机

有 限状态机是一种用来进行对象行为建模的工具，其作用主要是描述对象在它的生命周期内所经历的状态序列，以及如何响应来自外界的各种事件。在面向对象的软件 系统中，一个对象无论多么简单或者多么复杂，都必然会经历一个从开始创建到最终消亡的完整过程，这通常被称为对象的生命周期。一般说来，对象在其生命期内 是不可能完全孤立的，它必须通过发送消息来影响其它对象，或者通过接受消息来改变自身。在大多数情况下，这些消息都只不过是些简单的、同步的方法调用而 已。例如，在银行客户管理系统中，客户类（Customer）的实例在需要的时候，可能会调用帐户（Account）类中定义的getBalance() 方法。在这种简单的情况下，类Customer并不需要一个有限状态机来描述自己的行为，主要原因在于它当前的行为并不依赖于过去的某个状态。

遗 憾的是并不是所有情况都会如此简单，事实上许多实用的软件系统都必须维护一两个非常关键的对象，它们通常具有非常复杂的状态转换关系，而且需要对来自外部 的各种异步事件进行响应。例如，在VoIP电话系统中，电话类（Telephone）的实例必须能够响应来自对方的随机呼叫，来自用户的按键事件，以及来 自网络的信令等。在处理这些消息时，类Telephone所要采取的行为完全依赖于它当前所处的状态，因而此时使用状态机就将是一个不错的选择。

游 戏引擎是有限状态机最为成功的应用领域之一，由于设计良好的状态机能够被用来取代部分的人工智能算法，因此游戏中的每个角色或者器件都有可能内嵌一个状态 机。考虑RPG游戏中城门这样一个简单的对象，它具有打开（Opened）、关闭（Closed）、上锁（Locked）、解锁（Unlocked）四种 状态，如图1所示。当玩家到达一个处于状态Locked的门时，如果此时他已经找到了用来开门的钥匙，那么他就可以利用它将门的当前状态转变为 Unlocked，进一步还可以通过旋转门上的把手将其状态转变为Opened，从而成功地进入城内。

图1 控制城门的状态机JpVLinux联盟

在描述有限状态机时，状态、事件、转换和动作是经常会碰到的几个基本概念。

状态（State）　指的是对象在其生命周期中的一种状况，处于某个特定状态中的对象必然会满足某些条件、执行某些动作或者是等待某些事件。"

事件（Event）　指的是在时间和空间上占有一定位置，并且对状态机来讲是有意义的那些事情。事件通常会引起状态的变迁，促使状态机从一种状态切换到另一种状态。

转换（Transition）　指的是两个状态之间的一种关系，表明对象将在第一个状态中执行一定的动作，并将在某个事件发生同时某个特定条件满足时进入第二个状态。

动作（Action）　指的是状态机中可以执行的那些原子操作，所谓原子操作指的是它们在运行的过程中不能被其他消息所中断，必须一直执行下去。

二、手工编写状态机

与 其他常用的设计模式有所不同，程序员想要在自己的软件系统中加入状态机时，必须再额外编写一部分用于逻辑控制的代码，如果系统足够复杂的话，这部分代码实 现和维护起来还是相当困难的。在实现有限状态机时，使用switch语句是最简单也是最直接的一种方式，其基本思路是为状态机中的每一种状态都设置一个 case分支，专门用于对该状态进行控制。下面的代码示范了如何运用switch语句，来实现图1中所示的状态机：

　　
　　switch (state)　{
　　
　　　// 处理状态Opened的分支
　　　case (Opened): {
　　　　// 执行动作Open
　　　　open();
　　　　// 检查是否有CloseDoor事件
　　　　if (closeDoor()) { 
　　　　　// 当前状态转换为Closed
　　　　　changeState(Closed)
　　　　}
　　　　break;
　　　}
　　
　　　// 处理状态Closed的分支
　　　case (Closed): {
　　　　// 执行动作Close
　　　　close();
　　　　// 检查是否有OpenDoor事件
　　　　if (openDoor()) {
　　　　　// 当前状态转换为Opened
　　　　　changeState(Opened);
　　　　}
　　　　// 检查是否有LockDoor事件
　　　　if (lockDoor()) {
　　　　　// 当前状态转换为Locked
　　　　　changeState(Locked);
　　　　}
　　　　break;
　　　}
　　
　　　// 处理状态Locked的分支
　　　case (Locked): {
　　　　// 执行动作Lock
　　　　lock();
　　　　// 检查是否有UnlockDoor事件
　　　　if (unlockDoor()) {
　　　　　// 当前状态转换为Unlocked
　　　　　changeState(Unlocked);
　　　　}
　　　　break;
　　　}
　　
　　　// 处理状态Unlocked的分支
　　　case (Unlocked): {
　　　　// 执行动作Unlock
　　　　unlock();
　　　　// 检查是否有LockDoor事件
　　　　if (lockDoor()) {
　　　　　// 当前状态转换为Locked　　
　　　　　changeState(Locked)
　　　　}
　　　　// 检查是否有OpenDoor事件　　
　　　　if (openDoor()) {
　　　　　// 当前状态转换为Opened
　　　　　changeSate(Opened);
　　　　}
　　　　break;
　　　}
　　
　　}

JpVLinux联盟

三、自动生成状态机

为 实用的软件系统编写状态机并不是一件十分轻松的事情，特别是当状态机本身比较复杂的时候尤其如此，许多有过类似经历的程序员往往将其形容为"毫无创意"的 过程，因为他们需要将大量的时间与精力倾注在如何管理好状态机中的各种状态上，而不是程序本身的运行逻辑。作为一种通用的软件设计模式，各种软件系统的状 态机之间肯定会或多或少地存在着一些共性，因此人们开始尝试开发一些工具来自动生成有限状态机的框架代码，而在Linux下就有一个挺不错的选择 ──FSME（Finite State Machine Editor）。

图2 可视化的FSME

FSME 是一个基于Qt的有限状态机工具，它能够让用户通过图形化的方式来对程序中所需要的状态机进行建模，并且还能够自动生成用C++或者Python实现的状 态机框架代码。下面就以图1中城门的状态机为例，来介绍如何利用FSME来自动生成程序中所需要的状态机代码。

3.1状态机建模

首 先运行fsme命令来启动状态机编辑器，然后单击工具栏上" "New"按钮来创建一个新的状态机。FSME中用于构建状态机的基本元素一共有五种：事件（Event）、输入（Input）、输出（Output）、 状态（State）和转换（Transition），在界面左边的树形列表中可以找到其中的四种。

状态建模

在FSME 界面左边的树形列表中选择"States"项，然后按下键盘上的Insert键来插入一个新的状态，接着在右下方的"Name"文本框中输入状态的名称， 再在右上方的绘图区域单击该状态所要放置的位置，一个新的状态就创建好了。用同样的办法可以添加状态机所需要的所有状态。

图3 状态建模

事件建模

在FSME界面左边的树形列表中选" "Events"项，然后按下键盘上的Insert键来添加一个新的事件，接着在右下方的"Name"文本框中输入事件的名称，再单击"Apply"按钮，一个新的事件就创建好了。用同样的办法可以添加状态机所需要的所有事件。

图4 事件建模

状 态转换是整个建模过程中最重要的一个部分，它用来定义有限状态机中的一个状态是如何切换到另一个状态的。例如，当用来控制城门的状态机处于Opened状 态时，如果此时有Close事件产生，那么状态机的当前状态将切换到Closed状态，这样一个完整的过程在状态机模型中可以用closeDoor这样一 个转换来进行描述。

要 在FSME中添加这样一个转换，首先需要在界面左边的树形列表中选" "States"下的"Opened"项，然后按下键盘上的Insert键来添加一个新的转换，接着在右下角的"Name"文本框中输入转换的名字 "closeDoor"，在"Condition"文本框中输入"Close"表明触发该转换的条件是事件Close的产生，在"Target"下拉框中 选择"Closed"项表明该转换发生后状态机将被切换到Closed状态，最后再单击"Apply"按钮，一个新的状态转换关系就定义好了，如图5所 示。用同样的办法可以添加状态机所需要的所有转换。

图5 转换建模

3.2 生成状态机框架

使 用FSME不仅能够进行可视化的状态机建模，更重要的是它还可以根据得到的模型自动生成用C++或者Python实现的状态机框架。首先在FSME界面左 边的树形列表中选择"Root"项，然后在右下角的"Name"文本框中输入状态机的名字"DoorFSM"，再从"Initial State"下拉列表中选择状态"Opened"作为状态机的初始化状态。

图6 设置初始属性

在将状态机模型保存为door.fsm文件之后，使用下面的命令可以生成包含有状态机定义的头文件：

　　[xiaowp@linuxgam" code]$ fsmc door.fsm -d -o DoorFSM.

进一步还可以生成包含有状态机实现的框架代码：

　　[xiaowp@linuxgam code]$ fsmc door.fsm -d -impl DoorFSM.h -o DoorFSM.cpp

　　

如果想对生成的状态机进行验证，只需要再手工编写一段用于测试的代码就可以了：

　　/* 
　　 * TestFSM.cpp
　　 * 测试生成的状态机框架
　　 */
　　
　　#include "DoorFSM.h"
　　
　　int main() 
　　{
　　　DoorFSM door;
　　　door.A(DoorFSM::Close);
　　　door.A(DoorFSM::Lock);
　　　door.A(DoorFSM::Unlock);
　　　door.A(DoorFSM::Open);
　　}