Linux有限状态机FSM的理解与实现

有限状态机(finite state machine)简称FSM,表示有限个状态及在这些状态之间的转移和动作等行为的数学模型,在计算机领域有着广泛的应用。FSM是一种逻辑单元内部的一种高效编程方法,在服务器编程中,服务器可以根据不同状态或者消息类型进行相应的处理逻辑,使得程序逻辑清晰易懂。

那有限状态机通常在什么地方被用到?

处理程序语言或者自然语言的 tokenizer,自底向上解析语法的parser,
各种通信协议发送方和接受方传递数据对消息处理,游戏AI等都有应用场景。

状态机有以下几种实现方法,我将一一阐述它们的优缺点。

一、使用if/else if语句实现的FSM
使用if/else if语句是实现的FSM最简单最易懂的方法,我们只需要通过大量的if /else if语句来判断状态值来执行相应的逻辑处理。

看看下面的例子,我们使用了大量的if/else if语句实现了一个简单的状态机,做到了根据状态的不同执行相应的操作,并且实现了状态的跳转。

//比如我们定义了小明一天的状态如下
enum
{
  GET_UP,
  GO_TO_SCHOOL,
  HAVE_LUNCH,
  GO_HOME,
  DO_HOMEWORK,
  SLEEP,
};

int main()
{
  int state = GET_UP;
  //小明的一天
  while (1)
  {
    if (state == GET_UP)
    {
      GetUp(); //具体调用的函数
      state = GO_TO_SCHOOL; //状态的转移
    }
    else if (state == GO_TO_SCHOOL)
    {
      Go2School();
      state = HAVE_LUNCH;
    }
    else if (state == HAVE_LUNCH)
    {
      HaveLunch();
    }
    ...
    else if (state == SLEEP)
    {
      Go2Bed();
      state = GET_UP;
    }
  }

  return 0;
}

看完上面的例子,大家有什么感受?是不是感觉程序虽然简单易懂,但是使用了大量的if判断语句,使得代码很低端,同时代码膨胀的比较厉害。这个状态机的状态仅有几个,代码膨胀并不明显,但是如果我们需要处理的状态有数十个的话,该状态机的代码就不好读了。

二、使用switch实现FSM

使用switch语句实现的FSM的结构变得更为清晰了,其缺点也是明显的:这种设计方法虽然简单,通过一大堆判断来处理,适合小规模的状态切换流程,但如果规模扩大难以扩展和维护。

int main()
{
  int state = GET_UP;
  //小明的一天
  while (1)
  {

    switch(state)
    {
    case GET_UP:
      GetUp(); //具体调用的函数
      state = GO_TO_SCHOOL; //状态的转移
      break;
    case GO_TO_SCHOOL:
      Go2School();
      state = HAVE_LUNCH;
      break;
    case HAVE_LUNCH:
      HaveLunch();
      state = GO_HOME;
      break;
      ...
    default:
      break;
    }
  }

  return 0;
}

三、使用函数指针实现FSM

使用函数指针实现FSM的思路:建立相应的状态表和动作查询表,根据状态表、事件、动作表定位相应的动作处理函数,执行完成后再进行状态的切换。

当然使用函数指针实现的FSM的过程还是比较费时费力,但是这一切都是值得的,因为当你的程序规模大时候,基于这种表结构的状态机,维护程序起来也是得心应手。

下面给出一个使用函数指针实现的FSM的框架:

我们还是以“小明的一天”为例设计出该FSM。

先给出该FSM的状态转移图:

下面讲解关键部分代码实现

首先我们定义出小明一天的活动状态

//比如我们定义了小明一天的状态如下
enum
{
  GET_UP,
  GO_TO_SCHOOL,
  HAVE_LUNCH,
  DO_HOMEWORK,
  SLEEP,
};

我们也定义出会发生的事件

enum
{
  EVENT1 = 1,
  EVENT2,
  EVENT3,
};

定义状态表的数据结构

typedef struct FsmTable_s
{
  int event;  //事件
  int CurState; //当前状态
  void (*eventActFun)(); //函数指针
  int NextState; //下一个状态
}FsmTable_t;

接下来定义出最重要FSM的状态表,我们整个FSM就是根据这个定义好的表来运转的。

FsmTable_t XiaoMingTable[] =
{
  //{到来的事件,当前的状态,将要要执行的函数,下一个状态}
  { EVENT1, SLEEP,      GetUp,    GET_UP },
  { EVENT2, GET_UP,     Go2School,  GO_TO_SCHOOL },
  { EVENT3, GO_TO_SCHOOL,  HaveLunch,  HAVE_LUNCH },
  { EVENT1, HAVE_LUNCH,   DoHomework,  DO_HOMEWORK },
  { EVENT2, DO_HOMEWORK,   Go2Bed,    SLEEP },

  //add your codes here
};

状态机的注册、状态转移、事件处理的动作实现

/*状态机注册*/
void FSM_Regist(FSM_t* pFsm, FsmTable_t* pTable)
{
  pFsm->FsmTable = pTable;
}

/*状态迁移*/
void FSM_StateTransfer(FSM_t* pFsm, int state)
{
  pFsm->curState = state;
}

/*事件处理*/
void FSM_EventHandle(FSM_t* pFsm, int event)
{
  FsmTable_t* pActTable = pFsm->FsmTable;
  void (*eventActFun)() = NULL; //函数指针初始化为空
  int NextState;
  int CurState = pFsm->curState;
  int flag = 0; //标识是否满足条件
  int i;

  /*获取当前动作函数*/
  for (i = 0; i<g_max_num; i++)
  {
    //当且仅当当前状态下来个指定的事件,我才执行它
    if (event == pActTable[i].event && CurState == pActTable[i].CurState)
    {
      flag = 1;
      eventActFun = pActTable[i].eventActFun;
      NextState = pActTable[i].NextState;
      break;
    }
  }

  if (flag) //如果满足条件了
  {
    /*动作执行*/
    if (eventActFun)
    {
      eventActFun();
    }

    //跳转到下一个状态
    FSM_StateTransfer(pFsm, NextState);
  }
  else
  {
    // do nothing
  }
}

主函数我们这样写,然后观察状态机的运转情况

int main()
{
  FSM_t fsm;
  InitFsm(&fsm);
  int event = EVENT1;
  //小明的一天,周而复始的一天又一天,进行着相同的活动
  while (1)
  {
    printf("event %d is coming...\n", event);
    FSM_EventHandle(&fsm, event);
    printf("fsm current state %d\n", fsm.curState);
    test(&event);
    sleep(1); //休眠1秒,方便观察
  }

  return 0;
}

看一看该状态机跑起来的状态转移情况:

上面的图可以看出,当且仅当在指定的状态下来了指定的事件才会发生函数的执行以及状态的转移,否则不会发生状态的跳转。这种机制使得这个状态机不停地自动运转,有条不絮地完成任务。

与前两种方法相比,使用函数指针实现FSM能很好用于大规模的切换流程,只要我们实现搭好了FSM框架,以后进行扩展就很简单了(只要在状态表里加一行来写入新的状态处理就可以了)。

需要FSM完整代码的童鞋请访问我的github

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

时间: 2017-06-24

Linux shell脚本编程if语句的使用方法(条件判断)

if 语句格式if  条件then Commandelse Commandfi        别忘了这个结尾If语句忘了结尾fitest.sh: line 14: syntax error: unexpected end of fi     if 的三种条件表达式 ifcommandthen if 函数then 命令执行成功,等于返回0 (比如grep ,找到匹配)执行失败,返回非0 (grep,没找到匹配)if [ expression_r_r_r  ]then    表达式结果为真,则返回0

linux shell流程控制语句实例讲解(if、for、while、case语句实例)

一.shell条件语句(if用法) if语句结构[if/then/elif/else/fi] 复制代码 代码如下: if 条件测试语句 then action [elif 条件 action else action ] fi 如果对于:条件测试语句不是很清楚,可以参考:linux shell 逻辑运算符.逻辑表达式详解shell命令,可以按照分号分割,也可以按照换行符分割.如果想一行写入多个命令,可以通过"';"分割.如: 复制代码 代码如下: [chengmo@centos5 ~]$

linux shell中 if else以及大于、小于、等于逻辑表达式介绍

比如比较字符串.判断文件是否存在及是否可读等,通常用"[]"来表示条件测试. 注意:这里的空格很重要.要确保方括号的空格.笔者就曾因为空格缺少或位置不对,而浪费好多宝贵的时间. if ....; then....elif ....; then....else....fi[ -f "somefile" ] :判断是否是一个文件[ -x "/bin/ls" ] :判断/bin/ls是否存在并有可执行权限[ -n "$var" ]

Linux Shell中curl和wget使用代理IP的方法教程

前言 大家都知道,在Linux Shell中提供两个非常实用的命令来爬取网页,它们分别是 curl 和 wget,本文将给大家详细介绍关于在Linux Shell中curl和wget使用代理IP的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看吧. curl 和 wget 使用代理 curl 支持 http.https.socks4.socks5 wget 支持 http.https 代理示例: #!/bin/bash # # curl 支持 http.https.socks4.so

Linux Shell中三种引号的用法及区别

Linux Shell中有三种引号,分别为双引号(" ").单引号(' ')以及反引号(` `). 其中双引号对字符串中出现的$.''.`和\进行替换:单引号不进行替换,将字符串中所有字符作为普通字符输出,而反引号中字符串作为shell命令执行,并返回执行结果.具体含义如下: 双引号(" "):在双引号中,除了$, '', `和\以外所有的字符都解释成字符本身. 单引号(' '):在单引号中所有的字符包括特殊字符($,'',`和\)都将解释成字符本身而成为普通字符.

Linux shell中的printf的详细用法

Linux shell中的printf的详细用法 一 语法 printf '输出类型输出格式' 输出内容 输出类型: %ns:输出字符串.n是数字指代输出几个字符. %ni:输出整数.n是数字指代输出几个数字. %m.n:输出浮点数.m和n是数字,指代输出的整数位数和小数 如%8.2代表共输出8位数,其中2位是小数,6位是整数. 输出格式:  二 实战 [root@localhost ~]# printf %s 1 2 3 4 5 6 123456[root@localhost ~]# prin

linux shell 中 2>&amp;1的含义

linux shell 中"2>&1"的含义 脚本: nohup /mnt/Nand3/H2000G  >/dev/null  2>&1  & 对于& 1 更准确的说应该是文件描述符 1,而1 一般代表的就是STDOUT_FILENO,实际上这个操作就是一个dup2(2)调用.他标准输出到all_result ,然后复制标准输出到文件描述符2(STDERR_FILENO),其后果就是文件描述符1和2指向同一个文件表项,也可以说错误的输出

linux shell中实现循环日期的实例代码

下面通过一段代码给大家介绍linux shell中实现循环日期,具体代码如下所示: #!/usr/bin/env bash start_date="20180726" end_date="20180830" while [ "$start_date" -le "$end_date" ]; do stat_date=`date -d "$start_date" +%Y-%m-%d` echo $stat_da

linux shell 中数组的定义和for循环遍历的方法

linux shell中的语法和普通编程语言 c/c++ java 的不太一样,平时用的不多,所以总是记不住,写脚本才会去查怎么用. 今天突然被问到数组怎么去遍历.平时写shell脚本也经常遍历数组,但是一下没答上来,被鄙视了. 所以平时学习还是好好总结吧,不能每次都问度娘谷爷.IT 知识体系较为庞大,细节的东西也太多,平时遇到问题应该的多总结记笔记. linux 中定义一个数据的语法为: variable=(arg1 arg2 arg3 ....) 中间用空格分开.数组的下标从0开始. 1 获

linux shell中的比较符号与特殊符号介绍

shell字符串比较.判断是否为数字 二元比较操作符,比较变量或者比较数字.注意数字与字符串的区别. 整数比较 -eq 等于,如:if [ "$a" -eq "$b" ] -ne 不等于,如:if [ "$a" -ne "$b" ] -gt 大于,如:if [ "$a" -gt "$b" ] -ge 大于等于,如:if [ "$a" -ge "$b"

Linux Shell中的特殊符号和含义简明总结(包含了绝大部份)

在Linux Shell中有很多的特殊符号,这对于我们写Shell脚本时要特别留意:一方面要知道这些特殊符号的用法,这些符号用好了可以达到事半功倍的效果:但另一方面要避免这些特殊符号的过度使用而导致脚本难以调试.难以阅读. 这些特殊符号罗列出来大致如下: 复制代码 代码如下: # ; ;; . , / / 'string'| ! $ ${} $? $$ $* "string"* ** ? : ^ $# $@ `command`{} [] [[]] () (()) || &~ ~

深入理解Linux shell中2&gt;&1的含义(全网最全,看完就懂)

A.首先了解下1和2在Linux中代表什么 在Linux系统中0 1 2是一个文件描述符 名称 代码 操作符 Java中表示 Linux 下文件描述符(Debian 为例) 标准输入(stdin) 0 < 或 << System.in /dev/stdin -> /proc/self/fd/0 -> /dev/pts/0 标准输出(stdout) 1 >, >>, 1> 或 1>> System.out /dev/stdout ->