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

Jing Li, Jian Jia Chen, Kunal Agrawal, Chenyang Lu, Chris Gill, Abusayeed Saifullah

Research output: Chapter in Book/Report/Conference proceedingConference contribution

108 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - Euromicro Conference on Real-Time Systems
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages85-96
Number of pages12
ISBN (Electronic)9781479957989
DOIs
StatePublished - Oct 21 2014
Externally publishedYes
Event26th Euromicro Conference on Real-Time Systems, ECRTS 2014 - Madrid, Spain
Duration: Jul 8 2014Jul 11 2014

Publication series

NameProceedings - Euromicro Conference on Real-Time Systems
ISSN (Print)1068-3070

Other

Other26th Euromicro Conference on Real-Time Systems, ECRTS 2014
CountrySpain
CityMadrid
Period7/8/147/11/14

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Analysis of Federated and Global Scheduling for Parallel Real-Time Tasks'. Together they form a unique fingerprint.

Cite this