从零开始的状态机漫谈（4）——多实例

【说在前面的话】

在前面的讲解中，我们介绍了如何使用状态图的方式来设计有限状态机、明确了状态图设计的“清晰”原则，并结合最简单和常用的switch状态机翻译模式详细说明了状态图的“无脑翻译”方法。

比如下面这个状态图就是一个典型：

通过图示，我们能清晰的看出该状态机实现的是“通用字符串输出”的功能。其实，这里我算是埋下了一个小小的“彩蛋”——当然，它的真实身份是一个陷阱。如果你已经熟悉了我前面介绍的翻译规则，很容易就会发现这里存在的巨大问题：是的，这个状态图按照switch翻译法无脑翻译的后果，将是一个根本无法正常工作的状态机：

#include <stdint.h>
#include <stdbool.h>

typedef enum {
    fsm_rt_err          = -1,
    fsm_rt_on_going     = 0,
    fsm_rt_cpl          = 1,
} fsm_rt_t;

extern bool serial_out(uint8_t chByte);

#define PRINT_STR_RESET_FSM()               \
        do { s_tState = START; } while(0)

fsm_rt_t print_str(const char *pchStr)
{
    static enum {
        START = 0,
        IS_END_OF_STRING,
        SEND_CHAR,
    } s_tState = START;

    switch (s_tState) {
        case START:
            s_tState = IS_END_OF_STRING;
            break;   
        case IS_END_OF_STRING:
            if (*pchStr == '\0') {
                PRINT_STR_RESET_FSM();
                return fsm_rt_cpl;
            }
            s_tState = SEND_CHAR;
            break;
        case SEND_CHAR:
            if (serial_out(*pchStr)) {
                pchStr++;
                s_tState = IS_END_OF_STRING;
            }
            break;
    }

    return fsm_rt_on_going;
}

不仔细看的小伙伴也许会挠挠后脑勺，说：“代码很漂亮……但我也没看出有啥问题啊”？

不打紧，我们来看看这个状态机时如何使用的：

int main(void)
{
    ...
    while(true) {
        static const char c_tDemoStr[] = {"Hello world!\r\n"};

        print_str(c_tDemoStr);
    }
}

还没看出问题么？

好了，节目效果到了，我也不卖关子了，这一状态机存在的问题如下：

pchStr是一个局部变量，它保存了状态机函数 print_str被调用时用户所传递的字符串首地址；
该状态机在执行的过程中，不可避免的要多次出让（Yield）处理器时间，以达到“非阻塞”的目的；
由于pchStr是一个局部变量，它的生命周期在退出print_str函数后就结束了；而每次重新进入print_str函数，它的值都会被复位成“hello world\r\n”的起始地址。

这里，pchStr本质上是状态机print_str的上下文，该状态图设计最大的问题就是未保存print_str的上下文，导致每次进出状态机函数都会重新刷新关键的状态信息。

既然问题清楚了，修改方式也迎刃而解，如下图所示：

也就是说，我们可以通过引入一个静态变量 s_pchStr的方式来保存状态机的关键上下文信息。对比图片，可以注意到：修改后的图在复位后的初始化阶段（也就是start的行为部分）对静态变量 s_pchStr做了一个初始化——用pchStr为其赋值。此后，图中所有针对字符串的操作也都是使用 s_pchStr 来完成了。

重新翻译后的代码如下：

fsm_rt_t print_str(const char *pchStr)
{
    static enum {
        START = 0,
        IS_END_OF_STRING,
        SEND_CHAR,
    } s_tState = START;
    static const char *s_pchStr = NULL;

    switch (s_tState) {
        case START:
            s_pchStr = pchStr;
            s_tState = IS_END_OF_STRING;
            //break;    //!< fall-through
        case IS_END_OF_STRING:
            if (*s_pchStr == '\0') {
                PRINT_STR_RESET_FSM();
                return fsm_rt_cpl;
            }
            s_tState = SEND_CHAR;
            //break;    //!< fall-through
        case SEND_CHAR:
            if (serial_out(*s_pchStr)) {
                pchStr++;
                s_tState = IS_END_OF_STRING;
            }
            break;
    }

    return fsm_rt_on_going;
}

【一系列似是而非的问题……】

经过上面的一连串操作，我们成功的排除了陷阱，获得了一个能正常工作的状态机。然而，眼尖的小伙伴还是能很快的发现这里的限制：

状态机print_str 使用了静态变量来保存状态（s_tState）和关键的上下文（s_pchStr），因此几乎肯定是不可重入的；
状态机print_str使用了共享函数serial_out()，即便该函数本身可以保证原子性，但它仍然是一个临界资源——换句话说，即便抛开 print_str的可重入性问题不谈，当有该状态机存在多个实例时，你能保证每个字符串的打印都是完整的么？比如：

int main(void)
{
    ...
    while(true) {
        print_str(“I have a pen...”);
        print_str("I have an apple...");
    }
}

你实际打印出来的绝对不是你想要的结果。

此时，我们可以说，print_str 也不是线程安全（thread-safe）的。

根据维基百科的描述：

In computing, ... a reentrant procedure can be interrupted in the middle of its execution and then safely be called again ("re-entered") before its previous invocations complete execution.
https://en.wikipedia.org/wiki/Reentrancy\_(computing)

大体翻译成中文就是：

……可重入的程序（函数）允许在执行的过程中被打断，并在打断所执行的代码中再次安全的调用……

这里，我们需要注意一个细节，就是“可重入”关注的是，在任意时刻，无论以什么样的方式，该函数被多次调用时是否“安全”。换句话说，它并不是“非常在意”可重入本身对功能的影响，它在意的是这样调用是否“安全”。

以我们的print_str为例，由于状态机的中使用了静态变量，尤其是状态变量s_tState——这意味着同时执行的多个实例，彼此共享同一个状态变量……换句话说，当多个print_str同时执行时，它们是彼此干扰的。这意味着同时执行多个print_str是“不安全”的，是会出问题的（比如字符串长度不一致时很可能会出现buffer-overflow的问题），因此可以说 print_str是不可重入的。

但换一个角度，假设我们已经解决了print_str的不可重入问题，比如：妥善的解决了状态变量和上下文的存储问题，那么就满足了“可重入”关于“安全”的要求——因为当存在多个实例的时候，这样执行并不会导致系统崩溃，或是buffer-overflow——只不过打印出来的字符串并不完整而已。这就是为什么人们常说的：

可重入的函数不一定线程安全；
线程安全的函数也不一定可重入。

本质上，我们要解决的并不单纯是状态机的“可重入”问题——只把眼光放在可重入上就“格局小了”。

我们要实现的是“支持多实例的状态机”。

【多实例的状态机】

所谓多实例的状态机，就是指那些同一时刻可以安全存在多个运行实例的状态机——本质上每个实例都是一个任务——以多任务的眼光去看待状态机的多实例问题，格局就宽阔了起来。

通过前面的分析，我们已经注意到了问题所在，即：以现有的实现方式，如果存在多个 print_str调用（实例），那么它们其实是在“竞争”关键的状态变量 s_tState和上下文 s_pchStr。

说到解决方案，让我想起一个非常古老的关于打篮球的笑话：说民国时期，民风并未完全开化，一个老古董第一次去看了篮球赛。回来后，村里人让他给大家讲讲篮球赛是怎么回事。这个老古董说：太惨了，全场10个人穷的都只能穿汗衫裤衩……关键是，全场就只有一个球，惹得他们抢来抢去……为什么不能给他们人手发一个球呢？

聪明的你一定看出来了，解决状态机多实例的方式就是“给每个实例都发一个球”。具体来说，就是：

为状态机定义一个控制块；
在控制块里存放状态变量；
在控制块里存放状态机的上下文；
建立状态机实例时，首先要建立一个控制块，并对其进行必要的初始化；
在随后调用状态机时，应该首先传递状态机的控制块给状态机函数。

对应到图例上，我们一般会在状态图的某个角落（比如左下角或右下角）通过一个矩形框列举状态机上下文的所有内容。如下图所示：

观察修改后的状态图，我们应该注意以下的一些变化：

在图的右下角，出现了一个带标题的矩形框。这里标题print_str_t是状态机控制块的类型名称；下面的列表中列举了上下文的内容，在本例中就是 pchStr，注意，它已经去掉了"s_"前缀。
状态图中通过 "this.xxxx" 的方式来访问状态机上下文中的内容。

【基本的翻译方法】

一般来说，无论采用何种状态机翻译方式，可重入的状态机一定会包含一个控制块。在C语言中，我们会为其定义一个结构体类型：

typedef struct <控制块类型名称> {
    uint8_t chState;      //!< 状态变量
    <上下文列表>
} <控制块类型名称>；

以print_str状态图为例：

typedef struct print_str_t {
    uint8_t chState;     //!< 状态变量
    const char *pchStr;  //!< 上下文
} print_str_t;

这里，我们并不会规定用户用何种方式来为 print_str_t 类型分配存储空间——这个选择权应该留个用户自己——无论是定义静态局部变量、全局变量还是从堆或者池中分配，都可以。

无论采用哪种分配方式，我们都需要提供一个专门的函数来对状态机进行初始化。推荐的格式是：

#undef this
#define this    (*ptThis)
...

int <状态机名称>_init(<状态机类型名称> *ptThis[, <形参列表>])
{
    ...
    this.chState = 0;    //!< 复位状态变量，这里固定用0
    /*! \note 这里根据需要可以初始化那些只需要初始化一次的上下文
     */   
    /*! \note 这里也可以对输入的参数进行有效性检测，如果发现错误，
     *！       就返回负数值。这里既可以自定义一套枚举，也可以简单
     *！       返回 -1 了事。
     */   
    return 0;             //!< 如果一切顺利返回0，表示正常
}

以 print_str为例：

int print_str_init(print_str_t *ptThis)
{
    if (NULL == ptThis) {
        return -1;     //!< 是的，我偷懒了
    }
    
    this.chState = 0;
    //在这个例子中，this.pchStr 更适合在运行时刻由用户指定。
    
    return 0;
}

接下来，我们就需要对状态机函数进行小小的改造，其格式为：

#include <assert.h>

fsm_rt_t <状态机名称>(<状态机类型名> *ptThis[, <形参列表>])
{
    //!< 这种事情就不适合在release版本的运行时刻检查
    assert(NULL != ptThis);   
    enum {
        START = 0,
        <状态列表>
    };
    ...
    
    switch (this.chState) {
        ...
    }
    
    return fsm_rt_on_going;
}

最后，该图的翻译为：

#undef this
#define this (*ptThis)

#define PRINT_STR_RESET_FSM()               \
        do { this.State = START; } while(0)

fsm_rt_t print_str(print_str_t *ptThis, const char *pchStr)
{
    enum {
        START = 0,
        IS_END_OF_STRING,
        SEND_CHAR,
    };

    switch (this.chState) {
        case START:
            this.pchStr = pchStr;
            this.chState = IS_END_OF_STRING;
            //break;    //!< fall-through
        case IS_END_OF_STRING:
            if (*(this.pchStr) == '\0') {
                PRINT_STR_RESET_FSM();
                return fsm_rt_cpl;
            }
            this.chState = SEND_CHAR;
            //break;    //!< fall-through
        case SEND_CHAR:
            if (serial_out(*(this.pchStr))) {
                this.pchStr++;
                this.chState = IS_END_OF_STRING;
            }
            break;
    }

    return fsm_rt_on_going;
}

此时，我们就可以“安全”的进行多实例调用了：

static print_str_t s_tPrintTaskA;
static print_str_t s_tPrintTaskB;

int main(void)
{
    ...
    print_str_init(&s_tPrintTaskA);
    print_str_init(&s_tPrintTaskB);
    
    while(true) {
        print_str(&s_tPrintTaskA, “I have a pen...”);
        print_str(&s_tPrintTaskB, "I have an apple...");
    }
}

至此，我们就完成了状态机print_str多实例的整个改造和部署过程。

【说在后面的话】

实际上，无论你的状态机本来就只需要单实例还是考虑要支持多实例，至少在Arm架构下，统一采用支持多实例的方式来设计其实在上下文的访问效率上是更高的，这在文章《散装 vs 批发谁效率高？变量访问被ARM架构安排的明明白白》有详细介绍，这里就不再赘述。

一旦习惯了使用多实例的方式来设计状态图，其实你就真正进入了“多任务程序设计”的领域——无论你是使用RTOS还是裸机，此时此刻，或多或少，都在同一个起跑线上了。

前面的例子讲解中，我们还遗留了一个所谓线程安全（Thread-safe）的问题没有解决。实际上，在完成了状态机的多实例化改造后，这一问题其实已经完全不是状态机设计的问题了——而是一个地地道道的普通多任务间同步和通信的问题（IPC问题）。

如何在状态机设计中体现多任务通信的方法和设计原则，这是我们后续文章的课题。有兴趣的小伙伴可以持续关注这个系列。

从另外一个角度来看。我们为每一个状态机都引入了一个控制块，从面向对象开发的视角来看，本质上是将状态机都以类的形式进行了改造，这里：

控制块的定义就是状态机的类（Class）定义；
状态机函数是类的方法（Method）；
初始化函数是类的构造函数（Constructor）；
实际上，状态机函数中用 this 来访问上下文，也已经暴露其OO的本质。

结合我在《真刀真枪模块化（2.5）—— 君子协定》介绍的方法，我们还可以真正做到对状态机的类进行私有化保护——是不是格局越来越大了呢？

首发：裸机思维
作者： GorgonMeducer 傻孩子

专栏推荐文章

如果你喜欢我的思维，欢迎订阅裸机思维
版权归裸机思维（傻孩子图书工作室旗下公众号）所有，
所有内容原创，严禁任何形式的转载。

推荐阅读

目录