Petri网
更新时间:2024-06-06 14:56:01 阅读量: 综合文库 文档下载
Petri网是对离散并行系统的数学表示。Petri网是1960年代由卡尔·A·佩特里发明的,适合于描述异步的、并发的计算机系统模型。 Petri网既有严格的数学表述方式,也有直观的图形表达方式,既有丰富的系统描述手段和系统行为分析技术,又为计算机科学提供坚实的概念基础。
由于Petri网能够表达并发的事件,被认为是自动化理论的一种。研究领域趋向认为Petri网是所有流程定义语言之母。
* 经典Petri网
经典的Petri网是简单的过程模型,由两种节点:库所和变迁,有向弧,以及令牌等元素组成的。
o Petri网的结构 (1) Petri网的元素:
+ 库所(Place)圆形节点 + 变迁(Transition)方形节点
+ 有向弧(Connection)是库所和变迁之间的有向弧
+ 令牌(Token)是库所中的动态对象,可以从一个库所移动到另一个库所。
(2) Petri网的规则是: + 有向弧是有方向的
+ 两个库所或变迁之间不允许有弧 + 库所可以拥有任意数量的令牌 o 行为
如果一个变迁的每个输入库所(input place)都拥有令牌,该变迁即为被允许(enable)。一个变迁被允许时,变迁将发生(fire),输入库所(input place)的令牌被消耗,同时为输出库所(output place)产生令牌。 + 变迁的发生是原子的
+ 有两个变迁都被允许的可能,但是一次只能发生一个变迁
+ 如果出现一个变迁,其输入库所的个数与输出库所的个数不相等,令牌的个数将发生变化
+ Petri网络是静态的
+ Petri网的状态由令牌在库所的分布决定 o Petri网的形式化定义
一个经典的Petri网由四元组(库所,变迁,输入函数,输出函数)组成。任何图都可以映射到这样一个四元组上,反之亦然。 o Petri网流程建模
一个流程的状态是由在场所中的令牌建模的,状态的变迁是由变迁建模的。令牌表示事物(人,货物,机器),信息,条件,或对象的状态; 库所代表库所,通道或地理位置;变迁代表事件,转化或传输。
一个流程有当前状态,可达状态,不可达状态。 o 经典Petri网的局限性
+ 没有测试库所中零令牌的能力 + 模型容易变得很庞大
+ 模型不能反映时间方面的内容
+ 不支持构造大规模模型,如自顶向下或自底向上
* 高级Petri网
为了解决经典Petri网中的问题,研究出了高级Petri网,在以下方面进行了扩展:
o 令牌着色
一个令牌通常代表具有各种属性的对象,因此令牌拥有值(颜色)代表由令牌建模的对象的具体特征,如一个令牌代表一个工人(张三,28岁,经验3级)。 o 时间
为了进行分析,我们需要建模期间,延迟等,因此每一个令牌拥有一个时间戳,变迁决定生产出的令牌的延迟。 o 层次化
构造一个复杂性与数据流图相当的Petri网的机制。子网是由库所,变迁和子网构成的网络。 o 时序
增加时序逻辑的定义,更好的描述行为过程。
* Petri网的应用
Petri网的应用非常广泛,以下是Petri网比较常用的几种应用:
o 软件设计 o 工作流管理 o 工作流模式 o 数据分析 o 并行程序设计
o 协议验证
背景
卡尔·A·佩特里是一名物理学家,他发明Petri网主要是从物理的角度去描述并发现象的。据佩特里本人所述,他认为60年代计算机
科学的概念构架由于缺乏并发不适合于描述物理系统。其中一个重要的概念,就是Petri网里面不存在所谓的“全局时间”的概念,因为这跟狭义相对论是冲突的。相反,Petri网可以描述每一个节点的时序。
从狭义相对论的观点出发,两个时空点之间如果没有因果关系把它们连接起来(或者说“类空”的),它们就是独立的,不能说其中一个发生在前另一个在后或者相反。因此,Petri网里面的两种变迁(见下文)如果都有发生的条件,则不能认为其执行顺序有任何关系。然而,Petri网旨在描述变迁之间的因果关系,并由此构造时序。
[编辑] 经典Petri网
经典的Petri网是简单的过程模型,由两种节点:库所和变迁,有向弧,以及令牌等元素组成的。
[编辑] 结构
Petri网的元素:
? ? ? ?
库所(Place)圆形节点 变迁(Transition)方形节点
有向弧(Connection)是库所和变迁之间的有向弧
令牌(Token)是库所中的动态对象,可以从一个库所移动到另一个库所。
Petri网的规则是:
? ? ?
有向弧是有方向的
两个库所或变迁之间不允许有弧 库所可以拥有任意数量的令牌
[编辑] 行为
如果一个变迁的每个输入库所(input place)都拥有令牌,该变迁即为被允许(enable)。一个变迁被允许时,变迁将发生(fire),输入库所(input place)的令牌被消耗,同时为输出库所(output place)产生令牌。 注意:
?
变迁的发生是原子的,也就是说,没有一个变迁只发生了一半的可能性。
?
有两个或多个变迁都被允许的可能,但是一次只能发生一个变迁。这种情况下变迁发生的顺序没有定义。
?
如果出现一个变迁,其输入库所的个数与输出库所的个数不相等,令牌的个数将发生变化,也就是说,令牌数目不守恒。
?
Petri网络是静态的,也就是说,不存在发生了一个变迁之后忽然冒出另一个变迁或者库所,从而改变Petri网结构的可能。
?
Petri网的状态由令牌在库所的分布决定。也就是说,变迁发生完毕、下一个变迁等待发生的时候才有确定的状态,正在发生变迁的时候是没有一个确定的状态的。
两个变迁争夺一个令牌的情形被称之为冲突。当发生冲突的时候,由于Petri网的时序是不确定的,因此具体哪个变迁得以发生也是不确定的。实际应用中,往往需要避免这种情形。用于描述现象的Petri网也可能自然出现冲突,这表明我们对于变迁发生的条件没有完全了解。
多个弧连接两个节点的情况。在输入库所和变迁之间的弧的个数决定了该变迁变为被允许需要的令牌的个数。弧的个数决定了消耗/产生的令牌的个数。
[编辑] Petri网的形式化定义
一个经典的Petri网由四元组(库所,变迁,输入函数,输出函数)组成。 任何图都可以映射到这样一个四元组上,反之亦然。
被允许的形式化 变迁发生的形式化 Petri网到变迁系统的映射 可达性图
Petri 是一个三元组(P,T,F) F(P X T)U(T X P)是弧的集合
[编辑] 流程建模
一个流程的状态是由在场所中的令牌建模的,状态的变迁是由变迁建模的。令牌表示事物(人,货物,机器),信息,条件,或对象的状态; 库所代表库所,通道或地理位置;变迁代表事件,转化或运输 一个流程(Flow)有当前状态,可达状态,不可达状态。
[编辑] 经典Petri网的局限性
? ? ? ?
没有测试库所中零 模型容易变得很庞大 模型不能反映时间方面的内容
不支持构造大规模模型,如自顶向下或自底向上
[编辑] 高级Petri网
为了解决经典Petri网中的问题,研究出了高级Petri网,在以下方面进行了扩展:
? ?
令牌着色 -- 令牌具有属性 时间-- 变迁有延迟时间
?
层次化 -- 一个变迁可以是一个子Petri网
[编辑] 令牌着色
一个令牌通常代表具有各种属性的对象,因此令牌拥有值(颜色)代表由令牌建模的对象的具体特征,如一个令牌代表一个工人(张三,28岁,经验3级)。
[编辑] 时间
为了进行分析,我们需要建模期间,延迟等,因此每一个令牌拥有一个时间戳,变迁决定生产出的令牌的延迟。
[编辑] 层次化
构造一个复杂性与数据流图相当的Petri网的机制。 子网是由库所,变迁和子网构成的网络。
[编辑] 时序
增加时序逻辑的定义,更好的描述行为过程。
正在阅读:
Petri网06-06
2022年空军工程大学566计算机专业基础综合之计算机网络复试仿真04-11
八卦口诀图解03-08
作业答案03-16
《清稗类钞》服饰类04-12
高二英语期末测试题_305-01
当前我国房地产信托融资分析05-20
基于SNMP的网络性能监测系统设计05-11
关于社会道德滑坡与诚信缺失的思考09-24
- 必修一物理寒假作业
- 2019-201X年5月大学生入党积极分子思想汇报-word范文模板(3页)
- 药物分析习题五
- 重拾应用意识 体会数学价值(沈建军)
- 2017全国高校辅导员结构化面试题集及参考答案
- 广东徐闻县实验中学2014届高三第二次月测地理试题
- 今天你共鸣了么?
- 2018-2019正能量读后感1000字-推荐word版(6页)
- 2018年中国截切型盖板针布行业专题研究分析报告目录
- 中国移动业务处理流程大全
- 公文写作常用词汇和句子集锦2016
- ARM课程设计说明书
- 教师资格证教育学论文
- 中考试卷分析
- 环境监测试卷(五)
- 党风廉政建设广播稿1
- 快速制作香香宫煮麻辣烫教程
- 《国际金融学》习题
- 文明施工保障措施方案
- 春兰维修资料故障代码
- Petri
- 微电极及其应用
- 病理科规章制度
- (精品)企业人才招聘现状问题及趋势研究毕业论文
- HTZZ-50A感性负载直流电阻快速测试仪
- 初中数学八年级下册《相似三角形的判定和性质》
- 云南艺术学院学士学位论文封面
- 湖南省湘潭凤凰中学高二数学小题训练
- 充分利用教学资源,提高基础薄弱学校的英语教学水平
- 中国石油大学华东现代远程教育《安全原理》在线作业
- 中国传统文化概观形成性考核作业册简答题
- 二年级语文阅读练习、看图写话(含答案)(2)
- 案例分析:大班幼儿之间的冲突
- 市场比较法是指将估价对象与估价时点近期有过交易的类似房地产进
- 南京农业大学科技工作手册
- 2050.阳泉煤业(集团)有限责任公司寺家庄矿边坡支护工程施工组织
- 电力系统自动装置-复习思考题
- 关于印发重点监控药品管理制度的通知
- 第1单元 课时1 补充习题
- 我国旅游网站存在的问题
- 专题15 完形填空之记叙文类-3年高考2年模拟1年原创备战2018高考