有限状态机(Finite State Machine,FSM),简称状态机。今天这篇文档的主体思路,来自本人授权的一项发明专利。第一次尝试写出来,希望分享给更多人。

我当时写这个专利的时候,太有感觉了。非常的激动,同时我也很想分享给同事,但是可能太抽象了,未果。然后我想申请优秀专利奖,没有渠道!所以最近刷屏的屠呦呦没有评上院士的消息,我听后,心想意料之中吧。当年在学校写论文那个叫痛苦,说实话,我真的没感觉,后面终于东拼西凑,勉强过关。我妈说要我去读博士,我不敢了!同学建议我去大学当老师,我也不敢,我真怕误人子弟,我自己都怀疑自己读的书怎么用,完全没多少实践啊,虽然当时我也参加了导师的项目,用Delphi做了个界面。但是那叫实践吗,反正当时就是没感觉,没开窍。而经过这些年的摸爬打滚,几年后分成两次写了几篇专利,现在都已授权。这些专利都是非常有感觉,不是带任务的那种,所以基本上是一气呵成。其中有三篇是围绕一个主题从不同角度写的,太有感觉了。我当时想,我现在应该对得起这张文凭了!你们说如果我现在去大学当老师,会有人要吗?我觉得难,现在当老师都要求博士了,还要留过洋的,或者博士后了吧,所以不想了。。。不过我辈仍需努力吧,说不定哪天你不是坐在评委席上,就是坐在候选人席上:)

第一次知道状态机,还是在华为做测试,测传统的通信产品。从一个传统的通信协议里面知道了这个名字,当时只是觉得这个名字挺好的,当时没想太多,所以具体是哪个通信协议我也忘了,当然还是记住了其中的基本思路。几年后,在这里重构我们的软件时,在多线程中,创新性的运用了这个机制。非常好的一种方法,用了这种方法后基本没有乱七八糟的Bug,而且好扩展,很容易加功能!而其实在之前解决死锁的问题时,雏形就已经出来了。所以可以先阅读下当时我是怎么解决死锁问题的,有助于你的理解。

而最近我在参加一些架构师公开课的时候,发现老师们都在使用这个机制了。但是看很多学员有点懵懂,所以我就想哪天把它写出来。同时也说明了,理解和使用状态机需要有一定的编程基础,有些抽象。但读懂了,收获会不少!太好用了! 

 

状态机,表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

确切的描述是它是一个有向图形,由一组节点和一组相应的转移函数组成。状态机通过响应一系列事件而“运行”。每个事件都在属于“当前” 节点的转移函数的控制范围内,其中函数的范围是节点的一个子集。函数返回“下一个”(也许是同一个)节点。这些节点中至少有一个必须是终态。当到达终态,状态机停止。

可以理解为,系统的行为如果在不同的时间或环境下,其工作不同,并且行为可以分成有限的状态以及不重叠的程序块时,系统显现出了状态行为。正是因为状态机具有有限个状态,所以在实际工程中可以实现。但也并不意味着只能进行有限次处理,相反,有限状态机是闭环系统,有限无穷,可以用有效的状态处理无穷的事务。

更通俗点,状态机是通过有限且充分的状态个数记录线程的各种操作行为,并能在各种环境下、不同事件、不同时间的驱动下,切换到下一个合适的状态,如此反复。

总之,状态机,是一种对流程控制进行抽象的方法。

我们举一个常见的TCP连接对文件进行读操作的例子进行说明。

 

首先我们把整个流程分解成五个阶段: Session不可用阶段、Session建立阶段、验证阶段、文件处理阶段、Session终止阶段。

这一步很关键,尽量将粒度降低,抽象出尽可能多的状态。而且也可以分层,进入文件处理阶段,又可以细分为文件的打开、循环读、文件关闭至少三个阶段。

当然本文,主要围绕Session层来展开描述。所以如果按正常的流程,这五步的执行情况如下图。

    最佳实践之有限状态机-LMLPHP

我们很多人,可能将这五步写在一个函数中,把所有的步骤放在一个函数中按顺序执行,再加文件处理阶段一个大的while循环。

当然逻辑上这样也没有问题,但是有两点值得改进

(1)代码的可复用性基本上没有和可读性不佳;

(2)更主要的是没有真正的对这个五个阶段进行抽象化。

于是,有人想到了对流程控制进行修改,中间可能的失败直接往后跳到某个阶段,不再完全是顺序执行,如下图。

    最佳实践之有限状态机-LMLPHP

绿色的线为变更的地方。这种方法,对比前面思考的稍微多一些,但还是不够充分。上面提出的两点改进,并没有实质变化。

程序的流程控制是任意一个环节都可能存在失败,而且最好还可以重来,也就是说不一定只能往后结束或者退出,而是可以自我更正或者恢复。如下图。

    最佳实践之有限状态机-LMLPHP

 

红色的线为变更的地方。验证阶段,如果第一次失败了,是否存在多个用户名密码呢。文件处理阶段,如果当前文件读取失败,是否可以读下一个文件呢。

那有的人会说,问题也来了,如果都放在一个函数中,那岂不是又要加循环。如果两次往回判断,得加两个while循环!这样的推断没问题。但同时解决方法也是有的。

也就是回到了开始提到的两点改进,对策如下

首先,将所有的步骤放在一个函数里面,这是停留在面向过程的编码,不是面向对象。所以,第一步需要将这个五步分别建立五个方法。这样每个方法都可以复用,即使将五个方法按顺序执行,最少的代码可能只需五行代码,至少也看不到文件处理阶段的while循环了,代码量是不是大大减少。可读性是不是更佳,一看方法名就知道在做什么,而不需要看大段代码,不需要关注实现细节。

其次,将五个阶段定义五个值,一个枚举变量的五个值,最好是定义五个宏,为了可读性。那么加上switch和case,外面再加上一个while循环,注意仅仅需要一个while。是不是就可以很方便的进行状态切换,不管是往前切还是往后切、反复切。这就是状态机真正的精髓

我们再重复下状态机的设计过程。首先将流程抽象成几个可以重复可以复用的步骤,每个步骤尽量单独封装成函数或者方法。然后再对这个几个步骤或者说方法,定义一个枚举变量,枚举值对应的宏名称和方法名可以一一对应。那么再就可以在一个函数中,或者多线程的run函数中加上while、switch和case的流程控制,显然每个case对应了一个方法,再根据方法的返回值再判断下一个状态是什么,再进入下一次的while和下一个case,如此反复。

我们贴一段伪代码,示范一下。

bool bExit = 0;
m_nStatus = P_INIT;
while ( !bExit)
{
    switch (m_nStatus)
    {
        case P_INIT:
        {
            E_P_ERR  eErr = Init();

             if (eErr == P_ERR_INIT)//初始化错误
            {
                  m_nStatus = P_EXIT;//直接退出
            }
            else if (eErr == P_OK)
            {
                  m_nStatus = P_OPEN; //正常执行下一步
            }
            //省去若干代码
            break;
        }
        case P_OPEN:
        {
            E_P_ERR  eErr = Open();

             if (eErr == P_ERR_OPEN)//打开失败
            {
                  //m_nStatus = P_EXIT;//可以省去,状态未变化
                  continue;//再次尝试打开,或者打开下一个文件
            }
            else if (eErr == P_OK)
            {
                  m_nStatus = P_READ;//正常,可以开始读取文件
            }
            //省去若干代码
            break;
        }
        //省去若干代码
    }
    //省去若干代码
}//while
                        

 从代码可以看出,程序结构非常简单,流程非常清晰,对状态的转换非常明确。

事实上,我们在实现中,代码远不止这么简单。但是基本框架是类似的,更多的考虑是一些初始化、准备工作和一些异常处理工作。

而整个流程下来,你会发现这里都用不上锁,而且涉及到的每个对象也用不上锁: 

对session不需要加锁,

对文件链表不需要加锁,

对缓冲的读写不要加锁,等等

最后整个流程除了维护状态机本身的锁以外,不需要任何锁!

因为即使再复杂、再多的控制,对于状态机而言,只是其中一个状态而已!

而状态机的锁,主要是给外界了解和提供当前的状态,所以一般也就是为了getStatus函数需要而加上,所以使用不频繁。

爽不爽,有没有被颠覆的感觉!:)

上一篇,提到过,尽量少用锁,我是不是兑现了我的诺言:)

 

最后,状态机的本质是把流程抽象化,尽量分解出可重复的步骤。最终可以大大简化流程,提高代码的健壮性,基本达到无锁实现,大大减少锁带来的性能消耗,提升性能;而且流程清晰,可读性好!

状态机适用于两个状态以上及需要重复使用的情况,特别适用于多线程。

 

推荐阅读:

经验总结:内存泄露

经验总结:死锁 

经验总结:如何用巧力解决问题 

经验总结:如何把Bug的偶现变必现

05-30 03:09