FSM有限状态机其一

发表于 更新于

最近在学习关于有限状态机的知识，感觉有点麻头，写个博客输出一下

一、有限状态机的数学本质

有限状态机（Finite State Machine, FSM）是一个五元组：

text

( Σ, S, s0, δ, F )

  • Σ：有限的事件集合（输入字母表）

  • S：有限的状态集合

  • s0：初始状态（s0 ∈ S）

  • δ：状态转移函数 δ: S × Σ → S

  • F：终止状态集合（可空，嵌入式系统通常无终止状态）

用一句话概括：
给定当前状态和输入事件，状态转移函数 δ 唯一地确定下一个状态。

一个简单的demo是这样的

1
2
3
4
5
6
7
8
9
10
11
12
State current = CLOSED;

void handle_event(Event e) {
    switch (current) {
        case CLOSED:
            if (e == OPEN) current = OPENED;
            break;
        case OPENED:
            if (e == CLOSE) current = CLOSED;
            break;
    }
}

在这个handel_event内，我们用一个switch实现了根据当前状态和传入的事件，进行状态·切换的功能。

毫无疑问它是可用的，但当你面对以下现实需求时，switch-case 会迅速变成灾难：

  1. 状态数量增加（例如播放器有 10+ 状态）→ switch 嵌套太深。

  2. 需要进入/退出动作（控制硬件）→ 每个 case 里都要重复写硬件操作。

  3. 多个状态共享行为（例如“停止”在多个状态下都要回到 Idle）→ 代码重复。

  4. 需要记住离开时的子状态（历史状态）→ 无法用纯 δ 函数表达。

在C语言中实现有限状态机（FSM）的方法主要有以下5种常见方式，如果考虑变体或组合可扩展至更多，但核心典型方法如下：

  1. switch 语句法
    最经典的方法，用 switch(state) 分支处理每个状态下的事件和转移。代码直观，适合状态数不多的FSM。

  2. 函数指针表法
    为每个状态定义一个处理函数，用函数指针数组或结构体数组存储，当前状态对应函数被调用，函数内执行动作并返回下一状态。适合状态多、逻辑复杂的FSM。

  3. 状态转移表法
    构建二维表（或结构体数组），行表示当前状态，列表示输入事件，表项为目标状态和/或动作函数指针。通过查表驱动转移，易于维护和动态修改。

  4. goto 标签法（Duff风格或状态机模式）
    利用 goto 和标签实现类似协程的FSM，常见于嵌入式或解析器（如Protothreads）。不推荐用于大型系统，但可手动模拟可抢占状态机。

  5. 面向对象模拟法
    用结构体封装状态变量和函数指针（类似虚表），模拟C++的多态行为。每个状态是一个“类”，通过统一接口调用。适合需要状态复用或继承的场景。

此外，还有枚举+宏封装、消息队列+状态机等变体，但本质是上述方法的组合。因此，公认的核心实现方式通常为 3～5种。若按不同编程范式划分，可认为是 4～6种。实际应用中，switch和函数指针表最为常见。

我使用的方法是函数指针表法。

我们可以先来修改最上面那个简单的例子，本质上就是利用函数指针把耦合的代码给拆开来了，方便后期新增/修改状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 事件枚举
typedef enum {
    EVENT_OPEN,
    EVENT_CLOSE,
    EVENT_NONE
} Event;

// 状态枚举
typedef enum {
    STATE_CLOSED,
    STATE_OPENED,
} State;

#define STATE_COUNT = (sizeof(State)/sizeof(STATE_CLOSED))
typedef struct StateMachine StateMachine;
typedef void (*StateHandler)(StateMachine *fsm, Event evt);

struct StateMachine {
    State        current_state;
    StateHandler state_table[STATE_COUNT];
};

观察StateMachine结构体，我们可以发现，其中包含当前状态，以及一个指针数组，数组的元素类型为void (StateHandler)(StateMachine fsm, Event evt); 的数组，也就是上面所说的为每个状态定义一个处理函数，用函数指针数组或结构体数组存储，当前状态对应函数被调用，函数内执行动作并返回下一状态。适合状态多、逻辑复杂的FSM。** 该函数指针指向对应状态的处理函数。

我自认为FSM的核心在于

收到事件–>找到对应状态的处理函数–>执行状态转移

在之前的Switch的方法中，我们找到对应状态的处理函数这一步是在一个函数内由Switch语句完成的，但是在函数表法中，我们会有这样一个函数

1
2
3
4
5
void fsm_dispatch(StateMachine *fsm, Event evt) {
    if (evt == EVENT_NONE)
        return;
    fsm->state_table[fsm->current_state](fsm, evt);
}

该函数根据状态机当前状态，调用对应处理函数，参数为状态机自身与触发事件。

而接下来的执行状态转移这一步，在这个最为简单的demo中，我们直接在每个单独状态的处理函数中处理当前状态的切换，我们可以选一个状态的处理函数出来看一下。

1
2
3
4
5
6
7
8
9
10
11
static void state_closed(StateMachine *fsm, Event evt) {
    switch (evt) {
        case EVENT_OPEN:
            printf("[Closed]-> Opened (tigger:OPEN)\n");
            fsm->current_state = STATE_OPENED;
            break;
        default:
            printf("[Closed] Event ignored : %s\n", event_name(evt));
            break;
    }
}

其中fsm->current_state = STATE_OPENED; 这一句完成的功能就是实现当前状态的切换。

这就是我们这个最简单FSM demo 的核心代码部分，在接下来的博客中，我们会为其新增一些新的功能进去，代码的复杂度也会进一步提升。

我把完整的代码贴在下面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

// 事件枚举
typedef enum {
    EVENT_OPEN,
    EVENT_CLOSE,
    EVENT_NONE
} Event;

// 状态枚举
typedef enum {
    STATE_CLOSED,
    STATE_OPENED,
    STATE_COUNT // 仅用于标记状态个数
} State;

typedef struct StateMachine StateMachine;
typedef void (*StateHandler)(StateMachine *fsm, Event evt);

struct StateMachine {
    State        current_state;
    StateHandler state_table[STATE_COUNT];
};

const char *event_name(Event evt);
static void state_closed(StateMachine *fsm, Event evt);
static void state_opened(StateMachine *fsm, Event evt);

void fsm_init(StateMachine *fsm) {
    fsm->current_state             = STATE_CLOSED; // 初始状态
    fsm->state_table[STATE_CLOSED] = state_closed;
    fsm->state_table[STATE_OPENED] = state_opened;
}

void fsm_dispatch(StateMachine *fsm, Event evt) {
    if (evt == EVENT_NONE)
        return;
    fsm->state_table[fsm->current_state](fsm, evt);
}

static void state_closed(StateMachine *fsm, Event evt) {
    switch (evt) {
        case EVENT_OPEN:
            printf("[Closed]-> Opened (tigger:OPEN)\n");
            fsm->current_state = STATE_OPENED;
            break;
        default:
            printf("[Closed] Event ignored : %s\n", event_name(evt));
            break;
    }
}

static void state_opened(StateMachine *fsm, Event evt) {
    switch (evt) {
        case EVENT_CLOSE:
            printf("[Opened]-> Closed (tigger:CLOSE)\n");
            fsm->current_state = STATE_CLOSED;
            break;
        default:
            printf("[Opened] Event ignored: %s\n", event_name(evt));
            break;
    }
}

const char *event_name(Event evt) {
    switch (evt) {
        case EVENT_OPEN:
            return "OPEN";
        case EVENT_CLOSE:
            return "CLOSE";
        case EVENT_NONE:
            return "NONE";
    }
}

int main(void) {
    StateMachine fsm;
    fsm_init(&fsm);

    // 模拟事件序列
    Event test_events[] = {EVENT_OPEN,
        EVENT_OPEN, // 重复开门（应被忽略）
        EVENT_CLOSE,
        EVENT_CLOSE, // 重复关门（应被忽略）
        EVENT_OPEN};

    for (size_t i = 0; i < sizeof(test_events) / sizeof(test_events[0]); i++) {
        printf("\n[Event] %s\n", event_name(test_events[i]));
        fsm_dispatch(&fsm, test_events[i]);
        printf("[Current State] %s\n", fsm.current_state == STATE_CLOSED ? "Closed" : "Opened");
    }

    return 0;
}