模拟实时系统的点区间优先级时间Petri网与TCTL验证
作者:
作者单位:

作者简介:

何雷锋(1991-),男,博士生,主要研究领域为Petri网,模型检测,形式化方法;
刘关俊(1978-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为Petri网,模型检测,形式化方法,机器学习,人机物系统,工作流系统,无人机协同系统.

通讯作者:

刘关俊,E-mail:liuguanjun@tongji.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(62172299,62032019);上海市级科技重大专项(2021SHZDZX0100);中央高校基本科研业务费专项资金


Time-point-interval Prioritized Time Petri Nets Modelling Real-time Systems and TCTL Checking
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    时间Petri网为实时系统提供了一种形式化的建模方法,时间计算树逻辑(TCTL)为描述实时系统与时间相关的设计需求提供了一种逻辑化的表达方式,因此,基于时间Petri网的TCTL模型检测广泛应用于实时系统的正确性验证.然而对于一些涉及优先级的实时系统,例如多核多任务实时系统,这里不仅需要考虑任务之间的时间约束,还要考虑任务执行的优先级以及引入优先级带来的抢占式调度问题,致使相应的建模和分析变得更加困难.为此,提出了点区间优先级时间Petri网,通过在时间Petri网上定义变迁发生的优先级以及变迁的可挂起性,从而可以模拟实时系统的抢占式调度机制.首先,高优先级的任务抢占低优先级的任务所占用的资源,导致后者被中断;然后,前者执行完毕后释放资源;最后,后者再次获得资源,从中断的地方恢复.通过点区间优先级时间Petri网来模拟多核多任务实时系统,使用TCTL来描述它们的设计需求,设计了相应的模型检测算法,开发了相应的模型检测器以验证它们的正确性.通过一个实例,来说明该模型和方法的有效性.

    Abstract:

    Time Petri nets is a formal method for modelling real-time systems, and timed computation tree logic (TCTL) is a logical expression for specifying time-related design requirements of real-time systems, so time Petri net based TCTL model checking has been widely used to verify the correction of real-time systems. For those real-time systems with priority such as multi-core multi-task real-time systems, it not only needs to consider time constraints among tasks but also needs to consider priority of task execution and the preemptive scheduling problem caused by priority, which results that modelling and analysis of these systems become more difficult. Therefore, this study proposes time-point-interval prioritized time Petri nets. By defining priority of transition firing and suspendable transitions in time Petri nets, time-point-interval prioritized time Petri nets can model preemptive scheduling of real-time systems, i.e., first of all, a high-priority task preempts the resource of a low-priority task, which results in the interruption of the latter, then the former is completed and releases the resource, and finally the latter gets the resource again and resumes from the interruption. This study uses time-point-interval prioritized time Petri nets to model multi-core multi-task real-time systems, uses TCTL to describe their design requirements, designs the corresponding model checking algorithms, and develops the corresponding model checker to verify their correctness. An example is used to show the effectiveness of the proposed model and method.

    参考文献
    相似文献
    引证文献
引用本文

何雷锋,刘关俊.模拟实时系统的点区间优先级时间Petri网与TCTL验证.软件学报,2022,33(8):2947-2963

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-09-05
  • 最后修改日期:2021-10-14
  • 录用日期:
  • 在线发布日期: 2022-01-28
  • 出版日期: 2022-08-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号