C 상태 머신 설계
C와 C ++를 혼합하여 작은 프로젝트를 만들고 있습니다. 나는 작업자 스레드 중 하나의 중심에 작은 작은 상태 머신을 만들고 있습니다.
SO를 좋아하는 사람이 상태 머신 설계 기술을 공유 할 수 있을지 궁금합니다.
참고 : 나는 주로 구현 기술을 시험하고 테스트 한 후에 있습니다.
업데이트 : SO에 수집 된 모든 위대한 입력을 기반 으로이 아키텍처에 정착했습니다.
내가 이전에 디자인 한 상태 머신 (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이 일반적으로 단일 컴파일 단위 안에 잠겨 있고 모든 변수가 해당 단위에 정적이기 때문에 전역을 사용하는 것이 들리는 것만 큼 나쁘지는 않습니다 (그래서 위의 "전역"주위에 따옴표를 사용했습니다. FSM보다 진정한 글로벌). 모든 세계와 마찬가지로주의가 필요합니다.
그런 다음 전이 배열은 가능한 모든 전이와 해당 전이에 대해 호출되는 함수 (포괄적 마지막 것 포함)를 정의합니다.
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특정 상태의 이벤트가 함수를 호출 할 수 있도록 비슷하게 작동합니다.
또한 전환 배열의 끝에 도달하면 ST_ANY/EV_ANY조합 을 사용하여 FSM이 올바르게 작성되지 않았다는 오류가 발생합니다 .
임베디드 시스템의 통신 스택 및 프로토콜의 초기 구현과 같은 많은 통신 프로젝트에서 이와 유사한 코드를 사용했습니다. 가장 큰 장점은 전환 배열 변경의 단순성과 상대적 용이성입니다.
나는 오늘날 더 적합 할 수있는 더 높은 수준의 추상화가있을 것임에 틀림 없다. 그러나 그것들이 모두 같은 종류의 구조로 귀결 될 것이라고 생각한다.
또한 ldog주석의 상태와 같이 모든 함수에 구조 포인터를 전달하고 이벤트 루프에서 사용하면 전역을 피할 수 있습니다. 이를 통해 여러 상태 머신이 간섭없이 나란히 실행될 수 있습니다.
기계 별 데이터 (최소한 상태)를 보유하는 구조 유형을 작성하고 전역 대신 사용하십시오.
내가 거의 수행하지 않은 이유는 내가 작성한 대부분의 상태 머신이 단일 유형 (예 : 일회성, 프로세스 시작, 구성 파일 읽기)이기 때문에 둘 이상의 인스턴스를 실행할 필요가 없기 때문입니다. . 그러나 둘 이상을 실행해야하는 경우 가치가 있습니다.
다른 답변은 좋지만 상태 머신이 매우 단순 할 때 사용한 매우 "경량"구현은 다음과 같습니다.
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 ... */
}
}
상태 머신이 함수 포인터 및 상태 전이 테이블 접근 방식이 지나치게 과도 할 정도로 간단 할 때 이것을 사용합니다. 이것은 종종 문자 별 또는 단어 별 구문 분석에 유용합니다.
컴퓨터 과학의 모든 규칙을 어기는 것에 대해 용서해주십시오. 그러나 스테이트 머신은 goto성명서가 더 효율적일뿐만 아니라 코드를 더 깨끗하고 읽기 쉽게 만드는 몇 안되는 곳 중 하나입니다 . goto명령문은 레이블을 기반으로 하기 때문에 숫자의 혼란을 추적하거나 열거 형을 사용하지 않고 주 이름을 지정할 수 있습니다. 또한 함수 포인터 또는 거대한 스위치 문과 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진술 을 사용하는 경우 , 그렇게하는 동안 발로 자신을 촬영하기가 매우 쉽기 때문에 여전히주의해야합니다.
State Machine Compiler http://smc.sourceforge.net/을 고려할 수 있습니다 .
이 화려한 오픈 소스 유틸리티는 간단한 언어로 상태 머신에 대한 설명을 받아 C 및 C ++를 포함하여 12 개 정도의 언어 중 하나로 컴파일합니다. 유틸리티 자체는 Java로 작성되었으며 빌드의 일부로 포함될 수 있습니다.
이를 수행하는 이유는 GoF 상태 패턴 또는 다른 접근 방식을 사용하여 수동 코딩하는 대신 상태 머신이 코드로 표현되면 기본 구조가이를 지원하기 위해 생성해야하는 상용구의 무게에 따라 사라지는 경향이 있기 때문입니다. 이 접근 방식을 사용하면 여러 가지 우려 사항을 분리 할 수 있으며 상태 머신의 구조를 '보이게'유지할 수 있습니다. 자동 생성 된 코드는 사용자가 직접 만질 필요가없는 모듈로 들어가므로 작성한 지원 코드에 영향을주지 않고 상태 시스템의 구조로 되돌아 갈 수 있습니다.
죄송합니다. 저는 너무 열정적이며 의심 할 여지없이 모든 사람을 미루고 있습니다. 그러나 최고 수준의 유틸리티이며 잘 문서화되어 있습니다.
C / C ++ Users Journal의 기사 가 훌륭했던 Miro Samek (블로그 State Space , 웹 사이트 State Machines & Tools ) 의 작업을 확인하십시오 .
이 웹 사이트에는 상태 머신 프레임 워크 (QP 프레임 워크) , 이벤트 핸들러 (QEP) , 기본 모델링 도구 (QM) 및 추적 도구 (QSpy)의 공개 소스 및 상업용 라이센스 모두에서 완전한 (C / C ++) 구현이 포함되어 있습니다. 상태 머신을 그리고 코드를 생성하고 디버깅 할 수 있습니다.
이 책은 구현의 이유 / 이유 및 사용 방법에 대한 광범위한 설명을 포함하며 계층 적 및 유한 상태 머신의 기본을 이해하는 데 유용한 자료입니다.
이 웹 사이트에는 내장 플랫폼과 함께 소프트웨어를 사용하기위한 여러 보드 지원 패키지에 대한 링크도 포함되어 있습니다.
paxdiablo가 설명 한 것과 비슷한 것을 수행했습니다. 상태 / 이벤트 전환 배열 대신에만 이벤트 값을 한 축의 인덱스로 사용하고 현재 상태 값을 2 차원 함수 포인터 배열로 설정했습니다. 다른 사람. 그런 다음 그냥 전화 state = state_table[event][state](params)하면 올바른 일이 발생합니다. 유효하지 않은 상태 / 이벤트 조합을 나타내는 셀은 물론 그렇게 말하는 함수에 대한 포인터를 얻습니다.
분명히 이것은 상태 및 이벤트 값이 인접한 범위이고 0에서 시작하거나 충분히 가까운 경우에만 작동합니다.
Stefan Heinzmann은 그의 기사 에서 매우 훌륭한 템플릿 기반 C ++ 상태 머신 "프레임 워크"를 제공합니다 .
이 기사에는 완전한 코드 다운로드에 대한 링크가 없으므로 코드를 프로젝트에 붙여 넣고 체크 아웃하는 자유를 얻었습니다. 아래의 것들이 테스트되었으며 사소하지만 거의 명백한 누락 된 부분이 포함되어 있습니다.
여기서 중요한 혁신은 컴파일러가 매우 효율적인 코드를 생성한다는 것입니다. 빈 출입 통제 비용은 없습니다. 비어 있지 않은 입 / 출력 조치가 인라인됩니다. 컴파일러는 또한 상태 차트의 완전성을 확인합니다. 누락 된 조치는 링크 오류를 생성합니다. 잡히지 않는 유일한 것은 실종 Top::init입니다.
이것은 누락되지 않은 채 살 수 있다면 Miro Samek의 구현에 대한 훌륭한 대안입니다. 이것은 UML 의미를 올바르게 구현하지만 완전한 UML Statechart 구현과는 거리가 있습니다 .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)
상태 머신 (적어도 프로그램 제어를위한 것)에서 내가 좋아하는 기술은 함수 포인터를 사용하는 것입니다. 각 상태는 다른 기능으로 표시됩니다. 이 함수는 입력 기호를 사용하여 다음 상태에 대한 함수 포인터를 반환합니다. 중앙 디스패치 루프 모니터는 다음 입력을 가져 와서 현재 상태로 공급하고 결과를 처리합니다.
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);
}
}
그런 다음 개별 상태 함수는 입력을 켜서 적절한 값을 처리하고 반환 할 수 있습니다.
가장 간단한 경우
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 ++ 템플릿을 이용하고 있다고 생각하지만 구문이 암호화되어 있습니다.
2 차원 테이블
나는 과거에 상태 / 이벤트 테이블을 사용했지만 가장 간단한 경우에는 필요하지 않으며 스위치 화면이 한 화면을 넘게 확장하더라도 명확하고 가독성을 선호한다고 말해야합니다. 더 복잡한 경우에는 다른 사람들이 지적했듯이 테이블이 빨리 사라집니다. 여기에있는 관용구는 메모리 소비 테이블을 유지하지 않고도 (프로그램 메모리 일지라도) 많은 이벤트와 상태를 추가 할 수 있습니다.
기권
특별한 요구는이 관용구의 유용성을 떨어 뜨릴 수 있지만, 나는 그것들이 매우 명확하고 유지 보수가 용이하다는 것을 알았습니다.
테스트되지는 않았지만 코딩하기가 재미있어서 원래의 대답보다 더 세련된 버전으로 제공됩니다. 최신 버전은 mercurial.intuxication.org 에서 찾을 수 있습니다 .
sm.h
#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
"use '#define SM_ARGS (void)' to get an empty argument list"
#endif
#ifndef SM_STATES
#error "SM_STATES undefined: " \
"you must provide a list of comma-separated states"
#endif
typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;
#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)
#define sm_def(NAME) \
static sm_state NAME ## _fn SM_ARGS; \
static const sm_state NAME = (sm_state)NAME ## _fn; \
static sm_state NAME ## _fn SM_ARGS
example.c
#include <stdio.h>
#define SM_ARGS (int i)
#define SM_STATES EVEN, ODD
#include "sm.h"
sm_def(EVEN)
{
printf("even %i\n", i);
return ODD;
}
sm_def(ODD)
{
printf("odd %i\n", i);
return EVEN;
}
int main(void)
{
int i = 0;
sm_state state = EVEN;
for(; i < 10; ++i)
state = sm_transit(state)(i);
return 0;
}
나는 paxdiable의 답변을 정말로 좋아했고 가드 변수 및 상태 머신 특정 데이터와 같은 내 응용 프로그램에 누락 된 모든 기능을 구현하기로 결정했습니다.
커뮤니티와 공유하기 위해이 사이트에 구현을 업로드했습니다. ARM 용 IAR Embedded Workbench를 사용하여 테스트되었습니다.
https://sourceforge.net/projects/compactfsm/
또 다른 흥미로운 오픈 소스 도구는 statecharts.org의 Yakindu Statechart Tools입니다 . Harel 상태 차트를 사용하므로 계층 적 및 병렬 상태를 제공하고 C 및 C ++ (및 Java) 코드를 생성합니다. 라이브러리를 사용하지 않지만 '일반 코드'접근 방식을 따릅니다. 이 코드는 기본적으로 스위치 케이스 구조를 적용합니다. 코드 생성기는 사용자 정의 할 수도 있습니다. 또한이 도구는 다른 많은 기능을 제공합니다.
이 늦게 (평소대로)오고 있지만 지금까지 답변을 스캔하면 중요한 것이 빠져 있다고 생각합니다.
내 자신의 프로젝트 에서 모든 유효한 주 / 이벤트 조합에 대한 기능을 갖지 않는 것이 매우 도움이 될 수 있음을 발견했습니다 . 나는 2D 상태 / 이벤트 테이블을 효과적으로 갖는 아이디어를 좋아합니다. 그러나 테이블 요소가 단순한 함수 포인터 이상이되는 것을 좋아합니다. 대신 디자인을 마음대로 구성하여 간단한 원자 요소 또는 동작으로 구성하려고합니다. 그렇게하면 상태 / 이벤트 테이블의 각 교차점에 간단한 원자 요소를 나열 할 수 있습니다. 아이디어는 질량의 N 제곱 (일반적으로 매우 간단한) 함수를 정의 할 필요가 없다는 것입니다. 왜 오류가 발생하기 쉽고, 시간이 오래 걸리고, 쓰기가 어렵고, 읽기가 어려운 이유가 무엇입니까?
선택적 새 상태 및 테이블의 각 셀에 대한 선택적 함수 포인터도 포함합니다. 함수 포인터는 원자 적 조치 목록을 실행하지 않으려는 예외적 인 경우를 위해 존재합니다.
새 코드를 작성하지 않고 테이블을 편집하기 만하면 다양한 기능을 표현할 수있을 때 올바르게하고 있다는 것을 알고 있습니다.
Alrght, 나는 내 것이 다른 사람들과 조금 다르다고 생각합니다. 다른 답변에서 볼 수있는 것보다 코드와 데이터가 조금 더 분리되어 있습니다. 나는 이것을 작성하기위한 이론을 실제로 읽었습니다. 정규 표현식없이 슬프게도 전체 정규 언어를 구현합니다. 울만, 민스키, 촘스키 내가 모든 것을 이해했다고 말할 수는 없지만, 나는 가능한 한 직접적으로 그들의 말을 통해 옛 주인으로부터 이끌어 냈습니다.
'yes'상태 또는 'no'상태로의 전환을 결정하는 술어에 대한 함수 포인터를 사용합니다. 이를 통해보다 어셈블리 언어와 같은 방식으로 프로그래밍하는 일반 언어에 대한 유한 상태 억 셉터를 쉽게 만들 수 있습니다. 바보 같은 이름을 선택하지 마십시오. 'czek'== '확인'. 'grok'== [해커 사전에서 찾아보십시오].
따라서 각 반복마다 czek은 현재 문자를 인수로 사용하여 술어 함수를 호출합니다. 술어가 true를 리턴하면, 문자가 소비되고 (포인터가 진행됨) 'y'전이에 따라 다음 상태를 선택합니다. 술어가 false를 리턴하면 문자가 소비되지 않으며 'n'전환을 따릅니다. 따라서 모든 지시는 양방향 브랜치입니다! 나는 당시 멜의 이야기를 읽고 있었을 것입니다.
이 코드는 포스트 스크립트 인터프리터 에서 직접 제공 되며 comp.lang.c의 동료로부터 많은 안내를 받아 현재 형식으로 발전했습니다. 포스트 스크립트에는 기본적으로 구문이 없으며 (밸런스 괄호 만 필요)이 같은 일반 언어 수락 기는 파서 기능도합니다.
/* currentstr is set to the start of string by czek
and used by setrad (called by israd) to set currentrad
which is used by israddig to determine if the character
in question is valid for the specified radix
--
a little semantic checking in the syntax!
*/
char *currentstr;
int currentrad;
void setrad(void) {
char *end;
currentrad = strtol(currentstr, &end, 10);
if (*end != '#' /* just a sanity check,
the automaton should already have determined this */
|| currentrad > 36
|| currentrad < 2)
fatal("bad radix"); /* should probably be a simple syntaxerror */
}
/*
character classes
used as tests by automatons under control of czek
*/
char *alpha = "0123456789" "ABCDE" "FGHIJ" "KLMNO" "PQRST" "UVWXYZ";
#define EQ(a,b) a==b
#define WITHIN(a,b) strchr(a,b)!=NULL
int israd (int c) {
if (EQ('#',c)) { setrad(); return true; }
return false;
}
int israddig(int c) {
return strchrnul(alpha,toupper(c))-alpha <= currentrad;
}
int isdot (int c) {return EQ('.',c);}
int ise (int c) {return WITHIN("eE",c);}
int issign (int c) {return WITHIN("+-",c);}
int isdel (int c) {return WITHIN("()<>[]{}/%",c);}
int isreg (int c) {return c!=EOF && !isspace(c) && !isdel(c);}
#undef WITHIN
#undef EQ
/*
the automaton type
*/
typedef struct { int (*pred)(int); int y, n; } test;
/*
automaton to match a simple decimal number
*/
/* /^[+-]?[0-9]+$/ */
test fsm_dec[] = {
/* 0*/ { issign, 1, 1 },
/* 1*/ { isdigit, 2, -1 },
/* 2*/ { isdigit, 2, -1 },
};
int acc_dec(int i) { return i==2; }
/*
automaton to match a radix number
*/
/* /^[0-9]+[#][a-Z0-9]+$/ */
test fsm_rad[] = {
/* 0*/ { isdigit, 1, -1 },
/* 1*/ { isdigit, 1, 2 },
/* 2*/ { israd, 3, -1 },
/* 3*/ { israddig, 4, -1 },
/* 4*/ { israddig, 4, -1 },
};
int acc_rad(int i) { return i==4; }
/*
automaton to match a real number
*/
/* /^[+-]?(d+(.d*)?)|(d*.d+)([eE][+-]?d+)?$/ */
/* represents the merge of these (simpler) expressions
[+-]?[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?
[+-]?[0-9]*\.[0-9]+([eE][+-]?[0-9]+)?
The complexity comes from ensuring at least one
digit in the integer or the fraction with optional
sign and optional optionally-signed exponent.
So passing isdot in state 3 means at least one integer digit has been found
but passing isdot in state 4 means we must find at least one fraction digit
via state 5 or the whole thing is a bust.
*/
test fsm_real[] = {
/* 0*/ { issign, 1, 1 },
/* 1*/ { isdigit, 2, 4 },
/* 2*/ { isdigit, 2, 3 },
/* 3*/ { isdot, 6, 7 },
/* 4*/ { isdot, 5, -1 },
/* 5*/ { isdigit, 6, -1 },
/* 6*/ { isdigit, 6, 7 },
/* 7*/ { ise, 8, -1 },
/* 8*/ { issign, 9, 9 },
/* 9*/ { isdigit, 10, -1 },
/*10*/ { isdigit, 10, -1 },
};
int acc_real(int i) {
switch(i) {
case 2: /* integer */
case 6: /* real */
case 10: /* real with exponent */
return true;
}
return false;
}
/*
Helper function for grok.
Execute automaton against the buffer,
applying test to each character:
on success, consume character and follow 'y' transition.
on failure, do not consume but follow 'n' transition.
Call yes function to determine if the ending state
is considered an acceptable final state.
A transition to -1 represents rejection by the automaton
*/
int czek (char *s, test *fsm, int (*yes)(int)) {
int sta = 0;
currentstr = s;
while (sta!=-1 && *s) {
if (fsm[sta].pred((int)*s)) {
sta=fsm[sta].y;
s++;
} else {
sta=fsm[sta].n;
}
}
return yes(sta);
}
/*
Helper function for toke.
Interpret the contents of the buffer,
trying automatons to match number formats;
and falling through to a switch for special characters.
Any token consisting of all regular characters
that cannot be interpreted as a number is an executable name
*/
object grok (state *st, char *s, int ns,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
if (czek(s, fsm_dec, acc_dec)) {
long num;
num = strtol(s,NULL,10);
if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
error(st,limitcheck);
/* } else if (num > INT_MAX || num < INT_MIN) { */
/* error(limitcheck, OP_token); */
} else {
return consint(num);
}
}
else if (czek(s, fsm_rad, acc_rad)) {
long ra,num;
ra = (int)strtol(s,NULL,10);
if (ra > 36 || ra < 2) {
error(st,limitcheck);
}
num = strtol(strchr(s,'#')+1, NULL, (int)ra);
if ((num==LONG_MAX || num==LONG_MIN) && errno==ERANGE) {
error(st,limitcheck);
/* } else if (num > INT_MAX || num < INT_MAX) { */
/* error(limitcheck, OP_token); */
} else {
return consint(num);
}
}
else if (czek(s, fsm_real, acc_real)) {
double num;
num = strtod(s,NULL);
if ((num==HUGE_VAL || num==-HUGE_VAL) && errno==ERANGE) {
error(st,limitcheck);
} else {
return consreal(num);
}
}
else switch(*s) {
case '(': {
int c, defer=1;
char *sp = s;
while (defer && (c=next(st,src)) != EOF ) {
switch(c) {
case '(': defer++; break;
case ')': defer--;
if (!defer) goto endstring;
break;
case '\\': c=next(st,src);
switch(c) {
case '\n': continue;
case 'a': c = '\a'; break;
case 'b': c = '\b'; break;
case 'f': c = '\f'; break;
case 'n': c = '\n'; break;
case 'r': c = '\r'; break;
case 't': c = '\t'; break;
case 'v': c = '\v'; break;
case '\'': case '\"':
case '(': case ')':
default: break;
}
}
if (sp-s>ns) error(st,limitcheck);
else *sp++ = c;
}
endstring: *sp=0;
return cvlit(consstring(st,s,sp-s));
}
case '<': {
int c;
char d, *x = "0123456789abcdef", *sp = s;
while (c=next(st,src), c!='>' && c!=EOF) {
if (isspace(c)) continue;
if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
else error(st,syntaxerror);
d = (char)c << 4;
while (isspace(c=next(st,src))) /*loop*/;
if (isxdigit(c)) c = strchr(x,tolower(c)) - x;
else error(st,syntaxerror);
d |= (char)c;
if (sp-s>ns) error(st,limitcheck);
*sp++ = d;
}
*sp = 0;
return cvlit(consstring(st,s,sp-s));
}
case '{': {
object *a;
size_t na = 100;
size_t i;
object proc;
object fin;
fin = consname(st,"}");
(a = malloc(na * sizeof(object))) || (fatal("failure to malloc"),0);
for (i=0 ; objcmp(st,a[i]=toke(st,src,next,back),fin) != 0; i++) {
if (i == na-1)
(a = realloc(a, (na+=100) * sizeof(object))) || (fatal("failure to malloc"),0);
}
proc = consarray(st,i);
{ size_t j;
for (j=0; j<i; j++) {
a_put(st, proc, j, a[j]);
}
}
free(a);
return proc;
}
case '/': {
s[1] = (char)next(st,src);
puff(st, s+2, ns-2, src, next, back);
if (s[1] == '/') {
push(consname(st,s+2));
opexec(st, op_cuts.load);
return pop();
}
return cvlit(consname(st,s+1));
}
default: return consname(st,s);
}
return null; /* should be unreachable */
}
/*
Helper function for toke.
Read into buffer any regular characters.
If we read one too many characters, put it back
unless it's whitespace.
*/
int puff (state *st, char *buf, int nbuf,
object *src,
int (*next)(state *,object *),
void (*back)(state *,int, object *)) {
int c;
char *s = buf;
while (isreg(c=next(st,src))) {
if (s-buf >= nbuf-1) return false;
*s++ = c;
}
*s = 0;
if (!isspace(c) && c != EOF) back(st,c,src); /* eat interstice */
return true;
}
/*
Helper function for Stoken Ftoken.
Read a token from src using next and back.
Loop until having read a bona-fide non-whitespace non-comment character.
Call puff to read into buffer up to next delimiter or space.
Call grok to figure out what it is.
*/
#define NBUF MAXLINE
object toke (state *st, object *src,
int (*next)(state *, object *),
void (*back)(state *, int, object *)) {
char buf[NBUF] = "", *s=buf;
int c,sta = 1;
object o;
do {
c=next(st,src);
//if (c==EOF) return null;
if (c=='%') {
if (DUMPCOMMENTS) fputc(c, stdout);
do {
c=next(st,src);
if (DUMPCOMMENTS) fputc(c, stdout);
} while (c!='\n' && c!='\f' && c!=EOF);
}
} while (c!=EOF && isspace(c));
if (c==EOF) return null;
*s++ = c;
*s = 0;
if (!isdel(c)) sta=puff(st, s,NBUF-1,src,next,back);
if (sta) {
o=grok(st,buf,NBUF-1,src,next,back);
return o;
} else {
return null;
}
}
boost.org에는 두 가지 상태 차트 구현이 있습니다.
항상 그렇듯이 boost는 템플릿 지옥으로 당신을 안내합니다.
첫 번째 라이브러리는보다 성능이 중요한 상태 머신을위한 것입니다. 두 번째 라이브러리는 UML 상태 차트에서 코드로 직접 전환 경로를 제공합니다.
다음 은 두 저자가 반응 하는 두 곳 의 비교를 요청 하는 SO 질문 입니다.
다소 복잡한 제어 로직 비트에 대한 이 일련의 Ars OpenForum 게시물 에는 C의 상태 시스템으로서 매우 따르기 쉬운 구현이 포함되어 있습니다.
이 어딘가에 보았다
#define FSM
#define STATE(x) s_##x :
#define NEXTSTATE(x) goto s_##x
FSM {
STATE(x) {
...
NEXTSTATE(y);
}
STATE(y) {
...
if (x == 0)
NEXTSTATE(y);
else
NEXTSTATE(x);
}
}
C ++과 OO 코드를 사용할 수 있다고 가정하면 'GoF'상태 패턴 (GoF = Gang of Four, 디자인 패턴을 작성하여 디자인 패턴을 작성한 사람)을 평가하는 것이 좋습니다.
특히 복잡하지는 않으며 널리 사용되고 논의되므로 예제와 설명을 온라인으로 쉽게 볼 수 있습니다.
또한 나중에 코드를 유지 관리하는 다른 사람이 인식 할 수 있습니다.
효율성이 걱정된다면 많은 요소가 성능에 영향을 미치고 항상 단순히 OO 나쁘고 기능적인 코드가 아니라는 점에서 비 OO 방식이 더 효율적인지 확인하기 위해 실제로 벤치마킹 할 가치가 있습니다. 마찬가지로 메모리 사용이 제약 조건 인 경우 상태 패턴을 사용하는 경우 특정 응용 프로그램에 실제로 문제가 있는지 확인하기 위해 일부 테스트 또는 계산을 다시 수행 할 가치가 있습니다.
다음은 Craig가 제안한 것처럼 'Gof'상태 패턴에 대한 링크입니다.
귀하의 질문은 매우 일반적입니다.
다음은 유용한 두 가지 참조 기사입니다.
-
이 기사는 임베디드 시스템을위한 상태 머신을 구현하는 간단한 방법을 설명합니다. 이 기사의 목적 상 상태 머신은 소수의 상태 중 하나에있을 수있는 알고리즘으로 정의됩니다. 상태는 입력과 출력, 그리고 다음 상태에 대한 입력의 관계를 규정하는 조건입니다.
정통한 독자라면이 기사에서 설명하는 상태 머신은 Mealy 머신이라는 것을 빨리 알 수 있습니다. Mealy 머신은 출력이 상태 전용 함수 인 Moore 머신과 달리 출력이 현재 상태 및 입력의 함수 인 상태 머신입니다.- C 및 C ++의 상태 머신 코딩
이 기사에서는 상태 머신 기본 사항과 C 또는 C ++로 상태 머신을 코딩하기위한 간단한 프로그래밍 지침에 중점을 둡니다. 이러한 간단한 기술이보다 일반화되어 소스 코드에서 바로 상태 머신 구조를 쉽게 볼 수 있기를 바랍니다.
- C 및 C ++의 상태 머신 코딩
내가 사용한 상태 머신 컴파일러를 성공으로 자바와 파이썬 프로젝트.
이것은 많은 답변이 담긴 오래된 게시물이지만 C의 유한 상태 머신에 대한 고유 한 접근 방식을 추가한다고 생각했습니다. 모든 상태에 대한 골격 C 코드를 생성하는 Python 스크립트를 만들었습니다. 이 스크립트는 FsmTemplateC의 GituHub 에 문서화되어 있습니다.
이 예제는 내가 읽은 다른 접근법을 기반으로합니다. goto 또는 switch 문을 사용하지 않고 대신 포인터 매트릭스 (조회 테이블)에 전이 함수가 있습니다. 이 코드는 큰 멀티 라인 이니셜 라이저 매크로 및 C99 기능 (지정된 이니셜 라이저 및 복합 리터럴)에 의존하므로 이러한 방식이 마음에 들지 않으면이 방법이 마음에 들지 않을 수 있습니다.
다음은 FsmTemplateC를 사용하여 스켈레톤 C 코드를 생성 하는 개찰구 예제 의 Python 스크립트입니다 .
# dict parameter for generating FSM
fsm_param = {
# main FSM struct type string
'type': 'FsmTurnstile',
# struct type and name for passing data to state machine functions
# by pointer (these custom names are optional)
'fopts': {
'type': 'FsmTurnstileFopts',
'name': 'fopts'
},
# list of states
'states': ['locked', 'unlocked'],
# list of inputs (can be any length > 0)
'inputs': ['coin', 'push'],
# map inputs to commands (next desired state) using a transition table
# index of array corresponds to 'inputs' array
# for this example, index 0 is 'coin', index 1 is 'push'
'transitiontable': {
# current state | 'coin' | 'push' |
'locked': ['unlocked', ''],
'unlocked': [ '', 'locked']
}
}
# folder to contain generated code
folder = 'turnstile_example'
# function prefix
prefix = 'fsm_turnstile'
# generate FSM code
code = fsm.Fsm(fsm_param).genccode(folder, prefix)
생성 된 출력 헤더에는 typedef가 포함됩니다.
/* function options (EDIT) */
typedef struct FsmTurnstileFopts {
/* define your options struct here */
} FsmTurnstileFopts;
/* transition check */
typedef enum eFsmTurnstileCheck {
EFSM_TURNSTILE_TR_RETREAT,
EFSM_TURNSTILE_TR_ADVANCE,
EFSM_TURNSTILE_TR_CONTINUE,
EFSM_TURNSTILE_TR_BADINPUT
} eFsmTurnstileCheck;
/* states (enum) */
typedef enum eFsmTurnstileState {
EFSM_TURNSTILE_ST_LOCKED,
EFSM_TURNSTILE_ST_UNLOCKED,
EFSM_TURNSTILE_NUM_STATES
} eFsmTurnstileState;
/* inputs (enum) */
typedef enum eFsmTurnstileInput {
EFSM_TURNSTILE_IN_COIN,
EFSM_TURNSTILE_IN_PUSH,
EFSM_TURNSTILE_NUM_INPUTS,
EFSM_TURNSTILE_NOINPUT
} eFsmTurnstileInput;
/* finite state machine struct */
typedef struct FsmTurnstile {
eFsmTurnstileInput input;
eFsmTurnstileCheck check;
eFsmTurnstileState cur;
eFsmTurnstileState cmd;
eFsmTurnstileState **transition_table;
void (***state_transitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
void (*run)(struct FsmTurnstile *, FsmTurnstileFopts *, const eFsmTurnstileInput);
} FsmTurnstile;
/* transition functions */
typedef void (*pFsmTurnstileStateTransitions)(struct FsmTurnstile *, FsmTurnstileFopts *);
- enum
eFsmTurnstileCheck은 전환이로 차단되었는지,EFSM_TURNSTILE_TR_RETREAT진행이 허용되는지EFSM_TURNSTILE_TR_ADVANCE또는 함수 호출이로 전환되지 않았 는지 판별하는 데 사용됩니다EFSM_TURNSTILE_TR_CONTINUE. - enum
eFsmTurnstileState은 단순히 상태 목록입니다. - enum
eFsmTurnstileInput은 단순히 입력 목록입니다. FsmTurnstile구조체 전이 체크 기능 룩업 테이블, 현재 상태, 명 상태, 및 시스템을 실행하는 기본 함수에 별명 상태 머신의 심장부이다.- 모든 함수 포인터 (별칭)
FsmTurnstile는 구조체에서만 호출해야하며 지속적인 상태, 객체 지향 스타일을 유지하려면 포인터를 처음으로 입력해야합니다.
이제 헤더의 함수 선언에 대해
/* fsm declarations */
void fsm_turnstile_locked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_locked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_locked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_unlocked_unlocked (FsmTurnstile *fsm, FsmTurnstileFopts *fopts);
void fsm_turnstile_run (FsmTurnstile *fsm, FsmTurnstileFopts *fopts, const eFsmTurnstileInput input);
함수 이름의 형식은 {prefix}_{from}_{to}, {from}이전 (현재) 상태와 {to}다음 상태입니다. 전이 테이블에서 특정 전이를 허용하지 않으면 함수 포인터 대신 NULL 포인터가 설정됩니다. 마지막으로, 마법은 매크로와 함께 발생합니다. 여기에서 전이 테이블 (상태 열거 형의 행렬)을 만들고 상태 전이 함수 조회 테이블 (함수 포인터의 행렬) :
/* creation macro */
#define FSM_TURNSTILE_CREATE() \
{ \
.input = EFSM_TURNSTILE_NOINPUT, \
.check = EFSM_TURNSTILE_TR_CONTINUE, \
.cur = EFSM_TURNSTILE_ST_LOCKED, \
.cmd = EFSM_TURNSTILE_ST_LOCKED, \
.transition_table = (eFsmTurnstileState * [EFSM_TURNSTILE_NUM_STATES]) { \
(eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
EFSM_TURNSTILE_ST_UNLOCKED, \
EFSM_TURNSTILE_ST_LOCKED \
}, \
(eFsmTurnstileState [EFSM_TURNSTILE_NUM_INPUTS]) { \
EFSM_TURNSTILE_ST_UNLOCKED, \
EFSM_TURNSTILE_ST_LOCKED \
} \
}, \
.state_transitions = (pFsmTurnstileStateTransitions * [EFSM_TURNSTILE_NUM_STATES]) { \
(pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
fsm_turnstile_locked_locked, \
fsm_turnstile_locked_unlocked \
}, \
(pFsmTurnstileStateTransitions [EFSM_TURNSTILE_NUM_STATES]) { \
fsm_turnstile_unlocked_locked, \
fsm_turnstile_unlocked_unlocked \
} \
}, \
.run = fsm_turnstile_run \
}
FSM을 만들 때는 매크로 FSM_EXAMPLE_CREATE()를 사용해야합니다.
이제 소스 코드에서 위에 선언 된 모든 상태 전이 함수를 채워야합니다. FsmTurnstileFopts구조체는 상태 머신 /로부터 데이터를 전달하기 위해 사용될 수있다. 모든 전환은 전환 을 차단하거나 명령 상태로 전환 할 수 있도록 fsm->check동일하게 설정해야합니다 . 실제 예제는 (FsmTemplateC) [ https://github.com/ChisholmKyle/FsmTemplateC] 에서 찾을 수 있습니다 .EFSM_EXAMPLE_TR_RETREATEFSM_EXAMPLE_TR_ADVANCE
코드에서 매우 간단한 실제 사용법은 다음과 같습니다.
/* create fsm */
FsmTurnstile fsm = FSM_TURNSTILE_CREATE();
/* create fopts */
FsmTurnstileFopts fopts = {
.msg = ""
};
/* initialize input */
eFsmTurnstileInput input = EFSM_TURNSTILE_NOINPUT;
/* main loop */
for (;;) {
/* wait for timer signal, inputs, interrupts, whatever */
/* optionally set the input (my_input = EFSM_TURNSTILE_IN_PUSH for example) */
/* run state machine */
my_fsm.run(&my_fsm, &my_fopts, my_input);
}
간단하고 빠른 인터페이스를 제공하는 모든 헤더 비즈니스와 모든 기능은 내 마음에 가치가 있습니다.
오픈 소스 라이브러리 OpenFST를 사용할 수 있습니다 .
OpenFst는 가중 유한 상태 변환기 (FST)를 구성, 결합, 최적화 및 검색하기위한 라이브러리입니다. 가중 유한 상태 변환기는 각 전이에 입력 레이블, 출력 레이블 및 가중치가있는 자동 모드입니다. 보다 친숙한 유한 상태 억 셉터는 각 전환의 입력 및 출력 레이블이 동일한 변환기로 표시됩니다. 유한 상태 억 셉터는 문자열 집합 (특히, 정규 또는 합리적인 집합)을 나타내는 데 사용됩니다. 유한 상태 변환기는 문자열 쌍 사이의 이진 관계 (특히, 합리적인 변환)를 나타내는 데 사용됩니다. 가중치는 특정 전환에 소요되는 비용을 나타내는 데 사용할 수 있습니다.
void (* StateController)(void);
void state1(void);
void state2(void);
void main()
{
StateController=&state1;
while(1)
{
(* StateController)();
}
}
void state1(void)
{
//do something in state1
StateController=&state2;
}
void state2(void)
{
//do something in state2
//Keep changing function direction based on state transition
StateController=&state1;
}
개인적으로 포인터 배열과 함께 자기 참조 구조체를 사용합니다. 나는 얼마 전에 github에 대한 튜토리얼을 업로드했다.
https://github.com/mmelchger/polling_state_machine_c
참고 :이 스레드가 상당히 오래되었다는 것을 알고 있지만 상태 머신의 디자인에 대한 의견을 얻고 C에서 가능한 상태 머신 디자인에 대한 예를 제공 할 수 있기를 바랍니다.
다음은 메시지 대기열을 이벤트로 사용하는 Linux 용 Finite State Machine의 예입니다. 이벤트는 큐에 배치되고 순서대로 처리됩니다. 상태는 각 이벤트에 발생하는 상황에 따라 변경됩니다.
다음과 같은 상태의 데이터 연결에 대한 예입니다.
- 초기화되지 않은
- 초기화
- 연결됨
- MTU 협상
- 인증
내가 추가 한 한 가지 작은 추가 기능은 각 메시지 / 이벤트에 대한 타임 스탬프였습니다. 이벤트 핸들러는 너무 오래된 (만료 된) 이벤트를 무시합니다. 이것은 예기치 않은 상태에 빠질 수있는 실제 세계에서 많이 발생할 수 있습니다.
이 예제는 Linux에서 실행되며 아래의 Makefile을 사용하여 컴파일하고 사용하십시오.
state_machine.c
#include <stdio.h>
#include <stdint.h>
#include <assert.h>
#include <unistd.h> // sysconf()
#include <errno.h> // errno
#include <string.h> // strerror()
#include <sys/time.h> // gettimeofday()
#include <fcntl.h> // For O_* constants
#include <sys/stat.h> // For mode constants
#include <mqueue.h>
#include <poll.h>
//------------------------------------------------
// States
//------------------------------------------------
typedef enum
{
ST_UNKNOWN = 0,
ST_UNINIT,
ST_INIT,
ST_CONNECTED,
ST_MTU_NEGOTIATED,
ST_AUTHENTICATED,
ST_ERROR,
ST_DONT_CHANGE,
ST_TERM,
} fsmState_t;
//------------------------------------------------
// Events
//------------------------------------------------
typedef enum
{
EV_UNKNOWN = 0,
EV_INIT_SUCCESS,
EV_INIT_FAIL,
EV_MASTER_CMD_MSG,
EV_CONNECT_SUCCESS,
EV_CONNECT_FAIL,
EV_MTU_SUCCESS,
EV_MTU_FAIL,
EV_AUTH_SUCCESS,
EV_AUTH_FAIL,
EV_TX_SUCCESS,
EV_TX_FAIL,
EV_DISCONNECTED,
EV_DISCON_FAILED,
EV_LAST_ENTRY,
} fsmEvName_t;
typedef struct fsmEvent_type
{
fsmEvName_t name;
struct timeval genTime; // Time the event was generated.
// This allows us to see how old the event is.
} fsmEvent_t;
// Finite State Machine Data Members
typedef struct fsmData_type
{
int connectTries;
int MTUtries;
int authTries;
int txTries;
} fsmData_t;
// Each row of the state table
typedef struct stateTable_type {
fsmState_t st; // Current state
fsmEvName_t evName; // Got this event
int (*conditionfn)(void *); // If this condition func returns TRUE
fsmState_t nextState; // Change to this state and
void (*fn)(void *); // Run this function
} stateTable_t;
// Finite State Machine state structure
typedef struct fsm_type
{
const stateTable_t *pStateTable; // Pointer to state table
int numStates; // Number of entries in the table
fsmState_t currentState; // Current state
fsmEvent_t currentEvent; // Current event
fsmData_t *fsmData; // Pointer to the data attributes
mqd_t mqdes; // Message Queue descriptor
mqd_t master_cmd_mqdes; // Master command message queue
} fsm_t;
// Wildcard events and wildcard state
#define EV_ANY -1
#define ST_ANY -1
#define TRUE (1)
#define FALSE (0)
// Maximum priority for message queues (see "man mq_overview")
#define FSM_PRIO (sysconf(_SC_MQ_PRIO_MAX) - 1)
static void addev (fsm_t *fsm, fsmEvName_t ev);
static void doNothing (void *fsm) {addev(fsm, EV_MASTER_CMD_MSG);}
static void doInit (void *fsm) {addev(fsm, EV_INIT_SUCCESS);}
static void doConnect (void *fsm) {addev(fsm, EV_CONNECT_SUCCESS);}
static void doMTU (void *fsm) {addev(fsm, EV_MTU_SUCCESS);}
static void reportFailConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doAuth (void *fsm) {addev(fsm, EV_AUTH_SUCCESS);}
static void reportDisConnect (void *fsm) {addev(fsm, EV_ANY);}
static void doDisconnect (void *fsm) {addev(fsm, EV_ANY);}
static void doTransaction (void *fsm) {addev(fsm, EV_TX_FAIL);}
static void fsmError (void *fsm) {addev(fsm, EV_ANY);}
static int currentlyLessThanMaxConnectTries (void *fsm) {
fsm_t *l = (fsm_t *)fsm;
return (l->fsmData->connectTries < 5 ? TRUE : FALSE);
}
static int isMoreThanMaxConnectTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxMTUtries (void *fsm) {return TRUE;}
static int isMoreThanMaxMTUtries (void *fsm) {return TRUE;}
static int currentyLessThanMaxAuthTries (void *fsm) {return TRUE;}
static int isMoreThanMaxAuthTries (void *fsm) {return TRUE;}
static int currentlyLessThanMaxTXtries (void *fsm) {return FALSE;}
static int isMoreThanMaxTXtries (void *fsm) {return TRUE;}
static int didNotSelfDisconnect (void *fsm) {return TRUE;}
static int waitForEvent (fsm_t *fsm);
static void runEvent (fsm_t *fsm);
static void runStateMachine(fsm_t *fsm);
static int newEventIsValid(fsmEvent_t *event);
static void getTime(struct timeval *time);
void printState(fsmState_t st);
void printEvent(fsmEvName_t ev);
// Global State Table
const stateTable_t GST[] = {
// Current state Got this event If this condition func returns TRUE Change to this state and Run this function
{ ST_UNINIT, EV_INIT_SUCCESS, NULL, ST_INIT, &doNothing },
{ ST_UNINIT, EV_INIT_FAIL, NULL, ST_UNINIT, &doInit },
{ ST_INIT, EV_MASTER_CMD_MSG, NULL, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_SUCCESS, NULL, ST_CONNECTED, &doMTU },
{ ST_INIT, EV_CONNECT_FAIL, ¤tlyLessThanMaxConnectTries, ST_INIT, &doConnect },
{ ST_INIT, EV_CONNECT_FAIL, &isMoreThanMaxConnectTries, ST_INIT, &reportFailConnect },
{ ST_CONNECTED, EV_MTU_SUCCESS, NULL, ST_MTU_NEGOTIATED, &doAuth },
{ ST_CONNECTED, EV_MTU_FAIL, ¤tlyLessThanMaxMTUtries, ST_CONNECTED, &doMTU },
{ ST_CONNECTED, EV_MTU_FAIL, &isMoreThanMaxMTUtries, ST_CONNECTED, &doDisconnect },
{ ST_CONNECTED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_MTU_NEGOTIATED, EV_AUTH_SUCCESS, NULL, ST_AUTHENTICATED, &doTransaction },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, ¤tyLessThanMaxAuthTries, ST_MTU_NEGOTIATED, &doAuth },
{ ST_MTU_NEGOTIATED, EV_AUTH_FAIL, &isMoreThanMaxAuthTries, ST_MTU_NEGOTIATED, &doDisconnect },
{ ST_MTU_NEGOTIATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_AUTHENTICATED, EV_TX_SUCCESS, NULL, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_TX_FAIL, ¤tlyLessThanMaxTXtries, ST_AUTHENTICATED, &doTransaction },
{ ST_AUTHENTICATED, EV_TX_FAIL, &isMoreThanMaxTXtries, ST_AUTHENTICATED, &doDisconnect },
{ ST_AUTHENTICATED, EV_DISCONNECTED, &didNotSelfDisconnect, ST_INIT, &reportDisConnect },
{ ST_ANY, EV_DISCON_FAILED, NULL, ST_DONT_CHANGE, &doDisconnect },
{ ST_ANY, EV_ANY, NULL, ST_UNINIT, &fsmError } // Wildcard state for errors
};
#define GST_COUNT (sizeof(GST)/sizeof(stateTable_t))
int main()
{
int ret = 0;
fsmData_t dataAttr;
dataAttr.connectTries = 0;
dataAttr.MTUtries = 0;
dataAttr.authTries = 0;
dataAttr.txTries = 0;
fsm_t lfsm;
memset(&lfsm, 0, sizeof(fsm_t));
lfsm.pStateTable = GST;
lfsm.numStates = GST_COUNT;
lfsm.currentState = ST_UNINIT;
lfsm.currentEvent.name = EV_ANY;
lfsm.fsmData = &dataAttr;
struct mq_attr attr;
attr.mq_maxmsg = 30;
attr.mq_msgsize = sizeof(fsmEvent_t);
// Dev info
//printf("Size of fsmEvent_t [%ld]\n", sizeof(fsmEvent_t));
ret = mq_unlink("/abcmq");
if (ret == -1) {
fprintf(stderr, "Error on mq_unlink(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
}
lfsm.mqdes = mq_open("/abcmq", O_CREAT | O_RDWR, S_IWUSR | S_IRUSR, &attr);
if (lfsm.mqdes == (mqd_t)-1) {
fprintf(stderr, "Error on mq_open(), errno[%d] strerror[%s]\n",
errno, strerror(errno));
return -1;
}
doInit(&lfsm); // This will generate the first event
runStateMachine(&lfsm);
return 0;
}
static void runStateMachine(fsm_t *fsm)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
// Cycle through the state machine
while (fsm->currentState != ST_TERM) {
printf("current state [");
printState(fsm->currentState);
printf("]\n");
ret = waitForEvent(fsm);
if (ret == 0) {
printf("got event [");
printEvent(fsm->currentEvent.name);
printf("]\n");
runEvent(fsm);
}
sleep(2);
}
}
static int waitForEvent(fsm_t *fsm)
{
//const int numFds = 2;
const int numFds = 1;
struct pollfd fds[numFds];
int timeout_msecs = -1; // -1 is forever
int ret = 0;
int i = 0;
ssize_t num = 0;
fsmEvent_t newEv;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return -1;
}
fsm->currentEvent.name = EV_ANY;
fds[0].fd = fsm->mqdes;
fds[0].events = POLLIN;
//fds[1].fd = fsm->master_cmd_mqdes;
//fds[1].events = POLLIN;
ret = poll(fds, numFds, timeout_msecs);
if (ret > 0) {
// An event on one of the fds has occurred
for (i = 0; i < numFds; i++) {
if (fds[i].revents & POLLIN) {
// Data may be read on device number i
num = mq_receive(fds[i].fd, (void *)(&newEv),
sizeof(fsmEvent_t), NULL);
if (num == -1) {
fprintf(stderr, "Error on mq_receive(), errno[%d] "
"strerror[%s]\n", errno, strerror(errno));
return -1;
}
if (newEventIsValid(&newEv)) {
fsm->currentEvent = newEv;
} else {
return -1;
}
}
}
} else {
fprintf(stderr, "Error on poll(), ret[%d] errno[%d] strerror[%s]\n",
ret, errno, strerror(errno));
return -1;
}
return 0;
}
static int newEventIsValid(fsmEvent_t *event)
{
if (event == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return FALSE;
}
printf("[%s]\n", __func__);
struct timeval now;
getTime(&now);
if ( (event->name < EV_LAST_ENTRY) &&
((now.tv_sec - event->genTime.tv_sec) < (60*5))
)
{
return TRUE;
} else {
return FALSE;
}
}
//------------------------------------------------
// Performs event handling on the FSM (finite state machine).
// Make sure there is a wildcard state at the end of
// your table, otherwise; the event will be ignored.
//------------------------------------------------
static void runEvent(fsm_t *fsm)
{
int i;
int condRet = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
// Find a relevant entry for this state and event
for (i = 0; i < fsm->numStates; i++) {
// Look in the table for our current state or ST_ANY
if ( (fsm->pStateTable[i].st == fsm->currentState) ||
(fsm->pStateTable[i].st == ST_ANY)
)
{
// Is this the event we are looking for?
if ( (fsm->pStateTable[i].evName == fsm->currentEvent.name) ||
(fsm->pStateTable[i].evName == EV_ANY)
)
{
if (fsm->pStateTable[i].conditionfn != NULL) {
condRet = fsm->pStateTable[i].conditionfn(fsm->fsmData);
}
// See if there is a condition associated
// or we are not looking for any condition
//
if ( (condRet != 0) || (fsm->pStateTable[i].conditionfn == NULL))
{
// Set the next state (if applicable)
if (fsm->pStateTable[i].nextState != ST_DONT_CHANGE) {
fsm->currentState = fsm->pStateTable[i].nextState;
printf("new state [");
printState(fsm->currentState);
printf("]\n");
}
// Call the state callback function
fsm->pStateTable[i].fn(fsm);
break;
}
}
}
}
}
//------------------------------------------------
// EVENT HANDLERS
//------------------------------------------------
static void getTime(struct timeval *time)
{
if (time == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s]\n", __func__);
int ret = gettimeofday(time, NULL);
if (ret != 0) {
fprintf(stderr, "gettimeofday() failed: errno [%d], strerror [%s]\n",
errno, strerror(errno));
memset(time, 0, sizeof(struct timeval));
}
}
static void addev (fsm_t *fsm, fsmEvName_t ev)
{
int ret = 0;
if (fsm == NULL) {
fprintf(stderr, "[%s] NULL argument\n", __func__);
return;
}
printf("[%s] ev[%d]\n", __func__, ev);
if (ev == EV_ANY) {
// Don't generate a new event, just return...
return;
}
fsmEvent_t newev;
getTime(&(newev.genTime));
newev.name = ev;
ret = mq_send(fsm->mqdes, (void *)(&newev), sizeof(fsmEvent_t), FSM_PRIO);
if (ret == -1) {
fprintf(stderr, "[%s] mq_send() failed: errno [%d], strerror [%s]\n",
__func__, errno, strerror(errno));
}
}
//------------------------------------------------
// end EVENT HANDLERS
//------------------------------------------------
void printState(fsmState_t st)
{
switch(st) {
case ST_UNKNOWN:
printf("ST_UNKNOWN");
break;
case ST_UNINIT:
printf("ST_UNINIT");
break;
case ST_INIT:
printf("ST_INIT");
break;
case ST_CONNECTED:
printf("ST_CONNECTED");
break;
case ST_MTU_NEGOTIATED:
printf("ST_MTU_NEGOTIATED");
break;
case ST_AUTHENTICATED:
printf("ST_AUTHENTICATED");
break;
case ST_ERROR:
printf("ST_ERROR");
break;
case ST_TERM:
printf("ST_TERM");
break;
default:
printf("unknown state");
break;
}
}
void printEvent(fsmEvName_t ev)
{
switch (ev) {
case EV_UNKNOWN:
printf("EV_UNKNOWN");
break;
case EV_INIT_SUCCESS:
printf("EV_INIT_SUCCESS");
break;
case EV_INIT_FAIL:
printf("EV_INIT_FAIL");
break;
case EV_MASTER_CMD_MSG:
printf("EV_MASTER_CMD_MSG");
break;
case EV_CONNECT_SUCCESS:
printf("EV_CONNECT_SUCCESS");
break;
case EV_CONNECT_FAIL:
printf("EV_CONNECT_FAIL");
break;
case EV_MTU_SUCCESS:
printf("EV_MTU_SUCCESS");
break;
case EV_MTU_FAIL:
printf("EV_MTU_FAIL");
break;
case EV_AUTH_SUCCESS:
printf("EV_AUTH_SUCCESS");
break;
case EV_AUTH_FAIL:
printf("EV_AUTH_FAIL");
break;
case EV_TX_SUCCESS:
printf("EV_TX_SUCCESS");
break;
case EV_TX_FAIL:
printf("EV_TX_FAIL");
break;
case EV_DISCONNECTED:
printf("EV_DISCONNECTED");
break;
case EV_LAST_ENTRY:
printf("EV_LAST_ENTRY");
break;
default:
printf("unknown event");
break;
}
}
Makefile
CXX = gcc
COMPFLAGS = -c -Wall -g
state_machine: state_machine.o
$(CXX) -lrt state_machine.o -o state_machine
state_machine.o: state_machine.c
$(CXX) $(COMPFLAGS) state_machine.c
clean:
rm state_machine state_machine.o
참고 URL : https://stackoverflow.com/questions/1647631/c-state-machine-design
'development' 카테고리의 다른 글
| C #에서 개체가 null인지 확인 (0) | 2020.05.12 |
|---|---|
| PowerShell에서 사용자 입력을위한 프롬프트 (0) | 2020.05.12 |
| 알림 클릭에서 활동으로 매개 변수를 보내는 방법은 무엇입니까? (0) | 2020.05.12 |
| 코드 숨김 [중복]에서 ASP.Net 페이지의 URL 가져 오기 (0) | 2020.05.12 |
| 스크롤바가 웹 페이지를 재배치하지 못하게하는 방법은 무엇입니까? (0) | 2020.05.12 |