基于周期虚拟缩减的实时任务调度和分析方法  

Real-time Task Scheduling and Analysis Method Based on Virtual Zoom Out Period

作　　者：刘洪标 乔磊[2] 杨孟飞[3] 陈熙 马智 李少峰 LIU Hong-Biao;QIAO Lei;YANG Meng-Fei;CHEN Xi;MA Zhi;LI Shao-Feng(School of Computer Science and Technology,Xidian University,Xian 710071,China;Beijing Institute of Control Engineering,Beijing 100190,China;China Academy of Space Technology,Beijing 100094,China)

机构地区：[1]西安电子科技大学计算机科学与技术学院,陕西西安710071 [2]北京控制工程研究所,北京100190 [3]中国空间技术研究院,北京100094

出　　处：《软件学报》2022年第9期3512-3528,共17页Journal of Software

基　　金：国家自然科学基金(61632005,62032004)。

摘　　要：针对航天器等安全关键系统中实时任务调度和可调度性分析的实际问题,提出基于任务周期虚拟缩减的可调度性判定方法,构建SHT (strong-hard task)任务模型对强硬实时任务进行精确描述,并根据任务时间特性分配优先级.虚拟化所有强实时任务为一个硬实时任务,对此硬实时任务周期虚拟缩减并计算出其最差虚拟执行时间,然后按RMS可调度性判定公式判定.给出了判定方法的严格证明,可对包含n个SHT任务的任务集进行快速可调度性判定,此算法时间复杂度仅为O(n~2).在我国空间站计算机进行了对比验证,实验表明判定效率优于现有可调度性判定方法,平均运行时间开销降低了41.8%,可调度率提高了5.7%.Regarding the practical problems of the real-time task scheduling and analysis in safety-critical systems such as spacecraft, this study proposes a schedulability determination method based on virtual zoom out period, constructing a strong-hard task(SHT) model to accurately describe real-time tasks, and allocates priority based on task’s time characteristics. Virtualizing all strong real-time task as a hard real-time task, virtually reduces the period of the hard real-time task and calculates the worst virtual execution time, and then determines the schedulability according to the RMS schedulability judgment formula. This paper presents a rigorous proof of the method,which can make a fast schedulability determination on an SHT task set containing n tasks, and the time complexity of this algorithm is only O(n~2). Comparative verification was carried out on the China space station computer, and the experiments show that the schedulability determination efficiency is better than the existing methods. The average running time overhead is reduced by 41.8%, and the schedulable ratio is increased by 5.7%.

关 键 词：动态扩展 实时任务 周期虚拟缩减 优先级分配 可调度性 

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