是否存在典型的状态机实现模式?

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

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

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

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

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,因此可以将读取下一个字符的操作合并到宏本身中:

#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的其他技术中,转换的结构被埋入控制结构(while、if、switch…)中,并由变量值控制(典型地是a) state

我从一篇发表在《计算机语言》杂志上的文章中学到了这项技术,不幸的是,这篇文章已不再出版。

我也使用了表格法。然而,也存在开销。为什么要存储第二个指针列表?C中不带()的函数是常量指针。因此,您可以:

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语句前后执行
• 交换机的实现可能很慢

请注意两个属性,它们都是赞成和反对的。我认为,这种转变为州与州之间的过度共享提供了机会,州与州之间的相互依赖性可能变得难以管理。然而,对于少数几个状态,它可能是可读性和可维护性最好的。

在里面 Martin Fowler's UML Distilled ,他在第10章状态机图中指出(无双关语):

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

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

嵌套开关

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状态模式的一个实现:

状态表

以福勒为灵感,以下是我的示例:

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语言)

first-class functions . 这个 Stateless library 存在,该博客显示了一个简单的代码示例。A. Java implementation (pre Java8) Python example on GitHub

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

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

logic grid 随着状态机变得越来越大,哪个更易于维护

对于简单的情况,可以使用切换样式方法。我发现过去行之有效的方法是处理过渡:

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 atate
    // might be dependent on the new state

    current_state = new_state;
}

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

我对boost库一无所知,但这种方法非常简单,不需要任何外部依赖,而且易于实现。

switch()是C中实现状态机的一种强大且标准的方法,但是如果有大量状态,它会降低可维护性。另一种常用方法是使用函数指针存储下一个状态。这个简单的例子实现了一个设置/复位触发器:

/* Implement each state as a function with the same prototype */
void state_one(int set, int reset);
void state_two(int set, int reset);

/* Store a pointer to the next state */
void (*next_state)(int set, int reset) = state_one;

/* Users should call next_state(set, reset). This could
   also be wrapped by a real function that validated input
   and dealt with output rather than calling the function
   pointer directly. */

/* State one transitions to state one if set is true */
void state_one(int set, int reset) {
    if(set)
        next_state = state_two;
}

/* State two transitions to state one if reset is true */
void state_two(int set, int reset) {
    if(reset)
        next_state = state_one;
}

我在由Jonathan Valvano和Ramesh Yerraballi撰写的edx.org课程《嵌入式系统-塑造世界UTAustinX-UT.6.02x》第10章中发现了摩尔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];  
  }
}

你可能想调查一下 FSM生成器软件。从状态描述语言和/或(Windows)状态图编辑器,您可以生成C、C++、java和许多其他代码…再加上漂亮的文档和图表。 源代码和二进制文件 iMatix

This article 是状态模式的好方法(虽然它是C++,而不是C)。

如果你能把手放在书上“ Head First Design Patterns

我最喜欢的模式之一是state设计模式。对同一组给定的输入做出不同的响应或行为。
在状态机中使用switch/case语句的一个问题是,当您创建更多的状态时,switch/case变得更难/难以读取/维护,促进了无组织的意大利面代码,并且在不破坏某些内容的情况下进行更改变得越来越困难。我发现使用设计模式可以帮助我更好地组织数据,这是整个抽象的要点。 与其围绕您来自的州来设计州代码,不如构建代码,以便在您进入新州时记录该州。这样,您就可以有效地获得您以前状态的记录。我喜欢@JoshPetit的答案,并将他的解决方案向前推进了一步,直接从GoF书籍中获得:

stateCText.h:

#define STATE (void *)
typedef enum fsmSignal
{
   eEnter =0,
   eNormal,
   eExit
}FsmSignalT;

typedef struct fsm 
{
   FsmSignalT signal;
   // StateT is an enum that you can define any which way you want
   StateT currentState;
}FsmT;
extern int STATECTXT_Init(void);
/* optionally allow client context to set the target state */
extern STATECTXT_Set(StateT  stateID);
extern void STATECTXT_Handle(void *pvEvent);

stateCText.c:

#include "stateCtxt.h"
#include "statehandlers.h"

typedef STATE (*pfnStateT)(FsmSignalT signal, void *pvEvent);

static FsmT      fsm;
static pfnStateT UsbState ;

int STATECTXT_Init(void)
{    
    UsbState = State1;
    fsm.signal = eEnter;
    // use an enum for better maintainability
    fsm.currentState = '1';
    (*UsbState)( &fsm, pvEvent);
    return 0;
}

static void ChangeState( FsmT *pFsm, pfnStateT targetState )
{
    // Check to see if the state has changed
    if (targetState  != NULL)
    {
        // Call current state's exit event
        pFsm->signal = eExit;
        STATE dummyState = (*UsbState)( pFsm, pvEvent);

        // Update the State Machine structure
        UsbState = targetState ;

        // Call the new state's enter event
        pFsm->signal = eEnter;            
        dummyState = (*UsbState)( pFsm, pvEvent);
    }
}

void STATECTXT_Handle(void *pvEvent)
{
    pfnStateT newState;

    if (UsbState != NULL)
    {
         fsm.signal = eNormal;
         newState = (*UsbState)( &fsm, pvEvent );
         ChangeState( &fsm, newState );
    }        
}


void STATECTXT_Set(StateT  stateID)
{
     prevState = UsbState;
     switch (stateID) 
     {
         case '1':               
            ChangeState( State1 );
            break;
          case '2':
            ChangeState( State2);
            break;
          case '3':
            ChangeState( State3);
            break;
     }
}

stateholders.h:

/* define state handlers */
extern STATE State1(void);
extern STATE State2(void);
extern STATE State3(void);

stateholders.c:

#include "stateCtxt.h:"

/* Define behaviour to given set of inputs */
STATE State1(FsmT *fsm, void *pvEvent)
{   
    STATE nextState;
    /* do some state specific behaviours 
     * here
     */
    /* fsm->currentState currently contains the previous state
     * just before it gets updated, so you can implement behaviours 
     * which depend on previous state here
     */
    fsm->currentState = '1';
    /* Now, specify the next state
     * to transition to, or return null if you're still waiting for 
     * more stuff to process.  
     */
    switch (fsm->signal)
    {
        case eEnter:
            nextState = State2;
            break;
        case eNormal:
            nextState = null;
            break;
        case eExit:
            nextState = State2;
            break;
    }

    return nextState;
}

STATE  State3(FsmT *fsm, void *pvEvent)
{
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '2';
    /* Now, specify the next state
     * to transition to
     */
     return State1;
}

STATE   State2(FsmT *fsm, void *pvEvent)
{   
    /* do some state specific behaviours 
     * here
     */
    fsm->currentState = '3';
    /* Now, specify the next state
     * to transition to
     */
     return State3;
}

根据我的经验,使用“switch”语句是处理多种可能状态的标准方法。尽管我很惊讶您正在将转换值传递给每状态处理。我认为状态机的全部意义在于每个状态执行一个动作。然后,下一个操作/输入确定要转换到哪个新状态。所以我希望每个状态处理函数立即执行为进入状态而确定的任何操作,然后再决定是否需要转换到另一个状态。

有一本书名为 Practical Statecharts in C/C++ . 然而,事实并非如此 对于我们所需要的东西来说太重了。

对于支持哪种编译器 __COUNTER__ ,您可以将它们用于简单(但较大)的状态mashine。

  #define START 0      
  #define END 1000

  int run = 1;
  state = START;    
  while(run)
  {
    switch (state)
    {
        case __COUNTER__:
            //do something
            state++;
            break;
        case __COUNTER__:
            //do something
            if (input)
               state = END;
            else
               state++;
            break;
            .
            .
            .
        case __COUNTER__:
            //do something
            if (input)
               state = START;
            else
               state++;
            break;
        case __COUNTER__:
            //do something
            state++;
            break;
        case END:
            //do something
            run = 0;
            state = START;
            break;
        default:
            state++;
            break;
     } 
  } 

__柜台__ 而不是硬编码的数字是你 可以在其他状态中间添加状态,而不用每次都重新编号。 如果编译器不支持 ,在有限的范围内,可谨慎使用 __LINE__

您可以在c中使用最简单的UML状态机框架。 https://github.com/kiishor/UML-State-Machine-in-C

状态机由 state_machine_t

//! Abstract state machine structure
struct state_machine_t
{
   uint32_t Event;          //!< Pending Event for state machine
   const state_t* State;    //!< State of state machine.
};

状态由指向的指针表示 state_t

若框架是为有限状态机配置的,那个么 州

typedef struct finite_state_t state_t;

// finite state structure
typedef struct finite_state_t{
  state_handler Handler;        //!< State handler function (function pointer)
  state_handler Entry;          //!< Entry action for state (function pointer)
  state_handler Exit;           //!< Exit action for state (function pointer)
}finite_state_t;

该框架提供了一个API dispatch_event

state_machine_result_t dispatch_event(state_machine_t* const pState_Machine[], uint32_t quantity);

state_machine_result_t switch_state(state_machine_t* const, const state_t*);

state_machine_result_t traverse_state(state_machine_t* const, const state_t*);

有关如何实现分层状态机的更多详细信息,请参阅GitHub存储库。

代码示例
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine/readme.md
https://github.com/kiishor/UML-State-Machine-in-C/blob/master/demo/simple_state_machine_enhanced/readme.md

在C++中,考虑 State pattern .

您的问题类似于“是否存在典型的数据库实现模式”? 答案取决于你想要实现什么?如果您想要实现更大的确定性状态机,您可以使用模型和状态机生成器。 示例可在www.StateSoft.org-SM Gallery上查看。贾努斯·多布罗沃尔斯基

我也更喜欢表驱动的方法。我用过 switch 过去的声明。我遇到的主要问题是调试转换并确保设计的状态机已正确实现。这发生在存在大量状态和事件的情况下。

下面是这种方法的演示。

/*Demo implementations of State Machines
 *
 * This demo leverages a table driven approach and function pointers
 *
 * Example state machine to be implemented
 *
 *          +-----+      Event1        +-----+      Event2        +-----+
 *    O---->|  A  +------------------->|  B  +------------------->|  C  |
 *          +-----+                    +-----+                    +-----+
 *             ^                                                     |
 *             |                       Event3                        |
 *             +-----------------------------------------------------+
 *
 * States: A, B, C
 * Events: NoEvent (not shown, holding current state), Event1, Event2, Event3
 *
 * Partly leveraged the example here: http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/
 *
 * This sample code can be compiled and run using GCC.
 * >> gcc -o demo_state_machine demo_state_machine.c
 * >> ./demo_state_machine
 */

#include <stdio.h>
#include <assert.h>

// Definitions of state id's, event id's, and function pointer
#define N_STATES  3
#define N_EVENTS  4

typedef enum {
  STATE_A,
  STATE_B,
  STATE_C,
} StateId;

typedef enum {
  NOEVENT,
  EVENT1,
  EVENT2,
  EVENT3,
} Event;
typedef void (*StateRoutine)();

// Assert on number of states and events defined
static_assert(STATE_C==N_STATES-1,
  "Number of states does not match defined number of states");
static_assert(EVENT3==N_EVENTS-1,
  "Number of events does not match defined number of events");

// Defining State, holds both state id and state routine
typedef struct {
    StateId id;
    StateRoutine routine;
}  State;

// General functions
void evaluate_state(Event e);

// State routines to be executed at each state
void state_routine_a(void);
void state_routine_b(void);
void state_routine_c(void);

// Defining each state with associated state routine
const State state_a = {STATE_A, state_routine_a};
const State state_b = {STATE_B, state_routine_b};
const State state_c = {STATE_C, state_routine_c};

// Defning state transition matrix as visualized in the header (events not
// defined, result in mainting the same state)
State state_transition_mat[N_STATES][N_EVENTS] = {
   { state_a, state_b, state_a, state_a},
   { state_b, state_b, state_c, state_b},
   { state_c, state_c, state_c, state_a}};

// Define current state and initialize
State current_state = state_a;

int main()
{
    while(1) {
    // Event to receive from user
    int ev;

    printf("----------------\n");
    printf("Current state: %c\n", current_state.id + 65);
    printf("Event to occur: ");
    // Receive event from user
    scanf("%u", &ev);
    evaluate_state((Event) ev); // typecast to event enumeration type
    printf("-----------------\n");
    };
    return (0);
}

/*
 * Determine state based on event and perform state routine
 */
void evaluate_state(Event ev)
{
    //Determine state based on event
  current_state = state_transition_mat[current_state.id][ev];
  printf("Transitioned to state: %c\n", current_state.id + 65);
    // Run state routine
    (*current_state.routine)();
}

/*
 * State routines
 */
void state_routine_a() {
  printf("State A routine ran. \n");

}
void state_routine_b() {
  printf("State B routine ran. \n");
}
void state_routine_c() {
  printf("State C routine ran. \n");
}

Boost有状态图库。 http://www.boost.org/doc/libs/1_36_0/libs/statechart/doc/index.html