유한 상태 기계 FSM의 구현 및 이해

FSM(Finite State Machine)은 유한 상태와 이러한 상태 간의 전환 및 동작과 같은 동작에 대한 수학적 모델을 나타냅니다. 컴퓨터 분야에서 널리 사용됩니다. FSM은 서버 프로그래밍에서 서버가 다양한 상태나 메시지 유형에 따라 해당 처리 논리를 수행할 수 있는 논리 단위 내의 효율적인 프로그래밍 방법으로, 프로그램 논리를 명확하고 이해하기 쉽게 만듭니다.

유한 상태 기계는 일반적으로 어디에 사용되나요?

프로그래밍 언어나 자연어를 처리하는 토크나이저, 문법을 상향식으로 구문 분석하는 파서,
데이터 전송을 위한 다양한 통신 프로토콜 발신자와 수신자, 메시지 처리, 게임 AI 등을 위한 응용 시나리오가 있습니다.

상태 머신에는 여러 가지 구현 방법이 있으며 그 장점과 단점을 하나씩 설명하겠습니다.

1. if/else if 문을 사용하여 FSM 구현

if/else if 문을 사용하는 것은 FSM을 구현하는 가장 간단하고 이해하기 쉬운 방법입니다. 해당하는 논리적 처리를 실행합니다.

아래 예를 보면 간단한 상태 머신을 구현하고 다양한 상태에 따라 해당 작업을 수행하고 상태 점프를 실현하기 위해 많은 수의 if/else if 문을 사용합니다.

//比如我们定义了小明一天的状态如下
enum
{
    GET_UP,
    GO_TO_SCHOOL,
    HAVE_LUNCH,
    GO_HOME,
    DO_HOMEWORK,
    SLEEP,
};


int main()
{
    int state = GET_UP;
    //小明的一天
    while (1)
    {
        if (state == GET_UP)
        {
            GetUp(); //具体调用的函数
            state = GO_TO_SCHOOL;  //状态的转移
        }
        else if (state == GO_TO_SCHOOL)
        {
            Go2School();
            state = HAVE_LUNCH;
        }
        else if (state == HAVE_LUNCH)
        {
            HaveLunch();
        }
        ...
        else if (state == SLEEP)
        {
            Go2Bed();
            state = GET_UP;
        }
    }

    return 0;
}

위의 예를 읽고 어떤 생각이 드시나요? 프로그램이 간단하고 이해하기 쉽지만 if 판단문을 많이 사용하여 코드가 매우 저급화되고 코드가 부풀어 오른다고 생각하십니까? 이 상태 머신에는 상태가 몇 개밖에 없고 코드 확장이 명확하지 않습니다. 그러나 처리해야 할 상태가 수십 개라면 이 상태 머신의 코드를 읽기 어려울 것입니다.

2. switch를 사용하여 FSM 구현

switch 문을 사용하여 구현한 FSM의 구조는 더욱 명확해졌고 단점도 분명해졌습니다. 이 설계 방법은 간단하지만 많은 판단을 거쳐 처리되므로 적합합니다. 소규모 상태 전환 과정을 거치지만, 규모가 커지면 확장 및 유지가 어렵습니다.

int main()
{
    int state = GET_UP;
    //小明的一天
    while (1)
    {

        switch(state)
        {
        case GET_UP:
            GetUp(); //具体调用的函数
            state = GO_TO_SCHOOL;  //状态的转移
            break;
        case GO_TO_SCHOOL:
            Go2School();
            state = HAVE_LUNCH;
            break;
        case HAVE_LUNCH:
            HaveLunch();
            state = GO_HOME;
            break;
            ...
        default:
            break;
        }
    }

    return 0;
}

3. 함수 포인터를 사용하여 FSM 구현

FSM을 구현하기 위해 함수 포인터를 사용하는 아이디어: 해당 상태 테이블과 액션 쿼리 테이블을 설정하고, 상태 테이블, 이벤트 및 Action Table을 작성하고, 실행이 완료된 후 진행합니다. 상태 전환.

물론, FSM을 구현하기 위해 함수 포인터를 사용하는 과정은 여전히 ​​상대적으로 시간이 많이 걸리고 힘들지만 그만한 가치가 있습니다. 프로그램이 대규모인 경우 이 테이블 구조를 기반으로 하는 상태 머신을 사용하면 쉽게 할 수 있기 때문입니다. 프로그램을 유지하기 위해.

다음은 함수 포인터를 사용하여 구현된 FSM의 프레임워크입니다.

우리는 이 FSM을 설계하기 위해 여전히 "Xiao Ming's Day"를 예로 사용합니다.

먼저 FSM의 상태 전이 다이어그램을 제공합니다.

코드 구현의 핵심 부분은 아래에 설명되어 있습니다.

먼저 Xiao Ming의 하루 활동 상태를 정의합니다

//比如我们定义了小明一天的状态如下
enum
{
    GET_UP,
    GO_TO_SCHOOL,
    HAVE_LUNCH,
    DO_HOMEWORK,
    SLEEP,
};

우리는 또한 다음과 같은 이벤트를 정의합니다. 발생

enum
{
    EVENT1 = 1,
    EVENT2,
    EVENT3,
};

정의 상태 테이블의 데이터 구조

typedef struct FsmTable_s
{
    int event;   //事件
    int CurState;  //当前状态
    void (*eventActFun)();  //函数指针
    int NextState;  //下一个状态
}FsmTable_t;

다음으로, 가장 중요한 FSM 상태 테이블은 이 정의된 테이블을 기반으로 전체 FSM이 작동하도록 정의됩니다.

FsmTable_t XiaoMingTable[] =
{
    //{到来的事件，当前的状态，将要要执行的函数，下一个状态}
    { EVENT1,  SLEEP,           GetUp,        GET_UP },
    { EVENT2,  GET_UP,          Go2School,    GO_TO_SCHOOL },
    { EVENT3,  GO_TO_SCHOOL,    HaveLunch,    HAVE_LUNCH },
    { EVENT1,  HAVE_LUNCH,      DoHomework,   DO_HOMEWORK },
    { EVENT2,  DO_HOMEWORK,     Go2Bed,       SLEEP },

    //add your codes here
};

상태 머신의 등록, 상태 전송, 이벤트 처리 작업이 구현됩니다

/*状态机注册*/
void FSM_Regist(FSM_t* pFsm, FsmTable_t* pTable)
{
    pFsm->FsmTable = pTable;
}

/*状态迁移*/
void FSM_StateTransfer(FSM_t* pFsm, int state)
{
    pFsm->curState = state;
}

/*事件处理*/
void FSM_EventHandle(FSM_t* pFsm, int event)
{
    FsmTable_t* pActTable = pFsm->FsmTable;
    void (*eventActFun)() = NULL;  //函数指针初始化为空
    int NextState;
    int CurState = pFsm->curState;
    int flag = 0; //标识是否满足条件
    int i;

    /*获取当前动作函数*/
    for (i = 0; i<g_max_num; i++)
    {
        //当且仅当当前状态下来个指定的事件，我才执行它
        if (event == pActTable[i].event && CurState == pActTable[i].CurState)
        {
            flag = 1;
            eventActFun = pActTable[i].eventActFun;
            NextState = pActTable[i].NextState;
            break;
        }
    }


    if (flag) //如果满足条件了
    {
        /*动作执行*/
        if (eventActFun)
        {
            eventActFun();
        }

        //跳转到下一个状态
        FSM_StateTransfer(pFsm, NextState);
    }
    else
    {
        // do nothing
    }
}

메인 함수를 이렇게 작성하고 상태 머신의 작동을 관찰합니다

int main()
{
    FSM_t fsm;
    InitFsm(&fsm);
    int event = EVENT1; 
    //小明的一天,周而复始的一天又一天，进行着相同的活动
    while (1)
    {
        printf("event %d is coming...\n", event);
        FSM_EventHandle(&fsm, event);
        printf("fsm current state %d\n", fsm.curState);
        test(&event); 
        sleep(1);  //休眠1秒，方便观察
    }

    return 0;
}

상태 전송을 살펴보세요 실행 중인 상태 머신:

위 그림에서 볼 수 있듯이 함수의 실행과 상태의 전송은 지정된 상태에서 지정된 이벤트가 발생할 때만 발생하고, 그렇지 않으면 상태 점프가 발생하지 않습니다. 이 메커니즘은 상태 시스템을 자동으로 지속적으로 실행하여 순서대로 작업을 완료하도록 합니다.

처음 두 가지 방법과 비교하면 함수 포인터를 사용하여 FSM을 구현하는 것은 대규모 전환 프로세스에 잘 사용될 수 있습니다. FSM 프레임워크를 구현하는 한 향후 확장은 매우 간단할 것입니다(상태 테이블에 행을 추가하기만 하면 됩니다). ) 새로운 상태 핸들러를 작성하세요).

FSM의 전체 코드가 필요하면 내 github을 방문하세요

위 내용은 유한 상태 기계 FSM의 구현 및 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!