基于优先级时间Petri网的实时嵌入式多核系统分析  

Analysis of Real-time Embedded Multi-core System Based on Prioritized Time Petri Net

作　　者：张凯文 刘关俊[1] 孙彦韬 李晓锋[2] 关健[2] 解毅 顾斌[2] ZHANG Kai-Wen;LIU Guan-Jun;SUN Yan-Tao;LI Xiao-Feng;GUAN Jian;XIE Yi;GU Bin(Department of Computer Science and Technology,Tongji University,Shanghai 201804,China;Beijing Institute of Control Engineering,Beijing 100190,China)

机构地区：[1]同济大学计算机科学与技术系,上海201804 [2]北京控制工程研究所,北京100190

出　　处：《软件学报》2024年第9期4123-4140,共18页Journal of Software

基　　金：国家自然科学基金(62172299,62192730,62032019);北京控制工程研究所高可信嵌入式软件工程技术实验室开放基金(LHCESET202201);北京控制工程研究所空间光电测量与感知实验室开放基金(LabSOMP-2023-03);CCF-华为胡杨林基金-形式化专项(CCF-HuaweiFM202305)。

摘　　要：已有的基于点区间优先级时间Petri网分析实时嵌入式多核系统的工作,存在以下不足:(1)点区间优先级时间Petri网只考虑每个任务的执行时间是一个固定值的情况,而更多的实际应用中每个任务的执行时间是在一个区间范围内,因此不能模拟这些应用;(2)没有实现从任务依赖图到点区间优先级时间Petri网的自动转化,不便于工程设计人员使用;(3)没有考虑任务间互斥访问共享变量的情况.为此,定义了优先级时间Petri网(Pri-TPN)以弥补第1个不足;定义带有资源分配与优先级的任务依赖图(TDG-RAP)以弥补第3个不足;给出从TDG-RAP到Pri-TPN的转化规则与算法以弥补第2个不足,以及基于Pri-TPN分析任务最坏执行时间与系统死锁的算法;开发工具软件,方便工程设计人员使用.Existing work on the analysis of real-time embedded multi-core systems using point-interval prioritized time Petri nets has the following limitations.(1)Point-interval prioritized time Petri nets only consider the case where the execution time of each task is a fixed value,but in many practical applications,the execution time of a task is generally within a range so that this kind of model cannot be used to analyze these applications.(2)There is a lack of automatic transformation from task dependency graphs to this point-interval prioritized time Petri nets,and thus it is inconvenient for engineering designers.(3)The case of mutually exclusive access to shared variables has not been considered.To address these issues,this study defines prioritized time Petri nets(Pri-TPN)to overcome the first limitation and introduces a task dependency graph with resource allocation and priority(TDG-RAP)to overcome the third limitation.It develops algorithms based on Pri-TPN for analyzing the worst-case execution time(WCET)and system deadlocks of tasks.Additionally,a tool software is developed to facilitate its use by engineering designers.

关 键 词：实时嵌入式多核系统 优先级时间Petri网 可达图 任务依赖图 最坏执行时间(WCET) 死锁 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]