状态机在单片机程序设计中的应用

状态机思路在单片机程序设计中的应用

状态机的概念 状态机是软件编程中的一个重要概念。 比这个概念更重要的是 对它的灵活应用。在一个思路清晰而且高效的程序中,必然有状态机 的身影浮现。 比如说一个按键命令解析程序,就可以被看做状态机:本来在 A 状态下, 触发一个按键后切换到了 B 状态; 再触发另一个键后切换 到 C 状态,或者返回到 A 状态。这就是最简单的按键状态机例子。 实际的按键解析程序会比这更复杂些, 但这不影响我们对状态机的认 识。 进一步看,击键动作本身也可以看做一个状态机。一个细小的 击键动作包含了:释放、抖动、闭合、抖动和重新释放等状态。 同样,一个串行通信的时序(不管它是遵循何种协议,标准串 口也好、I2C 也好;也不管它是有线的、还是红外的、无线的)也都 可以看做由一系列有限的状态构成。 显示扫描程序也是状态机;通信命令解析程序也是状态机;甚 至连继电器的吸合/释放控制、发光管(LED)的亮/灭控制又何尝不 是个状态机。 当我们打开思路,把状态机作为一种思想导入到程序中去时, 就会找到解决问题的一条有效的捷径。 有时候用状态机的思维去思考 程序该干什么,比用控制流程的思维去思考,可能会更有效。这样一

来状态机便有了更实际的功用。 程序其实就是状态机。 程序其实就是状态机。 也许你还不理解上面这句话。请想想看,计算机的大厦不就是 建立在“0”和“1”两个基本状态的地基之上么? 状态机的要素 状态机可归纳为4个要素,即现态、条件、动作、次态。这样 的归纳,主要是出于对状态机的内在因果关系的考虑。“现态”和“条 件”是因,“动作”和“次态”是果。详解如下: ①现态:是指当前所处的状态。 ②条件:又称为“事件”。当一个条件被满足,将会触发一个动 作,或者执行一次状态的迁移。 ③动作:条件满足后执行的动作。动作执行完毕后,可以迁移 到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足 后,也可以不执行任何动作,直接迁移到新状态。 ④次态:条件满足后要迁往的新状态。“次态”是相对于“现态” 而言的,“次态”一旦被激活,就转变成新的“现态”了。 如果我们进一步归纳,把“现态”和“次态”统一起来,而把“动 作”忽略(降格处理) ,则只剩下两个最关键的要素,即:状态、迁移 条件。 状态机的表示方法有许多种,我们可以用文字、图形或表格的 形式来表示一个状态机。 纯粹用文字描述是很低效的,所以就不介绍了。接下来先介绍

图形的方式。 状态迁移图(STD) 状态迁移图( ) 状态迁移图(STD) ,是一种描述系统的状态、以及相互转化关 系的图形方式。状态迁移图的画法有许多种,不过一般都大同小异。 我们结合一个例子来说明一下它的画法,如图1所示。

图1 状态迁移图 ①状态框:用方框表示状态,包括所谓的“现态”和“次态”。 ②条件及迁移箭头:用箭头表示状态迁移的方向,并在该箭头 上标注触发条件。 ③节点圆圈: 当多个箭头指向一个状态时, 可以用节点符号 (小 圆圈)连接汇总。 ④动作框:用椭圆框表示。 ⑤附加条件判断框:用六角菱形框表示。 状态迁移图和我们常见的流程图相比有着本质的区别, 具体体 现为:在流程图中,箭头代表了程序 PC 指针的跳转;而在状态迁移 图中,箭头代表的是状态的改变。 我们会发现, 这种状态迁移图比普通程序流程图更简练、 直观、

易懂。这正是我们需要达到的目的。 状态迁移表 除了状态迁移图, 我们还可以用表格的形式来表示状态之间的 关系。这种表一般称为状态迁移表。 表1就是前面介绍的那张状态迁移图的另一种描述形式。 表1 状态迁移表

①采用表格方式来描述状态机,优点是可容纳更多的文字信 息。例如,我们不但可以在状态迁移表中描述状态的迁移关系,还可 以把每个状态的特征描述也包含在内。 ②如果表格内容较多,过于臃肿不利于阅读,我们也可以将状 态迁移表进行拆分。经过拆分后的表格根据其具体内容,表格名称也 有所变化。 ③比如,我们可以把状态特征和迁移关系分开列表。被单独拆 分出来的描述状态特征的表格,也可以称为“状态真值表”。这其中比 较常见的就是把每个状态的显示内容单独列表。 这种描述每个状态显 示内容的表称之为“显示真值表”。同样,我们把单独表述基于按键的 状态迁移表称为“按键功能真值表”。另外,如果每一个状态包含的信 息量过多,我们也可以把每个状态单独列表。 ④由此可见,状态迁移表作为状态迁移图的有益补充,它的表

现形式是灵活的。 ⑤状态迁移表优点是信息涵盖面大,缺点是视觉上不够直观, 因此它并不能取代状态迁移图。比较理想的是将图形和表格结合应 用。用图形展现宏观,用表格说明细节。二者互为参照,相得益彰。 用状态机思路实现一个时钟程序 接下来,我将就状态机的应用,结合流程图、状态迁移图和状 态迁移, 举一个实际例子。 下面这张图是一个时钟程序的状态迁移图, 如图2所示。

图2 时钟程序状态迁移图 把这张图稍做归纳, 就可以得到它的另一种表现形式——状态 迁移表,如表2所示。 表2 时钟程序状态迁移表

状态机应用的注意事项 基于状态机的程序调度机制,其应用的难点并不在于对状态机 概念的理解,而在于对系统工作状态的合理划分。 初学者往往会把某个“程序动作”当作是一种“状态”来处理。我 称之为“伪态”。那么如何区分“动作”和“状态”。本匠人的心得是看二 者的本质:“动作”是不稳定的,即使没有条件的触发,“动作”一旦执 行完毕就结束了; 而“状态”是相对稳定的, 如果没有外部条件的触发, 一个状态会一直持续下去。 初学者的另一种比较致命的错误, 就是在状态划分时漏掉一些 状态。我称之为“漏态”。 “伪态”和“漏态”这两种错误的存在,将会导致程序结构的涣 散。因此要特别小心避免。 更复杂的状态机 前面介绍的是一种简单的状态结构。它只有一级,并且只有一 维,如图3所示。

图3 线性状态机结构 如果有必要,我们可以建立更复杂的状态机模型。 1 多级状态结构 多级状态结构 状态机可以是多级的。 在分层的多级状态机系统里面, 一个“父 状态”下可以划分多个“子状态”,这些子状态共同拥有上级父状态的 某些共性,同时又各自拥有自己的一些个性。 在某些状态下,还可以进一步划分子状态。比如,我们可以把 前面的时钟例子修改如下: 把所有和时钟功能有关的状态,合并成1个一级状态。在这个状态下, 又可以划分出3个二级子状态,分别为显示时间、设置小时、设置分 钟; 同样,我们也可以把所有和闹钟功能有关的状态,合并成1个 一级状态。在这个状态下,再划分出4个二级子状态,分别为显示闹 钟、设置“时”、设置“分”、设置鸣叫时间。 我们需要用另一个状态变量(寄存器)来表示这些子状态。 子状态下面当然还可以有更低一级的孙状态 (子子孙孙无穷尽 也) ,从而将整个状态体系变成了树状多级状态结构,如图4所示。

图4 树状多级状态结构 2 多维状态结构 状态结构也可以是多维的。 从不同的角度对系统进行状态的划 分,这些状态的某些特性是交叉的。比如,在按照按键和显示划分状 态的同时,又按照系统的工作进程做出另一种状态划分。这两种状态 划分同时存在,相互交叉,从而构成了二维的状态结构空间。 举一个这方面的例子,如:空调遥控器,如图5所示。

图5 多维状态机结构 同样,我们也可以构建三维、四维甚至更多维的状态结构。每 一维的状态都需要用一个状态变量(寄存器)来表示。

无论多级状态结构和多维状态结构看上去多么迷人, 匠人的忠 告是:我们依然要尽可能地简化状态结构,能用单级、单维的结构, 就不要给自己找事,去玩那噩梦般的复杂结构。 简单的才是最有效的。 结束语 对状态机的理解需要一个由浅入深的过程。 这个过程应该是与 实践应用和具体案例思考相结合的。 当一种良好的思路成为设计的习 惯,它就能给设计者带来回报。愿这篇手记里介绍的基于状态机的编 程思路能给新手们带来一些启迪,帮助大家找到“程序设计”的感觉。

【转载 1】有限状态机的实现 < type="text/javascript">

有限状态机(Finite State Machine 或者 Finite State Automata)是软件领 域中一种重要的工具,很多东西的模型实际上就是有限状态机。

最近看了一些游戏编程 AI 的材料,感觉游戏中的 AI,第一要说的就 是有限状态机来实现精灵的 AI,然后才是 A*寻路,其他学术界讨论 比较多的神经网络、模糊控制等问题还不是很热。

FSM 的实现方式: 1) switch/case 或者 if/else 这无意是最直观的方式, 使用一堆条件判断, 会编程的人都可以做到, 对简单小巧的状态机来说最合适,但是毫无疑问,这样的方式比较原 始,对庞大的状态机难以维护。

2) 状态表 维护一个二维状态表,横坐标表示当前状态,纵坐标表示输入,表中 一个元素存储下一个状态和对应的操作。这一招易于维护,但是运行 时间和存储空间的代价较大。

3) 使用 State Pattern 使用 State Pattern 使得代码的维护比 switch/case 方式稍好,性能上也 不会有很多的影响,但是也不是 100%完美。不过 Robert C. Martin 做了两个自动产生 FSM 代码的工具,for java 和 for C++各一个,在

http://www.objectmentor.com/resources/index 上有免费下载,这个工具 的输入是纯文本的状态机描述,自动产生符合 State Pattern 的代码, 这样 developer 的工作只需要维护状态机的文本描述,每必要冒引入 bug 的风险去维护 code。

4) 使用宏定义描述状态机 一般来说,C++编程中应该避免使用#define,但是这主要是因为如果 用宏来定义函数的话, 很容易产生这样那样的问题, 但是巧妙的使用, 还是能够产生奇妙的效果。 MFC 就是使用宏定义来实现大的架构的。 在实现 FSM 的时候,可以把一些繁琐无比的 if/else 还有花括号的组 合放在宏中,这样,在代码中可以 3)中状态机描述文本一样写,通 过编译器的预编译处理产生 1) 一样的效果, 我见过产生 C 代码的宏, 如果要产生 C++代码,己软 MFC 可以,那么理论上也是可行的。

【评】 :状态表的实现方法, 专家编程》第 8 章有具体说明,转载 《C 【6】

☆──────────────────────传说中的分隔

符──────────────────────────── ──☆

【转载 2】有限状态机的 c 实现

2007-05-11 15:12

这儿以四位密码校验作为状态机的例子,连续输入 2479 就可以通过 密码测试。一个非常简单的例子,在实际的状态机实例中,状态转移 表要更復雜一些, 不過方式非常類似。 在狀態查詢的地方可以做優化, 同時對于輸入量也可以做有效性優化。具體代碼如下:

view plaincopy to clipboardprint? c.h

typedef enum{ STATE1 = 1,

STATE2, STATE3, STATE4, STATE5,//password pass //...ADD here }STATE;

typedef enum{ INPUT1 = '2', INPUT2 = '4', INPUT3 = '7', INPUT4 = '9', }INPUT;

typedef struct { STATE cur_state; INPUT input; STATE next_state; }STATE_TRANS; c.h

typedef enum{ STATE1 = 1, STATE2, STATE3, STATE4, STATE5,//password pass //...ADD here }STATE;

typedef enum{ INPUT1 = '2', INPUT2 = '4', INPUT3 = '7', INPUT4 = '9', }INPUT;

typedef struct { STATE cur_state; INPUT input; STATE next_state; }STATE_TRANS;

c.c

#include

<stdio.h>

#include "c.h"

STATE_TRANS state_trans_arry[] = { {STATE1,INPUT1,STATE2}, {STATE2,INPUT2,STATE3}, {STATE3,INPUT3,STATE4}, {STATE4,INPUT4,STATE5}, }; #define STATE_TRANS_CNT

(sizeof(state_trans_arry)/sizeof(state_trans_arry[0]))

int main() { int i; char ch;

STATE state_machine = STATE1;

while(ch != 'e') { ch = getchar(); if((ch >= '0') && (ch <= '9'))//for digit password input only { for(i = 0;i < STATE_TRANS_CNT;i++) { if((ch == state_trans_arry[i].input) && (state_machine ==

state_trans_arry[i].cur_state)) { state_machine = state_trans_arry[i].next_state; continue; } else if(i == (STATE_TRANS_CNT - 1))//no transfer match,reset state { state_machine = STATE1; } } if(state_machine == STATE5)

printf("Password correct,state transfer machine pass!\n"); } } return 0; } c.c

#include

<stdio.h>

#include "c.h"

STATE_TRANS state_trans_arry[] = { {STATE1,INPUT1,STATE2}, {STATE2,INPUT2,STATE3}, {STATE3,INPUT3,STATE4}, {STATE4,INPUT4,STATE5}, }; #define STATE_TRANS_CNT

(sizeof(state_trans_arry)/sizeof(state_trans_arry[0]))

int main() {

int i; char ch; STATE state_machine = STATE1;

while(ch != 'e') { ch = getchar(); if((ch >= '0') && (ch <= '9'))//for digit password input only { for(i = 0;i < STATE_TRANS_CNT;i++) { if((ch == state_trans_arry[i].input) && (state_machine ==

state_trans_arry[i].cur_state)) { state_machine = state_trans_arry[i].next_state; continue; } else if(i == (STATE_TRANS_CNT - 1))//no transfer match,reset state { state_machine = STATE1; }

} if(state_machine == STATE5) printf("Password correct,state transfer machine pass!\n"); } } return 0; }

【评】 在 VC6 下运行该程序并没有达到目的, : 即连续输入字符 2479 也没有任何输出信息,个人根据转载第一遍文章的 FSM 的实现的第 一种方法,见【原创之源程序】

☆──────────────────────传说中的分隔 符──────────────────────────── ──☆

【转载 3】有限状态机自动机

状态图--一个图的数据结构! 1.while + switch; 2.状态机:就是指定系统的所有可能的状态及状态间跳转的条件,然 后设一个初始状态输入给这台机器,机器就会自动运转,或最后处于 终止状态,或在某一个状态不断循环。 游戏中状态切换是很频繁的。 可能以前要切换状态就是 if~else,或 者设标志,但这些都不太结构化, 如果把它严格的设为一种标准的 状态机,会清楚的多。

比如控制一扇门的运动, 初始时门是关的, 当有力作用在门上时, 门开始慢慢打开,力的作用完后,门渐渐停止不动, 当有反向的力 时,门又渐渐关上, 知道回到初始关的状态。 这个你会怎么来编程 实现呢。 似乎很麻烦, 的确,没有状态机的思想时会很烦,设很多 标志,一堆 if 条件。 用状态机的话,不只是代码更清晰, 关键是更符合逻辑和自然规律, 不同状态不同处理, 满足条件则跳转到相关状态。

伪码如下:

enum { CLOSED, // 关上状态 CLOSING, // 正在关状态 OPENED, // 打开状态 OPENING, // 正在开的状态 }doorState = CLOSED; // 初始为关

Update() { switch(doorState) case CLOSED: if (有人推门) doorState = OPENING; // 跳转到正在开状态 break; case OPENING: door.Rotation += DeltaAngle; // 门的旋转量递增 if (门的速度为零) / / 力的作用已去 doorState = OPENED; // 跳转到开状态 break; case OPENED: if (有人关门)

doorState = CLOSING; break; case CLOSING: door.Rotation -= DeltaAngle; // 门的旋转量递减 if (门的旋转角度减为零) doorState = CLOSED; // 门已关上 break; }

// 而绘制代码几乎不用怎么变, 门就是会严格按照状态机的指示去 运动, 该停就会停 Render() { RotateView(door.Rotation); DrawDoor(door.Position); } enum { CLOSED, // 关上状态 CLOSING, // 正在关状态 OPENED, // 打开状态 OPENING, // 正在开的状态

}doorState = CLOSED; // 初始为关

Update() { switch(doorState) case CLOSED: if (有人推门) doorState = OPENING; // 跳转到正在开状态 break; case OPENING: door.Rotation += DeltaAngle; // 门的旋转量递增 if (门的速度为零) / / 力的作用已去 doorState = OPENED; // 跳转到开状态 break; case OPENED: if (有人关门) doorState = CLOSING; break; case CLOSING: door.Rotation -= DeltaAngle; // 门的旋转量递减 if (门的旋转角度减为零) doorState = CLOSED; // 门已关上

break; }

// 而绘制代码几乎不用怎么变, 门就是会严格按照状态机的指示去 运动, 该停就会停 Render() { RotateView(door.Rotation); DrawDoor(door.Position); }

这是一个简单但很典型的例子, 状态机的应用太多了。 就说一个基本游戏的运转: (用到了一个状态然后还有子状态) UpdateGame() BEGIN; switch(gameState) case 等待选择菜单: //它有三个子状态。 if (选择菜单项 == 开始)

{ 游戏初始; gameState = 开始游戏 } if (选择菜单项 == 选项) gameState = 设置 if (选择菜单项 == 退出) gameState = 退出

case 开始:

游戏运行; if (用户按退出键) gameState = 等待选择菜单 ; ...其他的状态跳转处理; case 退出: 释放资源; 退出; case 设置: 分别处理不同的选项, 跳转不同的子状态; case .... // 其他状态的处理

END; UpdateGame() BEGIN; switch(gameState) case 等待选择菜单: //它有三个子状态。 if (选择菜单项 == 开始) { 游戏初始; gameState = 开始游戏 } if (选择菜单项 == 选项) gameState = 设置 if (选择菜单项 == 退出) gameState = 退出

case 开始:

游戏运行; if (用户按退出键) gameState = 等待选择菜单 ; ...其他的状态跳转处理; case 退出:

释放资源; 退出; case 设置: 分别处理不同的选项, 跳转不同的子状态; case .... // 其他状态的处理

END;

某一个状态可以包含更多的子状态, 这样最好是同一层次的状态设 为一个枚举, 并分到另一个 switch 处理 如 enum STATES{state1, state2, state3}; state2 又包含若干状态 则 再 定 义 sub_state2_3,}; enum SUB_STATE2{sub_state2_1, sub_state2_2,

想很多基本的渲染效果, 如淡入淡出, 闪烁等等, 用状态的思想 会事半功倍, 思路也更清晰。

其实像 Opengl, Direct3D 这样的渲染引擎本身就是状态机, 当你设 置渲染的状态, 这台机器就保持这个状态进行渲染工作,如保持光 照位置,保持片元颜色, 直到你再次改变它的状态。

状态机的应用实在太广, 相关理论也很多, 最近上课学的随机过程 里也讲到一些, 数字电路里的时序逻辑器件也是用状态机来描述。 这些不必多说了。

总之, 用状态机的角度去看待问题, 往往能把比较复杂的系统分解 为能单独处理的众多子状态, 处理也会得心应手。希望大家多用它, 很好的东西。

二、 推荐这个:[程序员杂志 2004.8 月刊_state 模式和 composite 模式实现 的状态机引擎] http://www.contextfree.net/wangyw/source/oofsm.html

个人感觉状态机的几个不同实现阶段: 1、 switch/case 最原始的实现方式,是很多的 c 程序员习惯采用的方式。

2、查找表[状态、事件、动作],稍微做了一点改进。有点类似 MFC 的 雏形。

3、在以上基础上做的一些改进或者变体。 [比如用一个栈结构,激活的状态位于栈顶,自动的映射事件和动作

的对应,再或者通过一些巧妙的宏等手段进行包装。但是线性结构在 实际中使用比较受限、过于技巧性的宏比较难于理解...]

4、面向对象的设计下、灵活运用模式。如上面给出的链接。重用性 和灵活性方面都有不错的表现。沿袭类似的设计思路、根据实际开发 内容进行改造后利用。

【评】 :伪代码部分,可以帮助很好的理解【转载 1】文章中叙述的 FSM 的实现方法 1;查找表[状态、事件、动作],稍微做了一点改进。 有点类似 MFC 的雏形类似于【转载 1】文章中叙述的 FSM 的实现方 法 2(状态表)

☆──────────────────────传说中的分隔 符──────────────────────────── ──☆

【转载 4】fsm implemented in C code(FSM 状态机用 C 实现)

用 C 语言实现一个状态机,很简单,和大家分享 这是我做毕业设计时,用 nRF24L01 组建了一个简单的网络,做的一 个小的状态机,网络中三个节点,开始拓扑为网状,后来为星型。

#include <stdio.h> #include <stdlib.h> #include <string.h>

//Finite state machine declaration //state declaration #define IDLE 0 //idle state in rx mode #define M_BROADCAST 1 //broadcast state in tx mode,broadcast to be a master point #define M_WAIT_BROADCAST_ACK 2 //wait for broadcast ack state in rx mode,wait for the point ack in a specific time window #define M_WAIT_COMMAND 3 //wait for command state,wait for PC command via UART #define M_BROADCAST_CANCEL 4 //broadcast cancel state,broadcast to cancel master point

#define S_BROADCAST_ACK 5 //slave mode,send back self physical address #define S_WAIT_COMMAND 6 //slave mode, wait for command from the master point

//state transition trig //used in master mode int isReqBeMaster = 0;//Is PC request the point to be master? int isTimeout = 0;//Is time out? int isReqCancelMaster = 0;//Is request to cancel master? //used in slave mode int isRxBroadcast = 0;//Is there a point broadcast to be master? int isRxBroadcastCancel = 0;//Is receive broadcast cancel master?

typedef struct fsmtag { int state; //state int timeouttime; //time out time in milliseconds }fsm;

//function prototype

int main() { fsm f;

f.state = IDLE; f.timeouttime = 0;

while(1) { switch(f.state) { case IDLE: puts("IDLE\nWait isRxBroadcast(1/0):"); scanf("%d %d",&isReqBeMaster,&isRxBroadcast); if(isReqBeMaster) { f.state = M_BROADCAST; break; } else if(isRxBroadcast) for isReqBeMaster(1/0)

{ f.state = S_BROADCAST_ACK; break; } else break; case M_BROADCAST: puts("M_BROADCAST\nBroadcasting...\n"); f.state = M_WAIT_BROADCAST_ACK; case M_WAIT_BROADCAST_ACK: puts("M_WAIT_BROADCAST_ACK\nWaiting isTimeout(1/0):"); scanf("%d",&isTimeout); if(isTimeout) { f.state = M_WAIT_COMMAND; break; } else break; case M_WAIT_COMMAND: puts("M_WAIT_COMMAND\nWaiting for for

isReqCancelMaster(1/0):"); scanf("%d",&isReqCancelMaster); if(isReqCancelMaster) { f.state = IDLE; break; } else break; //Slave mode routine case S_BROADCAST_ACK: puts("S_BROADCAST_ACK\nAcking...\n"); f.state = S_WAIT_COMMAND; break; case S_WAIT_COMMAND: puts("S_WAIT_COMMAND\nWaiting isRxBroadcastCancel(1/0):"); scanf("%d",&isRxBroadcastCancel); if(isRxBroadcastCancel) { f.state = IDLE; break; for

} else break; default: puts("default"); printf("%d\n",rand()); f.state = IDLE; } }

return 0; } #include <stdio.h> #include <stdlib.h> #include <string.h>

//Finite state machine declaration //state declaration #define IDLE 0 //idle state in rx mode #define M_BROADCAST 1 //broadcast state in tx mode,broadcast to be a master point

#define M_WAIT_BROADCAST_ACK 2 //wait for broadcast ack state in rx mode,wait for the point ack in a specific time window #define M_WAIT_COMMAND 3 //wait for command state,wait for PC command via UART #define M_BROADCAST_CANCEL 4 //broadcast cancel state,broadcast to cancel master point

#define S_BROADCAST_ACK 5 //slave mode,send back self physical address #define S_WAIT_COMMAND 6 //slave mode, wait for command from the master point

//state transition trig //used in master mode int isReqBeMaster = 0;//Is PC request the point to be master? int isTimeout = 0;//Is time out? int isReqCancelMaster = 0;//Is request to cancel master? //used in slave mode int isRxBroadcast = 0;//Is there a point broadcast to be master? int isRxBroadcastCancel = 0;//Is receive broadcast cancel master?

typedef struct fsmtag

{ int state; //state int timeouttime; //time out time in milliseconds }fsm;

//function prototype

int main() { fsm f;

f.state = IDLE; f.timeouttime = 0;

while(1) { switch(f.state) { case IDLE: puts("IDLE\nWait isRxBroadcast(1/0):"); scanf("%d %d",&isReqBeMaster,&isRxBroadcast); for isReqBeMaster(1/0)

if(isReqBeMaster) { f.state = M_BROADCAST; break; } else if(isRxBroadcast) { f.state = S_BROADCAST_ACK; break; } else break; case M_BROADCAST: puts("M_BROADCAST\nBroadcasting...\n"); f.state = M_WAIT_BROADCAST_ACK; case M_WAIT_BROADCAST_ACK: puts("M_WAIT_BROADCAST_ACK\nWaiting isTimeout(1/0):"); scanf("%d",&isTimeout); if(isTimeout) { f.state = M_WAIT_COMMAND; for

break; } else break; case M_WAIT_COMMAND: puts("M_WAIT_COMMAND\nWaiting isReqCancelMaster(1/0):"); scanf("%d",&isReqCancelMaster); if(isReqCancelMaster) { f.state = IDLE; break; } else break; //Slave mode routine case S_BROADCAST_ACK: puts("S_BROADCAST_ACK\nAcking...\n"); f.state = S_WAIT_COMMAND; break; case S_WAIT_COMMAND: puts("S_WAIT_COMMAND\nWaiting for for

isRxBroadcastCancel(1/0):"); scanf("%d",&isRxBroadcastCancel); if(isRxBroadcastCancel) { f.state = IDLE; break; } else break; default: puts("default"); printf("%d\n",rand()); f.state = IDLE; } }

return 0; }

【评】 :很实用的一个状态机程序

☆──────────────────────传说中的分隔 符──────────────────────────── ──☆

【转载 5】状态机的两种写法

有限状态机 FSM 思想广泛应用于硬件控制电路设计,也是软件 上常用的一种处理方法(软件上称为 FMM--有限消息机)。 它把复杂的 控制逻辑分解成有限个稳定状态,在每个状态上判断事件,变连续处 理为离散数字处理,符合计算机的工作特点。同时,因为有限状态机 具有有限个状态,所以可以在实际的工程上实现。但这并不意味着其 只能进行有限次的处理,相反,有限状态机是闭环系统,有限无穷, 可以用有限的状态,处理无穷的事务。 有限状态机的工作原理如图 1 所示,发生事件(event)后,根据当 前状态(cur_state),决定执行的动作(action),并设置下一个状态号 (nxt_state)。

------------| 发生事件 event ----->| cur_state | | nxt_state ------------当前状态 图 1 有限状态机工作原理 |-------->设置下一状态号 |-------->执行动作 action

e0/a0 --->-| -------->---------e0/a0 | | | | S0 |----| e1/a1 V ---------|-----<-----| e2/a2 S1 | |

-<-----------| e2/a2

---------| S2

----------

----------

图 2 一个有限状态机实例

-------------------------------------------当前状态 s0 s1 s2 | 事件

-------------------------------------------a0/s0 -a0/s0 | e0

-------------------------------------------a1/s1 --| e1

-------------------------------------------a2/s2 a2/s2 -| e2

--------------------------------------------

表 1 图 2 状态机实例的二维表格表示(动作/下一状 态)

图 2 为一个状态机实例的状态转移图,它的含义是: 在 s0 状态,如果发生 e0 事件,那么就执行 a0 动作,并保 持状态不变; 如果发生 e1 事件,那么就执行 a1 动作,并将状 态转移到 s1 态; 如果发生 e2 事件,那么就执行 a2 动作,并将状 态转移到 s2 态; 在 s1 状态,如果发生 e2 事件,那么就执行 a2 动作,并将

状态转移到 s2 态; 在 s2 状态,如果发生 e0 事件,那么就执行 a0 动作,并将 状态转移到 s0 态; 有限状态机不仅能够用状态转移图表示, 还可以用二维的表格代 表。 一般将当前状态号写在横行上, 将事件写在纵列上, 如表 1 所示。 其中“--”表示空(不执行动作,也不进行状态转移), “an/sn”表示执 行动作 an,同时将下一状态设置为 sn。表 1 和图 2 表示的含义是完全 相同的。 观察表 1 可知,状态机可以用两种方法实现:竖着写(在状态中 判断事件)和横着写(在事件中判断状态)。 这两种实现在本质上是完全 等效的,但在实际操作中,效果却截然不同。

================================== 竖着写(在状态中判断事件)C 代码片段 ================================== cur_state = nxt_state; switch(cur_state){ case s0: if(e0_event){ 就执行 a0 动作,并保持状态不变; 执行 a0 动作; //nxt_state = s0; //因为状态号是自身,所以 //在当前状态中判断事件 //在 s0 状态 //如果发生 e0 事件, 那么

可以删除此句,以提高运行速度。 } else if(e1_event){ 就执行 a1 动作,并将状态转移到 s1 态; 执行 a1 动作; nxt_state = s1; } else if(e2_event){ 就执行 a2 动作,并将状态转移到 s2 态; 执行 a2 动作; nxt_state = s2; } break; case s1: if(e2_event){ 就执行 a2 动作,并将状态转移到 s2 态; 执行 a2 动作; nxt_state = s2; } break; case s2: if(e0_event){ //在 s2 状态 //如果发生 e0 事件, 那么 //在 s1 状态 //如果发生 e2 事件, 那么 //如果发生 e2 事件,那么 //如果发生 e1 事件,那么

就执行 a0 动作,并将状态转移到 s0 态; 执行 a0 动作; nxt_state = s0; } }

================================== 横着写(在事件中判断状态)C 代码片段 ================================== //e0 事件发生时,执行的函数 void e0_event_function(int * nxt_state) { int cur_state;

cur_state = *nxt_state; switch(cur_state){ case s0: 生时,s1 处为空 case s2: 执行 a0 动作; *nxt_state = s0; } //观察表 1, e0 事件发 在

}

//e1 事件发生时,执行的函数 void e1_event_function(int * nxt_state) { int cur_state;

cur_state = *nxt_state; switch(cur_state){ case s0: 生时,s1 和 s2 处为空 执行 a1 动作; *nxt_state = s1; } } //观察表 1, e1 事件发 在

//e2 事件发生时,执行的函数 void e2_event_function(int * nxt_state) { int cur_state;

cur_state = *nxt_state;

switch(cur_state){ case s0: 生时,s2 处为空 case s1: 执行 a2 动作; *nxt_state = s2; } } //观察表 1, e2 事件发 在

上面横竖两种写法的代码片段,实现的功能完全相同,但是,横 着写的效果明显好于竖着写的效果。理由如下: 1、竖着写隐含了优先级排序(其实各个事件是同优先级的),排 在前面的事件判断将毫无疑问地优先于排在后面的事件判断。这种 if/else if 写法上的限制将破坏事件间原有的关系。而横着写不存在此 问题。 2、由于处在每个状态时的事件数目不一致,而且事件发生的时 间是随机的,无法预先确定,导致竖着写沦落为顺序查询方式,结构 上的缺陷使得大量时间被浪费。对于横着写,在某个时间点,状态是 唯一确定的, 在事件里查找状态只要使用 switch 语句, 就能一步定位 到相应的状态,延迟时间可以预先准确估算。而且在事件发生时,调 用事件函数,在函数里查找唯一确定的状态,并根据其执行动作和状 态转移的思路清晰简洁,效率高,富有美感。

总之,我个人认为,在软件里写状态机,使用横着写的方法比较 妥帖。

竖着写的方法也不是完全不能使用,在一些小项目里,逻辑不太 复杂,功能精简,同时为了节约内存耗费,竖着写的方法也不失为一 种合适的选择。 在 FPGA 类硬件设计中,以状态为中心实现控制电路状态机(竖 着写)似乎是唯一的选择,因为硬件不太可能靠事件驱动(横着写)。不 过,在 FPGA 里有一个全局时钟,在每次上升沿时进行状态切换,使 得竖着写的效率并不低。虽然在硬件里竖着写也要使用 IF/ELSIF 这 类查询语句(用 VHDL 开发),但他们映射到硬件上是组合逻辑,查询 只会引起门级延迟(ns 量级),而且硬件是真正并行工作的,这样竖着 写在硬件里就没有负面影响。因此,在硬件设计里,使用竖着写的方 式成为必然的选择。 这也是为什么很多搞硬件的工程师在设计软件状 态机时下意识地只使用竖着写方式的原因,盖思维定势使然也。

TCP 和 PPP 框架协议里都使用了有限状态机,这类软件状态机 最好使用横着写的方式实现。以某 TCP 协议为例,见图 3,有三种类 型的事件: 上层下达的命令事件; 下层到达的标志和数据的收包事件; 超时定时器超时事件。

上层命令(open,close)事件

-----------------------------------------------------| timeout -----------------------------------------------------RST/SYN/FIN/ACK/DATA 等收包事件 TCP | <----------超时事件

图 3 三大类 TCP 状态机事件

由图 3 可知,此 TCP 协议栈采用横着写方式实现,有 3 种事件 处理函数,上层命令处理函数(如 tcp_close);超时事件处理函数 (tmr_slow);下层收包事件处理函数(tcp_process)。值得一提的是,在 收包事件函数里,在各个状态里判断 RST/SYN/FIN/ACK/DATA 等标 志(这些标志类似于事件),看起来象竖着写方式,其实,如果把包头 和数据看成一个整体,那么,RST/SYN/FIN/ACK/DATA 等标志就不 必被看成独立的事件,而是属于同一个收包事件里的细节,这样,就 不会认为在状态里查找事件,而是总体上看,是在收包事件里查找状 态(横着写)。

在 PPP 里更是到处都能见到横着写的现象,有时间的话再细说。 我个人感觉在实现 PPP 框架协议前必须了解横竖两种写法,而且只

有使用横着写的方式才能比较完美地实现 PPP。

──────────传说中的分隔符──────────── ──────────────────☆

【转载 6】用 C 语言实现有限状态机--读《C 专家编程》

有限状态机(finite state machine)是一个数学概念,如果把它运用于程 序中,可以发挥很大的作用。它是一种协议,用于有限数量的子程序 ("状态")的发展变化。每个子程序进行一些处理并选择下一种状态(通 常取决于下一段输入)。

有限状态机(FSM)可以用作程序的控制结构。 FSM 对于那些基于输入 的在几个不同的可选动作中进行循环的程序尤其合适。 投币售货机就 是 FSM 的一个好例子。另外一个你可以想到的复杂的例子就是你正 在用的东西,想到了吗?没错,就是操作系统。在投币售货机的例子 中,输入是硬币,输出是待售商品,售货机有"接受硬币","选择商 品","发送商品"和"找零钱"等几种状态。

它的基本思路是用一张表保存所有可能的状态, 并列出进入每个状态 时可能执行的所有动作,其中最后一个动作就是计算(通常在当前状 态和下一次输入字符的基础上,另外再经过一次表查询)下一个应该

进入的状态。你从一个"初始状态"开始。在这一过程中,翻译表可能 告诉你进入了一个错误状态,直到到达结束状态。

在 C 语言中,有好几种方法可以用来表达 FSM,但它们绝大多数都 是基于函数指针数组。一个函数指针数组可以像下面这样声明:

void (*state[MAX_STATES]) ();

如果知道了函数名,就可以像下面这样对数组进行初始化。

extern int a(),b(),c(),d();

int (*state[]) ()={a,b,c,c};

可以通过数组中的指针来调用函数:

(*state[i]) ();

所有函数必须接受同样的参数,并返回同种类型的返回值(除非你把 数组元素做成一个联合)。函数指针是很有趣的。注意,我们可以去 掉指针形式,把上面的调用写成:

state[i] ();

甚至

(******state[i]) ();

这是一个在 ANSI C 中流行的不良方法:调用函数和通过指针调用函 数(或任意层次的指针间接引用)可以使用同一种语法。

如果你想干得漂亮一点, 可以让状态函数返回一个指向通用后续函数 的指针,并把它转换为适当的类型。这样,就不需要全局变量了。如 果你不想搞得太花哨, 可以使用一个 switch 语句作为一种简朴的状态 机, 方法是赋值给控制变量并把 switch 语句放在循环内部。 关于 FSM 还有最后一点需要说明: 如果你的状态函数看上去需要多个不同的参 数, 可以考虑使用一个参数计数器和一个字符串指针数组, 就像 main 函数的参数一样。 我们熟悉的 int argc,char *argv[]机制是非常普遍的, 可以成功地应用在你所定义的函数中。

☆──────────────────────传说中的分隔 符──────────────────────────── ──☆

【原创之源程序】密码锁(最简单的实现 switch/if-else 形的)

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef enum{

STATE0 = 0,

STATE1,

STATE2,

STATE3,

STATE4,//password pass

//...ADD here

}STATE;

typedef enum{

INPUT1 = '2',

INPUT2 = '4',

INPUT3 = '7',

INPUT4 = '9',

}INPUT;

int main()

{

char ch;

STATE current_state = STATE0;

while(1){

printf("请输入数字进行解码:");

while((ch = getchar()) != '\n'){

if((ch < '0') || (ch > '9')){

printf("非数字,请重新输入!\n");

break;

}

switch(current_state){

case STATE0:

if(ch == '2') = STATE1;

current_state

break;

case STATE1:

if(ch == '4')

current_state = STATE2;

break;

case STATE2:

if(ch == '7')

current_state = STATE3;

break;

case STATE3:

if(ch == '9')

current_state = STATE4;

break;

default:

current_state = STATE0;

break;

}

}

if(current_state == STATE4){

printf("Correct, lock is open!\n");

break;

}else

printf("Wrong, unlocked!\n");

}

return 0;

} #include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef enum{

STATE0 = 0,

STATE1,

STATE2,

STATE3,

STATE4,//password pass

//...ADD here

}STATE;

typedef enum{

INPUT1 = '2',

INPUT2 = '4',

INPUT3 = '7',

INPUT4 = '9',

}INPUT;

int main()

{

char ch;

STATE current_state = STATE0;

while(1){

printf("请输入数字进行解码:");

while((ch = getchar()) != '\n'){

if((ch < '0') || (ch > '9')){

printf("非数字,请重新输入!\n");

break;

}

switch(current_state){

case STATE0:

if(ch == '2') = STATE1;

current_state

break;

case STATE1:

if(ch == '4')

current_state = STATE2;

break;

case STATE2:

if(ch == '7')

current_state = STATE3;

break;

case STATE3:

if(ch == '9')

current_state = STATE4;

break;

default:

current_state = STATE0;

break;

}

}

if(current_state == STATE4){

printf("Correct, lock is open!\n");

break;

}else

printf("Wrong, unlocked!\n");

}

return 0;

}


相关文档

单片机编程中有限状态机的应用
状态机思路在单片机程序设计中的应用
有限状态机在单片机编程中的应用
状态机思路在单片机程序设计中的应用状态机的概念状态机是软件
状态机在单片机C程序中的应用
状态机思路在程序设计中的应用
状态机思想在程序设计中的应用(上)
单片机应用系统中的编程语言
单片机案例教学及在系统编程技术的应用
论文:单片机应用系统中的编程语言
电脑版