事件队列与状态机的工程实践

2024-05-13

2866 字

一、状态机概要

在有穷自动机一文中从理论角度给出了状态机（或做自动机）的定义，本文从编码的角度来进一步阐述状态机的原理；状态机的实现无非是三个要素：状态、事件、行为 。用更直白的话来说就是：

当前系统处于什么状态？
当前发生了什么事？
在这样的状态下发生了这样的事，系统要怎么应对？

一句话描述状态机就是：某个对象在当前状态下，接收到某个事件执行某个动作，将对象的状态切换为下一个状态；当然在理论中对于状态机的定义有一个 转移函数 的概念，用于描述了在给定输入条件下从一个状态到另一个状态的转移过程，这个概念在实际编码过程中已隐含在其中了

二、状态机实现方式

现在我们使用C语言定义一些状态用来模拟一次网络请求，如下所示：

typedef enum
{
    STATE_init,
    STATE_connect,
    STATE_query,
    STATE_finish

} FSMState;

2.1 switch-case方式

这种方式可以说是最常见的方式，其实现形式也比较简单：

int main(){
    FSMState fsmState;
    while (fsmState != STATE_finish)
    {
        switch (fsmState)
        {
            case STATE_init:            
                handleStateInit();          //初始化状态响应
                break;
            case STATE_connect:
                handleStateConnect();       //连接服务状态响应
                break;
            case STATE_query:
                handleStateQuery();         //查询服务状态响应
                break;
            case STATE_finish:
                handleStateFinish();        //结束状态响应
                break;
            }
    }
}

这里其实是有一些疑问的，对比上面所说的状态机的三个要素：状态、事件、行为，能清晰分辨出来第一个要素状态就是 fsmState ，行为就是对应的处理函数，那么事件呢？是什么？首先要明白的是 状态机状态的跃迁都是受事件驱动的 ，所以在处理函数中一定隐含着事件。现在试着拆解一下在这个过程中的事件 :

typedef enum {
  EVENT_start,
  EVENT_connect_success,
  EVENT_connect_error,
  EVENT_query_success,
  EVENT_query_error
}Event;

将上面的switch-case结构的状态机展开，得到如下形式：

int main(){
    FSMState fsmState;
    Event event;
    while (fsmState != STATE_finish)
    {
    switch (fsmState)
    {
        case STATE_init:            
            switch (event)
            {
                case EVENT_start: 
                    /*STATE_init 状态下 EVENT_start 事件的响应，切换状态*/
                    doActionForStart();
                    fsmState = STATE_connect;
                    break;
                default:
                    /*STATE_init 状态下 其他 事件的响应，不处理，不切换状态*/
                    doActionNULL(); 
                    break;
            }
            break;
        case STATE_connect:
            switch (event)
            {
                case EVENT_connect_success: 
                    doActionForConnectSuccess();
                    fsmState = STATE_query;
                    break;
                case EVENT_connect_error: 
                    doActionForConnectError();
                    fsmState = STATE_finish;
                    break;
                default:
                    /*STATE_connect 状态下 其他 事件的响应，不处理，不切换状态*/
                    doActionNULL(); 
                    break;
            }
            break;
        case STATE_query:
            ......
            break;
        case STATE_finish:
            ......
            break;
        }
    }
}

当然并不是任何一个状态都要处理事件，因此上面有很多的 doActionNULL() ，在实际开发中这些是可以省略。

2.2 表驱动方式

在 2.1 所展示的方式中，可以看出当随着状态和事件越来越多，整个状态机的长度会非常的长，不利于维护，此时可以考虑采用表格驱动的方式：

定义状态表：

typedef struct
{ 
    Event event;                // 触发事件
    FSMState curState;          // 当前状态 
    void (*trans_action)(Event *event, void *params);  // 响应函数
    FSMState nextState;            // 跳转状态

}FSMTable;

要注意的是表格驱动方式比较迷惑的地方在于，跳转状态是事先确定的，这看起来似乎转移函数执行成功与否，系统都将按着既定的状态走，其实不然，表格驱动方式由两个元素来控制流程，第一个是状态，第二个是事件，关键就在于响应函数中去控制事件的跃迁

表驱动的方式，其实就是维护一张状态表，为了精确的描绘出状态与事件以及转移函数的关系，同时为了避免无意义的状态和事件处理，首先要做的是绘制出系统的状态图：

状态图中每一条线就是驱动表中的一条数据，由此可以得出：


FSMTable fsmtb[] = { 
    /*事件                    当前状态        响应函数                  下一个状态 */
    { EVENT_start,           STATE_init,    handleInitForStart,      STATE_connect },
    { EVENT_connect_success, STATE_connect, handleConnectForSuccess, STATE_query }, 
    { EVENT_query_success,   STATE_query,   handleQueryForSuccess,   STATE_finish },
    { EVENT_connect_error,   STATE_connect, handleConnectForError,   STATE_finish },
    { EVENT_connect_error,   STATE_query,   handleQueryForError,     STATE_finish }
};

注意响应函数的写法：

void handleInitForStart(Event *event, void *params){
    //初始化资源，连接网络
    int result = connect(ip,port);
    if(result){
        *event = EVENT_connect_success;
    } else {
        *event = EVENT_connect_error;
    }
}

void handleConnectForSuccess(Event *event, void *params){
    //连接成功，开始查询
    int result = query(ip,port);
    if(result){
        *event = EVENT_query_success;
    } else {
        *event = EVENT_query_error;
    }
}

void handleQueryForSuccess(Event *event, void *params){
    //查询成功，结束
    *event = EVENT_finish;
}

void handleConnectForError(Event *event, void *params){
    //连接失败，结束
    *event = EVENT_finish;
}

void handleQueryForError(Event *event, void *params){
    //查询失败，结束
    *event = EVENT_finish;
}

示例中的响应函数是直接更新触发事件，在实际中可根据传入的参数或外部条件来更新触发事件

至此完成了状态机的所有前置条件，接下来就是实现状态机了，我们定义状态机的结构：

typedef struct
{
    FSMTable    *fsmtb;     /* 状态迁移表 */
    FSMState    cur_sta;    /* 状态机当前状态 */
    Event       event;      /* 当前的事件 */
    int     sta_max_n;      /* 状态机状态迁移数量 */
}FSM;

执行状态机：

int run_fsm_action(FSM* fsm, void *args)
{
    int max_n = fsm->sta_max_n, i=0;
    FSMState cur_sta = fsm->cur_sta;
    FSMTable *fsmtb = fsm->fsmtb;
    if(!fsm) return -1;

    for(i=0; i<max_n; ++i){
        if(fsmtb[i].curState == cur_sta && fsmtb[i].event == fsm->event){
            fsmtb[i].event_action(&fsm->event, args);    /* 调用对应的处理函数 */
            fsm->cur_sta = fsmtb[i].nextState;           /* 转移到下一个状态 */
            break;
        }
    }
    return 0;
}

int main()
{
    FSM fsm = {0};
    fsm.fsmtb = fsmtb;
    fsm.cur_sta = STATE_init;
    fsm.event=EVENT_start;
    fsm.sta_max_n = sizeof(fsmtb)/sizeof(fsmtb[0]);

    run_fsm_action(&fsm,NULL);
    return 0;
}

2.3 函数指针方式

函数指针方式在形式和理解方面是比较容易的：用枚举变量表示状态与事件，用函数指针数组表述行为，用函数返回值表示下一个状态。使用函数指针的表现形式也是比较容易的，只是要注意整个FSM的初始化，以及在状态和事件非法时的处理逻辑，枚举变量的值一定从0开始，并且每次递增加1，否则容易引发堆栈问题。这种函数指针实现方式效率要比比swich-case高一些。

先来定义一下函数指针数组：

// 函数指针
typedef FSMState (*FSM_DO_EVENT)(Event* event,void *params);
FSM_DO_EVENT fsmAction[STATE_finish][EVENT_stop];

//初始化函数指针数组
void initFSMTable(){
    FSMState state;
    Event event;
    for (state = STATE_init; state < STATE_finish; state++)
    {
        for (event = EVENT_start; event < EVENT_stop; event++)
        {
            fsmAction[state][event] = handle_do_null;
        }
    }
    fsmAction[STATE_init][EVENT_start] = handleInitForStart;
    fsmAction[STATE_connect][EVENT_connect_success] = handleConnectForSuccess;
    fsmAction[STATE_query][EVENT_query_success] = handleQueryForSuccess;
    fsmAction[STATE_connect][EVENT_connect_error] = handleConnectForError;
    fsmAction[STATE_query][EVENT_connect_error] = handleQueryForError;
}

用法如下所示：

// 同样这里再处理状态的时候是在响应函数中触发更新的，也可以由外边条件来触发
int main()
{
    initFSMTable();
    FSMState state = STATE_init;
    Event event = EVENT_start;
    
    while (1) {
        FSMState nextState = fsmAction[state][event](event,NULL); // 调用处理函数，并获取下一个状态
        if (nextState == STATE_finish) {
            printf("请求结束。\n");
            break; // 请求结束
        }
        state = nextState;
    }
    return 0;
}

三、分层状态机

在实际工程中当业务逻辑十分复杂，状态很多的时候，这将导致状态机代码量十分庞大，不利于维护，这就需要考虑将这些复杂的状态分成不同的模块，其特点是这些模块具有高内聚的特性，尽可能的不受其他模块的影响，而在外部由一个大的状态机去管理，这些不同的模块则由若干个子状态机管理。这就是本章节所说的 分层状态机（Hierarchical Finite State Machine，HFSM） 。概括的说，分层有限状态机是一种模型，用于描述复杂的状态转换系统。它通过将复杂的状态图分成多个子状态机，从而使得状态转换的处理更加清晰、可控。

首先将上面 2.1 章节的例子改造一下，实际工作中，系统的初始化、网络连接状态查询、状态更新等操作都可能经过一些列的操作之后才能完成，比如我们假定初始化时需要连接串口设备，给设备发送不同的指令来校验，通过之后认为初始化成功，在原来的方式中，我们需要给 FSMState 中添加一些状态：

typedef enum
{
    STATE_init,
    STATE_check_key,      //初始化校验设备是否配置秘钥
    STATE_check_auth,     //初始化校验设备是否授权
    STATE_init_device,    //初始化设备参数
    STATE_connect,
    STATE_query,
    STATE_finish

} FSMState;

这样我们就不得不在原有的状态机系统上添加这些状态和响应事件：

int main(){
    FSMState fsmState;
    while (fsmState != STATE_finish)
    {
        switch (fsmState)
        {
            case STATE_init:            
                handleStateInit();          //初始化状态响应
                break;
            case STATE_check_key:           //初始化校验设备是否配置秘钥
                handleStateCheckKey();
                break;
            case STATE_check_auth:          //初始化校验设备是否授权
                handleStateCheckAuth();
                break;
            case STATE_init_device:         //初始化设备参数
                handleStateCheckDevice();
                break;
            case STATE_connect:
                handleStateConnect();       //连接服务状态响应
                break;
            case STATE_query:
                handleStateQuery();         //查询服务状态响应
                break;
            case STATE_finish:
                handleStateFinish();        //结束状态响应
                break;
            }
    }
}

这样随着状态越来越多，代码会越来越长，而且会越来越复杂，所以需要一种更优雅的方式来处理状态机。注意到初始化模块功能比较内聚，可以提取出来使用一个子状态机管理：

typedef enum
{
    STATE_start,
    STATE_check_key,      //初始化校验设备是否配置秘钥
    STATE_check_auth,     //初始化校验设备是否授权
    STATE_init_device,    //初始化设备参数
    STATE_finish

} SubFSMInitState;

状态机运行系统可以改造为：

//子状态机返回值
typedef enum
{
    SUB_FSM_RETURN_ERROR,
    SUB_FSM_RETURN_SUCCESS

}SubFSMReturn

SubFSMReturn handleStateInit(){
    SubFSMInitState subState = STATE_start;
    SubFSMReturn ret = SUB_FSM_RETURN_ERROR;
    while(subState != STATE_finish){
        switch (subState){
            case STATE_start:
            ...
            break;
            case STATE_check_key:
            ...
            break;
            case STATE_check_auth:
            ...
            break;
            case STATE_init_device:
            ...
            break;
            case STATE_finish:
            ...
            break;
        }
    }
    return ret;
}

int main(){
    FSMState fsmState;
    while (fsmState != STATE_finish)
    {
        switch (fsmState)
        {
            case STATE_init:            
                SubFSMReturn ret = handleStateInit();    //初始化状态下的子状态机
                //根据子状态机返回值，更新父状态机状态
                if(ret == SUB_FSM_RETURN_SUCCESS){
                    fsmState = STATE_connect;
                } else {
                    fsmState = STATE_finish;
                }
                break;
            case STATE_connect:
                handleStateConnect();       //连接服务状态响应
                break;
            case STATE_query:
                handleStateQuery();         //查询服务状态响应
                break;
            case STATE_finish:
                handleStateFinish();        //结束状态响应
                break;
            }
    } 
}

四、事件队列与状态机

介绍到现在，是不是可以认为这已经足够应对所有的场景了？其实不然，在多线程场景下，对系统有不同的任务要求，但是状态机更多的是遵循一个固定的状态流转，无法满足异步任务的场景，那么应该如何解决呢？ 虽然任务是异步的，但当这些异步任务是按着先后顺序执行的时候，对于状态机来说就可以满足要求，先看如下一个示意图：

这里我将用户的操作抽象成不同的业务，而不同的业务是由一系列的模块组成的。这些模块例如：秘钥、Mqtt、Login、DS等具有高内聚的特性，控制线程 ControlThread 内部维持一个线程安全的队列，用户的操作被分解为不同的模块，这些模块被当做事件插入到队列当中，ControlThread 线程不断从队列中取出事件，这些事件内部又有各自的子状态机去处理，在控制线程中根据这些子状态机的返回状态来决定是否继续执行。

这样在面对不同的业务时，只需要将对应的事件插入队列当中然后等待执行即可。

Theme Preview

文章目录

分类

标签

归档

最新文章