Linux プログラミングにおける有限状態マシン FSM の理解と実装

Finite State Machine (略して FSM) は、限られた数の状態と、それらの状態間の遷移や動作などの動作から構成される数学的モデルを指し、コンピュータ分野で広く使用されています。 FSM は、プログラムの処理ロジックを論理ユニット内に実装するために使用される効率的なプログラミング手法であり、特にサーバー プログラミングでは、さまざまな状態やメッセージの種類に基づいて対応する処理を実行することで、プログラムのロジックをより明確かつ理解しやすくすることができます。 . .

それでは、有限状態マシンは通常どこで使用されるのでしょうか?

プログラミング言語や自然言語を処理するトークナイザー(トークナイザー)に適用でき、ボトムアップの文法パーサー(パーサー)による文法解析と分析を実装できます。さまざまな通信プロトコルにおいて、送信者と受信者はメッセージを処理します。それらの間でのデータの受け渡し、ゲーム内の人工知能など。

有限状態マシンの実装には、一般的に以下のような方法がありますが、それぞれのメリット・デメリットを順に紹介していきます。

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 中国語 Web サイトの他の関連記事を参照してください。