专栏首页裸机思维从零开始的状态机漫谈(4)——多实例

从零开始的状态机漫谈(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)—— 君子协定》介绍的方法,我们还可以真正做到对状态机的类进行私有化保护——是不是格局越来越大了呢?


原创不易,

如果你喜欢我的思维、觉得我的文章对你有所启发,

请务必 “点赞、收藏、转发” 三连,这对我很重要!谢谢!

欢迎订阅 裸机思维

本文分享自微信公众号 - 裸机思维(bare-metal),作者:GorgonMeducer 傻孩子

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-09-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从零开始的状态机漫谈(2)——switch:你的状态机初恋

    在前面的一篇文章《从零开始的状态机漫谈(1)——万物之始的语言》中,我们介绍了状态机在整个计算机科学中宛如“世界基石”般的地位,同时介绍了一种“面向嵌入式环境”...

    GorgonMeducer 傻孩子
  • 从零开始的状态机漫谈(1)——万物之始的语言

    也许从12年前我第一次开始分享状态机编写心得开始,“状态机”就像标签一样紧紧的贴在了“傻孩子”这个网络昵称的额头上——真是抠都扣不下来。不得不坦白的是,从一开始...

    GorgonMeducer 傻孩子
  • 从零开始的状态机漫谈(3)——状态机设计原则:清晰!清晰!还是清晰!

    我们常说状态机是一种思维方式、一种工具,同时它也是一种拥有极高自由度的语言。说到语言,类比我们日常使用的口语,你会发现:有的人表达能力很强——说话条理清晰、逻辑...

    GorgonMeducer 傻孩子
  • 故事工厂在DuerOS技能开发中的应用——百度2019AI开发者大会DuerOS公开课摘要解读之四

    在百度2019AI开发者大会上有很多相对精彩的公开课,DuerOS相关的公开课有4场,分别是:

    半吊子全栈工匠
  • 【深度学习研究系列】之漫谈RNN(一)

    从今天起,量化投资与机器学习公众号将为大家带来一个系列的 Deep Learning 原创研究。本次深度学习系列的撰稿人为 张泽旺 。希望大家有所收获,共同进步...

    量化投资与机器学习微信公众号
  • 【机器学习 基本概念】马尔可夫链

    马尔可夫链,因安德烈·马尔可夫(A.A.Markov,1856-1922)得名,是指数学中具有马尔可夫性质的离散事件随机过程。该过程中,在给定当前知识或信息的...

    魏晓蕾
  • 地球如果流浪,大数据究竟能做什么?

    每条大街小巷,每个人的嘴里,见面第一句话,就是:「道路千万条,安全第一条,行车不规范,亲人两行泪」。

    数澜科技
  • IM开发基础知识补课(三):快速理解服务端数据库读写分离原理及实践建议

    IM应用从服务端数据的角度来看,它是一种很特殊的应用场景,抛开基础数据、增值业务和附属功能不谈,单从IM聊天工具的立身之本——聊天数据来说,理论上是不需要在服务...

    JackJiang
  • 随机过程在数据科学和深度学习中有哪些应用?

    (图源:https://www.europeanwomeninmaths.org/etfd/)

    AI研习社
  • 随机过程在数据科学和深度学习中有哪些应用?

    (图源:https://www.europeanwomeninmaths.org/etfd/)

    AI科技评论
  • 5个零售商IoT使用案例,零售商终于接近物联网

    自从互联网以来,行业专家一直在谈论物联网。但是,从那时起,我们已经花了将近20年的时间才能开始谈论真正的解决方案和实际价值。挑战的一部分是在技术方面,只是弄清楚...

    首席架构师智库
  • 如何删库跑路?教你使用Binlog日志恢复误删的MySQL数据

    开个玩笑,今天文章的主题是如何使用Mysql内置的Binlog日志对误删的数据进行恢复,读完本文,你能够了解到:

    Rude3Knife的公众号
  • IM开发基础知识补课:正确理解前置HTTP SSO单点登陆接口的原理

    一个安全的信息系统,合法身份检查是必须环节。尤其IM这种以“人”为中心的社交体系,身份认证更是必不可少。

    JackJiang
  • 【深度学习系列】漫谈RNN之序列建模(机器翻译篇)

    推送第四日,量化投资与机器学习公众号将为大家带来一个系列的 Deep Learning 原创研究。本次深度学习系列的撰稿人为 张泽旺 ,DM-Master,目前...

    量化投资与机器学习微信公众号
  • 回顾戊戌年|VRPinea十佳AR/VR文章汇总

    昨日,已经迎来农历己亥年。值此辞旧迎新之际,VRPinea综合内容深度、读者评论、推荐量与阅读量等因素,特意为大家挑选出“戊戌年十佳文章”,与君共飨。也期望能借...

    VRPinea
  • 零基础IM开发入门(三):什么是IM系统的可靠性?

    本文编写时引用了“聊聊IM系统的即时性和可靠性”一文的部分内容和图片,感谢原作者。

    JackJiang
  • 【深度学习研究系列】之漫谈RNN(二)

    ? 推送第二日,量化投资与机器学习公众号将为大家带来一个系列的 Deep Learning 原创研究。本次深度学习系列的撰稿人为 张泽旺 ,DM-Master...

    量化投资与机器学习微信公众号
  • 程序员必须掌握的算法有哪些?谈谈这这几年学过的算法

    由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决...

    帅地
  • 第一次在腾讯写文章好紧张!

    自从网易被拒以后一颗心一直处于失恋状态,对于腾讯,完全是在不冷不热的状态下去听宣讲会的。

    重庆华哥哥

扫码关注云+社区

领取腾讯云代金券