Video在线视频

P/T系统的状态 变迁

就是可达标识集 变迁序列

用这两个呢

我们可以定义P/T系统的性质

那么petri网跟其它的系统模型

有区别的地方

在于它可以这两者并重

就是状态元素和变迁元素

同时出现在描述当中

这就是petri网的进程

petri网的进程呢是用一个网结构

把网系统里面所有发生的

录时的记录下来

记录下来的那个网叫做出现网

英文叫做occurence net

我给它翻译成出现网

出现网呢是这样定义的

第一它是个网结构

第二它是一个无环的结构

无环的网结构

也就是说没有循环

因为它记录的是这个事件的历史

发生了什么从头到尾记录下来

这个历史是不可能有循环的

现象

历史咱们讲历史现象可以重复

但是这个人已经不一样了

所以这个petri网的出现网呢

是没有环的

另外出现网的每一个s元素

最多有一个输入和一个输出

为什么呢因为每个s元素

都是由唯一的变迁产生的

和唯一的变迁消耗掉的

所以你记录的下来的就是

怎么产生的怎么消耗的

为什么说最多有一个呢

因为有可能这个资源

就是初始状态里面带的

它不是由变迁产生的

也可能这个资源产生以后没有被消耗

所以它就没有输出

因此这个出现网呢

就是这样的定义的

一个网结构它的s元素

最多一个输入最多一个输出

而且没有环的结构

比方说下面我们看见的这个图

它就是一个出现网

这个出现网呢

一共有三个t元素

有若干个s元素

你看所以s元素的

输入和输出最多有一个

那么这既然是一个系统的行为的记录

那么它必然跟这个系统就有联系

你记录的是系统里面的哪一个变迁呢

你记录的是消耗的哪一类的资源呢

所以它中间作为一个进程

不仅要有一个出现网的结构

还要有这个出现网到

你所记录的那个网系统的一个映射

这个呢就是完整的一个进程了

所以一个进程呢

它是由两部分组成

一个从出现网

到原来的网系统的一个映射

这就是那个系统的一个进程

比方说我们这个例子

这个就是它的一个进程

记录下来的就是t1发生

然后t2发生然后t3发生

这个映射呢按照这个顺序

e1映射到t1

e2映射到t2

e3呢又映射到t1

然后s元素这个对应

大家可以从这个图上可以看出来

我就不多说了

那个要想给出一个

形式化的或者是半形式化的这个映射

就是从出现网到网系统的映射

会很复杂

因为你那个权大于1的

所以它会有许多同样的s元素

有不同的弧连接到这个网结构

所以那个出现网会很复杂

那么为了让大家理解这个概念

但是又不泄露细节

我们一般的都是只对这种网系统

给出它的进程的定义

权函数呢都是1

这样就避免这个重复

另外呢

它的容量函数呢都是无穷

这种网啊其实是最古老的网

我说的古老有点夸大啊

就是说岁数最大的网

petri在他的博士论文里面

用的就是这种结构

就是容量是无穷的权都是1

我这里课上不会讲

但是书上我提到的

就是不管你这个权是几

你这个容量是几

我们都可以用技术手段把它改造成

这样的一种网系统

就是权是1容量函数是无穷

进程的定义我这儿就不给出来了

因为给出来也就是一些细节

所以我们不必局限在那个细节里面

我这课呢主要是讲概念

我已经提到过

为什么这个容量会是无穷

我刚才讲了我们都可以改造到无穷

容量无穷到底是什么含义啊

首先我们看看容量有限是什么意思

比方说这个图容量有限呢

它这个容量是5

容量是5这个t呢就只能发生一次

为什么呢

因为它虽然它发生一次

就要往里面放三个token

但是它只能容纳下5个

你要两次就放6个了

它就容纳不下了

所以这个有限的容量函数

体现的是一个空间资源的个数

我这个仓库有多大

我能容纳多少

所以体现的是一个物理概念

就是空间容量的大小

那么我这容纳不下6个

只能放5个

所以你只能发生一次

无穷大的空间这个有吗没有

容量函数有限

刚才我说了很容易理解

就是一个空间资源的量数量

那么容量函数是无穷是什么意思呢

难道我们有无限大的这个仓库吗

这当然显然是不可能的

这个它的含义是什么呢

就是我这个容量虽然有限

但是你这个系统里面的变迁的发生

不会因为我的容量受到影响

也就是说你运来的东西

你要装进来的东西

随时我都可以给你装下

这个时候

我们就不必考虑

它的容量具体的是几了

你比方说我一开始的时候说过

就是当我们把教堂婚礼

变成一个用P/T系统来表示的时候

那个容量到底是2还是3还是无穷呢

照理2就够了

因为只有一个新娘一个新郎

他们是同类的

那么我们没有必要

就是说他这个容量是2

你用容量是无穷表示也可以

所以呢就当做无穷

而不是这个真的无穷

如果是有限的它会出现什么呢

过去我们已经看过了

就是刚才这个也看过了

就是我们的基本现象叫做冲撞

如果能装5个的这个仓库

你硬要塞进去6个

那么就会发生冲撞

就超出了它的容量

这是我们基本现象里面的冲撞

如果移植到P/T系统来

它的定义会稍有不同

但是呢这个现象是一样的

就是容不下了

把这个空间资源用容量函数来表示

能够引出冲撞这个概念

冲撞这个概念呢非常的重要

如果你设计一个系统里面出现了冲撞

那么你就要小心了

这里面有出现这个accident

就是交通吧有事故的危险

你如果意识到了这一点

你意识到了空间资源

或一般资源的不同

因为一般的资源呢

比方说上次我说过

我喝进去的水不可能有人再来喝

再想来和我肚子里的水这不可能

但是开车的人都知道

有人会抢红灯

明明是绿灯有车正在正常的行驶

从东到西有可能就有人要抢这个红灯

要去抢占中间

那个十字路口的那个空间资源

所以空间资源被占用不能够阻止

下一次就强占这个空间

同一个空间资源的这个行为

所以冲撞是很危险的

有冲撞这个现象

冲撞并不是真的撞上了

真的发生事故了

而是说有这个潜在的危险性

如果我们在系统里面

发现了这种潜在的危险

那我们可以想办法来避免它

所以空间资源用容量函数来表示

有助于我们发现潜在的危险性

意识到了这一点以后

空间资源呢就可以用token来表示了

比方说红绿灯就是告诉你

红灯就告诉你

前面那个空间资源已经被占用了

你不能够抢占

比方说一个车库

车库里面呢

有停车位是两百个

那么它外面会有一个牌子显示

说还剩余比方说五十个

那么这就是用这个token

来表示空间资源的个数

那么从技术上来讲

你既然意识到这个危险

那么我们就可以

在我们的网系统里面

用技术手段

把这个冲撞现象给消除掉

这就是s补

那个s补呢我们看这个图

这个地方就是有冲撞

刚才我们已经看过了K=5

这个是3

那么它放进去

一次可以

你再第二次就会有冲撞了

那么怎么来消除这个冲撞

把这K=5改造成K等于无穷呢

就是s补

什么叫做s补

就是这个有冲撞的s元素

把它的补元素加到这个系统里面去

这个补元素是什么意思呢

一个从结构上来讲

一个的输入是另外一个的输出

一个的输出是另外一个的输入

这就是从结构上来讲的补

比方说这个s′

它的输入就是它的输出

它没有输出它没有输入

这是第一个条件

就是互为补库所

第二个条件

这两个里面的token的总数

加起来是5

所以两个条件一个是结构上的条件

一个是token的数目

这个token的数目

被占用的和没有被占用的

加起来的总数

就是这个空间的容量

所以这个既然里面没有

那么我们那边的就是个5

这个s′和s呢就叫做它的补库所

有了这个补库所以后我们看

这个t就只能发生一次了

它不能发生两次了

因为发生一次以后s′里面

就只有剩下两个token了

s′或者s呢是互补的

我刚才只讲了两个条件

实际上还有第三个条件

就是不仅结构上它是输入或输出

互为倒过来

输入就是输出

输出就是输入

而且弧上面的权要是一样的

比方说这儿的权是3

这的权是2

那么这个s′就不够资格

称为是s的补库所

所以补库所三个条件

结构上要相仿

权要一样

它的token的总数要等于

原来这个容量函数给定的那个量

所以这个s′呢

它不够资格它缺少一条

不能够成为这个s的补库所

如果我们把那个2改成3

那么它就是补库所了

那么原来这个地方有冲撞

它不能发生两次

那么这个时候呢我们看

它也不能发生两次

这个不能发生两次呢

就不是因为容量了

而是因为资源不够了

那里一共只有5个token

它一次要消耗3个

两次就是6个了

所以呢冲撞就没有了

所以这就是技术上来处理

空间资源的个数

用容量函数来表示

提醒我们有冲撞的可能性

意识了这个可能性以后

你可以通过技术处理

来把冲撞消失

来分析这个系统的行为

所以这就是这个s补

刚才这个进程我讲的很简单

那你自己回去看一看

这个进程从一个出现网

到这个网系统

它的对应关系 它的映射

那么这个呢是其它的系统没有的

这个在我们应用当中很少有人用

因为这个把一个出现网画出来会很复杂

你一个大的系统

你再去画一个出线网

因为出现网一个时间可以出现很多次

那么在出现网里

这个就会有很多个这个变迁

来表示同一个事件的发生

每一次都要有一个变迁

每一次都要有一个变迁

出现网会变的很复杂

所以在实际应用当中

我们不会用出现网

用这个系统的进程

来分析描述一个系统的行为

这个作用在哪里呢

这个进程这个概念的作用在哪里呢

在理论上

我们那个并发论

它的基础就是完整的四季系统

那个完整的出现网

所体现出来的性质

所以我这里只是把

这个进程这个概念呢介绍一下

网系统它有自己的独到之处

就是它可以变迁或状态并重

来分析描述这个系统的行为