软件学报

作者：刘洪标，宋程昊，王婷煜，姜菁菁，乔磊，杨孟飞

单位：刘洪标，西安电子科技大学 计算机科学与技术学院, 陕西 西安 71007011,宋程昊，北京控制工程研究所, 北京 10019002,王婷煜，西安电子科技大学 计算机科学与技术学院, 陕西 西安 71007003,姜菁菁，北京控制工程研究所, 北京 10019004,乔磊，北京控制工程研究所, 北京 10019005,杨孟飞，中国空间技术研究院, 北京 10009406

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

间歇实时任务的分区DM (deadline-monotonic)调度是一个经典的研究问题, 针对约束截止期间歇任务, 提出一种具有更高处理器利用率的多核分区调度算法PDM-FFD (partitioned deadline-monotonic first-fit decrease). 在PDM-FFD中, 首先将任务按照其相对截止期以非递减顺序进行排序, 然后采用first-fit策略选择处理器核分配任务, 且在各处理器核上采用DM调度策略进行任务调度. 最后通过对任务干扰时间的分析, 得出一种更为紧凑的可调度性判定方法, 并通过该可调度性方法来判定任务的可调度性. 证明PDM-FFD的加速因子为3 - (3△ + 1)/(m + △), 时间复杂度为O(n2) + O(nm), 其中△= ∑τj∈τCj×uj/Dmax, τj为任务集τ中的任务, Cj为该任务最差执行时间, uj为该任务利用率, Dmax为τ中的最大相对截止期, n为τ的任务数, m为处理器核数. 该加速因子严格小于3 - 1/m, 优于已有多核分区调度算法FBB-FFD. 实验表明, PDM-FFD算法在4核处理器上的处理器利用率比其他算法提高了18.5%, 且PDM-FFD的性能优势随着处理器核数、任务集利用率和任务数的增加而进一步扩大. 由于PDM-FFD算法具有高性能特性, 因此该算法可以广泛应用于资源受限的航天器、自动驾驶汽车、工业机器人等典型实时系统中.

来源：2024年第11期

《软件学报》期刊编辑部

查看软件学报杂志2024年第11期