1 有限状态机
有限状态机是一种具有离散输入输出系统的模型,在任何时刻都处于一个特定的状态。对于事件驱动的程序设计,它是非常有用的设计模型。在某一个状态下有事件发生时,根据当前状态和输入事件的不同,选择如何处理该事件以及是否需要转换到下一个状态。一个有限状态机(FSM)是一个五元组,M=(K,E,T,S,Z)。其中,K是一个有限的状态集合,它的每个元素称为“状态”;E表示该系统能接收的所有事件的集合,它的每个元素称为一个“事件”;T是状态转换函数,是K×E→K上的映射;S是系统的一个特殊状态,一般是系统启动时的初始状态;Z是K的一个子集,是一个终态集。
有限状态机一般有2种表示方式:状态转移表和状态转移图。通常用有向图来表示有限状态机,其节点代表状态。如图1所示,若在状态SO接收到某个输入事件e1后转向S1状态,就在图中画一条从SO到Sl的带箭头的弧线,并在弧线上标记e1。
2 基本思想
2.1 必要性分析
有限状态机是通过事件来触发状态的转变的,其事件来源主要有2个:其一是外部触发事件,如响应用户键盘的输入;其二是内部触发事件,如系统所发出来的各种命令。有限状态机这种事件驱动的特性具有良好的开放性,可以根据用户的要求方便地增加相应的状态与事件,完成系统功能的扩展。本文所研究的自动售货机配有1个5×5的管理键盘和1个3×7用户键盘,二者复用了部分的键盘扫描线;另外有37个外部事件源,加上几条内部命令,可能触发的事件达45个。如此多的事件,当某个事件发生时,如果采用if…else或switch…case语句进行一一判断,将非常复杂。而采用有限状态机,每个状态维护一张事件表,无需比较,大大提高了响应速度;并且就扩展需求较为频繁的自动售货机而言,有限状态机也是便于维护的。
2.2 实现方式
根据系统中各个状态之间是否存在包含关系,有限状态机可以分为常规状态机与层次型状态机(hierarchicalstate machine)。对于前者,系统中各个状态是独立的、互斥的,适合应用于那些存在状态数量不多的简单系统;而对于后者,系统中的状态除了互斥关系以外,还存在真包含的关系。
分析自动售货机这样一个状态机,图2为自动售货机的状态图(不完整)。