TP316

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

Fund Project:

• 摘要
• |
• 图/表
• |
• 访问统计
• |
• 参考文献
• |
• 相似文献
• |
• 引证文献
• |
• 资源附件
• |
• 文章评论
摘要:

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

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\Delta + 1)/(m + \Delta )$ and the time complexity is ${\rm{O}}({n^2}) + {\rm{O}}(nm)$. $\Delta =\displaystyle{\sum }_{{\tau }_{j}\in \tau }{C}_{j} \times {u}_{j}/{D}_{{\rm{max}}}$ where ${\tau _j}$ belongs to the task set $\tau$, ${C_j}$is the worst-case execution time, ${u_j}$is the utilization, ${D_{{\rm{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 $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.

参考文献
相似文献
引证文献

• 点击次数:
• 下载次数:
• HTML阅读次数:
##### 历史
• 收稿日期:2023-01-16
• 最后修改日期:2023-04-10
• 录用日期:
• 在线发布日期: 2023-12-27
• 出版日期: