缺少状态机信息是什么是状态机意思

使能了LDP能力的LSR周期性地发送Hello消息通告自己的存在。通过Hello消息LSR可以自动发现它周围的LSR邻居,并与其建立Hello邻接关系

LDP对等体发现机制分为两种:

LDP对等体之间通过周期性地發送Hello消息来维护Hello邻接关系。如果Hello保持定时器超时时仍没有收到新的Hello消息则删除Hello邻接关系。

通过交互Hello消息发现LSR邻居后LSR开始与其建立会话。这一过程可分为两步:

(2)     通过交换会话初始化消息对LSR之间的会话进行初始化协商会话中涉及的各种参数,如LDP版本、标签通告方式、Keepalive保持時间等如果会话参数协商通过,则LSR之间成功建立LDP会话

会话建立后,LDP对等体之间通过发送LDP PDULDP PDU中携带一个或多个LDP消息)来维护这个会话洳果在Keepalive报文发送时间间隔内,LDP对等体之间没有需要交互的信息则LSR发送Keepalive消息给LDP对等体,以便维持LDP会话如果Keepalive保持定时器超时时,没有收到任何LDP

一个LDP会话上可能存在多个Hello邻接关系当LDP会话上的最后一个Hello邻接关系被删除后,LSR将发送通知消息结束该LDP会话。

相邻LSR之间只会建立一个LDP會话但可在此会话中同时交互IPv4 FEC—标签映射和IPv6 FEC—标签映射。

LSR还可以通过发送Shutdown消息通知它的LDP对等体结束LDP会话。

利用LDP动态建立LSP的过程如所示LSR根据IP路由表项中的目的IP地址划分FEC,为不同的FEC分配不同的标签并将FEC—标签映射通告给对端LSR;对端LSR根据接收到的FEC—标签映射及本地为该FEC分配的标签建立标签转发表项。从IngressEgress的所有LSR都为该FEC建立对应的标签转发表项后就成功地建立了用于转发属于该FEC报文的LSP

}

自动机是计算机的简单理论模型通常将自动机分为有限自动机和图灵机。尽管有限自动机更简单但在定义图灵机之后数年,这个概念才被提出来

沃伦·麦卡洛克当时正在研究脑部创伤治疗精神病人,他想研究出一种解释大脑如何工作的理论。沃尔特·皮茨最初被培养成为一位逻辑学学者,但是却在全噺的数学生物物理学领域发表论文两人于1942年相识,认识到他们对相同类型的问题感兴趣于是开始联手研究彼此取长补短。他们发表了苐一篇论文“神经活动中内在的思想逻辑演算”(A Logical Calculus of Ideas Activity)在这篇论文中,他们借助细胞对神经元进行了建模虽然每个细胞都有多个输入,泹只有一个输出一个细胞的输出必须成为另一个细胞的输入,输入的类型有两种——抑制的和兴奋的如果兴奋的输入超过了一定阈值,且没有抑制输入细胞将会被激活。虽然细胞的集合和它们之间的连接被两人称为神经网络但他们没有意识到,这是大脑实际运作的簡化模型通过研究神经网络可以得知神经网络如何处理逻辑活动。他们的网络模型与神经元和人类的大脑具备相同的特征因此他们希朢自己的研究能够揭示人类逻辑推理的奥秘。

他们的论文引起了计算机专家约翰·冯·诺依曼和著名的数学家、哲学家诺伯特·维纳的注意两位学者对这篇论文印象深刻。维纳看到了其中蕴含的力量他意识到,这一观点具有广泛的适应性可以发展出控制论。控制论将催苼可以学习的机器的理念反过来也会孕育人工智能。冯·诺依曼认识到,麦卡洛克和皮茨对细胞和细胞间连接的描述,同样可以应用到电子组件和计算中。他在《关于EDVAC的报告》(First draft of a report on the EDVAC)一文中对此进行了详细的描述正是这篇论文奠定了现代计算机构建的基石。

另一个受到麦鉲洛克和皮茨影响的人是马文·明斯基,1954年明斯基在他的博士论文中对神经网络进行了研究展示了如何使用这些网络对自动机进行全面嘚描述。明斯基的著作《计算:有限和无限机器》是这一领域的经典之作高屋建瓴地描述了自动机和计算理论。通过对比物理学明斯基在这本书的前言中解释了这种使用理论机器研究的理论为什么是状态机能够发挥作用。

与物理学使用统计定义事件的方法不同我们是鼡逻辑定义的计算或表达式。它们被联系在一起不是通过几何或能量性质,而是通过它们与类似机器或类似定义之间的关系我们能够使用机器组件进行简单的交互,应用最显而易见的逻辑命题面对等价的现实物理机器时,我们必须解决极端复杂的分析等式

自动机被劃分为两类:一类具有有限内存,另一类具有无限内存下面只研究有限的一类

有限状态机(Finite State Machine,FSM)是一种抽象的机制 它包括有限数量的狀态。因此FSM是一个状态集值的一个有限集合。

闸机是一个常见的状态机这是《敏捷软件开发——原则、模式与实战》一书中展示的一個经典示例。在这里将以香港地铁站的闸机为例介绍有限状态机,其用例文本摘要如下:

通常闸机默认是关闭的当闸机收到有效卡信息时,则打开闸机;当乘客通过后则关闭闸机。如果有人非法通过则闸机会发出连续的“滴、滴、滴……”报警声;如果闸机已经打開,而乘客还在刷卡则闸机会发出“滴”的声音提示乘客,并显示“票价和余额闸机已经打开,请通过谢谢!”

FSM会响应“事件”而妀变状态,即将每个“事件”实现为一个函数当“事件”发生时,就意味着调用了一个函数FSM也执行动作产生输出,所执行的动作是当湔状态和输入事件的一个函数其目的是执行系统的任务。

事件是指在某个时刻发生的事情比如,闸机的“刷卡(card)”事件和“通过(pass)”事件状态是系统的状态。事件表示时间点状态表示时间段,状态对应对象接收的两次事件之间的时间间隔比如,闸机可能处于嘚状态:Locked状态和Unlocked状态

转换是从一个状态转移为另一个状态的路径,引发它的事件被称为事件触发器简称触发。而转换可以触发动作——表示对象的某个方法的调用比如,当事件card发生时闸机从Locked状态转换为Unlocked状态并执行打开闸机动作。转换还有一个监护条件逻辑测试——戓布尔测试只有测试通过时转换才发生。

而事件可以是外部事件和内部事件外部事件是在系统和它的执行者之间传递的事件,比如按下一个键和一个来自传感器的中断都是外部事件。内部事件是在系统内部的对象之间传送的事件比如,溢出异常是一个内部事件可鉯用UML对4种事件建模:信号、调用、时间推移或状态的一次改变。信号或调用可以带有参数参数值对转移(包括监护条件和动作的表达式)是可见的。

信号是一个异步事件在实例间异步传递消息的通信规约。消息是一个具名对象信号是消息的类型,象类一样信号也有屬性和操作。而信号事件是指发送或接收信号的事件其差别在于信号是对象之间的消息,而信号事件是指在某时某刻发生的事情

如果倳件没有产生任何效果,则FSM保持状态不变通常下一个状态依赖于当前状态和输入事件,有时状态转移会导致输出动作在某些情况下,雖然一个事件不会立即导致状态转换但它会影响随后的状态转换。如果事件已经产生则可以将该情况保存为一个条件,在之后进行检驗

监护条件是由一个方括号括起来的布尔表达式,放在触发器事件的后面其表示法为“事件[条件]”(Event[Condition]),条件是某一段时间内值为True或False通常“事件”引起了“状态转换”,当事件发生时为了发生转换,可选的“条件”的值必须为True可选的“动作”作为结果被执行。

动莋是与状态转换相关的可选的输出动作执行了计算(调用相应的函数),作为状态转换的结果事件导致状态转移,而动作是状态转移所产生的效果动作在状态转移时被触发,执行后自行终止

转换动作是指从某一状态转换为另一状态时产生的动作,该动作也可能发生茬状态转换至自身状态时为了描述状态图中的动作,将状态转换表示为:事件/动作(Event/Action)或事件[条件]/动作(Event[Condition]/Action)比如,card/unlock

考虑闸机状态图Φ的动作:当事件card发生时,闸机从Locked状态转换为Unlocked状态发生在该状态转移中的动作是获取card信息。作为状态机的输出该动作显示票价和余额並开锁。

通常多个动作可以和同一个状态转换关联因为动作都是并发执行的,所以这些动作之间不能有任何的相互依赖关系比如,不能同时发生两个并发的事件——计算余额和显示余额因为这两个动作有先后顺序的依赖关系,在余额计算之前不无法显示出来为了避開这个问题,可以引入“计算余额”的中间状态动作“计算余额”在进入该状态时执行,动作“显示余额”在退出该状态时执行

进入動作是指在开始进入该状态时触发的即时动作,使用保留字“进入(entry)”表示在状态框里表示为“进入/动作(entry/Action),即entry/[action-list]”

退出动作是指茬离开该状态时触发的即时动作,使用保留字“退出(exit)”表示在状态框里表示为“退出/动作(exit/Action),即exit/[action-list]”

由于状态图源自于用例,因此要从用例开发状态图首先需要用例中的一个特定的场景,即从用例中的一条特定路径描述对象之间的交互正常的业务序列详见图 4.8(a)。

如果闸机在Locked状态收到card事件则转移到Unlocked状态并执行unlock动作,此时闸机将它的状态改为Unlocked并调用unlock函数;如果闸机在Unlocked状态收到一个pass事件则转移箌Locked状态并执行lock动作,此时闸机将它的状态改为Locked并调用lock函数

如图 4.9 (a)所示为正常的业务序列图对应状态图,由于闸机处于打开状态或关闭状态時“card()”或“pass()”操作对应的处理是不同的,因此难以用一个序列图清晰地描绘对象交互与状态的关系如果以业务实体(闸机)的状态(咑开状态或关闭状态)为核心,将执行者与系统交互的具体操作称之为“事件”比如,card()、pass()等

图 4.9 闸机状态图

表4.1 闸机状态转移表

这些图是甴状态、事件、转换和动作组成的有向图,圆角矩形表示闸机的状态闸机始终保持状态直到转换促使它改变状态。转换用导向箭头表示通常由收到触发事件的元素发起。当输入的事件与有向边上的事件匹配时闸机将会从一个状态转换到另一个状态。

其中包含了起始状態、触发转移事件、终止状态和要执行的动作将其转换为状态转移表的表格,详见表 4.1由于状态转移表列出了所有状态下,接收所有事件后的状态是如何变化的因此很容易帮助发现遗漏了哪些状态转移。虽然状态转移表的优点是直观但其缺点也是非常明显的,那就是難以确认状态转移的完整性

显然,通用状态图与状态表描述状态机的行为开发者可以很容易检查那些未知的,甚至没有处理的情况仳如,闸机在Unlocked状态下没有处理card事件的转移且在Locked状态下也没有处理pass事件的转移。假设如果闸机在Locked状态收到一个非法pass事件则状态不变并执荇alarm动作,其业务序列图详见图 4.8(b)如果乘客不熟悉流程,当闸机已经转移到Unlocked状态时而乘客还在刷卡(card),则闸机会发出“滴”的声音提示乘客并显示“票价和余额,闸机已经打开请通过,谢谢!” 其业务序列图详见图 4.8(c)完整的闸机状态转移表详见

表 4.2 完整的闸機状态转移表


在关闭状态下,当需要增加报警功能时只需要新增一条事件/动作线,详见
图 4.9 (b)同理,增加一条事件/动作线表示闸门在已经咑开时继续刷卡的情况详见图 4.9 (c)。由于这两种情况不会改变闸机的状态因此导向箭头起始和结束均为同一状态。

在公众号后台回复关键芓“程序设计”即可在线阅读《程序设计与数据结构》;回复关键字“编程”,即可在线阅读《面向AMetal框架与接口的编程(上)》

}

(Finite-state machine)是一个非常有用的模型可鉯模拟世界上大部分事物。

简单说它有三个特征:

  * 状态总数(state)是有限的。
  * 任一时刻只处在一种状态之中。
  * 某种条件下会从一种状态转变(transition)到另一种状态。

它对JavaScript的意义在于很多对象可以写成有限状态机。

举例来说网页上有一个菜单元素。鼠标悬停嘚时候菜单显示;鼠标移开的时候,菜单隐藏如果使用有限状态机描述,就是这个菜单只有两种状态(显示和隐藏)鼠标会引发状態转变。

代码可以写成下面这样:


    // 当前状态
    // 绑定事件
    // 状态转换
          break;
          break;
          break;

可以看到有限状态机的写法,逻辑清晰表达力强,有利于封装事件一个对象的状态越多、发生的事件越多,就樾适合采用有限状态机的写法

另外,JavaScript语言是一种特别多的语言常用的解决方法是指定回调函数,但这样会造成代码结构混乱、难以测試和除错等问题有限状态机提供了:把异步操作与对象的状态改变挂钩,当异步操作结束的时候发生相应的状态改变,由此再触发其怹操作这要比回调函数、事件监听、发布/订阅等解决方案,在逻辑上更合理更易于降低代码的复杂度。

下面介绍一个有限状态机的函數库这个库非常好懂,可以帮助我们加深理解而且功能一点都不弱。

该库提供一个全局对象StateMachine使用该对象的create方法,可以生成有限状态機的实例


生成的时候,需要提供一个参数对象用来描述实例的性质。比如交通信号灯(红绿灯)可以这样描述:


交通信号灯的初始狀态(initial)为green,events属性是触发状态改变的各种事件比如warn事件使得green状态变成yellow状态,stop事件使得yellow状态变成red状态等等

生成实例以后,就可以随时查詢当前状态

* fsm.is(s) :返回一个布尔值,表示状态s是否为当前状态
* fsm.can(e) :返回一个布尔值,表示事件e是否能在当前状态触发
* fsm.cannot(e) :返回一个布尔值,表示事件e是否不能在当前状态触发

同时,它也允许为每个状态指定两个回调函数以green状态为例:

除了为每个事件和状态单独指定回调函數,还可以为所有的事件和状态指定通用的回调函数

如果事件的回调函数里面有异步操作(比如与服务器进行Ajax通信),这时我们可能希朢等到异步操作结束再发生状态改变。这就要用到transition方法


上面代码的回调函数里面,有一个异步操作(light.fadeOut)如果不希望状态立即改变,僦要让回调函数返回StateMachine.ASYNC表示状态暂时不改变;等到异步操作结束,再调用transition方法使得状态发生改变。

Javascript Finite State Machine还允许指定错误处理函数当发生了當前状态不可能发生的事件时自动触发。


比如当前状态是green,理论上这时只可能发生warn事件要是这时发生了stop事件,就会触发上面的错误处悝函数

}

我要回帖

更多关于 什么是状态机 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信