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

巫山老妖

发布于 2023-09-24 20:14:23

7200

发布于 2023-09-24 20:14:23

文章被收录于专栏：小巫技术博客小巫技术博客

文章思维导图

什么是有限状态机？

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

最简单的例子：开关灯，通过flick的动作来实现灯的开和关两种状态转移。以下是状态转移图（状态机的基本描述方式）：

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

entry：进入操作
do：当前状态执行操作
exit：退出操作

这是最简单的例子，实际上有限状态机有三个特征需要去理解，如果满足以下三个特征基本可以通过有限状态机来解决相应的业务问题：

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

举例：使用有限状态机实现一个下载器

下载器存在很多状态，而这些状态是有限的，并且每一次只处于一个状态中，状态之间的迁移需要在特定条件才会发生，所以它是满足有限状态机的三个特征的，我们可以考虑通过有限状态机来实现一个高质量下载器。基于前面学习到的状态机描述方式（状态转移图），分析下载器的状态转移可以画出以下状态转移图：

为什么是这些状态，我们可以考虑以下下载场景：

初始未开始下载时，下载任务的初始状态应该处于待开始状态
用户发起下载动作，下载状态从待开始转移至已开始状态，这个时候会往数据库插入一条记录
接着执行网络请求动作，下载状态从已开始转移至下载中状态，并且在循环写入文件的同时更新下载进度
如果下载过程中出现异常（比如I/O异常，网络异常等），这个时候会从下载中转移至下载失败状态
主动或者被动触发暂停动作，下载中转移至已暂停状态，如未恢复，状态转移结束
如果文件写入成功，则会从下载中转移至下载成功状态，最后状态结束

以上就是针对下载的场景去分析如果通过有限状态机来梳理下载状态的转换，可以看到通过状态转移图可以很清晰的了解状态之间的关系，可以更好的指导我们去写代码，也能提高团队协作的沟通效率。

有限状态机的实现方式

一般来说，状态机有以下几种实现方式：

实现方式	适用场景	优点	缺点
分支逻辑法	适用于条件简单，状态固定，没有新增和扩展的需求	状态机代码直译，简单直接，状态逻辑比较集中，容易查看	对于较复杂的状态机，这种方式容易遗漏或者写错。大量的if-else和switch-case代码分支判断逻辑，可读性和可扩展性比较差，对新增和修改的场景容易引入bug
查表法	通过二维数组来表达状态机，适用于复杂状态机，执行动作比较固定和简单的场景，比如游戏这种状态比较多的场景就适合用查表法	相对于分支逻辑的实现方式，查表法的代码实现更加清晰，可读性和可维护性更好	遇到比较复杂的动作，就无法通过简单的二维数组表示了，有一定的局限性
状态模式	状态模式通过将事件触发的状态转移和动作执行，拆分到不同的状态类中，来避免分支判断逻辑	代码结构更清晰，可以规避过多的分支逻辑判断，代码可维护性更高	状态模式会引入很多状态类，如果状态颗粒度控制不好，会导致状态类爆炸问题；另外逻辑比较分散，集中在状态类中，无法在一个地方整体看出整个状态机的逻辑

逐个解释一下这三种实现方式：

分支逻辑法

分支逻辑法比较简单，就是在代码中通过if-else或者switch-case来直译状态机，来看看我们的下载器目前是怎么判断状态的：

因为目前下载器的状态比较少，通过这种判断条件是可以接受的，如果有比较多的状态条件判断，后续代码就不易于维护和扩展了。这里提一句，分支判断虽然简单，但不太好写单元测试，因为你需要针对每个判断条件去写状态转移触发代码才能保证覆盖率。后面的状态模式通过继承和多态的方式来实现，一个是可以减少重复，第二个可以更明确状态的输入和输出，单元测试也会变得好写。

查表法

这里的查表法，其实是通过一个二维数组来表示的，举个马里奥游戏的例子，它的状态转移图如下所示：

注：图引用自：https://blog.csdn.net/wangyubin2010n/article/details/118002733

二维表表示

	吃蘑菇	碰到怪物	攻击
Small Mario	Mario Super Mario/+1000	Dead/-	-/-
Super Mario	Fire Mario/+1000	Small Mario/-	-/-
Fire Mario	-/+1000	Small Mario/-	-/发射火球
Dead Mario	-/-	-/-	-/-

注：-/-表示不存在这种状态转移

具体代码如下：

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给了我们很好的参考：