Memahami dan Pelaksanaan FSM Mesin Keadaan Terhad dalam Pengaturcaraan Linux

Finite State Machine (FSM) merujuk kepada model matematik yang terdiri daripada bilangan keadaan dan tingkah laku yang terhad seperti peralihan dan tindakan antara keadaan ini. Ia telah digunakan secara meluas dalam bidang komputer. FSM ialah kaedah pengaturcaraan yang cekap yang digunakan untuk melaksanakan logik pemprosesan program dalam unit logik Terutamanya dalam pengaturcaraan pelayan, dengan melakukan pemprosesan yang sepadan berdasarkan keadaan atau jenis mesej yang berbeza, logik program boleh dibuat dengan lebih jelas dan lebih mudah difahami. .

Jadi, di manakah mesin keadaan terhingga biasanya digunakan?

Ia boleh digunakan untuk tokenizer (tokenizer) yang memproses bahasa pengaturcaraan atau bahasa semula jadi, dan melaksanakan penghuraian tatabahasa dan analisis melalui penghurai tatabahasa (parser) dalam pelbagai protokol komunikasi, antara pengirim dan penerima Memproses mesej oleh menghantar data, dalam kecerdasan buatan permainan dan banyak lagi.

Untuk pelaksanaan mesin keadaan terhingga, secara amnya terdapat kaedah berikut saya akan perkenalkan kelebihan dan kekurangannya satu persatu.

1. Mesin keadaan terhingga dilaksanakan menggunakan pernyataan if/else if

Menggunakan pernyataan if/else if untuk melaksanakan mesin keadaan terhingga adalah kaedah yang paling mudah dan paling mudah difahami. Hanya gunakan sejumlah besar pernyataan if/else if untuk menentukan status semasa dan melaksanakan pemprosesan logik yang sepadan.

Berikut ialah contoh mesin keadaan mudah Kami menggunakan sejumlah besar pernyataan if/else if untuk melaksanakannya, melaksanakan operasi yang sepadan mengikut keadaan berbeza dan melaksanakan peralihan keadaan.

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
;

}

Setelah membaca contoh di atas, apakah pendapat anda? Adakah anda merasakan bahawa walaupun atur cara ini ringkas dan mudah difahami, ia menggunakan sejumlah besar pernyataan penghakiman if, yang menjadikan kod ini sangat rendah dan kodnya menjadi kembung. Terdapat hanya beberapa keadaan mesin keadaan ini, dan pengembangan kod tidak jelas Namun, jika terdapat berpuluh-puluh negeri yang perlu kita proses, kod mesin keadaan ini akan sukar dibaca.

2. Gunakan suis untuk melaksanakan FSM

Struktur FSM yang dilaksanakan menggunakan pernyataan suis telah menjadi lebih jelas, dan kelemahannya juga jelas: walaupun kaedah reka bentuk ini mudah dan diproses melalui banyak pertimbangan, ia sesuai untuk proses penukaran keadaan berskala kecil, tetapi sukar untuk kembangkan jika skala diperluaskan.

   
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. Gunakan penunjuk fungsi untuk melaksanakan FSM

Idea untuk menggunakan penunjuk fungsi untuk melaksanakan FSM: wujudkan jadual keadaan dan jadual pertanyaan tindakan yang sepadan, cari fungsi pemprosesan tindakan yang sepadan mengikut jadual keadaan, acara dan jadual tindakan, dan kemudian tukar keadaan selepas pelaksanaan dijalankan selesai.

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

Atas ialah kandungan terperinci Memahami dan Pelaksanaan FSM Mesin Keadaan Terhad dalam Pengaturcaraan Linux. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!