是否有典型的状态机实现模式？

Question

我们需要在C中实现一个简单的状态机.
标准的switch语句是最好的方法吗？
我们有一个当前状态(状态)和转换触发器.

switch(state)
{
  case STATE_1:
     state = DoState1(transition);
     break;
  case STATE_2:
     state = DoState2(transition);
     break;
}
...
DoState2(int transition)
{
   // Do State Work
   ...
   if(transition == FROM_STATE_2) {
     // New state when doing STATE 2 -> STATE 2
   }
   if(transition == FROM_STATE_1) {
    // New State when moving STATE 1 -> STATE 2
   }
   return new_state;
}

对于简单的状态机是否有更好的方法

编辑:对于C++,我认为Boost Statechart库可能是要走的路.但是,它对C 没有帮助.让我们专注于C用例.

Answer 1

我更喜欢对大多数状态机使用表驱动方法:

typedef enum { STATE_INITIAL, STATE_FOO, STATE_BAR, NUM_STATES } state_t;
typedef struct instance_data instance_data_t;
typedef state_t state_func_t( instance_data_t *data );

state_t do_state_initial( instance_data_t *data );
state_t do_state_foo( instance_data_t *data );
state_t do_state_bar( instance_data_t *data );

state_func_t* const state_table[ NUM_STATES ] = {
    do_state_initial, do_state_foo, do_state_bar
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    return state_table[ cur_state ]( data );
};

int main( void ) {
    state_t cur_state = STATE_INITIAL;
    instance_data_t data;

    while ( 1 ) {
        cur_state = run_state( cur_state, &data );

        // do other program logic, run other state machines, etc
    }
}

这当然可以扩展到支持多个状态机等.转换操作也可以适应:

typedef void transition_func_t( instance_data_t *data );

void do_initial_to_foo( instance_data_t *data );
void do_foo_to_bar( instance_data_t *data );
void do_bar_to_initial( instance_data_t *data );
void do_bar_to_foo( instance_data_t *data );
void do_bar_to_bar( instance_data_t *data );

transition_func_t * const transition_table[ NUM_STATES ][ NUM_STATES ] = {
    { NULL,              do_initial_to_foo, NULL },
    { NULL,              NULL,              do_foo_to_bar },
    { do_bar_to_initial, do_bar_to_foo,     do_bar_to_bar }
};

state_t run_state( state_t cur_state, instance_data_t *data ) {
    state_t new_state = state_table[ cur_state ]( data );
    transition_func_t *transition =
               transition_table[ cur_state ][ new_state ];

    if ( transition ) {
        transition( data );
    }

    return new_state;
};

表驱动方法更易于维护和扩展,并且更易于映射到状态图.

Answer 2

您可能已经看到了我提到FSM的另一个C问题的答案!我是这样做的:

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0) 
      NEXTSTATE(y);
    else 
      NEXTSTATE(x);
  }
}

定义了以下宏

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

这可以修改以适应特定情况.例如,您可能有一个FSMFILE要驱动FSM的文件,因此您可以将读取下一个char的操作合并到宏本身中:

#define FSM
#define STATE(x)         s_##x : FSMCHR = fgetc(FSMFILE); sn_##x :
#define NEXTSTATE(x)     goto s_##x
#define NEXTSTATE_NR(x)  goto sn_##x

现在你有两种类型的转换:一种转到状态并读取一个新字符,另一种转到一种状态而不消耗任何输入.

您还可以通过以下方式自动处理EOF:

#define STATE(x)  s_##x  : if ((FSMCHR = fgetc(FSMFILE) == EOF)\
                             goto sx_endfsm;\
                  sn_##x :

#define ENDFSM    sx_endfsm:

这种方法的好处在于,您可以直接将绘制的状态图转换为工作代码,相反,您可以轻松地从代码中绘制状态图.

在用于实现FSM的其他技术中,转换的结构被隐藏在控制结构中(而如果,切换......)并且由变量值(通常是state变量)控制,并且将良好的图表与a关联起来可能是一项复杂的任务.复杂的代码.

我从伟大的"计算机语言"杂志上发表的一篇文章中学到了这种技巧,不幸的是,该文章已不再发表.

Answer 3

我也使用了表格方法.但是,有开销.为什么要存储第二个指针列表？没有()的C函数是一个const指针.所以你可以这样做:

struct state;
typedef void (*state_func_t)( struct state* );

typedef struct state
{
  state_func_t function;

  // other stateful data

} state_t;

void do_state_initial( state_t* );
void do_state_foo( state_t* );
void do_state_bar( state_t* );

void run_state( state_t* i ) {
    i->function(i);
};

int main( void ) {
    state_t state = { do_state_initial };

    while ( 1 ) {
        run_state( state );

        // do other program logic, run other state machines, etc
    }
}

当然,根据您的恐惧因素(即安全性与速度),您可能需要检查有效指针.对于大于三个状态的状态机,上面的方法应该比等效的开关或表方法更少的指令.您甚至可以宏观化为:

#define RUN_STATE(state_ptr_) ((state_ptr_)->function(state_ptr_))

另外,我从OP的例子中感觉到,在考虑/设计状态机时应该进行简化.我不认为过渡状态应该用于逻辑.每个状态函数都应该能够执行其给定的角色,而无需明确了解过去的状态.基本上你设计的是如何从你所处的状态过渡到另一个状态.

最后,不要基于"功能"边界开始设计状态机,为此使用子功能.相反,根据何时需要等待某些事情发生才能继续进行划分状态.这将有助于在获得结果之前最小化运行状态机的次数.在编写I/O函数或中断处理程序时,这很重要.

另外,经典switch语句的一些优缺点:

优点:

• 它在语言中,因此记录清晰
• 状态定义在它们被调用的地方
• 可以在一个函数调用中执行多个状态
• 所有状态共有的代码可以在switch语句之前和之后执行

缺点:

• 可以在一个函数调用中执行多个状态
• 所有状态共有的代码可以在switch语句之前和之后执行
• 切换实现可能很慢

请注意pro和con这两个属性.我认为转换允许在州之间进行过多共享的机会,并且各州之间的相互依赖性变得难以管理.但是对于少数州,它可能是最易读和可维护的.

Answer 4

对于简单的状态机,只需为您的状态使用switch语句和枚举类型.根据您的输入在switch语句中进行转换.在实际程序中,您显然会更改"if(输入)"以检查转换点.希望这可以帮助.

typedef enum
{
    STATE_1 = 0,
    STATE_2,
    STATE_3
} my_state_t;

my_state_t state = STATE_1;

void foo(char input)
{
    ...
    switch(state)
    {
        case STATE_1:
            if(input)
                state = STATE_2;
            break;
        case STATE_2:
            if(input)
                state = STATE_3;
            else
                state = STATE_1;
            break;
        case STATE_3:
            ...
            break;
    }
    ...
}

Answer 5

还有逻辑网格,随着状态机变大,它更易于维护

Answer 6

在Martin Fowler的UML Distilled中,他在第10章State Machine Diagrams(强调我的)中指出(没有双关语):

状态图可以以三种主要方式实现:嵌套开关,状态模式和 状态表.

让我们使用手机显示状态的简化示例:

嵌套开关

Fowler给出了一个C#代码示例,但我已经将它改编为我的示例.

public void HandleEvent(PhoneEvent anEvent) {
    switch (CurrentState) {
    case PhoneState.ScreenOff:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            if (powerLow) { // guard condition
                DisplayLowPowerMessage(); // action
                // CurrentState = PhoneState.ScreenOff;
            } else {
                CurrentState = PhoneState.ScreenOn;
            }
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenOn:
        switch (anEvent) {
        case PhoneEvent.PressButton:
            CurrentState = PhoneState.ScreenOff;
            break;
        case PhoneEvent.PlugPower:
            CurrentState = PhoneState.ScreenCharging;
            break;
        }
        break;
    case PhoneState.ScreenCharging:
        switch (anEvent) {
        case PhoneEvent.UnplugPower:
            CurrentState = PhoneState.ScreenOff;
            break;
        }
        break;
    }
}

国家模式

这是我的GoF State模式示例的实现:

州表

从Fowler获取灵感,这是我的例子的表格:

Source State    Target State    Event         Guard        Action
--------------------------------------------------------------------------------------
ScreenOff       ScreenOff       pressButton   powerLow     displayLowPowerMessage  
ScreenOff       ScreenOn        pressButton   !powerLow
ScreenOn        ScreenOff       pressButton
ScreenOff       ScreenCharging  plugPower
ScreenOn        ScreenCharging  plugPower
ScreenCharging  ScreenOff       unplugPower

对照

嵌套开关将所有逻辑保留在一个位置,但是当存在大量状态和转换时,代码可能难以读取.与其他方法(没有多态或解释)相比,它可能更安全,更容易验证.

状态模式实现可能将逻辑分散在几个单独的类上,这可能使其理解为整体问题.另一方面,小班很容易理解.如果通过添加或删除转换来更改行为,则设计特别脆弱,因为它们是层次结构中的方法,并且代码可能会有很多更改.如果你遵循小接口的设计原则,你会发现这种模式并没有真正做到这一点.但是,如果状态机稳定,则不需要进行此类更改.

状态表方法需要为内容编写某种解释器(如果您使用您正在使用的语言进行反射,这可能会更容易),这可能需要做很多工作.正如Fowler指出的那样,如果您的表与您的代码分开,您可以修改软件的行为而无需重新编译.然而,这有一些安全隐患; 该软件的行为基于外部文件的内容.

编辑(不是真的用于C语言)

还有一种流畅的界面(也称为内部领域特定语言)方法,这可能是由具有一流功能的语言促成的.在无状态库是否存在,以及博客显示了代码的简单例子.一个Java实现(预Java8)进行了讨论.我在GitHub上也看到了一个Python示例.

Answer 7

对于简单的情况，您可以使用 switch 样式方法。我发现过去处理转换效果也很好：

static int current_state;    // should always hold current state -- and probably be an enum or something

void state_leave(int new_state) {
    // do processing on what it means to enter the new state
    // which might be dependent on the current state
}

void state_enter(int new_state) {
    // do processing on what is means to leave the current state
    // might be dependent on the new state

    current_state = new_state;
}

void state_process() {
    // switch statement to handle current state
}
   

我对 boost 库一无所知，但这种方法非常简单，不需要任何外部依赖项，并且很容易实现。

Answer 8

我在 edx.org 课程“嵌入式系统 - 塑造世界 UTAustinX - UT.6.02x”，第 10 章，作者 Jonathan Valvano 和 Ramesh Yerraballi 中发现了摩尔 FSM 的非常巧妙的 C 实现。

struct State {
  unsigned long Out;  // 6-bit pattern to output
  unsigned long Time; // delay in 10ms units 
  unsigned long Next[4]; // next state for inputs 0,1,2,3
}; 

typedef const struct State STyp;

//this example has 4 states, defining constants/symbols using #define
#define goN   0
#define waitN 1
#define goE   2
#define waitE 3


//this is the full FSM logic coded into one large array of output values, delays, 
//and next states (indexed by values of the inputs)
STyp FSM[4]={
 {0x21,3000,{goN,waitN,goN,waitN}}, 
 {0x22, 500,{goE,goE,goE,goE}},
 {0x0C,3000,{goE,goE,waitE,waitE}},
 {0x14, 500,{goN,goN,goN,goN}}};
unsigned long currentState;  // index to the current state 

//super simple controller follows
int main(void){ volatile unsigned long delay;
//embedded micro-controller configuration omitteed [...]
  currentState = goN;  
  while(1){
    LIGHTS = FSM[currentState].Out;  // set outputs lines (from FSM table)
    SysTick_Wait10ms(FSM[currentState].Time);
    currentState = FSM[currentState].Next[INPUT_SENSORS];  
  }
}