petri网导论

【实例简介】
petri网导论，吴哲辉，pdf版。抓紧下载
重点天摩计算机教材 Petr网导论 吴哲辉著 许才阴中 t D是验 Q 机械工业出版社等 China Machine Press 0)Fie. LF 本书是作者在从事 Petri网理论课程教学的基础上操写而成,主要介绍Per例的基本原 理和基本分析方法,以及这些原理和方法在对实际系统进行建模和分析中的应用,同时也 包含了一部分作者自己的研究成果。主要内容包括:Petr网的基本概念、基本性质和基本 分析方法,各种常见的Per网的变型模型,通用网论中并发论和同步论的基本内容等。 本书可作为高等院校计算机专业、自动化专业的研究生或高年级本科生教材,也可供 相关技术人员参考。 版权所有,慢权必究。 本书法律顾问北京市展达律师事务所 图书在版编目(cIP)数据 Petri网导论/吴哲辉著.-北京:机械工业出版社,2006.4 (重点大学计算机教材) ISBN7-111-18278-2 I.P…·Ⅱ.吴…Ⅲ计算机网络-高等学校-教材Ⅳ.TP393 中国版本图书馆CIP数据核字(2006)第019926号 机械工业出版社(北京市西城区百万庄大街22号邮政编码100037 责任编辑:李伯民 北京牛山世兴印刷厂印刷·新华书店北京发行所发行 2006年4月第1版第1次印刷 787mmx1092mm1/16·20印张 定价:35.00元 凡购本书,如有倒页、脱页、缺页,由本社发行部调换 本社购书电话:(010)68326294 前言 Petri网是分布式系统的建模和分析工具。它特别便于描述系统中进程或部件的顺序、 并发、冲突以及同步等关系。同其他系统网模型相比较,对真并发的恰切描述是 Petri网的 独特优势。 Petri网的概念是1962年由德国科学家 Carl adam petriz在他的博士论文“ Kommunikation mit automaten(用自动机通信)中首先提出来的。为了使并发这一概念直观化,论文中 提出了一种用于描述物理进程和物理系统的组合的网状模型。由此发展起来的一类系统模 型,后来被人们称之为Pet网。20世纪70年代初, Petri网的概念和思想方法受到欧美学者 的广泛关注。对 Petri刚的各种性质的研究,以及把Petr网应用于各种实际系统的建模和性 质分析的论文和研究报告开始大量涌现。经过40多年的发展,不仅Peri网理论本身已形成 门系统的、独立的学科分支,而且 Petri网在计算机科学技术(如操作系统、并行编译 网络协议、软件工程、形式语义、人工智能等),自动化科学技术(如离散事件动态系统 混杂系统等),机械设计与制造(如柔性制造系统),以及其他许多科学技术领域,都得到 广泛的应用。 Petri网理论的发展必将为信息论奠定坚实的理论基础。 作为一种系统模型, Petri网不仅可以刻画系统的结构,而且可以描述系统的动态行为 (如系统的状态变化等),Peri网既有直观的图形表示,又可以引入许多数学方法对其性质 进行分析。对于复杂的系统, Petri网可以对其进行分层描述,逐步求精,便于同面向对象 的思想方法相沟通。 应该说, Petri网的基本概念是十分简单的。借助 Petri网的图形表示,对Pen网的基本 结构和运行法则,只需半天时间就可以有个基本了解。然而, Petri网理论的内涵又是十分 丰富的。对 Petri网的各种性质进行分析,除了对 Petri网的运行规律要有深刻的理解外,还 需要在线性代数、图论、形式语言理论、逻辑学等方面有坚实的基础。至今,对 Petri网的 若干重要性质普遍适用的判定条件或判定算法尚未得到。即使是对某些Petr网子类给出了 相应的判定方法,也大多转化为线性方程组或线性不等式的整数解求解问题,网的局部结 构的求解问题,或者合法变迁序列的求解问题。对这些求解问题设计出有效算法也往往不 是轻而易举的事。至于通用网论,则是信息科学中的进程理论和方法同近代与现代物理的 时空观的有机融合。 c.A. Petri提出 Petri网这种系统模型,其目标是想用一种兼容物理和计 算机科学两者的语言和概念构架来形式描述制约通信进程的所有“自然法则”。这一宏伟计 划也尚未完全实现。 可以说, Petri网理论是一种易懂难精的学问。这一点类似于围棋。 Petri教授把他提出 Peri网概念这件工作戏称为发明了一种借助图形符号和小石子来玩的游戏。我体会也含有 这样的一层意思。 科学理论的生命力在于应用。 Petri网理论之所以能够得到长足的发展,也是因为它在 许多应用领域显示出很强的建模和分析能力。从事 Petri应用研究的工作者,除了应是其应 用领域的专家以外,还要求对 Petri网的基本概念、基本原理和基本分析方法有较系统的了 解。可以见到一些 Petri网应用论文,为了描述某些实际系统,往往在原型Petr网的基础上 添加上许多个“元”,提出所谓的新型Peri网,而作者并未对“新型Petr网”的分析方法进 行讨论,就下结论说这个网系统具有哪些性质。人们无从知道这些结论是怎么得到的。其 实,网系统模型越复杂,对其性质的分析就越困难(尽管加入一些新“元”能对实际系统 的描述带来一些方便)。当网模型中对一些“元”有很苛刻的限制条件,或者对其中一些 “元”不能给出形式化的表述时,即使只想用劂模型对实际系统作一些运行仿真研究,也是 难以做到的。因此,在从事 Petri网的应用研究时,即使只想用Per网作为实际系统的描述 和分析工具(而不准备对Petr网理论本身进行研究),也需要对Per的基本原理和基本分 析方法进行较系统的学习和了解。 本书主要介绍 Petri阏的基本原理和基本分析方法,以及这些原理和方法在对实际系统 进行建模和分析中的应用。全书共12章,大致可以分为三个部分。第一部分是前6章。这部 分以原型Petr网为主要对象,介绍Peti网的基本概念、基本性质和基本分析方法。我以为, 作为学习 Petri网理论的第一步,学习和掌握这部分内容是必要的。这些内容虽然是针对原 型Peri网展开讨论的,但所提出的原理和方法具有普遍意义。有些应用问题可能使用变型 Peti网建模更方便。然而,对毎一种变型模型,除了其本身添加的一些特定条件外,还是 要遵循 Petri网的基本规则的。因此,对变型模型的分析方法,就是Pet网的基本分析方法 同特定条件相结合的产物。第7章到第10章属于第二部分。这部分介绍几种 Petri网的变型模 型,包括高级Peti、增广Pcri和含时间因素的 Petri网等。这些变型模型都是在Peti网 应用硏究中、为了对某些实际系统建模的需要而提出的,并且已得到较普遍的认可。对于 这些变型模型,除了介绍其基本概念以外,我们也对其分析方法进行一些讨论,并通过举 例说明怎样用这些变型模型对实际系统进行建模和分析。第三部分是第11章和第12章。这 两章对通用网论中并发论和同步论的基本内容作一简介。通用网论是Peri教授致力于架构 描述制约通信进程的自然法则的主要内容。学习和了解这一部分内容,有助于对网论的思 想精髓加深理解 只要具有离散数学和线性代数的基础知识,就可以读懂本书的大部分章节。书中也有 少量内容涉及到形式语言与自动机理论、操作系统以及数字逻辑等方面的知识。 本书可以作为一门研究生课程的教材,用60学时讲授。第1章到第4章,以及第6章是基 本内容,这5章至少需要40学时。第5章可以根据情况选取部分内容讲授,第7章到第10章可 以只讲授各种系统模型的基本概念,可以让学生根据自己的兴趣和爱好选读应用实例,教 师给以指导。第11章和第12章不作为基本教学内容,只是给那些希望学习和研究通用网论 的学生提供一个人门导引。 本书的内容中也包含了一部分作者自己的研究成果。自1987年以来,作者在Petr网领 域的研究工作一直得到国家自然科学基金的资助。正是连续近20年不断的研究工作,使我 加深了对 Petri网基本原理的理解。借本书出版之际,谨向国家自然科学基金委员会致以衷 心的感谢。在作者长期承担国家自然科学基金项目的过程中,项目课题组成员困结协作 共同研究,许多成果都是同他们合作研究得到的。这些成员中,主要有王培良教授、许安 国教授和蒋昌俊教授等。在此向他们表示衷心的感谢。 本书是在作者从事 Petri网理论课程教学的基础上写成的。书中大部分题材都在作者编 写的讲义中采用过。教学的对象主要是硕士研究生。在教学过程中,不少研究生指出了讲 义中存在的一些不妥之处。一些研究生在课程学习之后,对某些问题展开了研究工作,他 们的一些研究成果也被收入本书中。方欢、孙琳、徐誉尹和吴振寰等,为本书稿的打印和 排版付出了艰辛的劳动。在此也一并向他们表示感谢 在此要感谢机槭工业岀版社华章分社。该分社温莉芳总编的真诚约稿和热情支持,使 我鼓起了撰写本书的勇气,并使本书得以付梓。 由于水平有限,书中可能会有一些错误和不妥之处,敬请专家和读者指正 吴哲辉 作者简介 吴哲辉1941年3月生于广东省连州市,1965年毕业于中山大学数学力 学系。1981年到1983年在美国芝加哥伊利诺伊大学作访问学者,学习计算机 科学理论,从那时起开始从事Petm网理论及应用的研究工作。现任山东科技 大学教授、博士生导师,中国计算机学会Peti网专委会主任。 从1987年开始,他主持承担过关于Peti网理论和应用研究的6项国家自然 科学基金顼目,在《中国科学》、《科学通报》、《计算杌学报》、《软件学 报》、《 Journal of the franklin institute》、《 International journal of mathematics and Computer Science》等国内外学术刊物发表学术论文100余篇,获得过原国 家教委、煤炭部和山东省的4硕省部级科技奖。先后被评为国家级有突出贡献 的中青年专家、山东省专业技术拔尖人才、全国模范教师等。 下面照片是2003年CA.Peri博士(中)到北京讲学时,作者(右)同北京 大学袁崇义教授(左)合影 目录 前言 4.5死锁与陷阱……… 8 作者简价 46结构公平性 97 4.7结构活性和活性单调性……………9 第1章网与网系统 ………………………l 思考与练习(4)…… nt++99 11网与子网…………………………1 考文献(4)…… ………100 1.2标识网与网系统 …6第5章一些 Petri网子类的动态性质分析 13库所变迁系统与加权 Petri网……………9 和判定……………………………105 14基本网系统与条件事件系统…………1251标识S-图… 105 15并发与冲突 14 52标识T-图……………………………107 15.!并发………………………1453标识自由选择网 I12 15.2冲突 16 54标识加权T—图…………………121 153一般Pem网中的并发与冲突……1855含本征二级活变迁的Pe网剖析…128 1.6系统的Pet网模型………………1956可达性等价于状态方程可满足性 思考与练习(1)……………… 23 的Petr网子类……………136 参考文献(1) 24 561活的标识T一图……………136 笫2章Pei网的动态性质 27 52行为等价于活的标识T一图的 21可达性、可逆性和可覆盖性 27 网系统…………39 22有界性和安全性 曹t …………28 5.63活的加权T系统……………141 23活性………………………………30 57唯一可达向量网系统与状态方程 24公平性 ………………34 求解………………………………l44 25持续性………… 571唯一可达向量网系统及其状态 思考与练习(2)… ………………42 方程求解 …145 叁考文献(2) 572把一般 Petri网转化为唯一可达 第3章 Petri网的分析方法… 向量网系统………………………50 31可达标识图与可覆盖性树………47思考与练习(5)…………………}52 32关联矩阵与状志方程…… 参考文献(5) ……………………I53 33变迁发生序列与 Petris语言………58第6章 Petri网运算… 3.4 Petri网进程 ……………………65 6.1插人… 57 思考与练习(3) ::::..·.:·:::4:4· 611插人控制器…………………l58 参考文献(3)… “4446 612插人计数器……… 160 第4章 Petri网的结构性质…14 613插入基本元素的补元素…………161 4.1结构有界性和守恒性 62删除 l62 4.2可重复性和协调性 63替换……………………………………l64 43S-不变量和T-不变量…………7964化简 …167 44可重复向量 6.5合成……………………………169 VIll 65.1共享合成……………………1699.5任务调度问题的时延Pe网方法……232 652同步合成………………………17296多媒体系统中媒体流间同步合成 66分解……3 的时间Per网分析方法 238 661Peti网的公平分解……I74 961作为媒体流间同步模型的时间 6.6.2其他分解运算……………177 Petri网…………………………………239 思考与练习(6)…………… 96.2作为媒体流的时间Peti网的同步 参考文献(6)………………………179 合成 4·:::4:····丰· ……240 第7章高级Pei网……………………l8 9.63同步变迁的同步层次判定…242 71颜色 Petri网……………………181 97随机Peti网…… 生售·鲁和曾世 247 711简单的颜色Petr网………81思考与练习(9)… …………249 7.2颜色Peti网的一般定义…186参考文献(9)… ………………249 72谓词/变迁网系统…… 188第10章其他Petr网变形模型简介……15 7.21简单的谓词/变迁网系统… 188 10.1受控Peri网 251 722谓词/变迁网系统的一般定义……1 102自控网系统 255 思考与练习(7)………………193 103时序 Petri网 参考文献(7) 194104连续Peri网 260 第8章增广Peti网………… 19 105模糊 Petri网 264 81带抑止弧的 Petri网 ,·: …197 思考与练习(10)……………………………260 82系统的增广 Petri网模型举例……201 参考文献(10)………………………266 82.1逻辑电路和时序电路的增广 Petri 第11章并发论……… …269 模型………………………201 111并发结构的基本定义…………269 82,2算术运算的增广 Petri网模型…2051.2并发结构的最简性 …272 8.3其他类型的增广 Petri网………20911.3并发结构的相干性和自然非序 274 831带约束集的 Petri网…… #+ 114并发结构的稠密性……………276 832含异或变迁的Pe网……11.5并发结构的拓扑学性质………28 833变迁含优先数的Pet网………2l 116并发结构上的连续性质 280 思考与练习(8)… “···“+“··““和4 212 参考文献(11)…………………283 参考文献(8)………………… …212第12章同步距离………285 第9章含时间因素的Petr网…………215121同步距离概念的实际背景…285 9.1时间 Petri网…………………… 215 122 Petri网中的同步距离定义………287 92时延Petr网………………27 12.3对同步距离定义进一步修改的建议…291 93求解肯定型工程问题的时延Per网 124某些Per网子类中的同步距离计算…295 方法………………………………………220 1241标识S-图中的同步距离计算……295 931肯定型工程问题的 Petri网模型…220 1242标识T-图中的同步距离计算…2 9.32根据网系统模型对肯定型工程 参考文献(12) 300 问题进行分析…………222 记号注释 …303 94求解非肯定型工程问题的时间 Petri 索引……… ………309 网方法…… ………227 【实例截图】
【核心代码】