大型状态机 vs 嵌套状态机

Question

我在一个实时系统中有一个状态机，只有很少的（3个）状态。

typedef enum {
    STATE1,
    STATE2,
    STATE3
} state_t;

然而，这些状态之间的转换需要相当长的时间，并且有它们自己的细分。因此，我有两个选择，要么扩展主状态机以表示所有中间状态：

typedef enum {
    STATE1,
    STATE1_PREPARE_TRANSITION_TO_STATE2,
    STATE1_DO_TRANSITION_TO_STATE2,
    STATE1_PREPARE_TRANSITION_TO_STATE3,
    STATE1_DO_TRANSITION_TO_STATE3,
    STATE2,
    ...
} state_t;

或者我为相关的主状态创建一个嵌套状态机：

typedef enum {
    STATE1_NOT_ACTIVE,
    STATE1_NORMAL,
    STATE1_PREPARE_TRANSITION_TO_STATE2,
    STATE1_DO_TRANSITION_TO_STATE2,
    STATE1_PREPARE_TRANSITION_TO_STATE3,
    STATE1_DO_TRANSITION_TO_STATE3
} sub_state1_t;
...

两种可能性都有其优点和缺点。大的状态机很容易变得混乱和复杂。然而，在第二种情况下保持所有状态的一致性也不是轻松的，许多函数需要关于全局状态和子状态的信息。

我想避免处理几个并行状态的复杂代码，例如：

if ((global_state == STATE1) &&
    (sub_state_1 == STATE1_DO_TRANSITION_TO_STATE2))
{
    ...
    if (transition_xy_done(...))
    {
        global_state = STATE2;
        sub_state_1 = STATE1_NOT_ACTIVE;
        sub_state_2 = STATE2_NORMAL;
    }
}

在处理这样的问题时，一般最好的方法是什么：使用许多小的和嵌套的状态机（其中包含许多无效组合），一个大的状态机还是其他方法？

- groovingandi

---

你考虑过使用状态机生成器吗？ - Hasturkun

有没有生成器工具可以决定一个大状态机还是几个嵌套的状态机更好？ - groovingandi

可能不是必须的，但是使用生成器可以更容易地设计/维护大型状态机。 - Hasturkun

Answer 1

许多小状态机将会为您提供更多代码灵活性，特别是如果您需要重新设计任何内容。然后，您应该（希望能够）在不必更改任何其他嵌套状态机的情况下更改嵌套状态机。

拥有更大的转换表不应导致更长的查找时间，因为我认为您会合理地将表布置在内存中。如果有什么变化，您实际上应该能够从大型机器中获得更快的速度，因为您不需要使用小状态机中可能需要的额外一两个步骤来干净地进行转换。但考虑到这种方法的复杂性，我建议以下操作：首先使用嵌套状态机进行设计，然后一旦一切正常，如有必要，请重构为单个状态机以获得一些速度增益。

- Gordon Seidoh Worley

Answer 2

首先，我要赞扬你认识到发生的事情并明确这些状态（因为它们实际上是模型中的额外状态，而不是真正带有动作的转换）。我经常看到状态机最终变成像你想避免的最后一个例子那样。当你在事件处理程序中测试“额外”状态变量时，这表明你的状态机具有更多的状态，而你实际上已经将其纳入设计中了 - 这些状态应该反映在设计中，而不是通过一堆意大利面式编码检查附加的“状态”编码在全局变量中插入到现有状态的事件处理程序中。

有几个C++框架可以建模分层状态机（HSMs）（这就是你嵌套状态机的想法听起来像），但我知道的唯一支持纯C的框架是Quantum Framework，我认为投入它可能意味着相当程度的承诺（即，它可能不是一个简单的更改）。然而，如果你想探索这种可能性，Samek已经写了很多关于如何在C中支持HSMs的文章（还有一本书）。

然而，如果您不需要HSM模型中的一些更复杂的部分（例如未由“最内层”状态处理的事件被冒泡以便由父状态可能处理，对整个状态层次结构提供完全进入和退出支持），那么支持嵌套状态机就像完全独立的状态机一样容易，只是在进入/退出父状态时开始和停止。

大型状态机模型可能更容易实现（它只是您现有框架中的几个状态）。 如果将这些状态添加到当前状态机模式不会使模型过于复杂，那么建议使用该方法。

换句话说，让最适合您的模型驱动如何在软件中实现状态机。

- Michael Burr

Answer 3

我认为没有一种单一的、通用的方法。正如其他人所说，这取决于你想做什么。

总的来说，我会避免在较大的状态机中嵌套小的状态机，因为当你试图简化事情时，不仅会增加更多的状态 - 因此增加了复杂性 - 而且现在你有两个状态变量要跟踪。

特别是，“内部”状态变量必须在遍历“外部”状态机中的状态时得到适当的初始化。例如，如果由于错误，在外部状态机中存在一个未能重置内部状态机状态变量的转换会怎样呢？

唯一可能的例外是所有内部状态机都执行相同的操作。如果可以通过使用数组等方式对数据进行参数化，则可以有一个内部状态机的单一实现，并且可能可以用计数器或类似物替换外部状态机。

举个简单的例子：

#define MyDataSIZE 10

void UpdateStateMachine(void)
{
    static enum {BeginSTATE, DoStuffSTATE, EndSTATE} State = BeginSTATE;
    static unsigned int Counter = 0;
    static unsigned int MyData[MyDataSIZE];

    switch(State)
    {
        default:
        case BeginSTATE:
            /* Some code */
            if(/* Some condition*/)
                {State = DoStuffSTATE;}
            break;
        case DoStuffSTATE:
            /* Some actions on MyData[Counter] */
            if(/* Some condition*/)
                {State = EndSTATE;}
            break;
        case EndSTATE:
            /* Some code */
            if(/* Some condition*/)
            {
                Counter++;
                if(Counter >= MyDataSIZE)
                    {Counter = 0;}
                State = BeginSTATE;
            } /* if */
            break;
    } /* switch */
} /* UpdateStateMachine() */

- Steve Melnikoff

Answer 4

正如您所提到的，大型状态机会变得混乱，因此很难维护。几个较小的状态机总是更容易理解和维护。

大型状态机的另一个缺点是转换表更大，因此查找时间更长。

- qrdl

Answer 5

为什么不使用状态模式呢？

- Wouter

---

也许我错过了什么，但我认为这与此无关，因为我受限于C语言，并且每个主状态没有类似的子状态。 - groovingandi

抱歉，我没有看到C标签。我以为是C++。 - Wouter

Answer 6

我支持使用更大的状态机，假设单个机器只能处于一个大状态机状态中，那么它应该在那里逻辑上存在。

通过使用一个大型机器，您正在利用环境的特性来防止同时存在两个状态的状态，从而使程序更安全、更易读。

此外，一个大状态机的优点是任何其他程序员都可以通过查看单个位置（即获取整体图像）轻松理解所有状态，而不是查看单个位置，希望了解子分区，然后必须查看每个子分区。

另外，正如您所建议的，使用多个状态机将迫使您发送更多参数，对每个状态执行多个测试等等...

至于未来的期望，我相信YAGNI。

- Liran Orevi