Optimal soft real-time semi-partitioned scheduling made simple (and dynamic)
Optimal soft real-time semi-partitioned scheduling made simple (and dynamic)
复制标题
DOI：
10.1145/3356401.3356402
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Clara Hobbs;Zelin Tong;James H. Anderson
中科院分区：
文献类型：
--
作者：
Clara Hobbs;Zelin Tong;James H. Anderson
半分区调度是多处理器实时调度的一种方法，其中大多数任务被固定到处理器，而一小部分任务被允许迁移。与全局调度相比，这种方法提供了减少的开销，并且与分区调度相比可以减少处理器容量损失。先前的工作已经导致了一些半分区调度算法，但它们的正确性通常取决于离线任务分配和在线执行的复杂交织。这种脆弱性导致很少有人提出支持动态任务系统的半分区调度算法，其中任务可以在运行时加入或离开系统，并且很少有人在任何意义上都是最优的。本文介绍了EDF-SC，第一个半分区调度算法，是最佳的调度（静态）软实时（SRT）零星的任务系统，并允许任务动态加入和离开。SRT概念的最优性EDF-SC提供的要求截止日期拖期是有界的任何任务系统，不会导致过度利用。在所有任务都可以被分配为固定任务的情况下，EDF-sc的行为与分区EDF完全相同。启发式提供，给EDF-SC的新的能力，稳定的工作量接近分区的情况下，任务加入和离开系统。
Semi-partitioned scheduling is an approach to multiprocessor real-time scheduling where most tasks are fixed to processors, while a small subset of tasks is allowed to migrate. This approach offers reduced overhead compared to global scheduling, and can reduce processor capacity loss compared to partitioned scheduling. Prior work has resulted in a number of semi-partitioned scheduling algorithms, but their correctness typically hinges on a complex intertwining of offline task assignment and online execution. This brittleness has resulted in few proposed semi-partitioned scheduling algorithms that support dynamic task systems, where tasks may join or leave the system at runtime, and few that are optimal in any sense. This paper introduces EDF-sc, the first semi-partitioned scheduling algorithm that is optimal for scheduling (static) soft real-time (SRT) sporadic task systems and allows tasks to dynamically join and leave. The SRT notion of optimality provided by EDF-sc requires deadline tardiness to be bounded for any task system that does not cause over-utilization. In the event that all tasks can be assigned as fixed, EDF-sc behaves exactly as partitioned EDF. Heuristics are provided that give EDF-sc the novel ability to stabilize the workload to approach the partitioned case as tasks join and leave the system.