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

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

针对航天器等安全关键系统中实时任务调度和可调度性分析的实际问题,提出基于任务周期虚拟缩减的可调度性判定方法,构建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%.