主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2022年专刊出版计划 微信服务介绍 最新一期:2021年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
郝宗寅,鲁法明.Petri网的反向展开及其在程序数据竞争检测的应用.软件学报,2021,32(6):15-0
Petri网的反向展开及其在程序数据竞争检测的应用
Reverse Unfolding of Petri Nets and its Application in Program Data Race Detection
投稿时间:2020-08-31  修订日期:2020-10-26
DOI:10.13328/j.cnki.jos.006240
中文关键词:  Petri网  可覆盖性判定  反向展开  启发式优化  数据竞争检测
英文关键词:Petri net  coverability determination  reverse unfolding  heuristic optimization  data race detection
基金项目:国家自然科学基金(61602279,61472229);国家重点研发计划(2016YFC0801406);山东省泰山学者工程专项基金(ts20190936);山东省高等学校青创科技支持计划(2019KJN024);山东省博士后创新专项基金(201603056);国家海洋局海洋遥测工程技术研究中心开放基金(2018002);山东科技大学领军人才与优秀科研创新团队项目(2015TDJH102)
作者单位E-mail
郝宗寅 山东科技大学 计算机科学与工程学院, 山东 青岛 266590
厦门大学 信息学院, 福建 厦门 361000 
 
鲁法明 厦门大学 信息学院, 福建 厦门 361000 fm_lu@163.com 
摘要点击次数: 56
全文下载次数: 27
中文摘要:
      展开技术借助分支进程可在一定程度上缓解Petri网性质分析中的状态爆炸问题.但展开网中仍然包含了系统的所有状态信息.某些应用问题仅需对系统特定状态的可覆盖性进行判定,以此为目标有望缩减网系统展开的规模.为此,本文针对安全Petri网的可覆盖性判定问题提出了一种目标导向的反向展开算法,结合启发式技术缩减展开的规模,以此提高目标标识可覆盖性判定的效率.进而,将反向展开算法应用于并发程序的形式化验证,将并发程序的数据竞争检测问题转换为Petri网特定标识的可覆盖性判定问题.实验对比了正向展开与反向展开在Petri网可覆盖性判定问题上的效率,结果表明,当Petri网展开的正向分支较多时,反向展开相比正向展开具有更高的可覆盖性判定效率.最后,本文对影响反向展开效率的关键因素做了分析与总结.
英文摘要:
      Unfolding technology can partially alleviate the state explosion problem in Petri net through branching processes. However, an unfolding still contains all states of a system. Some practical problems only need to determine the coverability of a specific state, which is expected to reduce the scale of unfolding net. In this paper, we propose a target-oriented reverse unfolding algorithm for the coverability problem of 1-safe Petri nets, which combines heuristic technology to reduce the scale of unfolding nets, thereby improving the efficiency of coverability determination. Furthermore, we apply the reverse unfolding technology to the formal verification of concurrent programs, and convert the data race detection problem into the coverability problem of a specific state in 1-safe Petri nets. The experiment compares the efficiency between forward unfolding and reverse unfolding in the coverability problem of Petri net. The results show that when the Petri net has more forward branches than backward branches, reverse unfolding is more efficient than forward unfodling. Finally, the key factors influencing the efficiency of reverse unfolding are analyzed.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利