C 状态机设计 [英] C state-machine design

问题描述

我正在用混合 C 和 C++ 制作一个小项目.我正在我的一个工作线程的核心构建一个小型状态机.

我想知道您的 SO 专家是否会分享您的状态机设计技术.

注意:我主要是在尝试之后经过测试的实现技术.

更新:基于在 SO 上收集的所有重要意见，我已经确定了这个架构:

解决方案

我之前设计的状态机(C，不是 C++)都归结为一个 struct 数组和一个循环.该结构基本上由一个状态和事件(用于查找)以及一个返回新状态的函数组成，例如:

typedef struct {国际圣;内幕；int (*fn)(void);} tTransition;

然后你用简单的定义来定义你的状态和事件(ANY 是特殊的标记，见下文):

#define ST_ANY -1#define ST_INIT 0#define ST_ERROR 1#define ST_TERM 2: :#define EV_ANY -1#define EV_KEYPRESS 5000#define EV_MOUSEMOVE 5001

然后定义转换调用的所有函数:

static int GotKey (void) { ... };static int FsmError (void) { ... };

所有这些函数都被编写为不接受变量并返回状态机的新状态.在此示例中，全局变量用于在必要时将任何信息传递到状态函数中.

使用全局变量并不像听起来那么糟糕，因为 FSM 通常被锁定在单个编译单元内，并且所有变量对于该单元都是静态的(这就是为什么我在上面的全局"周围使用引号 - 它们更多在 FSM 内共享，而不是真正的全球性).与所有全局变量一样，它需要小心.

然后转换数组定义了所有可能的转换以及为这些转换调用的函数(包括最后一个包罗万象的):

tTransition trans[] = {{ ST_INIT, EV_KEYPRESS, &GotKey},: :{ ST_ANY, EV_ANY, &FsmError}};#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

这意味着:如果您处于 ST_INIT 状态并且收到 EV_KEYPRESS 事件，请调用 GotKey.

FSM 的工作然后变成一个相对简单的循环:

state = ST_INIT;而(状态！= ST_TERM){事件 = GetNextEvent();for (i = 0; i < TRANS_COUNT; i++) {if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {if (((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {状态 = (trans[i].fn)();休息;}}}}

正如上面提到的，注意使用 ST_ANY 作为通配符，无论当前状态如何，都允许事件调用函数.EV_ANY 的工作原理也类似，允许处于特定状态的任何事件调用函数.

它还可以保证，如果您到达 transitions 数组的末尾，您会收到一条错误消息，指出您的 FSM 构建不正确(通过使用 ST_ANY/EV_ANY 组合.>

我在许多通信项目中使用了类似的代码，例如嵌入式系统的通信堆栈和协议的早期实现.最大的优势是它的简单性和更改转换数组的相对容易.

我毫不怀疑会有更高级别的抽象，它们现在可能更合适，但我怀疑它们都会归结为同一种结构.

<小时>

而且，正如 ldog 在评论中所述，您可以通过将结构指针传递给所有函数(并在事件循环中使用它)来完全避免全局变量.这将允许多个状态机并行运行而不受干扰.

只需创建一个结构类型来保存特定于机器的数据(最低限度的状态)并使用它而不是全局变量.

我很少这样做的原因仅仅是因为我编写的大多数状态机都是单例类型(例如一次性、进程启动、配置文件读取)，不需要运行更多比一个实例.但如果您需要运行多个，它就有价值.

I am crafting a small project in mixed C and C++. I am building one small-ish state-machine at the heart of one of my worker thread.

I was wondering if you gurus on SO would share your state-machine design techniques.

NOTE: I am primarily after tried & tested implementation techniques.

UPDATED: Based on all the great input gathered on SO, I've settled on this architecture:

解决方案

State machines that I've designed before (C, not C++) have all come down to a struct array and a loop. The structure basically consists of a state and event (for look-up) and a function that returns the new state, something like:

typedef struct {
    int st;
    int ev;
    int (*fn)(void);
} tTransition;

Then you define your states and events with simple defines (the ANY ones are special markers, see below):

#define ST_ANY              -1
#define ST_INIT              0
#define ST_ERROR             1
#define ST_TERM              2
: :
#define EV_ANY              -1
#define EV_KEYPRESS       5000
#define EV_MOUSEMOVE      5001

Then you define all the functions that are called by the transitions:

static int GotKey (void) { ... };
static int FsmError (void) { ... };

All these function are written to take no variables and return the new state for the state machine. In this example global variables are used for passing any information into the state functions where necessary.

Using globals isn't as bad as it sounds since the FSM is usually locked up inside a single compilation unit and all variables are static to that unit (which is why I used quotes around "global" above - they're more shared within the FSM, than truly global). As with all globals, it requires care.

The transitions array then defines all possible transitions and the functions that get called for those transitions (including the catch-all last one):

tTransition trans[] = {
    { ST_INIT, EV_KEYPRESS, &GotKey},
    : :
    { ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

What that means is: if you're in the ST_INIT state and you receive the EV_KEYPRESS event, make a call to GotKey.

The workings of the FSM then become a relatively simple loop:

state = ST_INIT;
while (state != ST_TERM) {
    event = GetNextEvent();
    for (i = 0; i < TRANS_COUNT; i++) {
        if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
            if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
                state = (trans[i].fn)();
                break;
            }
        }
    }
}

As alluded to above, note the use of ST_ANY as wild-cards, allowing an event to call a function no matter the current state. EV_ANY also works similarly, allowing any event at a specific state to call a function.

It can also guarantee that, if you reach the end of the transitions array, you get an error stating your FSM hasn't been built correctly (by using the ST_ANY/EV_ANY combination.

I've used code similar for this on a great many communications projects, such as an early implementation of communications stacks and protocols for embedded systems. The big advantage was its simplicity and relative ease in changing the transitions array.

I've no doubt there will be higher-level abstractions which may be more suitable nowadays but I suspect they'll all boil down to this same sort of structure.

---

And, as ldog states in a comment, you can avoid the globals altogether by passing a structure pointer to all functions (and using that in the event loop). This will allow multiple state machines to run side-by-side without interference.

Just create a structure type which holds the machine-specific data (state at a bare minimum) and use that instead of the globals.

The reason I've rarely done that is simply because most of the state machines I've written have been singleton types (one-off, at-process-start, configuration file reading for example), not needing to run more than one instance. But it has value if you need to run more than one.

这篇关于C 状态机设计的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！