Существует ли типичный шаблон реализации конечного автомата?

Question

Нам нужно реализовать простой конечный автомат в C .
Является ли стандартная инструкция переключения лучшим способом?
У нас есть текущее состояние (состояние) и триггер для перехода.

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

Есть ли лучший способ для простых конечных автоматов

EDIT: Я думаю, что для 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

Возможно, вы видели мой ответ на другой вопрос 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 структура переходов скрыта в управляющих структурах (в то время как, если, переключатель ...) и управляется значением переменных (обычно это переменная state), и это может быть сложной задачей связать красивую диаграмму с замысловатым кодом.

Я изучил эту технику из статьи, опубликованной в великом журнале «Компьютерный язык», который, к сожалению, больше не публикуется.

Answer 3

Я также использовал настольный подход. Тем не менее, есть накладные расходы. Зачем хранить второй список указателей? Функция в 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
    }
}

Конечно, в зависимости от вашего фактора страха (то есть от скорости до скорости), вы можете проверить правильность указателей. Для конечных автоматов, больших чем три или около того состояния, вышеупомянутый подход должен быть меньше инструкций, чем эквивалентный подход переключателя или таблицы. Вы могли бы даже макро-ize как:

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

Кроме того, из примера ОП я чувствую, что существует упрощение, которое следует сделать, когда вы думаете о / проектируете конечный автомат. Я не думаю, что переходное состояние должно использоваться для логики. Каждая функция состояния должна иметь возможность выполнять данную роль без явного знания прошлого состояния. По сути, вы разрабатываете способ перехода из состояния, в котором вы находитесь, в другое состояние.

Наконец, не начинайте проектирование конечного автомата на основе «функциональных» границ, используйте для этого подфункции. Вместо этого делите состояния на основе того, когда вам придется ждать, пока что-то произойдет, прежде чем вы сможете продолжить. Это поможет свести к минимуму количество запусков конечного автомата, прежде чем вы получите результат. Это может быть важно при написании функций ввода-вывода или обработчиков прерываний.

Кроме того, несколько плюсов и минусов классического оператора switch:

Плюсы:

• это на языке, поэтому оно задокументировано и понятно
• состояния определены там, где они называются
• может выполнять несколько состояний за один вызов функции
• код, общий для всех состояний, может быть выполнен до и после оператора switch

Минусы:

• может выполнять несколько состояний за один вызов функции
• код, общий для всех состояний, может быть выполнен до и после оператора switch
• Переключатель может быть медленным

Обратите внимание на два атрибута, которые как за, так и против. Я думаю, что переключение дает возможность слишком большого обмена между государствами, и взаимозависимость между государствами может стать неуправляемой. Однако для небольшого количества состояний он может быть наиболее читаемым и поддерживаемым.

Answer 4

Для простого конечного автомата просто используйте оператор switch и тип enum для вашего состояния. Делайте свои переходы внутри оператора 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;
    }
    ...
}

Answer 5

есть также логическая сетка , которая более удобна в обслуживании по мере того, как конечный автомат становится больше

Answer 6

В UML Distilled Мартина Фаулера , он заявляет (не каламбур) в главе 10 «Схемы конечных автоматов» (выделение мое):

Диаграмма состояний может быть реализована тремя основными способами: вложенный переключатель , шаблон состояния и таблицы состояний .

Давайте использовать упрощенный пример состояний дисплея мобильного телефона:

Вложенный переключатель

Фаулер привел пример кода на 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:

Таблицы состояний

Принимая вдохновение от Фаулера, вот таблица для моего примера:

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

Сравнение

Вложенный переключатель хранит всю логику в одном месте, но код может быть трудно читать при большом количестве состояний и переходов. Возможно, это более безопасно и проще для проверки, чем другие подходы (без полиморфизма или интерпретации).

Реализация шаблона State потенциально может распространить логику на несколько отдельных классов, что может затруднить понимание ее в целом. С другой стороны, маленькие классы легко понять отдельно. Дизайн особенно хрупок, если вы изменяете поведение, добавляя или удаляя переходы, так как они являются методами в иерархии и в коде может быть много изменений. Если вы живете по принципу дизайна небольших интерфейсов, вы увидите, что этот шаблон не очень хорошо работает. Однако, если конечный автомат стабилен, такие изменения не потребуются.

Подход таблиц состояний требует написания некоторого интерпретатора контента (это может быть проще, если у вас есть отражение в языке, который вы используете), что может потребовать много работы заранее. Как указывает Фаулер, если ваша таблица отделена от вашего кода, вы можете изменить поведение своего программного обеспечения без перекомпиляции. Это имеет некоторые последствия для безопасности, однако; программное обеспечение ведет себя на основе содержимого внешнего файла.

Редактировать (не совсем для языка C)

Существует также свободный подход к интерфейсу (он же внутренний предметно-ориентированный язык), которому, вероятно, способствуют языки с первоклассными функциями . Библиотека Stateless существует, и этот блог показывает простой пример с кодом. Обсуждается реализация Java (до Java8) . Мне также показали пример Python на GitHub .

Answer 7

Я нашел действительно блестящую реализацию Moore FSM на языке C на курсе edx.org «Встраиваемые системы - формируй мир» UTAustinX - UT.6.02x, глава 10, Джонатан Вальвано и Рамеш Йеррабалли ....

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

Answer 8

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

Answer 9

Для простых случаев вы можете использовать свой метод переключения стилей. Что я нашел, что хорошо работает в прошлом, так это также иметь дело с переходами:

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
}

Я ничего не знаю о библиотеке буста, но этот тип подхода очень прост, не требует никаких внешних зависимостей и прост в реализации.

Answer 10

Один из моих любимых шаблонов - шаблон государственного дизайна. Отвечать или вести себя по-разному на один и тот же набор входов.
Одна из проблем, связанных с использованием операторов switch / case для конечных автоматов, заключается в том, что по мере создания большего количества состояний switch / case становится труднее / громоздким для чтения / обслуживания, продвигает неорганизованный код спагетти и становится все труднее изменить, не нарушая чего-либо. Я считаю, что использование шаблонов проектирования помогает мне лучше организовывать свои данные, что и является целью абстракции. Вместо того, чтобы разрабатывать свой код состояния вокруг того, из какого состояния вы пришли, вместо этого структурируйте свой код так, чтобы он записывал состояние при входе в новое состояние. Таким образом, вы фактически получаете отчет о вашем предыдущем состоянии. Мне нравится ответ @ JoshPetit, и он сделал еще одно решение, прямо из книги GoF:

stateCtxt.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);

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

statehandlers.h:

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

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

Для большинства государственных машин, особенно Конечные автоматы, каждое состояние будет знать, каким должно быть его следующее состояние, и критерии перехода к следующему состоянию. Для проектов со свободным состоянием это может быть не так, поэтому существует возможность выставить API для переходных состояний. Если вы хотите больше абстракции, каждый обработчик состояний может быть выделен в свой собственный файл, который эквивалентен конкретным обработчикам состояний в книге GoF. Если ваш дизайн прост с несколькими состояниями, то и stateCtxt.c, и statehandlers.c могут быть объединены в один файл для простоты.