Video在线视频

这个EN系统和P/T系统

我们都讲过了

P/T系统还没讲完

概念上来讲

我们说这是属于两个区别的

但是如果从数学

纯粹从数学的角度来看

那么EN系统呢

是PT系统的一个特例

因为无非就是它的容量是1

所有的容量都是1

所有的权都是1对不对

所以它是它的一个特例

那么只不过我们在定义

EN系统的时候呢

是用那个所有有token的那些条件

把它组成的那个子集

叫做它就初始形态

而在这个P/T系统里面呢

我们不用子集

我们用的是这个映射

就是区别就在这儿

所以大家可以自己去推敲推敲

没有什么深奥的东西我就不多说了

那么现在回过头来

既然EN系统是P/T系统的一个特例

那么现在请你作为一个练习

把在EN系统里面

我们定义的那些基本现象

把它给移植到P/T系统中来

我们定义了EN系统的发生权

那么这个地方呢

我们也定义了P/T系统的发生权

你只要把PT系统的发生权

取代EN系统的发生权

定义就移植过来了

所以是个很容易的事情

自己去做一做

好 我们来看例子

我不定义了

就是这些基本现象我们不定义了

但是我们来看一看

有两个P/T系统

我所以说两个呢

是因为它们两个不连通

你把它看成一个也行

左边那一部分呢有两个t元素

右边那个有三个t元素

左边这两个共享一个库所

这个共享的库所里面有两个token

而权都是1因为是缺省值都是1

按照发生权的定义

这两个变迁都有发生权

所以这两个呢是并发的

就是这左边图里面的

这两个变迁是都可以发生的

t1可以发生t2也可以发生

而且它们两个同时发生

这个竞争的资源也够

它没有竞争

两个共享的资源是够的

所以t1和t2是并发的

一个新的现象就是

t1可以发生两次

t2也可以发生两次

只要对方不发生

所以按照定义呢

t1可以和自己并发

t2也可以跟自己并发

这第二个图里面有三个变迁

这三个变迁有一个共享的库所

这个共享的库所里面呢有两个token

所以这三个变迁

如果单独再来发生的话都有发生权

所以它们都可以发生

第一个变迁呢显然

和第三个变迁它们是可以并发的

实际上你如果仔细的看一看

思考一下的话

这三个变迁里面

任意两个都是并发的

中间那个自己可以和自己并发

第一个和第三个不可能

因为它们有一个输入

库所里面只有一个token

所以第一个只能发生一次

第三个只能发生1次

中间一个可以发生两次

所以呢这个它的并发关系呢是

任何两个都可以并发

中间一个可以跟自己并发

那么并发

所有的能够并发的这些变迁

组成的一个集合

我们就叫做并发步

并发步呢就是

我们可以把它写成这个多层级的方式

比方说上面我刚才讲的

那么t1可以和t2并发

我们写成t1加t2

那个t1可以自己跟自己并发

我们写成两个t1

t2可以跟自己并发我们写成两个t2

那么第二个例子里面

t1+t2 t1+t3 t2+t3等等

都是有一个并发步

另外两倍的t2

也是一个并发步是吧

所以这就是并发步

以及并发 并发步

和它的这个数学表示

基本现象呢这个冲突什么的

那么我就不再去举例子了

因为跟基本网系统里面是一样的

冲突呢就是共享的资源不够引起的

你也能发生我也能发生

但是我们共享的资源

不能够保证我们两个都发生

这就冲突了对吧

顺序也很容易

我能够发生你不能够发生

但是我发生以后你就能发生了

那你就得在我后面发生

这就是因果顺序关系

因为我产生的资源是你所需要的

要想研究一个P/T系统的性质

我们有几种可能性

一种可能就是把它所有的可能的状态

我们petri网里面叫做标识

研究程序的时候

把所有程序状态都找出来一样的

那么所有的这些状态组成的集合呢

叫做可达标识集

可达标识集呢有几种定义方法

我们在EN系统里面已经看到了

第一种就是

由下面这两条性质的

所有的那些标识组成的集合

就叫做它的可达标识集

而且是最小集合

注意最小的两个字是非常重要的

这两条是什么呢

第一我们现在这个定义这个可达标识啊

没有从初始标识开始

因为我们这个一旦有变迁发生

初始标识就不是初始标识了

就会改变到另外一个标识

我们必须考虑在任何一个标识下面

到底谁能发生

所以我们这个定义呢

是从任意的一个标识M来定义

从M出发可以到达的那些标识的集合

所以你既然是从M出发的

那么M一定是属于这个符号

这个符号呢就是表达

从M可以到达的所有标识的集合

那么M自己一定是属于它的

另外如果有M′属于它

而且有一个变迁t

t呢在这M′有发生权

然后它的后继续呢是M′′

那么这个时候M′′

一定也属于这个可达标识集

所有这样的标识组成的集合

其中最小的一个

就是系统的可达标识集

我们讲的系统的可达标识集

它的初始标识是什么呢

是给定的是M_0

所以我们把这个符号里面的M换成M_0

这就是P/T系统的可达标识集

我刚才特别强调了最小这两个字

在我过去的审稿过程当中啊

曾经有老师还不是学生跟我争论

我说你一定要有“最小”两个字

它把那个定义和构造混淆在一起了

它说我没放别的进去啊

一开始就是个M吗

后面你有了

发生了走了后继它才能放进去呢

我说你那个是构造算法

我们这个是定义

定义就是用性质来约束

那么这里我也不去细讲

就是数学的东西是严格的是准确的

你如果不能够准确的理解

那么你做出来的东西

就有可能是错误的

我这里举个例子

比方说所有可能标识

不管它从哪出发它就符合这两条

就是所有的标识组合成这个最大的集合

它就符合你这两条

M当然是里面的了对吧

你任何一个后继它也是里面的

但是这不是系统的可达标识集

所以你去比较比较这两个就知道

最小这个词是很重要的

另外一个呢定义方法呢

就是用自然语言来描述

说什么叫做可达标识集呢

可达标识集就是从M_0出发

经过有限多次变迁发生

能够到达的那些标识

组成的集合就是可达标识集

但是这个自然语言呢

往往它有不严格的地方

比方说我们这句话从M_0出发

经过有限多次

那么M_0属于不属于它呢

没有变迁发生

它就是个初始的东西

所以这就是它不严格的地方

咱们假定M_0属于它

我们加上这一句

从M_0出发包括M_0

经过有限多次变迁发生

能够到达的

所有的标识组成的集合

就叫做可达标识集

那么我们要来问一问

一个是定义的

一个是用自然语言描述的

这两者是不是一样呢

你用那个定义出来的东西是不是

就是我们用自然语言表达的这个东西呢

那怎么证明你自己去证我这不证了

这个老师在课堂上不做证明是有好处的

第一老师也可能在课堂上犯糊涂

证明错了

另外在证明的过程当中

学生有一个走神它就跟不上

所以那个漫长的证明过程

他就会不知道老师说什么了

有趣的一个例子是在上世纪20年代

在美国有一个大学

我忘记是哪个大学了

有一个数学系

当时数学系的学生并不多啊

我的老师当时在杭州大学教书的时候

他那个班上的学生只有四个人

所以他当时有一个很有趣的决定

就是我们这四个人

只要有一个人考试不及格

你们全都不及格

四个人全部补考

所以他们必须互相帮助

这个都让他及格才行

所以20世纪美国这个大学呢

这个系主任的学生也不多

他教了好多年的书

在这个课堂上

他没有完整的给出过一个定理证明

他证明了一半

这个屁股靠在课桌上就发呆了

待一会儿他回过头来

说你们自己回去证吧

我这就不证了

你们猜后果怎么样

他这个系里面

出了很多有名的数学家

为什么 学生回去自己证了

他自己一动手

跟自己不动手区别很大是不是

所以呢我在这也不证了

你们要想看证明

我的书上可能会有你去找一找

但是如果你自己证明了那是更好的

你的收获会更大

所以要想研究P/T系统的性质

我们第一关心它对所有可能的状态

这就是可达状态集 可达标识集

那么第二个我们关心的

就是所有的变迁序列

我现在关心这个系统里面发生什么了

这就是变迁序列

变迁序列是什么呢

比如说这个σ

是由τ1 τ2一直到τn组成的一个序列

我们把它称为P/T系统的一个变迁序列

如果这些变迁

就是τ1 τ2一直到τn

在初始标识之下

可以依着次序一个一个的发生

在M_O τ1能够发生后继是M_1

在M_1 τ2能够发生得到的后继是M_2

然后在M_2 τ2能够发生等等

一直到最后τn能够发生

最后的终止于这个M_n这个标识

符合这个要求的

这样一个序列就叫做一个变迁序列

所以我们变迁序列是有要求的

要能够依次发生

它才叫变迁序列

不是我把变迁拉出来随便摆一个顺序

就叫变迁序列不是的

有了变迁排成顺序

能按照这样的顺序发生

那才叫做变迁序列

这个变迁序列的这个

我们用一个符号来表示

就是它的M_n呢是这个变迁序列的后继

或者叫做终止标识

我们用这个符号来表示

这个变迁序列呢

我刚才讲的是有限的变迁序列

那么可以有无限的变迁序列

由变迁组成的无穷序列

叫做一个无穷变迁序列

它的定义是什么呢

如果这个无穷序列的任何一个前缀

就是我从这个无穷序列里面

从头算起

中间我随便切一刀

前面的那一块就叫它的前缀

任何一个前缀都是一个变迁序列

那么这个无穷序列

就叫做这个系统的一个无穷变迁序列

下面呢在文献当中

会用它来定义这个其它的概念

好 现在呢我们有了状态了

可达标识集 有了变迁了变迁序列

在这个计算机里面

我们在研究程序性质的时候

往往都研究的就是这个赋值语句序列

说什么叫做一个程序的性质

就是它这个所有可能执行的语句序列

具有的性质等等

所以这也是接下来的

有了这两个手段以后

我们现在来定系统的性质了

第一个性质叫做活性

什么叫做一个系统是活的

那么分两步定义

第一步定义

就是我们随便取一个变迁出来

说这个变迁在这个系统里面是活的

什么意思呢

就是你从可达标识里面

随便取出一个可以到达的标识

这个变迁要么在这个

任意随意取出来的那个标识底下

它就有发生权

发生权咱们定义过了

要么这个标识有一个

经过一系列的变迁发生以后

到达另外一个标识

在那个标识底下这个变迁

这个给定的变迁有发生权

也就是说这个变迁

在你任意给定的一个标识

要么现在就有发生权

要么有未来的潜在的发生权

那么这个t呢这个变迁呢

就叫做是活的

因为我即使现在不能发生

我有可能发生

多走几步我就能发生了

所以这叫做t是活的

那么什么叫做这个系统是活的呢

就是这个系统里面

所有的变迁都是活的

那么这个系统就是活的

这就是文献里面定义的活性

这个活性啊

只是一种数学上的定义

实际上在现实生活当中啊

这个定义是这个

直接在用来解决问题是不多的

你比方说电梯系统

它应该是活的吧

但是如果你这个电梯没有人来用

没有人来按bottom

这个电梯根本不动的

所以这个活性呢我们一定要灵活运用

你可以根据你的应用环境

来修改这个定理

说什么是活的

第二个性质就叫做有界性

如果你这个系统里面无论变迁怎么发生

所有的变迁里面的token的个数

都不超过给定的一个整数一个k

那么这个系统呢就叫做有界的

如果你知道这个k是几

你可以证明存在这么个k

但是你不知道它是几

那么我们就说它是有界的

如果你知道这个k是几

比方说k等于5

那你就说这个系统的是以5为界的

比方说我们刚才那个教堂婚礼

它的P/T系统它是有界系统

它的界就是2

因为只有两个新人

这两个新人会待在同一个库所里面

所以最多一个s元素里面就有两个token

不会超过两个的

教堂婚礼呢那个是1

作为P/T系统它的界是2

那么还有哲学家系统它的界呢是1

哲学家系统我到现在没有说过

那么下面呢我们看看

这个哲学家系统的

这个petri网的这个表示是什么

这个呢就是哲学家的petri网表示

这个哲学家问题

是petri网应用的一个很有

代表性的一个例子

我在后面应用的时候要专门来讲它

现在咱们先have a look

就是先看一眼

我不知道大家知道不知道

这个哲学家问题

那么我这儿呢重复一下

说有五个哲学家呀

围着一个圆的餐桌

坐在那等着就餐

五个哲学家呢

是每个哲学家

因为他是哲学家吗

他只有三种状态

一种状态就是思考

思考到感到他饿了

他就不思考了

就去要吃饭了

饥饿了以后他就要就餐

就处在一个就餐的状态

就餐完了以后继续思考

这一般人你要去打游戏啊

看手机呀

打篮球啊等等

哲学家不

哲学家就是思考

所以他一共有三个状态

思考状态 饥饿状态和就餐状况

你看哲学家思考状态

饥饿状态 就餐状态

这三个变迁就是这一个哲学家

他的完整的行为描述

这个餐桌上有什么呢

餐桌上只有五把叉子

这五把叉子呢

每一把放在相邻的两个哲学家之间

也就是说这个叉子呢

是相邻的两个哲学家共享的

哲学家要想就餐

必须要同时能够使用

他左右两边的两把叉子

他才能够就餐

这是告诉我们的

那么桌子上有没有菜有没有饭呢

这个是我们不关心的问题

还记得我们讲的那个四个步骤吗

我们要想把实际问题

给它抽象成一个petri网系统

我们必须要把那些

与我们的目的无关的忽略掉

所以这个地方呢

就有没有菜 中餐还是西餐

咱们不关心了

是吃完了没有

这不是我们要考虑的

这个哲学家问题呢

是一个杜撰的问题

是为了让大家思考

某一类问题杜撰出来的

为什么你到任何一个餐馆

都不可能只给你一把叉子

让两个人用是不是

所以这是个杜撰的问题

这问题到底是什么

计算机系的操作系统里面

把它当做一个思索问题

因为很容易

如果每个哲学家同时都饿了

每个人伸出右手就拿了一把叉子

结果呢谁也吃不成

这就叫思索

它是不是个思索的问题

我们以后再说

我们先看看这个地方

我们要想知道的就是活性

这个系统是不是活的

你看啊这个哲学家要想就餐

他必须要饿了

左边的叉子右边的叉子

他都可以供他使用

他就可以就餐了对吧

那么五个人在餐桌上的情况就是这样

就是用petri网来描述就是这样的

那么现在当然没有冲突

因为大家都在思考

我们来分析它的有界性

那么不管你怎么了

变迁怎么发生

它始终每个s元素里面只有一个token

所以它的这个是个有界系统

它的界呢是1

另外它是不是活的它是活的

这个我也不去仔细分析了

你去这个移动移动那个token试试看

它是活的

任何一个变迁在任何一个标识下

要么现在就能发生

要么在将来发生

但是有一种可能性

我要提醒大家注意

就是这里面有一种可能性是什么呢

其他的哲学家都一直在思考

他们就不想吃

然后其中一个哲学家

他是反复的去就餐

思考 饥饿 就餐

也就是说这三个变迁

构成的一个无穷序列

是我们这个系统的一个无穷变迁序列

其他哲学家都按住不动

不管他是自愿还是不自愿的

反正这是一种可能性

就是一个哲学家反复的

以至于到无穷多次的饥饿就餐思考

这里有一个无穷的变迁序列

所以我们注意这就是

这个无穷变迁序列呢

它有它的例子的

那么这个无穷变迁序列

用来干什么呀

在文献里面用它来定义公平性

说一个系统什么叫做公平的呢

如果这个系统里面

不存在无穷变迁序列

在这个无穷变迁序列当中

有的变迁只出现有限多次

有的变迁出现了无穷多次

不公平吗 对不对

那么刚才那个哲学家问题我们看了

就一个哲学家可以反复的

去就餐呐 就餐呐 就餐呐

其他哲学家可以不动

这是一种可能性

那么这种公平性的定义合理吗

咱们想想看合理吗

这个5个哲学家没有一个是VIP

也没有一个受到歧视

那么为什么你说他不公平呢

所以这个我们就提出的疑问

这个公平的定义是不公平的

但是这个这种定义啊

在我们的社会当中是客观存在的

大家为什么接受它客观存在的

说你这辈子过的不舒坦是不是

你觉得别人比你好

太不公平了这个社会

这社会上怎么跟你说呢

宗教里怎么跟你说呢

别着急善有善报恶有恶报

等着吧

这辈子不行下辈子

轮回吗是不是

那个轮回就变成无穷了是不是

你这辈子等不到好命运

下辈子下辈子不行再下辈子

反正一直无穷

所以无穷从哪来的从这而来

所以这种公平性

实际上是替社会上的不公平

找一个解释

我们要的公平就是就在这个社会

公平不公平

有人说了

社会上不可能有绝对的公平

我告诉你我们要的不是绝对的公平

我们要的是一个对公平性的一个度量

你说我公平

在什么程度上公平呢

我给他两块钱

只给你一块

这就是规律

我始终给他两块给你一块

公平不公平 不公平

但是公平不公平在什么地方

不公平的明处我告诉你

他是2你是1

你别给我推到下辈子去

下辈子我等不着是不是

所以这个公平性呢

我们将来在讲到同步距离

同步论的时候

我们会重新的定义这个公平性

我们会给公平性一个定量的描述

这个定量的描述

当然我不能给它固定死了

说只能这么定义可以商榷

这个呢就是我们研究自然科学

和社会科学可以结合在一起

解释一些这个社会现象

这个以后我还会专门提到这个问题

那么教堂婚礼是公平的

新郎新娘对吧他是公平的

不可能有一个新娘结了无穷多次婚

那么新郎一个都没出现

那就奇怪了是不是

所以教堂婚礼呢

按照它这个定义是公平的

不存在那样的无穷的现象

刚才看见的那个哲学家系统

明明没有歧视没有VIP

他偏偏说他是不公平的

所以这个定义呢是有问题的