Task Splitting and Load Balancing of Dynamic Real-Time Workloads for Semi-Partitioned EDF
Task Splitting and Load Balancing of Dynamic Real-Time Workloads for Semi-Partitioned EDF
复制标题
半分区 EDF 动态实时工作负载的任务拆分和负载平衡
DOI：
--
复制
发表时间：
2021
影响因子：
3.7
通讯作者：
G. Buttazzo
中科院分区：
文献类型：
--
作者：
Daniel Casini;Alessandro Biondi;G. Buttazzo
许多实时软件系统，例如在多媒体、云计算、机器人技术和实时数据库环境中常见的那些系统，其特点是动态工作负载，其中应用程序可以在运行时加入和离开系统。全局调度器可以透明地支持动态工作负载，而不需要任何离线任务分配阶段，从而为系统设计人员提供了优势。然而，与半分区调度器相比，这种调度器表现出较差的最坏情况性能，而半分区调度器在与智能任务分割和分区技术结合使用时可以实现近乎最佳的可调度性性能，并且在运行时开销方面也更轻。本文提出了一种利用半分区调度方法在多处理器系统上高效地调度动态实时工作负载的方法。提出了分区EDF调度下C=D分裂算法的线性时间逼近格式。然后，提出了一种负载均衡算法，在有限的重新分配次数下接受新的实时工作负载。本文最后报告了一项大规模的实验研究，表明：(i)与相应的精确方法（具有高得多的复杂性）相比，线性时间近似的特点是利用率损失非常有限，并且（ii）整个方法允许在全局和分区EDF调度方面取得相当大的改进。
Many real-time software systems, such as those commonly found in the context of multimedia, cloud computing, robotics, and real-time databases, are characterized by a dynamic workload, where applications can join and leave the system at runtime. Global schedulers can transparently support dynamic workload without requiring any off-line task-allocation phase, thus providing advantages to the system designer. Nevertheless, such schedulers exhibit poor worst-case performance when compared to semi-partitioned schedulers, which instead can achieve near-optimal schedulability performance when used in conjunction with smart task splitting and partitioning techniques, and they are also lighter in terms of run-time overhead. This article proposes an approach to efficiently schedule dynamic real-time workloads on multiprocessor systems by means of semi-partitioned scheduling. A linear-time approximation scheme for the C=D splitting algorithm under partitioned EDF scheduling is proposed. Then, a load-balancing algorithm is presented to admit new real-time workloads with a limited number of re-allocations. The article finally reports on a large-scale experimental study showing that (i) the linear-time approximation is characterized by a very limited utilization loss compared with the corresponding exact approach (that has a much higher complexity), and that (ii) the whole approach allows achieving considerable improvements with respect to global and partitioned EDF scheduling.
影响因子：
16.6
作者：
Davis, Robert I.;Burns, Alan
通讯作者：
Burns, Alan