状态机系统学习总结（转）

只看该作者 · 2011-2-27 11:04

1）明白：有限状态机系统在嵌入式软件中是个什么地位？（下面用粗体表示）
嵌入式系统软件的分类：
Ø 按处理器位数分类（嵌入式系统分为4位、8位、16位、32位和64位）
Ø 按产品应用类型分类（信息家电类；移动终端类；网络通信类；汽车电子类，工业控制类等）
Ø 按系统实时性来分类（根据实时性的强弱，嵌入式系统分为硬实时、软实时系统：硬实时：系统对系统响应时间有严格的要求，如果系统响应时间不能满足，会引起系统崩溃或致命的错误；软实时：系统对系统响应时间有要求，但是如果系统响应时间不能满足，不会导致系统出现致命的错误或崩溃，唉，说实话这里不是很明白，什么是致命的错误呢？）
Ø 软件复杂程度来分类（循环轮询系统；有限状态机系统；前后台系统；单处理器多任务系统；多处理器多任务系统）
Ø 多任务时处理器数目分类（单处理器多任务系统，多处理器多任务系统）
2）明白：为什么用有限状态机系统编写嵌入式软件。
有上面可知，软件软件复杂程度来分类（循环轮询系统；有限状态机系统；前后台系统；单处理器多任务系统；多处理器多任务系统）有这么多，下面就单就没种软件的系统（架构）做说明。
循环轮询系统：最简单的软件结构是循环轮询，程序依次检查系统的每一个输入条件，一旦条件成立就进行相应的处理。

通过上面的循环轮询系统的流程框图知道，循环轮训系统优点：对于简单的系统而言，便于编程和理解；没有中断机制，程序运行良好，不会出现随机问题。缺点：有限的应用领域(由于不可确定性)；对于大量的I/O服务的应用，不容易实现；大的程序不便于调试。因此合适于慢速和非常快速的简单系统。
系统软件结构框架如下：Initialize()
While(true){
if(condition_1) action_1();
if(condition_2) action_2();
……
if(condition_n) acition_n();
}
有限状态机系统（下面还会详细介绍），其实我觉得有限状态机系统和前后台系统通常是同事考虑和综合设计的，就是有限状态机系统也会用到前后台，前后台系统也会用到有限状态机(具体联系参考下面的状态机系统的详细介绍)。
有限状态机是实时系统设计中一种重要的，容易建立的，应用比较广泛的，以描述控制特性为主的建模方法，它可以应用于从系统分析道设计的所有阶段。
有限状态机系统优点：简单易用，状态间关系直观看到，便于编程；可以快速执行；只是通过改变输出功能来改变机器的响应。缺点：任何时刻系统只能有一个状态，无法表示并发性，不能描述异步并发系统；在系统部件多时，状态数随之增加，导致复杂性显著增长；对于大的应用系统，难于调试。
前后台系统：
后台：一个一直在运行的系统。
前台：是由一些中端处理过程组成。
当有一前台事件（外部事件）发生时，引起中断，于是将暂停后台的运行而进行前台处理，处理完毕后又回到后台（通常称为主程序）。
前后台系统运行方式如下图：

前后台系统流程图如下图：

注意，前后台系统的重中之重就是对中断的处理，包括：需要考虑中断现场的保护和恢复，中断嵌套，中断处理过程与主程序的协调（共享）问题。前后台系统性能主要由中断
延迟时间(interrupt latency time)，响应时间（response time）和恢复时间(recovery time)来刻画。
单处理器多任务系统；

只看该作者 · 2011-2-27 11:04

这个图是单任务系统(轮训，有限状态机或前后台系统)的常见程序执行流程，对于嵌入式系统，入口一般都是事件触发，然后是对事件判断或运算处理解析，及消息的分发过程，最后才会进入该事件对应的执行程序。中间即使有其他事件中断接入，也不会立即去执行后面中断的事件对应的执行程序了。例如当前在AD的执行程序中执行，突然外部中断发生，当然会先去执行外部中断的程序，但中断执行完毕后就会又返回到AD的执行程序中，只要AD的执行程序没有完毕就不会去执行外部中断时间对应的程序(当然外部中断事件解析和外部中断执行程序可以都放在外部中断中一起执行，这样就不用等待AD执行程序了，但是如果外部中断事件解析和外部中断执行程序时间十分短暂可以这样，不会出现什么问题，但是这种把什么都放到中断执行的思路在嵌入式系统设计中是不明智的，一旦执行程序耗时变大，整个系统效率将大打折扣)，所以单任务系统没有对各个事件对应的执行程序进行调度处理，难以控制实时性，无法实时控制某些程序准确执行。
如果采用如下并行的处理方式（已经很类似ucosii中的多任务了），就可以在任务执行层对程序进行通过优先级做任务调度处理了,但这需要每个任务间的通讯和协调，软件的复杂程度会加大，当回让系统根据实时效果。

3）状态机系统详细学习
第一：状态机是一种思想方法相信大多数工科学生在学习数字电路时都学习过状态机的基本概念，了解一些使用状态机描述时序电路的基本方法。但是，笔者希望大家能扩展思维，认识到状态机不仅仅是一种
时序电路设计工具，它更是一种思想方法。
我们先看下面一个简单的例子。在大学生活中，某学生的在校的学习生活可以简单地概
括为宿舍、教室、食堂之间的周而复始，用下图就可以形象地表现出来。这里画这张图，
并不是要讨论这个学生是否是一个“乖乖”类型学生，请大家注意，如果将图中的“地点”
认为是“状态”，将“功能”认为是状态的“输出”，这张图就是一张标准的状态转移图，也
就是说，我们用状态机的方式清晰地描述了这个学生的在校生活方式。

（上图：某学生在校生活状态转移图）
如果读者认为这张图描述的学生生活过于单调而怀疑状态机描述方法的威力，我们再看
看另一位生活丰富多彩的学生的在校生活，他（她）的在校生活方式可以用下图表示。

只看该作者 · 2011-2-27 11:04

上图：另一位学生在校生活状态转移图）同样如果将图中的“地点”认为是“状态”，将“功能”认为是状态的“输出”，将“条
件”认为是状态转移的“输入条件”，上图也是一张标准的状态转移图，通过状态机的方
式我们再次清晰地描述另一个学生的在校生活方式。
事实上使用状态机方式，我们可以细致入微地描述任何一个学生的在校生活方式。大家
通过前面两个简单举例已经发现状态机特别适合描述那些有发生有先后顺序，或者有逻辑规
律的事情——其实这就是状态机的本质。状态机的本质就是对具有逻辑顺序或时序规律事
件的一种描述方法。这个论断的最重要的两个词就是“逻辑顺序”和“时序规律”，这两点
就是状态机所要描述的核心和强项，换言之，所有具有逻辑顺序和时序规律的事情都适合用
状态机描述。
第二：有限状态机分析设计的基本原理
对于电子技术和电子工程类的读者，最先接触和使用到状态机应该是在数字逻辑电路课程里，状态机的思想和分析方法被应用于时序逻辑电路设计。其实，有限状态机（FSM）是实时系统设计中的一种数学模型，是一种重要的、易于建立的、应用比较广泛的、以描述控制特性为主的建模方法，它可以应用于从系统分析到设计（包括硬件、软件）的所有阶段。
很多实时系统，特别是实时控制系统，其整个系统的分析机制和功能与系统的状态有相当大的关系。有限状态机由有限的状态和相互之间的转移构成，在任何时候只能处于给定数目的状态中的一个。当接收到一个输入事件时，状态机产生一个输出，同时也可能伴随着状态的转移。
一个简单的有限状态机在数学上可以描述为：
（1）一个有限的系统状态的集合
其中(i = 1，2，…，q)。该式表示系统可能存（处）在的状态有q个，而在时刻Tk，系统的状态为其中之一Si（唯一性）。
（2）一个有限的系统输入信号的集合
其中(j = 1，2，…，m)，表示系统共有m个输入信号。该式表示在时刻Tk，系统的输入信号为输入集合的全集或子集（集合性）。
（3）一个状态转移函数F：
状态转移函数也是一个状态函数，它表示对于时刻Tk，系统在某一状态Si下，相对给定输入Ij后，FSM转入该函数产生的新状态，这个新状态就是系统在下一时刻（K+1）的状态。这个新的状态也是唯一确定的（唯一性）。
（4）一个有限的输出信号集合
其中(l = 1，2，…，n)，表示系统共有n个输出信号。该式表示对于在时刻Tk，系统的状态为Si时，其输出信号为输出集合的全集或子集（集合性）。这里需要注意的是，系统的输出只与系统所处的状态有关。
（5）时间序列
在状态机中，时间序列也是非常重要的一个因素，从硬件的角度看，时间序列如同一个触发脉冲序列或同步信号，而从软件的角度看，时间序列就是一个定时器。状态机由时间序列同步触发，定时检测输入，以及根据当前的状态输出相应的信号，并确定下一次系统状态的转移。在时间序列进入下一次触发时，系统的状态将根据前一次的状态和输入情况发生状态的转移。其次，作为时间序列本身也可能是一个系统的输入信号，影响到状态的改变，进而也影响到系统的输出。所以对于时间序列，正确分析和考虑选择合适的时间段的间隔也是非常重要的。间隔太短的话，对系统的速度、频率响应要求高，并且可能减低系统的效率；间隔太长时，系统的实时性差，响应慢，还有可能造成外部输入信号的丢失。一般情况下，时间序列的时间间隔的选取，应稍微小于外部输入信号中变化最快的周期值。
通常主要有两种方法来建立有限状态机，一种是“状态转移图”，另一种是“状态转移表”，分别用图形方式和表格方式建立有限状态机。实时系统经常会应用在比较大型的系统中，这时采用图形或表格方式对理解复杂的系统具有很大的帮助。
总的来说，有限状态机的优点在于简单易用，状态间的关系能够直观看到。应用在实时系统中时，便于对复杂系统进行分析。
下面将给出两个按键与显示相结合的应用设计实例，结合设计的例子，讨论如何使用有限状态机进行系统的分析和设计，以及如何在软件中进行描述和实现。

只看该作者 · 2011-2-27 11:05

第三、实力解析状态机系统例子1：基于状态机分析的简单按键设计
我们把单个按键作为一个简单的系统，根据状态机的原理对其动作和确认的过程进行分析，并用状态图表示出来，然后根据状态图编写出按键接口程序。
把单个按键看成是一个状态机话，首先需要对一次按键操作和确认的实际过程进行分析，根据实际的情况和系统的需要确定按键在整个过程的状态，每个状态的输入信号和输出信号，以及状态之间的转换关系。最后还要考虑时间序列的间隔。
采用状态机对一个系统进行分析是一项非常细致的工作，它实际上是建立在对真实系统有了全面深入的了解和认识的基础之上，进行综合和抽象化的模型建立的过程。这个模型必须与真实的系统相吻合，既能正确和全面的对系统进行描述，也能够适合使用软件或硬件方式来实现。
在一个嵌入式系统中，按键的操作是随机的，因此系统软件对按键需要一直循环查询。由于按键的检测过程需要进行消抖处理，因此取状态机的时间序列的周期为10ms左右，这样不仅可以跳过按键抖动的影响，同时也远小于按键0.3-0.5秒的稳定闭合期（如下图），不会将按键操作过程丢失。

很明显，系统的输入信号是与按键连接的I/O口电平，“1”表示按键处于开放状态，“0”表示按键处于闭合状态（下图）。而系统的输出信号则表示检测和确认到一次按键的闭合操作，用“1”表示。

上图：简单按键状态机的状态转换图
上图给出了一个简单按键状态机的状态转换图。在图中，将一次按键完整的操作过程分解为3个状态，采用时间序列周期为10ms。下面对该图做进一步的分析和说明，并根据状态图给出软件的实现方法。
首先，读者要充分体会时间序列的作用。在这个系统中，采用的时间序列周期为10ms，它意味着，每隔10ms检测一次按键的输入信号，并输出一次按键的确认信号，同时按键的状态也发生一次转换。
图中“状态0”为按键的初始状态：当按键输入为“1”时，表示按键处于开放，输出“0”（1/0），下一状态仍旧为“状态0”。当按键输入为“0”，表示按键闭合，但输出还是“0”（0/0）（没有经过消抖，不能确认按键真正按下），下一状态进入“状态1”。
“状态1”为按键闭合确认状态：它表示了在10ms前按键为闭合的，因此当再次检测到按键输入为“0”时，可以确认按键被按下了（经过10ms的消抖），输出“1”表示确认按键闭合（0/1），下一状态进入“状态2”。而当再次检测到按键的输入为“1”时，表示按键可能处在抖动干扰，输出为“0”（1/0），下一状态返回到“状态0”。这样，利用状态1，实现了按键的消抖处理。
“状态2”为等待按键释放状态：因为只有等按键释放后，一次完整的按键操作过程才算完成。
从对图的分析中可以知道，在一次按键操作的整个过程，按键的状态是从“状态0”>“状态1”->“状态2”，最后返回到“状态0”的。并且在整个过程中，按键的输出信号仅在“状态1”时给出了唯一的一次确认按键闭合的信号“1”（其它状态均输出“0”）。所以上面状态机所表示的按键系统，不仅克服了按键抖动的问题，同时也确保在一次按键整个的过程中，系统只输出一次按键闭合信号（“1”）。换句话讲，不管按键被按下的时间保持多长，在这个按键的整个过程中都只给出了一次确认的输出，因此在这个设计中，按键没有“连发”功能，它是一个最简单和基本的按键。
一旦有了正确的状态转换图，就可以根据状态转换图编写软件了。在软件中实现状态机的方法和程序结构通常使用多分支结构（IF-ELSEIF-ELSE、CASE等）实现。下面是根据图基于状态机方式编写的简单按键接口函数read_key()。
#define key_input PIND.7 // 按键输入口
#define key_state_0 0
#define key_state_1 1
#define key_state_2 2
char read_key(void)
{
static char key_state = 0;
char key_press, key_return = 0;
key_press = key_input; // 读按键I/O电平
switch (key_state)
{
case key_state_0: // 按键初始态
if (!key_press) key_state = key_state_1; // 键被按下，状态转换到键确认态
break;
case key_state_1: // 按键确认态
if (!key_press)
{
key_return = 1; // 按键仍按下，按键确认输出为“1”
key_state = key_state_2; // 状态转换到键释放态
}
else
key_state = key_state_0; // 按键已抬起，转换到按键初始态
break;
case key_state_2:
if (key_press) key_state = key_state_0; //按键已释放，转换到按键初始态
break;
}
return key_return;
}

只看该作者 · 2011-2-27 11:05

该简单按键接口函数read_key()在整个系统程序中应每隔10ms调用执行一次，每次执行时将先读取与按键连接的I/O的电平到变量key_press中，然后进入用switch结构构成的状态机。switch结构中的case语句分别实现了3个不同状态的处理判别过程，在每个状态中将根据状态的不同，以及key_press的值（状态机的输入）确定输出值（key_return），和确定下一次按键的状态值（key_state）。
函数read_key()的返回参数提供上层程序使用。返回值为0时，表示按键无动作；而返回1表示有一次按键闭合动作，需要进入按键处理程序做相应的键处理。
在函数read_key()中定义了3个局部变量，其中key_press和key_return为一般普通的局部变量，每次函数执行时，key_press中保存着刚检测的按键值。key_return为函数的返回值，总是先初始化为0，只有在状态1中重新置1，作为表示按键确认的标志返回。变量key_state非常重要，它保存着按键的状态值，该变量的值在函数调用结束后不能消失，必须保留原值，因此在程序中定义为“局部静态变量”，用static声明。如果使用的语言环境不支持static类型的局部变量，则应将key_state定义为全局变量（关于局部静态变量的特点请参考相关介绍C语言程序设计的书籍）。
例子2：基于有限状态机的自动售货机控制器
售货机上除基本自动售货功能外，增加了诸多功能，如GPRS短信模块以加强安全监控，在售货机上播放视频广告以提高运营商的经济效益等。这就使得存在于售货机内部的控制器(Vencling Machine Controller，VMC)的复杂程度也迅速增加，先前的一套用于小规模嵌入式系统的分析设计方法、应用程序结构、运行效率与易维护程度在当前的售货机需求面前显得有些力不从心了。有限状态机理论在计算机应用领域有着广泛的应用，状态机对处理一些复杂情况也大有裨益。在设计阶段，开发人员可以利用状态机模型来描述复杂的系统，从而大大缩短项目的开发周期，且系统易于维护。魏先民提出了有限状态机在嵌入式领域应用的一个基本框架，但是在这个框架中，系统中的所有状态都是互斥的关系，尽管有些状态之间存在着紧密的关系。V．Ayvazyan等论述了状态之间不仅存在互斥关系，还存在包含关系(父状态与子状态)。本文应用有限状态机的这些特性，提出一个层次型有限状态机(Hierarchical FSM，HFSM)模型，对售货机控制器(VMC)进行改进。
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为自动售货机的状态图(不完整)。

从图中可以看出，自动售货机控制器存在的状态数量是比较多的，但是无论何时，自动售货机总处于空闲、售货、商品价格设置、时间设置、测试等诸多状态之中的一个．这些状态之间是互斥的。同时，上面列举的所有状态都包含子状态，例如：状态S2(时间设置状态)包括日期设置、时分秒设置、星期设置等子状态，而对于S3(日期设置状态)又包括S4(日期显示状态)和S5(日期编辑状态)两个子状态。因此，对于自动售货机控制器这样一个系统，其内部的状态机是一种层次型状态机。本文根据层次型状态机的互斥与包含的双重特性，提出层次型有限状态机模型，并且用来实现自动售货机控制器。模型使用树结构来描述状态集，包含其他状态的状态称为“树枝节点”，不包含其他状态的状态称为“叶子节点”。为方便用单树结构描述，总是设计一个状态包含所有的状态节点，称为“根节点”，它是一个虚拟的节点，在系统中没有状态与其对应。状态机只能停留在叶子节点，而不能停留在树枝节点，每个树枝节点需指定一个子节点为它的默认子节点，以便状态机进入树枝节点时能停留到叶子节点。
3 层次型有限状态机模型
3．1 数据结构定义
HFSM模型采用树结构实现有限状态机，树上的每一个节点都对应了自动售货机状态机的一个状态。其中根节点是一个特殊的节点，它对应的是一个虚拟的并不存在的状态，其目的是为了构造一棵单树，而不是每一个功能对应一棵树。节点的数据结构如下：

其中，id为状态编号，每个状态编号在整个系统状态机中是唯一的；name为状态名；enter_func为状态进入操作；exit_func为状态退出操作；event_table为事件表；sub_state_table为子状态表。因为叶子节点没有子状态，而树枝节点没有状态事件表，所以结构中的事件表与子状态可以共享一段存储空间。事件表中每个元素是另外一个结构FSM_STATE_EVENT，它有事件id(与事件源一一对应)、事件操作(func)和下一状态编号(next_state_id)三个成员。图2所示的状态图子集经过处理形成图3所示的状态树，它是整个自动售货机状态树的一部分。

只看该作者 · 2011-2-27 11:05

3．2 状态转换算法
在有限状态机中，是通过事件的驱动而进行状态转换的。状态转换算法的关键就在于查找下一状态在状态树中的位置，也就是在状态树中查找下一状态的时间复杂度的问题。与常规状态机不同，层次型状态机中的各个状态不仅存在互斥关系，还存在包含关系，特别是当前状态与下一状态关系就更为紧密了，不仅存在局部相关性，而且在很多情况下，它们之间在状态树中表现为兄弟节点关系。因此，要在状态树查找下一状态，需先查找当前节点的兄弟节点，再查找父节点的兄弟节点。如此循环，直到找到下一状态或试图查找根节点的兄弟节点(根节点没有父节点，所以要查找的下一状态是不存在的)。状态查找算法如下：

有限状态机的一般状态转换过程是：系统首先执行exit_func退出当前状态，然后执行驱动此次状态转换的事件操作func，最后执行enter_func进入新状态。为了便于遍历状态树，系统为层次型有限状态机建立一个状态堆栈，堆栈中记录的数据是当前状态在状态树中对应的节点路径上所有节点(自身除外，因为没有必要人栈)的地址。堆栈的初始状态如图4所示，此时系统处于空闲S1状态，栈中只有根节点信息。在某个事件或一系列事件的驱动下(比如通过按键显示系统的当前日期)，系统将要从空闲状态转换到日期显示状态S4。从图3的自动售货机状态树可以看出，系统需要经过S1一S2一S3一S4的过程，中间的S2和S3是不可停留的状态。当按下管理键盘的“Time”键时，系统先执行exit_idle函数退出S1(空闲状态)，然后根据空闲状态的事件表得到下一状态编号，再通过状态查找算法搜索状态树，最后到达目的状态S4。S2与S3是两个中间状态，但是这两个状态节点的地址需要入栈。

3．3 模型评价
(1)扩展性
为层次型有限状态机模型增加新功能，只需在其根节点下增加一个子节点，因为新的子节点与其他兄弟节点是互斥的，所以模型可以很方便地进行系统功能扩展。
(2)查找算法时间复杂度
假设系统中存在的状态数量为n。如果不采用层次型有限状态机模型，那么系统中的各个状态都是相互独立、互斥的，相当于所有的状态都是一个虚拟根节点的子节点。这样的话，查找下一状态的时间复杂度为：

然而，上面的情况忽略了状态之间的相关性，很有可能当前状态与下一状态是兄弟关系，此时的比较次数就会明显减少。如果采用层次型状态机，假设系统子功能数目为m(m>1)，那么平均每个子功能的状态数目为n／m，当前状态与下一状态为兄弟节点的概率为p(0<p<1)。这种情况下的时间复杂度为：

其中，t1为当前状态与下一状态不是兄弟节点的查找时间，与状态树的平均深度^有关。但是由于存在局部相关性，并且这种相关性越大(即p值越大)，平均时间复杂度就越集中在前面部分(p·n)／(m·2)，后面的表达式值可以忽略不计，即：

显然，T(n)2<T(n)1。因此，该模型对于查找下一状态在时间复杂度上也是有优势的。
结语
通过建立层次型有限状态机模型，并应用改进的数据结构与状态转换算法，自动售货机控制器的程序结构更为清晰。原来存在于程序中的诸多标志变量，由状态机的各个状态所取代，使系统具有更好的扩展性；并且模型很好地利用了状态的相关性，缩短了查找所花费的时间。但是，该模型也存在一定的局限性。比如，很大数量在构造状态树时需要的存储空间给一般嵌入式系统的成本带来了挑战，不过可以试图通过让所有的状态共享内存空间的