Petri网不可达标识的判定方法研究及其在死锁检测中的应用

doi:10.13196/j.cims.2016.02.019

计算机集成制造系统 ›› 2016, Vol. 22 ›› Issue (第2期): 465-475.DOI: 10.13196/j.cims.2016.02.019

Petri网不可达标识的判定方法研究及其在死锁检测中的应用

鲁法明^1,2,曾庆田³⁺,段华⁴,彭延军¹,包云霞⁴

1.山东科技大学信息科学与工程学院
2.同济大学嵌入式系统与服务计算教育部重点实验室
3.山东科技大学电子通信与物理学院
4.山东科技大学数学与系统科学学院

出版日期:2016-02-29 发布日期:2016-02-29
基金资助:
国家自然科学基金资助项目(61170079,61202152,61472229,61502279);山东省科技发展资助项目(2014GGX101035,ZR2015FM013);山东省优秀中青年科学家科研奖励基金资助项目(BS2014DX013);同济大学嵌入式系统与服务计算教育部重点实验室开放课题基金资助项目(ESSCKF201403);山东科技大学科研创新团队支持计划与领军人才计划资助项目;山东省高等学校青年骨干教师国内访问学者资助项目。

Decidability method of Petri net non-reachability marks and its application in deadlock detection

Online:2016-02-29 Published:2016-02-29
Supported by:
Project supported by the National Natural Science Foundation,China(No.61170079,61202152,61472229,61502279),the S &T Development Fund of Shandong Province,China(No.2014GGX101035,ZR2015FM013),the Scientific Research Award Foundation for Outstanding Young Scientists of Shandong Province,China(No.BS2014DX013),the Open Project Foundation of Key Laboratory of Embedded System and Service Computing,Ministry of Education,Tongji University,China(No.ESSCKF201403),the SDUST Research Fund,China,and the Domestic Visiting Scholars Program for Young Teachers of Shandong Colleges and Universities,China.

摘要/Abstract

摘要： 为进行系统死锁检测,对Petri网特定标识的不可达性判定方法进行研究。对基于虹吸管、陷阱、S-不变量、加模S-不变量等结构特性以及基于状态方程解存在性的不可达标识判定方法进行分析,研究了上述方法可以判定的不可达标识之间的相互关系,建立了Petri网不可达标识的分类体系,为更好地进行标识不可达性判定提供了理论依据。分别结合哲学家就餐问题和一个跨组织协同业务流程Petri网模型的死锁状态,检测说明了标识不可达判定方法的应用。

关键词: Petri网, 可达性分析, 不可达标识分类, 死锁检测

Abstract: To make deadlock detection,the method for non-reachability decidability in specific mark of Petri net was researched.The decision method for non-reachability was analyzed based on solution existence of state equations and structural characteristics such as siphons,traps,S-invariants,modular S-invariants.The relationship of those non-reachable marks which could be decided through different non-reachability analysis method was discussed.A taxonomic hierarchy of Petri net non-reachable marks was established,which provided theoretical support for non-reachability decidability.In addition,the proposed method was applied to detect the deadlock state of two Petri nets which were used to model the dining philosophers problem and a cross-organizational collaborative business processes.

Key words: Petri nets, reachability analysis, non-reachable marks classification, deadlock detection

中图分类号:

TP301

鲁法明,曾庆田,段华,彭延军,包云霞. Petri网不可达标识的判定方法研究及其在死锁检测中的应用[J]. 计算机集成制造系统, 2016, 22(第2期): 465-475.

[1]	鲁法明,崔明浩,包云霞,曾庆田,段华. 基于程序运行轨迹Petri网模型挖掘的死锁检测方法[J]. 计算机集成制造系统, 2021, 27(9): 2611-2624.
[2]	王丽丽,方贤文. 基于行为距离的带隐变迁过程模型挖掘方法[J]. 计算机集成制造系统, 2021, 27(9): 2670-2679.
[3]	张海军,闫琼,张国辉,李庆宇,余杰. 基于数字孪生的制造资源动态优选决策[J]. 计算机集成制造系统, 2021, 27(2): 521-535.
[4]	李文川,高思源,章鑫,冯良清. 基于随机Petri网的企业RFID技术采纳内化建模与仿真[J]. 计算机集成制造系统, 2020, 26(第2): 470-480.
[5]	何彦,陈文奇,王禹林,岳冠楠,李育锋,田小成. 集成设计参数和制造参数的车削工件机加工能耗预测方法[J]. 计算机集成制造系统, 2020, 26(9): 2355-2366.
[6]	张立彬,吕焕培,胥芳,谭大鹏,陈教料,林琼. 面向低压电器的CPN协同装配任务建模与优化[J]. 计算机集成制造系统, 2020, 26(7): 1737-1748.
[7]	刘聪,程龙,曾庆田,闻立杰,欧阳春. 基于Petri网的分层业务过程挖掘方法[J]. 计算机集成制造系统, 2020, 26(6): 1525-1537.
[8]	黄苾,代飞,王亚博,莫启,曹涌,王雷光. 基于Petri网分析编排的可实现性[J]. 计算机集成制造系统, 2020, 26(6): 1548-1556.
[9]	韩咚,田银花,杜玉越,张琴. 基于Petri网可达图的业务对齐方法[J]. 计算机集成制造系统, 2020, 26(6): 1589-1606.
[10]	郝惠晶,方贤文,方娜,许健. 基于Petri网的业务流程低频行为挖掘与优化分析[J]. 计算机集成制造系统, 2020, 26(6): 1660-1667.
[11]	田银花,杜玉越,韩咚,刘伟. 基于Petri网的事件日志与过程模型对齐方法[J]. 计算机集成制造系统, 2019, 25(第4): 809-829.
[12]	王颖,周晓宇,王钊,张学馨,陈丽娇. 基于Artifact生命周期的业务流程一致性检查[J]. 计算机集成制造系统, 2019, 25(第4): 856-863.
[13]	滕苑秀,杜玉越,王路. 循环并发结构的过程模型修正方法[J]. 计算机集成制造系统, 2019, 25(第4): 882-893.
[14]	方欢,段瑞,詹悦. 基于后继关系的行为块过程挖掘方法[J]. 计算机集成制造系统, 2019, 25(第4): 901-908.
[15]	陈文冲,刘洪伟,齐二石,刘伟. 离散串联生产系统物理与信息过程匹配机理[J]. 计算机集成制造系统, 2019, 25(第11): 2923-2934.

Petri网不可达标识的判定方法研究及其在死锁检测中的应用

Decidability method of Petri net non-reachability marks and its application in deadlock detection

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics