《Petri网导论》PDF电子书

所需积分/C币:23 2018-04-08 15:56:07 12.86MB PDF

Petri网导论的扫描版电子书。Petri网是分布式系统的建模和分析工具,它特别便于描述系统中进程或部件的顺序,并发,冲突以及同步等关系。
本书是在作者从事Petr网理论课程教学的基础上写成的。书中大部分题材都在作者编 写的讲义中采用过。教学的对象主要是硕士研究生。在教学过程中,不少研究生指出了讲 义中存在的些不妥之处。一些研究生在课程学习之后,对某些问题展开了研究工作,他 们的一些研究成果也被收入本书中。方欢、孙琳、徐誉尹和吴振寰等,为本书稿的打印和 排版付出了艰辛的劳动。在此也…并向他们表示感谢 在此要感谢机械工业出版社华章分社。该分社温莉芳总编的真诚约稿和热情支持,使 我鼓起了撰写本书的勇气,并使本书得以付梓。 由于水平有限,书中可能会有一些错误和不妥之处,敬请专家和读者指正。 吴哲辉 作者简介 吴哲辉1941年3月生于广东省连州市,1965年毕业于中山大学数学力 学系。1981年到1983年在美国芝加哥伊利诺伊大学作访问学者,学习计算机 科学理论,从那时起开始从事 Petri网理论及应用的研究工作。现任山东科技 大学教授、博士生导师,中国计算机学会Peti网专委会主任 从1987年开始,他主持承担过关于Peti网理论和应用研究的6项国家自然 科学基金项目,在《中国科学》、《科学通报》、《计算机学报》、《软件学 报》、《 Journal of the franklin institute》、《 International journal of mathematics and Computer Science》等国内外学术刊物发表学术论文10余篇,获得过原国 家教委、煤炭部和山东省的4项省部级科技奖。先后被评为国家级有突出贡献 的中青年专家、山东省专业技术拔尖人才、全国模范教师等。 下面照片是2003年CA.Peti博士(中)到北京讲学时,作者(右)同北京 大学袁崇义教授(左)合影。 目录 前盲 4.5死锁与陷阱 ………88 作者简价 4.6结构公平性 ∴…9! 4.7结构活性和活性单调性 第1章网与网系统 思考与练习(4) 1.1网与子网 参考文献(4)……………………………100 2标识网与网系统 6第5章一些Peri网子类的动态性质分析 1.3库所变迁系统与加权 Petri网 和判定… 14基本网系统与条件事件系统 12 51标识S-图 05 1.5并发与冲突 暑◆昏 ………14 52标识-图… 107 151并发 4 53标识自由选择网… …I12 1.52冲突 16 54标识加权T—图………………12l 153一般Per网中的并发与冲突… 18 55含本征二级活变迁的Petr网剖析…28 16系统的Per网模型… 9 56可达性等价于状态方程可满足性 思考与练习(1)… 23 的 Petri阙子类 136 参考文献(l) 24 561活的标识T-图……………………136 第2章Peri网的动态性质 27 562行为等价于活的标识r一图的 21可达性、可逆性和可覆盖性 网系统 ………………I39 22有界性和安全性… 28 5.63活的加权T-系统… ……14l 23活性 30 57唯一可达向量网系统与状态方程 24公平性…… 求解 …………………144 25持续性 42 571唯一可达向量网系统及其状态 思考与练习(2) …42 方程求解 I45 参考文献(2)……… 5.72把一般Peri网转化为唯一可达 第3章 Petri网的分析方法 向量网系统 31可达标识图与可覆盖性树 思考与练习(5) 152 32关联矩阵与状态方程 ‘“4甲·和 参考文献(5)…………………………153 33变迁发生序列与Pet网语言 58第6章 Petri网运算………………!57 34Peti网进程 65 61插入… …………………l57 思考与练习(3) -68 611插人控制器 …158 参考文献(3) 69 61.2插人计数器 第4章 Petri网的结构性质 73 613插人基本元素的补元素 16 41结构有界性和守恒性 7362删除… 162 42可重复性和协调性 …………76 63替换… …∴I64 43S-不变量和T不变量… 64化 ■甲q·即自■■p山d■■口口■d口p口P口■口 ……l67 4.4可重复向量 86 65合成 6 9 6.51共享合成…… ……∴…169 9.5任务调度问题的时延Per网方法…232 6.52同步合成 96多媒体系统中媒体流间同步合成 66分解 173 的时间Pe网分析方法 …238 6.61Pet网的公平分解 I74 961作为媒体流间同步模型的时间 662其他分解运算 …177 Petri网… 239 思考与练习(6) 77 962作为媒体流的时间Peti网的同步 参考文献(6) 合成 ■■·司甲·■ 240 第7章高级Peti网 18 963同步变迁的同步层次判定……242 71颜色Petr网… I81 97随机 Petri网 247 7,1,1简单的颜色 Petri网… I81 思考与练习(9)…………………249 712颜色Peti网的一般定义 参考文献(9) 249 72谓词/变迁网系统 l88第10章其他 Petri网变形模型简介……25l 721简单的谓词变迁网系统 88 10.1受控 Petri阙 …251 2.2谓词/变迁网系统的一般定义…192 102自控网系统… 255 思考与练习(7) 193 103时序Peri阙 257 参考文献(7)… …94 104连续 Petri网 第8章增广 Petri网… 197 10.5模糊 Petri网 …264 81带抑止弧的Petr网……… l97 思考与练习(10) 82系统的增广 Petri网模型举例……207 参考文献(10)… …266 821逻辑电路和时序电路的增广 Petri 第11章并发论 269 模型… 201 11.1并发结构的基本定义…… 269 8.22算术运算的增广Peti网模型…205 112并发结构的最简性 83其他类型的增广 Petri网 209 13并发结构的相干性和自然非序 274 8.31带约束集的Per网 ∴…209 114并发结构的稠密性 ……276 832含异或变迁的Petr网 11.5并发结构的拓扑学性质 278 833变迁含优先数的 Petri网 -2I 16并发结构上的连续性质 280 思考与练习(8)… 212 参考文献(11) 283 参考文献(8)…………… 212第12章同步距离… 265 第9章含时间因素的Pet网 215 121同步距离概念的实际背景………28 91时间Peri网 ………2l5 122Peri网中的同步距离定义 287 92时延 Petri网 …………277 123对同步距离定义进一步修改的建议…29 93求解肯定型工程问题的时延Petr网 124某些Pet子类中的同步距离计算…295 方法 ·220 24.1标识S图中的同步距离计算…295 931肯定型工程问题的Pet网模型…220 1242标识7图中的同步距离计算…297 932根据网系统模型对肯定型工程 考文献12) 300 问题进行分析 222 记号注释… ……303 94求解非肯定型工程问题的时间 Petri 索引 网方法… 227 第1章网与网系统 1.1网与子网 re网是用于描述分布式系统的一种模型。它既能描述系统的结构,又能模拟系统 的运行。描述系统结构的部分称为网(net)。从形式上看,一个网就是一个没有孤立 结点的有向二分图 定义1.1满足下列条件的三元组N=(S,7;F)称作一个网 1)SUT≠ 2)S∩T=的 (12) 3)F(SxT)U(T×S) 4)dom(F)∪cod(F)=SUT (14) 其中 dom(F)={x∈SuT|∈S∪m:(x,y)∈F} cod(F)={x∈S∪Ty∈S∪T:(3,x)∈F (1.2)式指出,S和T是两个不相交的集合(一般情况下可假定它们为有限集),它 们是网N的基本元素集。S的元素称为S-元或库所( place),也称为位置,T的元素 称为T-元或变迁( transition),F是网N的流关系( fow relation)。用图形来表示一个 网时,把一个S-元画成一个小圆圈,一个T-元画成一个小矩形。对x,y∈S∪T,若 (x,y)∈F,则从x到y画一条有向边。(1.3)式指出,有向边只存在于小圆圈和小矩形 之间,任意两个小圆圈之间或任意两个小矩形之间都没有有向边相连接。(14)式指出, 一个网中不应有孤立结点。 定义12设N=(S,们;F)为一个网。对于x∈SUT,记 x={yy∈S∪T∧(y,x)∈F} 1.7) x={yy∈SuT∧(x,y)∈F} (18) 称°x为的前集或输入集,x·为x后集或输出集。称·∪x·为元素x的外延。□ 显然,一个库所的外延是变迁集T的一个子集,一个变迁的外延是库所集S的一个 子集。对ⅵ∈SuT,x的外延·x∪·都不可能是空集(否则x就是一个孤立结点)。 第1章网与网系统 例11图11是一个网N1=(S,T;F)的图形表示,其中 {s1,82,s3,s4} T={九1,t2,t3,t4} {(s1,t2),(82t1),(82,t4),(s3,t3),(s3, (s4,t3),(t1,s1),(t2,82),(t2,83),(t,81),(th,s4)} 图1.1网M1 对于库所81,它的前集和后集分别为 而变迁t2的前集和后集分别为 t2={8},={82,83 易知,在一个网N=(S,T;F)中,对任意t∈T和任意s∈S, t∈·s当且仅当8∈t ∈s·当且仅当s∈ 从图1.1可以看出,在网N1中对任意m∈SUT都有·x≠且x°≠ 图12网N2 图12是另一个网N2的图形表示。从图形表示可以看出,在网N2中 定义13设N=(S,;F是一个网。 1)若V∈SUT w∩x·= 则称N为一个纯网( pure net)。 11网与子网 2)若Va,y∈SUT, (。a=°y)∧(x·=y°)→x=y 则称N为一个简单网( simple net) 3)若∨8∈S, (1.11) 则称N为一个T-图( T-graph) 4)若∈T, (1.12) 则称N为一个S-图( S-graph)。 5)若比1,切∈T(≠t) t1∩·t≠的→+1=t2l (1.13) 则称N为一个自由选择网(free- choice net) 6)若V1,t∈T(t1≠t2), ∩°t≠的 (114) 则称N为一个扩充的自由选择网( extended free-choice net) 例12容易验证,图1.1所示的网N1和图12所示的网N2都既是纯网,又是简 单网。因为它们的每个基本元素(库所或者变迁)都满足(1.9)式,每两个不同的基本 元素都没有相同的外延(即(1.10)式中逻辑蕴含运算符“→”左边的条件只有当x和y 是同一元素时才成立)。 图13的网N不是纯网,因为库所s和83以及变迁t1和t都不满足(1.9)式 在网N3中,81和1互以对方为前集元素和后集元素(输入和输出),我们说它们 形成个自环。同样,s3和t也形成一个自环。可见,纯网就是不含自环的网 图14的网N4不是简单网,因为在N4中,t和t是两个不同的变迁(t2≠t3), 但它们有相同的前集和相同的后集(=·∧t=均),从而N4不满足(1.10)式 S3 图13网N3 图14网N4 图14的网N4是一个S-图,因为对N4的每一个变迁t(i∈{1,2,3,4}),都有 °tl|={=1。但M4不是T图,因为库所1和不满足(1.11)式的条件 第1章网与网系统 从图形表示中可以看出,网N1,N2和N3都既不是S-图也不是T-图。 图13的网N3和图1.4的网N4都是自由选择网。在网N3中,只有一对变迁t1和 t2使得°1∩°t≠0,而它们都只以一个库所1为前集元素(°t2|="ta=1)。同样 的情况出现在网N4中的变迂对t2和t3。 图11所示的网N1不是自由选择网。因为在N1中,°1n°t4≠⑩,但|t4|=2。 此外·t3∩°t4≠,而ts=2且°t4=2。 在图12的网N2中,对任意t,t(,j∈{1,2,3}且a≠j)都有·tzn∩=。也 就是说,在(1.13)式的逻辑蕴含式中,蕴含运算符“→”左边的逻辑值对网N2来说恒 为假,根据逻辑蕴含式的取值,(1.13)式的值对网N2来说恒为真。因此,N2也属于自 由选择网的范畴。 在图15的网N中,°∩°≠0,而°1=2且|t2|=2,因此网N5不是自由 选择网。但我们注意到 81,8 即N5满足(1.14)式,从而N5是一个扩充的自由选择网。 t2 S4 图15网N5 显然,自由选择网是扩充的自由选择网的一种特殊情形。 定义14设N=(S,T;F)为一个网 1)Na=(T,S;F)称为网N的对偶网( dual net); 2)N-1=(S,T;F-1)称为网N的逆网( inversed net),其中 (x,y)|(9,x)∈F} 把一个网中的全体库所改换为变迁,全体变迁改换为库所就得到这个网的对偶网。 个网的逆网就是把网中的全体有向边的方向倒置所得到的网。 定义15设N=(S,T;F)为一个网。如果 S1S,7∈T (1.15) F1=(S1×1)∪(T1×S1)∩F

...展开详情

评论 下载该资源后可以进行评论 5

LOOKAUST 这书值得收藏
2019-05-19
回复
qintaotao123 不错,值得拥有!五星好评
2019-05-01
回复
zjxiaos 比较难懂,硬着头皮读
2018-11-11
回复
txj_wf 内容太深奥,看不懂
2018-09-02
回复
当年老王 内容清晰,不错的资源~~
2018-07-10
回复
img
  • 签到新秀

    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 分享学徒

    成功上传1个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐