发布时间 : 星期四 文章用状态机原理进行软件设计更新完毕开始阅读
用状态机原理进行软件设计
池元武
展讯通信(上海)有限公司，PLD，上海
摘要：本文描述状态机基础理论，以及运用状态机原理进行软件设计和实现的方法。 关键词：有限状态机 层次状态机 面向对象分析 行为继承
参考文献
[1] Miro Samek, Ph.D
《Practical Statecharts in C/C++ Quantum Programming for Embedded Systems》 [2] OpenFans
http://www.openfans.net/viewArticle.html?id=289
缩略语
名称 FSM HSM OOP UML LSP PoC
描述 Finite State Machine Hierarchical State Machine Object Oriented Programming Unified Modeling Language Liskov Substitution Principle push to talk over cellular 目录
第1章 引言 ............................................................................................................................. 3 第2章 FSM概念 .................................................................................................................... 3
2.1 FSM定义 .................................................................................................................... 3 2.2 FSM要素 .................................................................................................................... 3 2.3 FSM图示 .................................................................................................................... 4 第3章 FSM设计方法 ............................................................................................................ 5
3.1 C Parser(注释分析程序) ............................................................................................ 5 3.2 Calc(计算器)程序举例 ............................................................................................... 6 第4章 HSM概念 ................................................................................................................. 11
4.1 programming-by-difference（按照差异编程） ...................................................... 11 4.2 HSM图示 ................................................................................................................. 12 4.3 HSM分析和OOP分析 ........................................................................................... 12 第5章 HSM设计方法 ......................................................................................................... 14
5.2 继承关系是否合理 .................................................................................................. 15 第6章 HSM在实际工程的应用 ......................................................................................... 17
6.1 PoC Audio Player ...................................................................................................... 17 6.2 PoC Call Control ....................................................................................................... 18 第7章 FSM实现 .................................................................................................................. 19
7.1 nested switch statement（嵌套switch语句） ......................................................... 20 7.2 state table(状态表) .................................................................................................... 22 7.3 Function Address As State(用函数指针作为状态) .................................................. 23 7.4 QFSM frame(QFSM框架) ....................................................................................... 25 第8章 HSM实现 ................................................................................................................. 28 第9章 附录 ........................................................................................................................... 31
第1章 引言
20多年以前，David Harel创造了状态机理论来描述复杂的交互系统。随后，状态机理论赢得了广泛的接受，并且被引入到许多软件系统中，最突出的是被引入到UML中作为其一个组成部分。
不过，状态机理论的发展却很缓慢。在众多原因中，状态机只是作为编程的实现工具而不是设计工具是一个最重要的原因。
本文的重点就在于，怎样利用状态机原理进行程序设计。本文会先给出普通的、一个平面上的FSM（有限状态机）的概念和实例，并指出其中的一些缺点，然后引出本文的重点HSM（层次状态机）的概念和设计方法。为了使本文既可以作为设计方法的参考，又可以作为实现方法的参考，本文会给出FSM和HSM的C语言实现。
第2章 FSM概念 2.1 FSM定义
总的来说，有限状态机系统，是指在不同阶段会呈现出不同的运行状态的系统，这些状态是有限的、不重叠的。这样的系统在某一时刻一定会处于其所有状态中的一个状态，此时它接收一部分允许的输入，产生一部分可能的响应，并且迁移到一部分可能的状态。
2.2 FSM要素
2.2.1 State(状态)
State(“状态”)，就是一个系统在其生命周期中某一时刻的运行情况，此时，系统会执行一些动作，或者等待一些外部输入。
2.2.2 Guard(条件)
状态机对外部消息进行响应的时候，除了需要判断当前的状态，还要判断跟这个状态相关的一些条件是否成立。这种判断称为guard（“条件”）。guard通过允许或者禁止某些操作来影响状态机的行为。
2.2.3 Event(事件)
Event（“事件”），就是在一定的时间和空间上发生的对系统有意义的事情。
2.2.4 Action(动作)
当一个Event被状态机系统分发的时候，状态机用Action(“动作”)来进行响应，比如修改一下变量的值、进行输入输出、产生另外一个Event或者迁移到另外一个状态等等。
2.2.5 Transition（迁移）
从一个状态切换到另一个状态被称为Transition（“迁移”）。引起状态迁移的事件被称为triggering event（“触发事件”），或者被简称为trigger（“触发”）。
2.3 FSM图示
图2-1用UML描述了一个键盘输入的模型（这个是个假想的模型，只是为了用来说明FSM图的要素）。
图 2-1 Keyboard FSM in UML format 1
State用圆角矩形来表示，矩形中会写上state的名字。
Transition用箭头来表示，箭头上会写上Event的名字，可选的后面可以加上“[guard]”或者“/action”。
说明，Initial Transition（“初始状态迁移”）用实心的圆形和箭头来表示。Initial Transition就是FSM实例启动的时候的最初状态。每个状态机都应该有这么一个initial transition，其箭头上不应该有Event，因为这个迁移不是由事件触发的，但是箭头上可以写action，比如初始化一些变量或者初始化硬件等等。 Final Transition（“最终状态迁移”）用圆圈实心圆和箭头表示，其意义是FSM实例生命周期的结束。