Linux 프로그래밍에서 유한 상태 기계 FSM의 이해 및 구현

FSM(Finite State Machine)은 제한된 수의 상태와 이러한 상태 간의 전환 및 동작과 같은 동작으로 구성된 수학적 모델을 말하며 컴퓨터 분야에서 널리 사용되었습니다. FSM은 프로그램의 처리 로직을 논리 단위 내에서 구현하는 데 사용되는 효율적인 프로그래밍 방법입니다. 특히 서버 프로그래밍에서는 다양한 상태나 메시지 유형에 따라 해당 처리를 수행함으로써 프로그램의 로직을 보다 명확하고 이해하기 쉽게 만들 수 있습니다. .

그렇다면 유한 상태 기계는 주로 어디에 사용되나요?

프로그래밍 언어나 자연어를 처리하는 토크나이저(tokenizer)에 적용할 수 있으며, 상향식 문법 파서(parser)를 통해 문법 파싱 및 분석을 구현하는 등 다양한 통신 프로토콜에서 송신자와 수신자 간 메시지를 처리합니다. 데이터 전달, 게임 내 인공 지능 등.

Finite State Machine의 구현에는 일반적으로 다음과 같은 방법이 있는데, 그 장점과 단점을 하나씩 소개하겠습니다.

1. if/else if 문을 사용하여 구현된 유한 상태 기계

if/else if 문을 사용하여 유한 상태 기계를 구현하는 것이 가장 간단하고 이해하기 쉬운 방법입니다. 다수의 if/else if 문을 사용하여 현재 상태를 확인하고 해당 논리적 처리를 수행하면 됩니다.

다음은 다양한 상태에 따라 해당 작업을 구현하고 상태 전환을 실현하기 위해 다수의 if/else if 문을 사용하는 간단한 상태 기계 예입니다.

으아악

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

2. 스위치를 사용하여 FSM

을 구현하세요.

switch 문을 사용하여 구현된 FSM의 구조는 더욱 명확해졌고 단점도 분명해졌습니다. 이 설계 방법은 간단하고 많은 판단을 거쳐 처리되지만 소규모 상태 전환 프로세스에는 적합하지만 규모 확장 확장 및 유지 관리.

으아악

3. FSM을 구현하려면 함수 포인터를 사용하세요

FSM 구현을 위해 함수 포인터를 사용하는 아이디어: 해당 상태 테이블과 액션 쿼리 테이블을 설정하고 상태 테이블, 이벤트, 액션 테이블에 따라 해당 액션 처리 함수를 찾은 다음 실행 후 상태를 전환합니다. 완전한.

当然使用函数指针实现的 FSM 的过程还是比较费时费力，但是这一切都是值得的，因为当你的程序规模大时候，基于这种表结构的状态机，维护程序起来也是得心应手。

下面给出一个使用函数指针实现的 FSM 的框架：

我们还是以 “小明的一天” 为例设计出该 FSM。

先给出该 FSM 的状态转移图：

下面讲解关键部分代码实现

首先我们定义出小明一天的活动状态：

//比如我们定义了小明一天的状态如下

enum

{

    GET_UP,

    GO_TO_SCHOOL,

    HAVE_LUNCH,

    DO_HOMEWORK,

    SLEEP,

};

我们也定义出会发生的事件

{

    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
; iif
 (
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 框架，以后进行扩展就很简单了（只要在状态表里加一行来写入新的状态处理就可以了）。

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