关于有限状态机(FSM)的一些思考

文章思想导图

什么是有限状况机？

有限状况机，英文翻译是 Finite State Machine，缩写为 FSM，简称为状况机。状况机有 3 个组成部分：状况（State）、事情（Event）、动作（Action）。其间，事情也称为搬运条件（Transition Condition）。事情触发状况的搬运及动作的履行。动作也不是有必要的，也可能只搬运状况，不履行任何动作。

最简略的比方：开关灯，经过flick的动作来完成灯的开和关两种状况搬运。以下是状况搬运图（状况机的根本描绘办法）：

每个状况有以下几个操作：

• entry：进入操作
• do：当时状况履行操作
• exit：退出操作

这是最简略的比方，实际上有限状况机有三个特征需求去了解，假如满意以下三个特征根本能够经过有限状况机来处理相应的事务问题：

• 有限的状况和事情
• 任何时刻只处于一个状况
• 特定条件下会进行状况迁移

举例：运用有限状况机完成一个下载器

下载器存在许多状况，而这些状况是有限的，并且每一次只处于一个状况中，状况之间的迁移需求在特定条件才会发生，所以它是满意有限状况机的三个特征的，咱们能够考虑经过有限状况机来完成一个高质量下载器。基于前面学习到的状况机描绘办法（状况搬运图），剖析下载器的状况搬运能够画出以下状况搬运图：

为什么是这些状况，咱们能够考虑以下下载场景：

• 初始未开端下载时，下载使命的初始状况应该处于待开端状况
• 用户建议下载动作，下载状况从待开端搬运至已开端状况，这个时分会往数据库插入一条记录
• 接着履行网络请求动作，下载状况从已开端搬运至下载中状况，并且在循环写入文件的同时更新下载进度
• 假如下载过程中出现反常（比方I/O反常，网络反常等），这个时分会从下载中搬运至下载失利状况
• 主动或许被动触发暂停动作，下载中搬运至已暂停状况，如未康复，状况搬运结束
• 假如文件写入成功，则会从下载中搬运至下载成功状况，最终状况结束

以上便是针对下载的场景去剖析假如经过有限状况机来梳理下载状况的转换，能够看到经过状况搬运图能够很明晰的了解状况之间的关系，能够更好的辅导咱们去写代码，也能进步团队协作的沟通效率。

有限状况机的完成办法

一般来说，状况机有以下几种完成办法：

逐个解释一下这三种完成办法：

分支逻辑法

分支逻辑法比较简略，便是在代码中经过if-else或许switch-case来直译状况机，来看看咱们的下载器现在是怎么判别状况的：

因为现在下载器的状况比较少，经过这种判别条件是能够接受的，假如有比较多的状况条件判别，后续代码就不易于保护和扩展了。这儿提一句，分支判别尽管简略，但不太好写单元测试，因为你需求针对每个判别条件去写状况搬运触发代码才能保证覆盖率。后面的状况形式经过继承和多态的办法来完成，一个是能够削减重复，第二个能够更明确状况的输入和输出，单元测试也会变得好写。

查表法

这儿的查表法，其实是经过一个二维数组来表明的，举个马里奥游戏的比方，它的状况搬运图如下所示：

注：图引用自：blog.csdn.net/wangyubin20…

二维表表明

注：-/-表明不存在这种状况搬运

详细代码如下：

public enum Event {
    GOT_MUSHROOM(0),
    GOT_CAPE(1),
    GOT_FIRE(2),
    MET_MONSTER(3);
    private int value;
    private Event(int value) {
        this.value = value;
    }
    public int getValue() {
        return this.value;
    }
}
public class MarioStateMachine {
    private int score;
    private State currentState;
    private static final State[][] transitionTable = {
        {SUPER, CAPE, FIRE, SMALL},
        {SUPER, CAPE, FIRE, SMALL},
        {CAPE, CAPE, CAPE, SMALL},
        {FIRE, FIRE, FIRE, SMALL}
    };
    private static final int[][] actionTable = {
        {+100, +200, +300, +0},
        {+0, +200, +300, -100},
        {+0, +0, +0, -200},
        {+0, +0, +0, -300}
    };
    public MarioStateMachine() {
        this.score = 0;
        this.currentState = State.SMALL;
    }
    public void obtainMushRoom() {
        executeEvent(Event.GOT_MUSHROOM);
    }
    public void obtainCape() {
        executeEvent(Event.GOT_CAPE);
    }
    public void obtainFireFlower() {
        executeEvent(Event.GOT_FIRE);
    }
    public void meetMonster() {
        executeEvent(Event.MET_MONSTER);
    }
    private void executeEvent(Event event) {
        int stateValue = currentState.getValue();
        int eventValue = event.getValue();
        this.currentState = transitionTable[stateValue][eventValue];
        this.score += actionTable[stateValue][eventValue];
    }
    public int getScore() {
        return this.score;
    }
    public State getCurrentState() {
        return this.currentState;
    }
}

这儿重视代码中的transitionTable和actionTable两个二维数组，分别是当时状况和要履行的动作，假如后续需求修正和新增状况只需求调整二维数组即可。

状况形式

状况形式界说：允许目标在内部状况改变时改变它的行为，目标看起来好像修正了它的类。

这个界说不太好了解，简略的来说便是封装基于状况的行为，并将行为委托到当时状况。

对应类结构图如下：

从类图能够看出咱们经过完成一个状况接口类，每一个详细状况经过完成接口的办法细节来完成状况搬运。

运用状况形式来重构代码有以下好处：

• 将每个状况的行为局部化到它自己的类中
• 将简略发生的if-else语句删去，以方便日后的保护
• 让每一个状况”对修正封闭“，让状况”对扩展开放“

但这儿还存在一个问题，经过接口来完成子类，会导致某个状况类并不需求支持其间的某个或许某些事情，但也要完成所有的事情函数，这儿能够将状况接口调整为抽象类，子类只需求完成自己需求的事情即可。

怎么处理传统有限状况机「状况爆破」问题

尽管状况形式能够很好的优化许多的if-else的逻辑分支，但假如面对State类许多的状况，完成状况切换将会变得十分痛苦。这个时分就需求引进层次状况机 （HSM: Hierarchical State Machine） ，各个状况经过树型层次组织起来，状况图是层次结构的，也便是说每个状况能够拥有子状况。简略来说，便是FSM当状况太多的时分，欠好保护，于是将状况分类，抽离出来，将同类型的状况做为一个状况机，然后再做一个大的状况机，来保护这些子状况机。

这儿Android Framework中的StateMachine给了咱们很好的参阅：

核心要害点有：

• 初始化是经过HandlerThread保护一个音讯队列
• 保护了一个状况树，经过StateInfo类对State进行封装，并记录State之间的父子关系
• SmHandle是音讯处理派发和状况控制切换的核心，运行在独自的线程上

层次状况机处理音讯示意图：

详细的源码剖析可参阅：segmentfault.com/a/119000002…

有限状况机不是「银弹」

前面都在说状况机的长处，那它有什么缺陷？

• 学习本钱，需求团队内成员相同了解什么是状况机，有一定的学习曲线
• 保护本钱，除非状况机是自己写的，其他成员假如想全盘了解会比较困难
• 状况粒度比较难掌握，假如颗粒度太小就会让状况保护变得十分困难，比方运用状况形式会发生许多状况类，导致类爆破
• 状况机速度慢，因为组合逻辑会弄出许多bit的next_state.即便选用one-hot编码，也改变不了多少。许多高速流水的景象，都不适合状况机。

有限状况机的一些展望

• 成为团队内不管是技能还是产品都能够经过状况搬运图来梳理事务的有利工具
• 能够运用有限状况机重构UI，下降事务杂乱度
• 协助团队写出易懂更好保护的代码，提高代码可测试性
• 运用图遍历算法（DFS/BFS），主动生成测试用例
• 行为上报和录制重放
• 依据代码生成状况搬运图完成可视化，参阅xstate

弥补资料：状况机代码可视化

咱们能够考虑一个问题，现在咱们完成状况机的思路，根本是先画状况搬运图，然后再依据状况搬运图去完成代码。这儿可能带来一个问题是，咱们既要保护状况搬运图，也要保护代码，那咱们有没有办法完成状况机代码可视化，协助咱们处理状况机保护的问题。参阅XState，咱们找到了一些思路：

状况机代码

生成的可视化状况机搬运图

参阅资料

• 维基百科：有限状况机
• statecharts.dev/
• 开端运用状况机来编写你的代码吧！
• 【第2497期】下降前端事务杂乱度新视角：状况机范式
• 详解Android Framework中的State Machine
• 状况形式详解
• 有限状况机FSM和层次状况机HSM
• Android状况机
• xstate.js.org/docs/