基于二叉决策图的Petri网可达集遍历和死锁研究
发布时间：2022-01-23 18:59
系统可达状态数通常随着Petri网的规模呈指数级增长,所以Petri网的状态组合爆炸问题,已成为Petri网应用的重要瓶颈。因此,如何以较小的时间和空间,快速求解系统Petri网可达状态集和严格极小信标集对Petri网在较大规模系统中的应用具有重要意义。严格极小信标的求解对于死锁的预防处理起关键作用。本文研究了二叉决策图（BDD）在Petri网领域的相关应用,提出了基于BDD快速求解Petri网严格极小信标的方法,并优化了可达集和极小信标的求解算法。首先,本文针对现有基于BDD求解Petri网可达集的算法,存在单个变迁传参和处理导致频繁调用子函数的不足,提出了多个变迁集合化传参与处理的方法,达到了大幅度减少子函数调用次数进而加快对可达集的求解的目的。然后,鉴于现有的文献中还没有使用BDD求解严格极小信标的方法,本文提出了基于BDD快速求解严格极小信标的方法。该方法便于理解和实现,直接使用BDD求解并处理Petri网的极小信标和陷阱,从而获得严格极小信标。并且只需要较少的求解时间和存储空间,且适用于大规模Petri网模型。另外,研究发现现有的基于BDD求解极小信标的算法,在判断信标间包含...
【文章来源】：南京理工大学江苏省 211工程院校
【文章页数】：65 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
1 绪论
1.1 研究背景与意义
1.2 相关技术研究进展
1.2.1 Petri网的发展
1.2.2 BDD的发展和应用
1.2.3 死锁的研究与处理
1.3 本文主要研究内容
1.4 本文组织结构安排
2 基本知识与概念
2.1 Petri网基本知识
2.1.1 Petri网的基本定义和性质
2.1.2 信标与陷阱的基本定义和性质
2.2 布尔代数
2.3 二叉决策图
2.3.1 二叉决策图的定义
2.3.2 二叉决策图的压缩规则
2.4 本章小结
3 Petri网可达集的符号化求解
3.1 可达集的基本概念
3.2 标识的符号化表示
3.3 可达集求解算法研究
3.4 可达集的求解实例
3.5 本章小结
4 Petri网严格极小信标的符号化求解
4.1 极小信标的符号化
4.1.1 信标和陷阱的符号化表示
4.1.2 信标的符号化求解
4.1.3 极小信标的符号化求解
4.2 陷阱的符号化求解
4.3 严格极小信标的符号化求解
4.4 本章小结
5 基于BDD符号化求解的实现
5.1 Petri网严格极小信的标求解流程
5.2 求解Petri网相关结构特征的仿真软件
5.2.1 基本结构和使用
5.2.2 软件运行函数描述
5.2.3 软件的输入输出
5.3 严格极小信标的求解实验
5.3.1 S~3PR模型实验
5.3.2 哲学家就餐问题实验
5.4 本章小结
6 基于严格极小信标的死锁预防
6.1 S~3PR模型死锁的预防策略
6.2 基于严格极小信标的死锁预防实验
6.3 本章小结
7 总结与展望
7.1 全文总结
7.2 研究展望
致谢
参考文献
附录
【参考文献】：
期刊论文
[1]基于BDD快速求解Petri网的陷阱和极小信标[J]. 张加浪,黄波. 解放军理工大学学报(自然科学版). 2017(03)
[2]安全Petri网事件分离状态的BDD算法[J]. 陈玉峰,李志武. 西安电子科技大学学报. 2010(01)
[3]Petri网的符号ZBDD可达树分析技术[J]. 李凤英,古天龙,徐周波. 计算机学报. 2009(12)
[4]应用Petri网的关联矩阵求最小割集的新方法[J]. 武滢,谢里阳,李进冬. 中国机械工程. 2008(09)
[5]S3PR网的一种死锁预防策略[J]. 闫明明,李志武,钟春富. 西安电子科技大学学报. 2008(02)
[6]UniNet Description of Dining Philosopher Problem[J]. DU Zhuomin1, HE Yanxiang1, ZHOU Guofu2 1. School of Computer, Wuhan University, Wuhan 430072, Hubei, China; 2. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, Hubei, China. Wuhan University Journal of Natural Sciences. 2007(06)
[7]基于面向对象智能Petri网的FMS单元控制模型[J]. 高春华. 中国机械工程. 2001(05)
[8]布尔与布尔代数[J]. 黄耀枢. 自然辩证法研究. 1985(04)
硕士论文
[1]S4PR网的严格极小信标计算及活性控制器优化方法[D]. 徐姗姗.浙江大学 2012
本文编号：3604976
【文章来源】：南京理工大学江苏省 211工程院校
【文章页数】：65 页
【学位级别】：硕士
【文章目录】：
摘要
Abstract
1 绪论
1.1 研究背景与意义
1.2 相关技术研究进展
1.2.1 Petri网的发展
1.2.2 BDD的发展和应用
1.2.3 死锁的研究与处理
1.3 本文主要研究内容
1.4 本文组织结构安排
2 基本知识与概念
2.1 Petri网基本知识
2.1.1 Petri网的基本定义和性质
2.1.2 信标与陷阱的基本定义和性质
2.2 布尔代数
2.3 二叉决策图
2.3.1 二叉决策图的定义
2.3.2 二叉决策图的压缩规则
2.4 本章小结
3 Petri网可达集的符号化求解
3.1 可达集的基本概念
3.2 标识的符号化表示
3.3 可达集求解算法研究
3.4 可达集的求解实例
3.5 本章小结
4 Petri网严格极小信标的符号化求解
4.1 极小信标的符号化
4.1.1 信标和陷阱的符号化表示
4.1.2 信标的符号化求解
4.1.3 极小信标的符号化求解
4.2 陷阱的符号化求解
4.3 严格极小信标的符号化求解
4.4 本章小结
5 基于BDD符号化求解的实现
5.1 Petri网严格极小信的标求解流程
5.2 求解Petri网相关结构特征的仿真软件
5.2.1 基本结构和使用
5.2.2 软件运行函数描述
5.2.3 软件的输入输出
5.3 严格极小信标的求解实验
5.3.1 S~3PR模型实验
5.3.2 哲学家就餐问题实验
5.4 本章小结
6 基于严格极小信标的死锁预防
6.1 S~3PR模型死锁的预防策略
6.2 基于严格极小信标的死锁预防实验
6.3 本章小结
7 总结与展望
7.1 全文总结
7.2 研究展望
致谢
参考文献
附录
【参考文献】：
期刊论文
[1]基于BDD快速求解Petri网的陷阱和极小信标[J]. 张加浪,黄波. 解放军理工大学学报(自然科学版). 2017(03)
[2]安全Petri网事件分离状态的BDD算法[J]. 陈玉峰,李志武. 西安电子科技大学学报. 2010(01)
[3]Petri网的符号ZBDD可达树分析技术[J]. 李凤英,古天龙,徐周波. 计算机学报. 2009(12)
[4]应用Petri网的关联矩阵求最小割集的新方法[J]. 武滢,谢里阳,李进冬. 中国机械工程. 2008(09)
[5]S3PR网的一种死锁预防策略[J]. 闫明明,李志武,钟春富. 西安电子科技大学学报. 2008(02)
[6]UniNet Description of Dining Philosopher Problem[J]. DU Zhuomin1, HE Yanxiang1, ZHOU Guofu2 1. School of Computer, Wuhan University, Wuhan 430072, Hubei, China; 2. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, Hubei, China. Wuhan University Journal of Natural Sciences. 2007(06)
[7]基于面向对象智能Petri网的FMS单元控制模型[J]. 高春华. 中国机械工程. 2001(05)
[8]布尔与布尔代数[J]. 黄耀枢. 自然辩证法研究. 1985(04)
硕士论文
[1]S4PR网的严格极小信标计算及活性控制器优化方法[D]. 徐姗姗.浙江大学 2012
本文编号：3604976
本文链接：https://www.wllwen.com/guanlilunwen/lindaojc/3604976.html
