并行机器中基于干扰时间的间歇实时任务分区DM调度
CSTR:
作者:
作者单位:

作者简介:

刘洪标(1995-), 男, 博士, 主要研究领域为嵌入式操作系统, 实时任务调度. ;宋程昊(1997-), 男, 硕士, 主要研究领域为嵌入式操作系统, 任务调度. ;王婷煜(1998-), 女, 博士, 主要研究领域为嵌入式操作系统, 任务调度, 文件系统. ;姜菁菁(1996-), 女, 博士, 主要研究领域为嵌入式操作系统, 形式化验证, 文件系统. ;乔磊(1982-), 男, 博士, 研究员, CCF专业会员, 主要研究领域为操作系统模型设计, 存储管理, 文件系统. ;杨孟飞(1962-), 男, 博士, 研究员, 博士生导师, CCF高级会员, 主要研究领域为空间飞行器嵌入式系统, 控制系统, 总体技术.

通讯作者:

杨孟飞, E-mail: yangmf@bice.org.cn

中图分类号:

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{\mathit\Delta} + 1)/(m + {\mathit\Delta} )$, 时间复杂度为${\rm{O}}({n^2}) + {\rm{O}}(nm)$, 其中${\mathit\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{\mathit\Delta} + 1)/(m + {\mathit\Delta} )$ and the time complexity is ${\rm{O}}({n^2}) + {\rm{O}}(nm)$. ${\mathit\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, 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.

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

刘洪标,宋程昊,王婷煜,姜菁菁,乔磊,杨孟飞.并行机器中基于干扰时间的间歇实时任务分区DM调度.软件学报,2024,35(11):5306-5318

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2023-01-16
  • 最后修改日期:2023-04-10
  • 录用日期:
  • 在线发布日期: 2023-12-27
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号