| 摘要: |
| 间歇实时任务的分区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算法具有高性能特性, 因此该算法可以广泛应用于资源受限的航天器、自动驾驶汽车、工业机器人等典型实时系统中. |
| 关键词: 间歇实时任务 分区DM (deadline-monotonic)调度 干扰时间 加速因子 资源受限 |
| DOI：10.13328/j.cnki.jos.007036 |
| 分类号: |
| 基金项目: |
|
| Partitioned DM Scheduling for Sporadic Real-time Tasks Based on Interference Time in Parallel Machine |
|
LIU Hong-Biao1, SONG Cheng-Hao2, WANG Ting-Yu1, JIANG Jing-Jing2, QIAO Lei2, YANG Meng-Fei3
|
|
1.School of Computer Science and Technology, Xidian University, Xi’an 710070, China;2.Beijing Institute of Control Engineering, Beijing 100190, China;3.China Academy of Space Technology, Beijing 100094, China
|
| Abstract: |
| 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(n2) + O(nm). △= ∑τj∈τCj×uj/Dmax where τj belongs to the task set τ, Cj is the worst-case execution time, uj is the utilization, Dmax 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 3 - 1/m, 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. |
| Key words: sporadic real-time task partitioned deadline-monotonic (DM) scheduling interference time speedup factor resource-constrained |
