分享

有限状态机在C语言编程中的各种应用

 xinyz4104 2015-08-05
 

有限状态机在C语言编程中的各种应用

1. 使用case的有限状态机

  1. //使用switch/case或者if/else实现的基于状态机(FSM)的密码锁  
  2. //只有正确输入密码 2479 才能解锁   
  3. #include <stdio.h>    
  4. #include <stdlib.h>    
  5. #include <string.h>     
  6.   
  7. typedef enum{     
  8.     STATE0 = 0,     
  9.     STATE1,     
  10.     STATE2,    
  11.     STATE3,     
  12.     STATE4,    
  13. }STATE;  
  14.     
  15.   
  16. int main()     
  17.   
  18. {     
  19.     char ch;   
  20.     STATE current_state = STATE0;      
  21.     while(1){     
  22.         printf("In put password:");     
  23.         while((ch = getchar()) != '\n')  
  24.         {     
  25.             if((ch < '0') || (ch > '9'))  
  26.             {     
  27.                 printf("Input num,ok?/n");     
  28.                 break;     
  29.             }     
  30.             switch(current_state){     
  31.             case STATE0:     
  32.                 if(ch == '2')   current_state = STATE1;     
  33.                 break;     
  34.             case STATE1:     
  35.                 if(ch == '4')   current_state = STATE2;     
  36.                 break;     
  37.             case STATE2:     
  38.                 if(ch == '7')   current_state = STATE3;     
  39.                 break;     
  40.             case STATE3:     
  41.                 if(ch == '9')   current_state = STATE4;     
  42.                 break;     
  43.             default:     
  44.                 current_state = STATE0;     
  45.                 break;     
  46.             }     
  47.         }   //end inner while   
  48.   
  49.         if(current_state == STATE4){     
  50.             printf("Correct, lock is open!\n");     
  51.             current_state =   STATE0;  
  52.               
  53.         }else  
  54.         {  
  55.             printf("Wrong, locked!\n");     
  56.             current_state =   STATE0;  
  57.               
  58.         }  
  59.         break;  
  60.     }     
  61.     return 0;     
  62.   
  63. }   
  64. //代码摘自http://blog.csdn.net/qp120291570/article/details/8634582   
2. 使用函数指针的有限状态机的应用

  1. //使用函数指针实现的基于状态机(FSM)的密码锁  
  2. //只有正确输入密码 2479 才能解锁   
  3. #include <stdio.h>    
  4. //这个秘密锁的密码是xxxx2479,就是说最后4位是2479,前面若干为为0~9里的数字,也可没有   
  5. #include <stdlib.h>    
  6. #include <string.h>     
  7.   
  8. //定义锁事件处理函数的函数指针类型  
  9. typedef void (*lock_func_temp)(char c);  
  10. typedef lock_func_temp (*lock_func)(char c);  
  11. lock_func state;  
  12.   
  13. //函数声明队列   
  14. //列出来,交叉引用才不会报错   
  15. lock_func init_state(char ch);  
  16. lock_func state1(char ch);  
  17. lock_func state2(char ch);  
  18. lock_func state3(char ch);  
  19. lock_func state4(char ch);  
  20.   
  21. //初始状态   
  22. lock_func init_state(char ch)  
  23. {  
  24.     if ((ch < '0') || (ch > '9'))  
  25.         return NULL;      
  26.     else  
  27.         return state1(ch); //这里还必须得有参数,不然就会漏处理一个字符   
  28. }  
  29.   
  30. //状态1   
  31. lock_func state1(char ch)  
  32. {  
  33.     if (ch == '2')  
  34.     {  
  35.         return state2;        
  36.     } else   
  37.     {  
  38.         return init_state;  
  39.     }  
  40. }  
  41.   
  42. //状态2   
  43. lock_func state2(char ch)  
  44. {  
  45.     if (ch == '4')  
  46.     {  
  47.         return state3;        
  48.     } else   
  49.     {  
  50.         return init_state;  
  51.     }     
  52. }  
  53.   
  54. //状态3   
  55. lock_func state3(char ch)  
  56. {  
  57.     if (ch == '7')  
  58.     {  
  59.         return state4;        
  60.     } else   
  61.     {  
  62.         return init_state;  
  63.     }  
  64. }  
  65.   
  66. //状态4   
  67. lock_func state4(char ch)  
  68. {  
  69.     if (ch == '9')  
  70.     {  
  71.         printf("Correct, lock is open!\n");   
  72.         return NULL;          
  73.     } else   
  74.     {  
  75.         return init_state;  
  76.     }  
  77. }  
  78.   
  79. //结束状态是NULL  
  80. //就是通过 return NULL;表达的结束状态.   
  81.    
  82. //状态转换在这里   
  83. void lock_handle (void)  
  84. {  
  85.     char ch;  
  86.     state = init_state;  
  87.     while (state)  
  88.     {  
  89.         ch = getchar();  
  90.         state = (*state)(ch);  
  91.     }  
  92. }   
  93.   
  94.    
  95. int main()     
  96. {         
  97.     lock_handle();  
  98. }   

3.基于状态矩阵的FSM应用

参考:http://www./archives/557


嵌入式系统中的状态机设计心得

在使用iTRON类OS的嵌入式系统中,除了驱动程序以外,大多数模块也就是中间件和应用程序是以任务(TASK)的形式设计的。而iTRON类OS大多采用C语言实现,于是用状态机的方式实现功能模块成为了主要的设计方法。
至于说面向对象,只要是稍微严谨一点的嵌入式系统,设计上要求程序完全覆盖所有的可能情况。程序不可能在紧急情况下抛出异常等待调试。同时由于对硬件和其它应用模块的往往具有严重的耦合性,代码的重用和扩展也不是那么随心所欲。当然还有基于语言的执行速度之类的考虑。这种情况下C语言往往取代大多数现代语言成为了主角吧。

iTRON类OS的任务间通讯一般通过两种方法,事件(EVENT)或者消息(MESSAGE)。
事件处理快捷,但是无法附带任何参数且不能叠加。
消息虽然传递稍慢,不过却可以通过内存池等方式附带一定数量的参数。而且多个同样的消息可以累积在消息栈中依次处理。

如果形象得比喻一下:
事件就是一串比特码,由特定为的0或1状态来判断事件是否发生,而任务以它自己的优先级别处理各种事件。
消息就是一个缓冲区,OS以FIFO的方式把消息依从旧到新的顺序分发给任务进行对应处理。

说到这里,我想强调一下本文讨论的重点是通过状态机的方式处理消息的模型。至于事件的对应,可能今后会另外展开讨论。

一个由OS管辖的嵌入式系统中的应用模块,在程序角度上是没有main函数,也不会被退出的(除非切断电源)。只要做过任何GUI程序,就不难理解这一点。程序被执行的瞬间,OS调用程序的初始化部分(Initialization),然后每隔一个固定的时间片程序的执行部分(Execute),当程序被关闭时休止部分(Exit)会被调用。
而嵌入式系统与桌面GUI系统的不同之处在于:
系统的电源被加载,OS完成初始化动作之后,往往会启动一个电源管理模块,而这个模块则会调用所有应用模块的初始化部分。
另一方面,OS或者电源管理模块在监测到电源即将被切断时,则调用所有应用模块的休止部分。
在系统正常运行时,OS会依据各个任务的优先级依次调用它们的执行部分,并且向它们分发各自所属的消息。

应用模块在收到消息后并不是立刻进行处理。设计良好的应用模块往往内部划分为多个状态,简单来说可以有种四到五种状态:睡眠状态,初始状态,空闲状态,繁忙状态和故障状态。当然了,根据不同的设计要求可以做相应的修改和扩充。应用模块内部根据不同的状态和可能接收到的所有消息编织出一张状态对应表。在表中填入适当的函数指针以响应不同状态下对各种消息的处理过程。这就是嵌入式系统中普遍的状态机模式。

举一个状态机实现的简单例子:
我们将建立一个假象的小机器人,这个机器人能坐能走还能打架,打坏了还能自己修复。我打算用状态机的模式来实现这些功能的框架。

/* 机器人能接受的事件 */
enum {
EVENT_POWERON = 0,
EVENT_POWEROFF,
EVENT_WALK,
EVENT_FIGHT,
EVENT_REST,
EVENT_REPAIR
EVENT_SIZE
};

/* 机器人的状态 */
enum {
STATUS_SLEEP,
STATUS_INITIAL,
STATUS_NORMAL,
STATUS_FIGHTING,
STATUS_BROKEN,
STATUS_MAX
};
/* 状态机函数指针的原型 */
typedef void (*MATRIX_FP)(const void*)

/* 状态机函数表格 */
const MATRIX_FP s_Robot_Matrix [EVENT_SIZE][STATUS_SIZE] = {
/* EVENT_POWERON */
{Robot_PowerOn, Robot_NoProcess, Robot_NoProcess, Robot_NoProcess, Robot_NoProcess},
/* EVENT_POWEROFF */
{Robot_NoProcess, Robot_PowerOff, Robot_PowerOff, Robot_PowerOff, Robot_PowerOff},
/* EVENT_WALK */
{Robot_NoProcess, Robot_NoProcess, Robot_Walk, Robot_Walk, Robot_NoProcess},
/* EVENT_FIGHT */
{Robot_NoProcess, Robot_NoProcess, Robot_BattleMode, Robot_Fight, Robot_NoProcess},
/* EVENT_REST */
{Robot_NoProcess, Robot_NoProcess, Robot_Rest, Robot_NormalMode, Robot_NoProcess},
/* EVENT_REPAIR */
{Robot_NoProcess, Robot_NoProcess, Robot_Repair, Robot_NoProcess, Robot_Repair},
};

/* 机器人事件接受分发函数 */
void Api_Robot_Execute(void *pMsgData) {
byEvent = Api_GetRobotEvent(pMsgData);
byStatus = Api_GetRobotStatus();
if (NULL != s_Robot_Matrix[byEvent][byStatus]) {
(s_Robot_Matrix[byEvent][byStatus])((const void*)(pMsgData);
} else {
Robot_NoProcess(pMsgData);
}
return;
}

以上是状态机的雏形。
我申明了机器人能响应的各种事件和机器人内部的各种状态。
同时用它们编织起一个状态/事件响应函数指针二维数组,也就是一直说到现在的状态机的矩阵。
最后我设计了一个对外来事件进行解释,对内部状态进行读取,并最终确定调用矩阵中具体哪个函数的事件分发函数。

下面在简单列举一下填写在矩阵中所有成员函数将实现什么样的功能。

/* 没有任何功能的空函数 */
void Robot_NoProcess(void *pMsgData);
/* 电源加载,初始化操作 */
void Robot_PowerOn(void *pMsgData);
/* 电源关闭,休止操作 */
void Robot_PowerOff(void *pMsgData);
/* 步行动作 */
void Robot_Walk(void *pMsgData);
/* 切换到战斗模式 */
void Robot_BattleMode(void *pMsgData);
/* 战斗动作 */
void Robot_Fight(void *pMsgData);
/* 休息动作 */
void Robot_Rest(void *pMsgData);
/* 切换到一般模式 */
void Robot_NormalMode(void *pMsgData);
/* 修理动作 */
void Robot_Repair(void *pMsgData);

机器人在启动和停止时要进行初始化处理和休止处理。
初始化处理完成后,默认为一般状态。
一般状态下可以行走,休息和修复战斗伤害。
在一般状态下执行收到攻击指令可以切换到攻击状态。
攻击状态下可以行走和攻击,并且可以通过休息指令切换回一般状态。
当机器人的对手太强大,自己被打得七零八落的时候,会强制切换到破损状态。
在破损状态下就只能进行修复动作了。
具体的实现我就不说了,如果有兴趣可以想象一下各个函数该怎么实现,一定会很有意思的。

另外还有两个函数没有交代:

/* 消息/事件转换函数 */
int Api_GetRobotEvent(void *pMsgData);
/* 内部状态取得函数 */
int Api_GetRobotStatus(void);

消息事件转换函数把外部的消息转换成状态机矩阵能够识别的事件代码。
而内部状态取得函数就像它的名字一样,只管返回内部状态,供调用状态机矩阵中的函数指针而使用。

在一个状态机系统的设计过程中,根据我自己的体会,我觉得以下几点一定要严格遵守。
在每一次将消息转化成事件后,读且仅读一次内部状态。并由此决定调用哪个成员函数。
成员函数中绝对不能再次读取状态并以它为分枝条件进行不同的处理。
一个外部模块绝对不能通过本模块的公开API直接修改本模块的内部状态。
状态机矩阵的成员函数宁可数量偏多内容类似,而切勿追求统一,盲目精简代码。
必要的时候一个状态/事件,响应一个成员函数,也比一个函数通过内部无数的分歧判断条件进行不同的处理来的容易维护。

关于状态机的内容有很多前人的研究成果。我只是在实时操作系统下的嵌入式环境中得到了一些微不足道的经验。
本文旨在抛砖引玉,希望有更多的朋友能够一起参与讨论。

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多