并行机器中基于干扰时间的间歇实时任务分区DM调度  

Partitioned DM Scheduling for Sporadic Real-time Tasks Based on Interference Time in Parallel Machine

作　　者：刘洪标 宋程昊 王婷煜 姜菁菁 乔磊[2] 杨孟飞[3] LIU Hong-Biao;SONG Cheng-Hao;WANG Ting-Yu;JIANG Jing-Jing;QIAO Lei;YANG Meng-Fei(School of Computer Science and Technology,Xidian University,Xi’an 710070,China;Beijing Institute of Control Engineering,Beijing 100190,China;China Academy of Space Technology,Beijing 100094,China)

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

出　　处：《软件学报》2024年第11期5306-5318,共13页Journal of Software

摘　　要：间歇实时任务的分区DM(deadline-monotonic)调度是一个经典的研究问题,针对约束截止期间歇任务,提出一种具有更高处理器利用率的多核分区调度算法PDM-FFD(partitioned deadline-monotonic first-fit decrease).在PDM-FFD中,首先将任务按照其相对截止期以非递减顺序进行排序,然后采用first-fit策略选择处理器核分配任务,且在各处理器核上采用DM调度策略进行任务调度.最后通过对任务干扰时间的分析,得出一种更为紧凑的可调度性判定方法,并通过该可调度性方法来判定任务的可调度性.证明PDM-FFD的加速因子为3-(3Δ+1)/(m+Δ),时间复杂度为O(n^(2))+O(nm),其中Δ=_(Στj∈τ)C_(j)×u_(j)/D_(max),τ_(j)为任务集τ中的任务,C_(j)为该任务最差执行时间,u_(j)为该任务利用率,D_(max)为τ中的最大相对截止期,n为τ的任务数,m为处理器核数.该加速因子严格小于3-1/m,优于已有多核分区调度算法FBB-FFD.实验表明,PDM-FFD算法在4核处理器上的处理器利用率比其他算法提高了18.5%,且PDM-FFD的性能优势随着处理器核数、任务集利用率和任务数的增加而进一步扩大.由于PDM-FFD算法具有高性能特性,因此该算法可以广泛应用于资源受限的航天器、自动驾驶汽车、工业机器人等典型实时系统中.Partitioned DM(deadline-monotonic)scheduling of sporadic real-time tasks is a classic research problem.This study proposes a partitioned scheduling algorithm PDM-FFD(partitioned deadline-monotonic first-fit decrease)with higher processor utilization for constrained-deadline sporadic tasks.In PDM-FFD,firstly tasks are sorted in non-decreasing order according to the relative deadline,then the first-fit strategy is utilized to select the processor core to allocate tasks,and each core adopts DM scheduling policy.Finally,a tighter schedulability determination method is obtained by analyzing the task interference time to determine the task schedulability.This study proves that the speedup factor of PDM-FFD is 3-(3Δ+1)=(m+Δ)and the time complexity is O(n^(2))+O(nm).Δ=_(Στj∈τ)C_(j)×u_(j)/D_(max),.whereτ_(j)belongs to the task set,is the worst-case execution time,is the utilization,D_(max)is the maximum relative deadline,n is the task number,and m is the processor core number.The speedup factor of PDM-FFD is strictly less than,which outperforms the existing multi-core partitioned scheduling algorithm FBB-FFD.Experiments show that PDM-FFD improves processor utilization by 18.5%compared to other available algorithms on a four-core processor.The PDM-FFD performance improves with the increasing processor core number,task set utilization,and task number.Due to high performance,PDM-FFD can be widely utilized in typical real-time systems such as resource-constrained spacecraft,autonomous vehicles,and industrial robots.

关 键 词：间歇实时任务 分区DM(deadline-monotonic)调度 干扰时间 加速因子 资源受限 

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