Compréhension et implémentation du FSM de machine à états finis dans la programmation Linux

Finite State Machine (FSM) fait référence à un modèle mathématique composé d'un nombre limité d'états et de comportements tels que des transitions et des actions entre ces états. Il a été largement utilisé dans le domaine informatique. FSM est une méthode de programmation efficace utilisée pour implémenter la logique de traitement d'un programme au sein d'une unité logique. En particulier dans la programmation serveur, en effectuant un traitement correspondant basé sur différents états ou types de messages, la logique du programme peut être rendue plus claire et plus facile à comprendre. .

Alors, où les machines à états finis sont-elles généralement utilisées ?

Il peut être appliqué aux tokenizers (tokenizers) qui traitent les langages de programmation ou les langages naturels, et implémentent l'analyse grammaticale et l'analyse via des analyseurs grammaticaux ascendants (analyseur) dans divers protocoles de communication, entre l'expéditeur et le destinataire. Traitement des messages par). transmission de données, intelligence artificielle dans les jeux, et bien plus encore.

Pour la mise en œuvre de machines à états finis, il existe généralement les méthodes suivantes, je présenterai leurs avantages et inconvénients une par une.

1. Machine à états finis implémentée à l'aide d'instructions if/else if

Utiliser des instructions if/else if pour implémenter des machines à états finis est la méthode la plus simple et la plus facile à comprendre. Utilisez simplement un grand nombre d'instructions if/else if pour déterminer l'état actuel et effectuer le traitement logique correspondant.

Ce qui suit est un exemple simple de machine à états.Nous utilisons un grand nombre d'instructions if/else if pour l'implémenter, effectuons les opérations correspondantes en fonction des différents états et implémentons les transitions d'état.

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
;

}

Après avoir lu les exemples ci-dessus, qu’en pensez-vous ? Pensez-vous que même si le programme est simple et facile à comprendre, il utilise un grand nombre d'instructions de jugement if, ce qui rend le code très bas de gamme et le code est gonflé. Il n'y a que quelques états de cette machine à états, et l'expansion du code n'est pas évidente. Cependant, si nous devons traiter des dizaines d'états, le code de cette machine à états sera difficile à lire.

2. Utilisez switch pour implémenter FSM

La structure du FSM implémentée à l'aide d'instructions switch est devenue plus claire et ses défauts sont également évidents : bien que cette méthode de conception soit simple et traitée par de nombreux jugements, elle convient aux processus de commutation d'état à petite échelle, mais il est difficile de élargir l'échelle Expansion et maintenance.

   
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. Utilisez des pointeurs de fonction pour implémenter FSM

L'idée d'utiliser des pointeurs de fonction pour implémenter FSM : établir la table d'état et la table de requête d'action correspondantes, localiser la fonction de traitement d'action correspondante en fonction de la table d'état, de l'événement et de la table d'action, puis changer d'état après l'exécution. complété.

当然使用函数指针实现的 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 框架，以后进行扩展就很简单了（只要在状态表里加一行来写入新的状态处理就可以了）。

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!