[c] 일반적인 상태 머신 구현 패턴이 있습니까?

우리는 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 사용 사례에 집중 하겠습니다 .

답변

대부분의 상태 머신에 테이블 기반 접근 방식을 선호합니다.

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

테이블 기반 접근 방식은 유지 관리 및 확장이 더 쉽고 상태 다이어그램에 매핑하는 것이 더 간단합니다.

답변

내가 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

특정 경우에 맞게 수정할 수 있습니다. 예를 들어 FSMFILEFSM을 구동하려는 파일 이있을 수 있으므로 다음 문자를 읽는 동작을 매크로 자체에 통합 할 수 있습니다.

#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을 구현하는 다른 기술에서 전환의 구조는 제어 구조에 묻히고 (If, switch …) 변수 값 (일반적으로 a state 변수)에 , nice 다이어그램을 a와 연결하는 것은 복잡한 작업 일 수 있습니다. 복잡한 코드.

나는 불행히도 더 이상 출판되지 않는 위대한 “컴퓨터 언어”잡지에 실린 기사에서이 기술을 배웠다.

답변

나는 또한 테이블 접근 방식을 사용했습니다. 그러나 오버 헤드가 있습니다. 두 번째 포인터 목록을 저장하는 이유는 무엇입니까? ()가없는 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
    }
}

물론 두려움 요인 (즉, 안전 대 속도)에 따라 유효한 포인터를 확인하는 것이 좋습니다. 3 개 정도의 상태보다 큰 상태 머신의 경우 위의 접근 방식은 동등한 스위치 또는 테이블 접근 방식보다 명령어가 적어야합니다. 다음과 같이 매크로화할 수도 있습니다.

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

또한 OP의 예에서 상태 머신을 생각 / 설계 할 때 수행해야하는 단순화가 있다고 느낍니다. 나는 전이 상태가 논리에 사용되어야한다고 생각하지 않습니다. 각 상태 기능은 과거 상태에 대한 명시 적 지식없이 주어진 역할을 수행 할 수 있어야합니다. 기본적으로 현재 상태에서 다른 상태로 전환하는 방법을 설계합니다.

마지막으로, “기능적”경계를 기반으로 상태 시스템의 설계를 시작하지 말고 하위 기능을 사용하십시오. 대신 계속하기 전에 어떤 일이 일어나기를 기다려야 할시기를 기준으로 상태를 나누십시오. 이렇게하면 결과를 얻기 전에 상태 머신을 실행해야하는 횟수를 최소화하는 데 도움이됩니다. 이것은 I / O 함수 또는 인터럽트 핸들러를 작성할 때 중요 할 수 있습니다.

또한 고전적인 switch 문의 몇 가지 장단점 :

장점 :

언어로되어 있으므로 문서화되고 명확합니다.
상태는 호출되는 위치에 정의됩니다.
하나의 함수 호출로 여러 상태를 실행할 수 있습니다.
모든 상태에 공통적 인 코드는 switch 문 전후에 실행할 수 있습니다.

단점 :

하나의 함수 호출로 여러 상태를 실행할 수 있습니다.
모든 상태에 공통적 인 코드는 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;
    }
    ...
}

답변

에서 마틴 파울러의 UML 증류 , 그는 (웃기 의도 없음) 제 10 장 상태 머신 다이어그램 (강조 광산)의 상태 :

상태 다이어그램은 중첩 스위치 , 상태 패턴 및
상태 테이블의 세 가지 주요 방법으로 구현할 수 있습니다 .

휴대폰 디스플레이 상태의 간단한 예를 사용하겠습니다.

중첩 스위치

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 상태 패턴을 사용한 예제 구현입니다.

상태 테이블

Fowler에서 영감을 얻은 예는 다음과 같습니다.

소스 상태 대상 상태 이벤트 보호 조치
-------------------------------------------------- ------------------------------------
화면 끄기 화면 끄기 누름 버튼 전원 낮음 디스플레이 낮음 전원 메시지
ScreenOff ScreenOn pressButton! powerLow
ScreenOn ScreenOff pressButton
ScreenOff Screen 충전 플러그 전원
ScreenOn Screen 충전 플러그 전원
화면 충전 화면 꺼짐 전원

비교

중첩 스위치는 모든 로직을 한곳에 보관하지만 상태와 전환이 많으면 코드를 읽기 어려울 수 있습니다. 다른 접근 방식 (다형성 또는 해석 없음)보다 더 안전하고 검증하기 쉽습니다.

상태 패턴 구현은 잠재적으로 로직을 여러 개별 클래스에 분산시켜 전체적으로 이해하는 데 문제가 될 수 있습니다. 반면에 소규모 수업은 개별적으로 이해하기 쉽습니다. 전환을 추가하거나 제거하여 동작을 변경하면 디자인이 특히 취약합니다. 전환은 계층 구조의 메서드이고 코드에 많은 변경이있을 수 있기 때문입니다. 작은 인터페이스의 디자인 원칙에 따라 생활한다면이 패턴이 제대로 작동하지 않는다는 것을 알 수 있습니다. 그러나 상태 머신이 안정적이면 이러한 변경이 필요하지 않습니다.

상태 테이블 접근 방식을 사용하려면 콘텐츠에 대한 일종의 인터프리터를 작성해야합니다 (사용중인 언어에 대한 성찰이있는 경우 더 쉬울 수 있음).이 작업은 미리 수행해야 할 많은 작업이 될 수 있습니다. Fowler가 지적했듯이 테이블이 코드와 분리되어 있으면 다시 컴파일하지 않고도 소프트웨어의 동작을 수정할 수 있습니다. 그러나 이것은 보안에 약간의 영향을 미칩니다. 소프트웨어는 외부 파일의 내용을 기반으로 작동합니다.

편집 (실제로 C 언어 용이 아님)

유창한 인터페이스 (일명 내부 도메인 특정 언어) 접근 방식도 있으며, 이는 아마도 일류 기능 을 가진 언어에 의해 촉진 될 것입니다 . 상태 비 라이브러리가 존재하고 그 블로그 프로그램 코드와 간단한 예제. 자바 구현 (Java8 사전) 논의된다. 나는 나타났다 GitHub의 파이썬 예제 뿐만 아니라.

답변

상태 머신이 커짐에 따라 유지 관리가 용이 한 로직 그리드 도 있습니다.

답변

간단한 경우에는 스타일 전환 방법을 사용할 수 있습니다. 내가 과거에 잘 작동했던 것은 전환도 처리하는 것입니다.

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
}

부스트 라이브러리에 대해 아무것도 모르지만 이러한 유형의 접근 방식은 매우 간단하고 외부 종속성이 필요하지 않으며 구현하기 쉽습니다.