当前课程知识点:Petri网:模型、理论与应用 > 第四章 网论 > 4-6 同步论 > Video
我不知道大家会不会问
说这个E2怎么可能反向发生
现在这个token在中间共享的那个
那个条件里面
他是这样的那么当E2发生以后
右边这个
条件里面就有个token了咱们从这个
情态
作为初始情态从这出发
这样一来E2的就可以反向发生
反向发生以后E1就可以正向发生
所以他是从一个情态就是右边的token
到另外一个情态就是左边的token
这个情态到情态的这个过程叫做一个
挠进程
挠进程是及于能够达到最大值也能达到最小值
这就是在文献里面曾经有过的定义
但是这个定义我觉得有点不太好接受啊
初学的人不太好接受所以我觉得还是咱们
还原它的本质它就是两个进程获得
同步距离是两个进程
跨进程的概念
不是在一个进程里面能够算出来的
现在我们看另外一个基本现场就是并发
这个图里面的E1或E2是并发的
这个并发呢
这里面这个大N没有写
其实不写大也家应该知道我们最初放大N的token
那么E1如果发生呢
这个就有n加1个token
在这个共享的虚线的这个观察窗口里面
就会有n加一个token
如果E1不发生E2发生
那么这个虚的就关上窗口里面
就会去掉一个token
这边的n减1个所以呢它的最大值
是n加1它的最小值是n减1
那结果也是2
它们的同步距离仍然是2
就是我刚才已经讲过了
比方说我们说话上嘴唇下嘴唇
拍手拍手左手E1或E2就是左手和右手
的动作要么缺一不可
所以E1或E2呢
你要么观察到两个都发生了
要么观察到一个也没有发生所以
你再加一个token的同时也要减掉一个token
所以它里面的token变化是没有的是不是等于0
所以这个同步距离就是零
那么现在问大家如果我两只手来拍桌子
这个同步距离是几呀
这个课程没时间让大家去思考
那么它同时就是并发
有我左手握右手时
互不依赖的是并发的
他的同步距离是几呢
刚才我看到了并发它的同步距离是2
怎么理解这个就是
在拍手的时候如果你用非常快的摄相机把它照下来
然后用非常慢的摄像放出来你就会发现
有可能一只手连续拍了两次桌子
中间没有另一手参加也就是说这样
右手后击的桌子抬起来以后右手先
左手后所以在左手两次击桌之间右手击
打击了这个桌子两次这就是同步距离为二
他们物理意义
所以并发它的同步距离是二
或者说说得更准确点是大于等于2
因为有的例子
我们可以看看并发的它是可能超过2的
咱们再看看这个例子
这个E1或E2那是不并发的
刚才我们例子里并发的时候
我们在上面加了两条弧
两个箭头
E1可以发生因为它只有一个输入
而且输入里面有token
E2不能发生因为E2现在我们加了一个
这个输入条件就是E1个后击里面
的s元素
所以它的发生规律是什么呢E1发生
然后E2发生然后E1又发生
然后这个E4发生
把这个系统里面E1
这些事件的发生规律了
就是用像这个公式所描述的一样
E1、E2、E4、E3
然后反复的这样发生
所以那个星号就表示
这个变迁序列是可以重复的
我们看到
它的规律是什么呀
E1发生两次E2发生一次
然后你看如果我们要把这个五个变迁
五个这个事件再重复一遍的话
我们就发现E1发生了四次而E2就发生了两次
如果我们再重复一次那么E1就发生了六次而
这个E2呢就发生了三次
所以这个最大值你看n里面的最大值是多少
一次就多下了一个再重复一遍
又多下了一个在重复一次又多下了一个
这个token可以无限的增长token数可以无限的增长
要多少个有多少个这就是刚才我说的
他的同步距离就是无穷了
但是这种无穷呢又是有规律的
因为它发生的次数始终是
2比1就是两次E1一次E2
所以我们体现这种规律虽然
一比一的规律是没有
但是一比二也是规律啊
我们怎么来描述这种规律呢
有加权的同步距离
来描述什么意思就是当E1发生的时候
我们往里面放一个token
当E2发生的时候我们从里面拿掉两个token
这样一来我们看这里面当
E1发生的时候token数变成n加1
当E2发生的时候这里面的token数变成n减1
然后E1再发生它又恢复了n
然后整个这五个事件
就这样循环就完了
所以在一次循环当中如果我们加权观察的话
观察窗口里面的token是没有变化
加一个减两个再加一个等于没有加没有减
所以这样一来它的同步距离呢
我们说它的加权同步距离就是2
写成什么样的就是写成底下这样
在这个第二个E2集合前面加上一个2
这就是它的权
然后后面的等于2这就是它的同步距离
所以加权同步距离体现的仍然是一种规律性
同步的就是事件发生
反复发生当中所呈现出来的规律性
什么叫异步刚才我们看过这个
这个呢这个我们再重新看一遍
这个E1或E2刚刚不说了它是不同步的
因为这个E1
可以发任意多次E2不发生
E2也可以发生任意多次而E1不发生
所以它是不同步
这里面的这个观察窗口里同的token
可以任意的多也可以任意的少
那么他有没有规律呢我们能不能用加权
来体现它们之间的规律呢
那么这里面咱们可以很容易的看出来
没有权可以加它就是真的异步
没有规律
不像我们刚才那个是1:2这个没有这个规律
所以像这种呢
无论是同步距离或者加权同步距离
它都不能得到一个有限数这样的两组事件
就叫做异步的
所以这是真正的异步不能够同步
所以同步距离的定义就是这样
观察窗口所得到的最大值或最大最小值
之间的差叫做同步距离
这就是我们的定义
但是它那个形式化的定义那是比较复杂
所有的进程所有可能的进程
计算一个它的最大值
所有的进程计算一个最小值
然后最大值或最小值的差就是这个同步距离
那么这个公式我就不写了咱们书上有
嗯我想我到现在我就讲的已经很清楚了就是
最大值或最小值它有可能
是的两个不同的进程里面取得的
在进程里面要算一个最大值
在进程里面也算一个最小值
然后这个进程
这个最大值最小值之间差距同步距离
我们不能再一个同一个进程
说这里面最多发生多少次
最少发生多少次它的差是多少
这就错了
确实是分别计算进程的最大值
进程的最小值然后这两个差是这个同步距离
我不知道同学们会不会有这个疑问
为什么叫同步距离
那么我们是有道理的
这个有一个大家都知道这个距离公理
距离公理很简单
自己同一个点到自己的距离是零
就是第一条dxx等于0
另外距离的值任意两点的距离的值
就是大于等于0的第三条
然后这个距离是
这个对称的就从x点到y点的距离
或从y点到x点的距离
是相等的然后第四个
距离三角不等式
两点之间的距离小于这个
另外两段的和就是三角形
两边的和大于等于第三边
所以这就是这个三角不等式
距离公理就这些
那么很容易证明我们的同步距离的定义呢
是满足这个公理的
距离公理都是满足的
第一最大值减了最小值它当然大于等于0
如果你这个观察的E1或E2
是同一个集合那么当然
它的距离就是零了因为什么呢
你放进去一个就要拿出来一个
因为它既属于E1又属于E2
这就是为什么我一开始说
E1或E2的交是空集没有共同元素
所以很容易证明我这就不去重复的说了
他还有第五条性质
就是像我们说到的两个里面
公共元素去掉以后它的同步距离是一样的
然后第六个呢也很容易理解
根据这个定义的话这个很容易计算
我在这儿要是不写只是用嘴讲的大家不太容易
听得明白所以我就
省点事儿不说了你要有兴趣可以
自己去证明因为这个并不难
这就是同步距离
同步距离是同步论的核心概念
是它的核心概念怎么算呢
我们要不要一个进程一个进程把所有的进程
按照定义把所有的进程都找出来
然后一个一个算它的最大值
然后一个一个算它的最小值
需要不需要这样做呢
不需要如果这样做的话那这个
就太麻烦了当然你可以写个算法
让计算机来帮你算这个上面写的东西
我想说我刚才已经说过了我们不用挠进程
不用这个反向发生这个概念来定义
这就是挠进程的定义
一个反向发生我已经说过了咱们就不多说了
怎么计算在遇到具体的问题的时候
我们可以来
根据那个网系统的特点我们可以算
这里我有一个方法的就是可以借助p/t系统
来给大家介绍一下怎么个算法
我们知道
在我们讲这个网系统的性质
我们曾经介绍过这个有一个算法
叫做覆盖数字构造算法
怎么构造这个覆盖数
我们知道这个算法是已经成熟的了
你在网上
可能有机会能够下载这个算法
那么构造出来以后
构造出这个数以后这个数
是有限的然后我们可以把
相同的结局就是标识相同的
重叠起来就变成一个可搭图
那么在可搭图上呢我们来计算
构造出可搭图以后
在这可搭图上来计算这个同步距离
就是一件很容易的事情了
可搭树的根是什么
是m零初始标识
m0里面加上一列
第一列就是你那个观察窗口a
这个观察窗口的这个它的值
m0加上这一列的值那是n
就是我们一开始放进去的
N那么多个token
然后你就把a当做一个
普通库所以后我说现在是p/t系统
当事件发生的时候按照我们的观察规律
加一个token或者减一个token
加一个token减一个token这样来做
它跟这个库所不同的是什么呢
因为它不是系统的一部分
它是个观察窗口
所以它的值如果你一开始这个n
不够大的话他的值可以变成负的
而一般的这个
标识那是不允许库所里面有负的
说我这个是负级token不可能
但是观察窗口可以给观察窗口区别于
库所的地方就在于它的值这个分量
可以是正整数可以是零也可以是负整数
如果你要是加权同步距离呢
那么你就在变迁发生的时候
你就把那个权算上就行了
或者多加或者多减都可以了
这样构造出来这个可搭图以后你去看一看
这个可搭图上面如果有圈有向圈
能在这个有向圈上面的图上面
会有变迁的名字
如果在这个这一圈的变迁
你算下来E1的变迁出现的数目
和E2变迁出现的数目如果不相等的话
那么这个同步距离就是无穷为什么呢因为你转一圈
就会净剩下或者净亏的几个token
因为他不相等
所以一般的来讲这个应该是
相等的如果不相同的同步距离就是无穷了
另外如果在构建可搭图或者可搭数的时候这个
观察窗口的分量变成∞了也就无穷了
那么当然它的同步距离
也就是无穷他的观察窗户的值不是无穷
而且每一个圈
E1变迁或者E2的变迁出现的数目是一样多
我们可以把这个圈去了
去了以后那就剩下一棵树了那么在这棵树上
这个观察窗口的最大值或最小值
很容易就找到了最大值和最小值之间的
这个差就是同步距离
因为这个EN系统是p/t系统的一个特例
它的全五分全都是一
这个容量函数都是一
所以这个算法也是EN系统这就是同步距离
同步距离我刚才说了
是通步论的核心概念
所以同步论第一让我们知道
什么是同步这个概念什么是系统的
同步系统什么是事件同步它是
事件反复发生当中体现出来的规律
而不是一次发生或另外一次发生之间的
关系所以从概念上来讲我们理解了同步
另外我们定义的同步距离这个定量的描述工具
那么要用那个同步论的应用的主要就是
同步距离的应用
所以我们下面就看这个同步距离的应用
下面我举几个例子
看看同步距离怎么样来
用到实践当中去
第一个例子就是评估双方
合同的这个最大损失
第二个是用于软件的规范
第三个用于系统的控制
我们一个一个来说
-概述
--Video
-有向网
--Video
-3-1 Petri网定义
--Video
-3-2 Petri网层次系统
--Video
-3-3 基本网(EN)系统
--第一部分
--第二部分
--第三部分
--第四部分
-第三章 Petri网--3-3 基本网系统课后思考题
-3-4 条件-事件(C-E)系统
--Video
-第三章 Petri网--3-4 条件-事件系统课后习题
-3-5 库所-变迁(P-T)系统
--Video
--Video
--Video
--Video
--Video
-3-5 库所-变迁(P-T)系统课后习题--作业
-3-6 网系统层次
--Video
-3-7 高级网系统
--Video
-3-8 化简网系统
--Video
-3-9 非线性网系统
--Video
-3-10 小结
--Video
-4-1 前言
--Video
-4-2 网拓扑
--Video
-4-3 并发论
--Video
-4-4 网逻辑
--Video
-4-5 信息流网
--Video
--Video
-4-6 同步论
--Video
--Video
-4-7 同步论-合同实例
--Video
-4-8 同步论-婚礼教堂实例
--Video
-4-9 同步论 同步器
--Video
-第四章 网论--思考题1
-4-10 实例与方法——电梯控制
--第一部分
--第二部分
--第三部分
--第四部分
-4-11 建模方法论
--Video
-4-12 汉诺塔问题
--第一部分
--第二部分
-第四章 网论--思考题2
-5-1 工作流管理联盟
--Video
-5-2 工作流网(WF_net)
--Video
-5-3 Artifacts
--Video
-5-4 BPMN2.0
--Video
-5-5 学界
--Video
-5-6 业务流程管理(BPM)
--Video
-5-7 BPM建模
--A of ARM
-5-8 流程举例
--第一部分
--第二部分
-5-9 流程之外
--Video
-Petri网小结
--Video
--Video
-6.1 过程挖掘基础
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
-6.2 过程挖掘工具
--Video
--Video
-6.3 过程挖掘算法介绍
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
--Video
-6.4 未来研究方向
--Video
-7.1 科研三要素
--Video
-7.2 Program today
--Video
-7.3 Program yesterday
--Video
-7.4 Theory of Programming
--Video
-7.5 A of ARM
--Video
-7.6 R of ARM
--Video
-7.7 M of ARM
--Video
-7.8 OESPA
--Video
-第七章 科研思考--习题
-8.1 树个靶子
--Video
-8.2 八卦与自然
--Video
-8.3 结束语和感谢
--Video
-第八章 总结--习题