Analysis of Federated and Global Scheduling for Parallel Real-Time Tasks

作者：Li Jing^*; Chen Jian Jia; Agrawal Kunal; Lu Chenyang; Gill Chris; Saifullah Abusayeed

来源：26th Euromicro Conference on Real-Time Systems, ECRTS 2014, 2014-07-08 To 2014-07-11.

DOI：10.1109/ECRTS.2014.23

• Dedicated cores
• Directed acyclic graph (DAG)
• Earliest deadline first
• Global scheduling
• Rate-monotonic
• Real-time scheduling strategies
• Real-time tasks
• Utilization task

This paper considers the scheduling of parallel real-time tasks with implicit deadlines. Each parallel task is characterized as a general directed acyclic graph (DAG). We analyze three different real-time scheduling strategies: two well known algorithms, namely global earliest-deadline-first and global rate-monotonic, and one new algorithm, namely federated scheduling. The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores. We prove capacity augmentation bounds for all three schedulers. In particular, we show that if on unit-speed cores, a task set has total utilization of at most m and the critical-path length of each task is smaller than its deadline, then federated scheduling can schedule that task set on m cores of speed 2, G-EDF can schedule it with speed 3 + v5/2 2.618, and G-RM can schedule it with speed 2 + v3 3.732. We also provide lower bounds on the speedup and show that the bounds are tight for federated scheduling and G-EDF when m is sufficiently large.

• 出版日期2014
• 单位Dortmund University; Washington University