C状态机设计

Question

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

我想知道你是否会在SO上分享你的状态机设计技巧.

注意:我主要是经过久经考验的实施技术.

更新:基于SO上收集的所有重要输入,我已经确定了这个架构:

Answer 1

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

typedef struct {
    int st;
    int ev;
    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通常被锁定在单个编译单元内,并且所有变量对于该单元都是静态的(这就是为什么我在上面使用"global"周围的引号 - 它们在FSM,而不是真正的全球性).与所有全局变量一样,它需要小心.

然后,transitions数组定义所有可能的转换以及为这些转换调用的函数(包括catch-all last):

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;
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;
            }
        }
    }
}

如上所述,请注意使用ST_ANY通配符,允许事件调用函数,无论当前状态如何.EV_ANY也可以类似地工作,允许特定状态下的任何事件调用函数.

它还可以保证,如果到达过渡数组的末尾,则会出现错误,指出您的FSM未正确构建(通过使用ST_ANY/EV_ANY组合.

我在许多通信项目中使用了类似的代码,例如早期实现通信堆栈和嵌入式系统协议.最大的优点是它的简单性和相对容易改变过渡阵列.

我毫无疑问会有更高级别的抽象,现在可能更合适,但我怀疑它们都归结为同样的结构.

并且,作为ldog注释中的状态,您可以通过将结构指针传递给所有函数(并在事件循环中使用它)来完全避免全局变量.这将允许多个状态机并排运行而不会产生干扰.

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

究其原因,我很少这样做根本就是因为大多数我已经写了一直单身类型的状态机(一次性的,在过程开始,配置文件,例如读取),而不是需要运行多个实例.但如果您需要运行多个,它就具有价值.

Answer 2

其他答案都很好,但是当状态机非常简单时我使用的一个非常"轻量级"的实现看起来像:

enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };

enum state current_state = ST_NEW;

while (current_state != ST_END)
{
    input = get_input();

    switch (current_state)
    {
        case ST_NEW:
        /* Do something with input and set current_state */
        break;

        case ST_OPEN:
        /* Do something different and set current_state */
        break;

        /* ... etc ... */
    }
}

当状态机足够简单以至于函数指针和状态转换表方法过度时,我会使用它.这对于逐字符或逐字解析通常很有用.

Answer 3

请原谅我打破计算机科学中的每一条规则,但状态机是少数几个(我只能计算两个手头)的地方之一,其中一个goto语句不仅效率更高,而且使您的代码更清晰,更易于阅读.因为goto语句基于标签,所以您可以命名状态,而不必记录数字或使用枚举.它还可以提供更清晰的代码,因为您不需要所有额外的功能指针或巨大的switch语句和while循环.我提到它也更有效吗？

这是状态机的外观:

void state_machine() {
first_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }

second_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }
}

你得到了一般的想法.关键在于,您可以以有效的方式实现状态机,并且可以相对容易地阅读并向读者尖叫他们正在查看状态机.请注意,如果您正在使用goto陈述,您仍然必须小心,因为这样做很容易在脚下射击.

Answer 4

您可以考虑使用State Machine Compiler http://smc.sourceforge.net/

这个出色的开源实用程序以简单的语言接受状态机的描述,并将其编译为十几种语言中的任何一种 - 包括C和C++.该实用程序本身是用Java编写的,可以作为构建的一部分包含在内.

这样做的原因,而不是使用GoF State模式或任何其他方法进行手动编码,一旦您的状态机表示为代码,底层结构往往会在需要生成支持它的样板的重量下消失.使用这种方法可以很好地分离关注点,并保持状态机的结构"可见".自动生成的代码会进入您不需要触摸的模块,这样您就可以返回并调整状态机的结构,而不会影响您编写的支持代码.

对不起,我过于热情,无疑让所有人都离开了.但它是一个顶级的实用程序,也有很好的文档记录.

Answer 5

一定要检查Miro Samek(博客State Space,网站状态机和工具)的工作,他们在C/C++用户期刊上的文章很棒.

该网站包含一个完整的(C/C++)实现,包括状态机框架(QP框架)的开源和商业许可,事件处理程序(QEP),基本建模工具(QM)和跟踪工具(QSpy).允许绘制状态机,创建代码并调试它们.

本书包含对实现的原因/原因以及如何使用它的广泛解释,也是了解层次和有限状态机基础知识的重要材料.

该网站还包含多个板支持包的链接,以便将软件与嵌入式平台配合使用.

Answer 6

我做了类似于paxdiablo描述的事情,而不是状态/事件转换数组,我设置了一个二维函数指针数组,事件值作为一个轴的索引,当前状态值为另一个.然后我打电话state = state_table[event][state](params),正确的事情发生了.当然,表示无效状态/事件组合的单元格会获得指向这样说的函数的指针.

显然,这仅在状态和事件值都是连续范围并且从0开始或足够接近时才有效.

Answer 7

Stefan Heinzmann在他的文章中给出了一个非常好的基于模板的C++状态机"框架" .

由于文章中没有完整代码下载的链接,因此我冒昧地将代码粘贴到项目中并进行检查.下面的东西经过测试,包括一些次要但非常明显的缺失部分.

这里的主要创新是编译器生成非常有效的代码.空进入/退出操作没有成本.非空入/出动作是内联的.编译器还在验证状态图的完整性.缺少的操作会生成链接错误.唯一没有抓到的是失踪Top::init.

这是Miro Samek实现的一个非常好的替代方案,如果你可以没有缺少的东西 - 这远不是一个完整的UML Statechart实现,虽然它正确实现了UML语义,而Samek的代码设计不处理退出/转换/输入操作的顺序正确.

如果这段代码适用于您需要做的事情,并且您的系统有一个不错的C++编译器,它可能比Miro的C/C++实现更好.编译器为您生成展平的O(1)转换状态机实现.如果程序集输出的审核确认优化按预期工作,则接近理论性能.最好的部分:它是相对微小,易于理解的代码.

#ifndef HSM_HPP
#define HSM_HPP

// This code is from:
// Yet Another Hierarchical State Machine
// by Stefan Heinzmann
// Overload issue 64 december 2004
// http://accu.org/index.php/journals/252

/* This is a basic implementation of UML Statecharts.
 * The key observation is that the machine can only
 * be in a leaf state at any given time. The composite
 * states are only traversed, never final.
 * Only the leaf states are ever instantiated. The composite
 * states are only mechanisms used to generate code. They are
 * never instantiated.
 */

// Helpers

// A gadget from Herb Sutter's GotW #71 -- depends on SFINAE
template<class D, class B>
class IsDerivedFrom {
    class Yes { char a[1]; };
    class No  { char a[10]; };
    static Yes Test(B*); // undefined
    static No Test(...); // undefined
public:
    enum { Res = sizeof(Test(static_cast<D*>(0))) == sizeof(Yes) ? 1 : 0 };
};

template<bool> class Bool {};

// Top State, Composite State and Leaf State

template <typename H>
struct TopState {
    typedef H Host;
    typedef void Base;
    virtual void handler(Host&) const = 0;
    virtual unsigned getId() const = 0;
};

template <typename H, unsigned id, typename B>
struct CompState;

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct CompState : B {
    typedef B Base;
    typedef CompState<H, id, Base> This;
    template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H>
struct CompState<H, 0, TopState<H> > : TopState<H> {
    typedef TopState<H> Base;
    typedef CompState<H, 0, Base> This;
    template <typename X> void handle(H&, const X&) const {}
    static void init(H&); // no implementation
    static void entry(H&) {}
    static void exit(H&) {}
};

template <typename H, unsigned id, typename B = CompState<H, 0, TopState<H> > >
struct LeafState : B {
    typedef H Host;
    typedef B Base;
    typedef LeafState<H, id, Base> This;
    template <typename X> void handle(H& h, const X& x) const { Base::handle(h, x); }
    virtual void handler(H& h) const { handle(h, *this); }
    virtual unsigned getId() const { return id; }
    static void init(H& h) { h.next(obj); } // don't specialize this
    static void entry(H&) {}
    static void exit(H&) {}
    static const LeafState obj; // only the leaf states have instances
};

template <typename H, unsigned id, typename B>
const LeafState<H, id, B> LeafState<H, id, B>::obj;

// Transition Object

template <typename C, typename S, typename T>
// Current, Source, Target
struct Tran {
    typedef typename C::Host Host;
    typedef typename C::Base CurrentBase;
    typedef typename S::Base SourceBase;
    typedef typename T::Base TargetBase;
    enum { // work out when to terminate template recursion
        eTB_CB = IsDerivedFrom<TargetBase, CurrentBase>::Res,
        eS_CB = IsDerivedFrom<S, CurrentBase>::Res,
        eS_C = IsDerivedFrom<S, C>::Res,
        eC_S = IsDerivedFrom<C, S>::Res,
        exitStop = eTB_CB && eS_C,
        entryStop = eS_C || eS_CB && !eC_S
    };
    // We use overloading to stop recursion.
    // The more natural template specialization
    // method would require to specialize the inner
    // template without specializing the outer one,
    // which is forbidden.
    static void exitActions(Host&, Bool<true>) {}
    static void exitActions(Host&h, Bool<false>) {
        C::exit(h);
        Tran<CurrentBase, S, T>::exitActions(h, Bool<exitStop>());
    }
    static void entryActions(Host&, Bool<true>) {}
    static void entryActions(Host& h, Bool<false>) {
        Tran<CurrentBase, S, T>::entryActions(h, Bool<entryStop>());
        C::entry(h);
    }
    Tran(Host & h) : host_(h) {
        exitActions(host_, Bool<false>());
    }
    ~Tran() {
        Tran<T, S, T>::entryActions(host_, Bool<false>());
        T::init(host_);
    }
    Host& host_;
};

// Initializer for Compound States

template <typename T>
struct Init {
    typedef typename T::Host Host;
    Init(Host& h) : host_(h) {}
    ~Init() {
        T::entry(host_);
        T::init(host_);
    }
    Host& host_;
};

#endif // HSM_HPP

测试代码如下.

#include <cstdio>
#include "hsm.hpp"
#include "hsmtest.hpp"

/* Implements the following state machine from Miro Samek's
 * Practical Statecharts in C/C++
 *
 * |-init-----------------------------------------------------|
 * |                           s0                             |
 * |----------------------------------------------------------|
 * |                                                          |
 * |    |-init-----------|        |-------------------------| |
 * |    |       s1       |---c--->|            s2           | |
 * |    |----------------|<--c----|-------------------------| |
 * |    |                |        |                         | |
 * |<-d-| |-init-------| |        | |-init----------------| | |
 * |    | |     s11    |<----f----| |          s21        | | |
 * | /--| |------------| |        | |---------------------| | |
 * | a  | |            | |        | |                     | | |
 * | \->| |            |------g--------->|-init------|    | | |
 * |    | |____________| |        | |-b->|    s211   |---g--->|
 * |    |----b---^       |------f------->|           |    | | |
 * |    |________________|        | |<-d-|___________|<--e----|
 * |                              | |_____________________| | |
 * |                              |_________________________| |
 * |__________________________________________________________|
 */

class TestHSM;

typedef CompState<TestHSM,0>     Top;
typedef CompState<TestHSM,1,Top>   S0;
typedef CompState<TestHSM,2,S0>      S1;
typedef LeafState<TestHSM,3,S1>        S11;
typedef CompState<TestHSM,4,S0>      S2;
typedef CompState<TestHSM,5,S2>        S21;
typedef LeafState<TestHSM,6,S21>         S211;

enum Signal { A_SIG, B_SIG, C_SIG, D_SIG, E_SIG, F_SIG, G_SIG, H_SIG };

class TestHSM {
public:
    TestHSM() { Top::init(*this); }
    ~TestHSM() {}
    void next(const TopState<TestHSM>& state) {
        state_ = &state;
    }
    Signal getSig() const { return sig_; }
    void dispatch(Signal sig) {
        sig_ = sig;
        state_->handler(*this);
    }
    void foo(int i) {
        foo_ = i;
    }
    int foo() const {
        return foo_;
    }
private:
    const TopState<TestHSM>* state_;
    Signal sig_;
    int foo_;
};

bool testDispatch(char c) {
    static TestHSM test;
    if (c<'a' || 'h'<c) {
        return false;
    }
    printf("Signal<-%c", c);
    test.dispatch((Signal)(c-'a'));
    printf("\n");
    return true;
}

int main(int, char**) {
    testDispatch('a');
    testDispatch('e');
    testDispatch('e');
    testDispatch('a');
    testDispatch('h');
    testDispatch('h');
    return 0;
}

#define HSMHANDLER(State) \
    template<> template<typename X> inline void State::handle(TestHSM& h, const X& x) const

HSMHANDLER(S0) {
    switch (h.getSig()) {
    case E_SIG: { Tran<X, This, S211> t(h);
        printf("s0-E;");
        return; }
    default:
        break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S1) {
    switch (h.getSig()) {
    case A_SIG: { Tran<X, This, S1> t(h);
        printf("s1-A;"); return; }
    case B_SIG: { Tran<X, This, S11> t(h);
        printf("s1-B;"); return; }
    case C_SIG: { Tran<X, This, S2> t(h);
        printf("s1-C;"); return; }
    case D_SIG: { Tran<X, This, S0> t(h);
        printf("s1-D;"); return; }
    case F_SIG: { Tran<X, This, S211> t(h);
        printf("s1-F;"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S11) {
    switch (h.getSig()) {
    case G_SIG: { Tran<X, This, S211> t(h);
        printf("s11-G;"); return; }
    case H_SIG: if (h.foo()) {
            printf("s11-H");
            h.foo(0); return;
        } break;
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S2) {
    switch (h.getSig()) {
    case C_SIG: { Tran<X, This, S1> t(h);
        printf("s2-C"); return; }
    case F_SIG: { Tran<X, This, S11> t(h);
        printf("s2-F"); return; }
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S21) {
    switch (h.getSig()) {
    case B_SIG: { Tran<X, This, S211> t(h);
        printf("s21-B;"); return; }
    case H_SIG: if (!h.foo()) {
            Tran<X, This, S21> t(h);
            printf("s21-H;"); h.foo(1);
            return;
        } break;
    default: break;
    }
    return Base::handle(h, x);
}

HSMHANDLER(S211) {
    switch (h.getSig()) {
    case D_SIG: { Tran<X, This, S21> t(h);
        printf("s211-D;"); return; }
    case G_SIG: { Tran<X, This, S0> t(h);
        printf("s211-G;"); return; }
    }
    return Base::handle(h, x);
}

#define HSMENTRY(State) \
    template<> inline void State::entry(TestHSM&) { \
        printf(#State "-ENTRY;"); \
    }

HSMENTRY(S0)
HSMENTRY(S1)
HSMENTRY(S11)
HSMENTRY(S2)
HSMENTRY(S21)
HSMENTRY(S211)

#define HSMEXIT(State) \
    template<> inline void State::exit(TestHSM&) { \
        printf(#State "-EXIT;"); \
    }

HSMEXIT(S0)
HSMEXIT(S1)
HSMEXIT(S11)
HSMEXIT(S2)
HSMEXIT(S21)
HSMEXIT(S211)

#define HSMINIT(State, InitState) \
    template<> inline void State::init(TestHSM& h) { \
       Init<InitState> i(h); \
       printf(#State "-INIT;"); \
    }

HSMINIT(Top, S0)
HSMINIT(S0, S1)
HSMINIT(S1, S11)
HSMINIT(S2, S21)
HSMINIT(S21, S211)

Answer 8

我喜欢状态机的技术(至少用于程序控制)是使用函数指针.每个州由不同的功能代表.该函数接受输入符号并返回下一个状态的函数指针.中央调度循环监视器接收下一个输入,将其提供给当前状态,并处理结果.

它上面的输入有点奇怪,因为C没有办法指示返回的函数指针的类型,所以状态函数返回void*.但你可以这样做:

typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
    state_handler current = initial_handler;
    /* Let's assume returning null indicates end-of-machine */
    while (current) {
        current = current(get_input);
    }
 }

然后,您的各个状态函数可以打开其输入以处理并返回适当的值.

Answer 9

最简单的情况

enum event_type { ET_THIS, ET_THAT };
union event_parm { uint8_t this; uint16_t that; }
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum { THIS, THAT } state;
  switch (state)
  {
    case THIS:
    switch (event)
    {
      case ET_THIS:
      // Handle event.
      break;

      default:
      // Unhandled events in this state.
      break;
    }
    break;

    case THAT:
    // Handle state.
    break;
  }
}

要点:状态是私有的,不仅是编译单元,还包括event_handler.特殊情况可以使用任何认为必要的构造与主开关分开处理.

更复杂的情况

当开关大于几个屏幕已满时,将其拆分为处理每个状态的函数,使用状态表直接查找函数.状态仍然是事件处理程序的私有状态.状态处理函数返回下一个状态.如果需要,某些事件仍然可以在主事件处理程序中获得特殊处理.我喜欢为状态进入和退出以及状态机启动引入伪事件:

enum state_type { THIS, THAT, FOO, NA };
enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT };
union event_parm { uint8_t this; uint16_t that; };
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum state_type state;
  static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that };
  enum state_type next_state = state_handler[state](event, parm);
  if (NA != next_state && state != next_state)
  {
    (void)state_handler[state](ET_EXIT, 0);
    state = next_state;
    (void)state_handler[state](ET_ENTER, 0);
  }
}

我不确定我是否修复了语法,特别是关于函数指针数组.我没有通过编译器运行任何这些.经过审核,我注意到在处理伪事件(调用state_handler()之前的(void)括号)时,我忘记显式丢弃下一个状态.即使编译器默默地接受遗漏,我也喜欢这样做.它告诉读者代码"是的,我的确意味着在不使用返回值的情况下调用函数",它可能会阻止静态分析工具对其进行警告.它可能是特殊的,因为我不记得曾见过其他人这样做.

要点:添加一点点复杂性(检查下一个状态是否与当前状态不同),可以避免其他地方重复的代码,因为状态处理函数可以享受进入和离开状态时发生的伪事件.请记住,在处理伪事件时状态不能更改,因为在这些事件之后会丢弃状态处理程序的结果.您当然可以选择修改行为.

状态处理程序看起来像这样:

static enum state_type handle_this(enum event_type event, union event_parm parm)
{
  enum state_type next_state = NA;
  switch (event)
  {
    case ET_ENTER:
    // Start a timer to do whatever.
    // Do other stuff necessary when entering this state.
    break;

    case ET_WHATEVER:
    // Switch state.
    next_state = THAT;
    break;

    case ET_TIMEOUT:
    // Switch state.
    next_state = FOO;
    break;

    case ET_EXIT:
    // Stop the timer.
    // Generally clean up this state.
    break;
  }
  return next_state;
}

更复杂

当编译单元变得太大时(不管你感觉如何,我应该说大约1000行),将每个状态处理程序放在一个单独的文件中.当每个状态处理程序变得比一些屏幕长时,将每个事件拆分为一个单独的函数,类似于状态开关被拆分的方式.您可以通过多种方式执行此操作,与州分开,或使用公共表,或组合各种方案.其他人已经在这里介绍了其中一些.如果要求速度,则对表进行排序并使用二进制搜索.

通用编程

我希望预处理器能够处理诸如排序表甚至从描述生成状态机等问题,允许您"编写有关程序的程序".我相信Boost人正在利用C++模板,但我发现语法含糊不清.

二维表

我过去曾使用状态/事件表,但我必须说,对于最简单的情况,我发现它们不是必需的,我更喜欢switch语句的清晰度和可读性,即使它确实延伸超过一个屏幕.对于更复杂的情况,表格很快就会失控,正如其他人所指出的那样.我在这里提到的习语允许你在你想要的时候添加一些事件和状态,而不必维护一个占用内存的表(即使它可能是程序存储器).

放弃

特殊需要可能会使这些习语变得不那么有用,但我发现它们非常清晰和易于维护.