Title

Capacity Augmentation Bound of Federated Scheduling for Parallel DAG Tasks

Authors

Jing Li, Washington University in St Louis
Abusayeed Saifullah, Washington University in St Louis
Kunal Agrawal, Washington University in St LouisFollow
Christopher Gill, Washington University in St. LouisFollow

Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2014

Filename

WUCSE-2014-44.pdf

DOI:

10.7936/K73B5XCM

Technical Report Number

WUCSE-2014-44

Abstract

We present a novel federated scheduling approach for parallel real-time tasks under a general directed acyclic graph (DAG) model. We provide a capacity augmentation bound of 2 for hard real-time scheduling; here we use the worst-case execution time and critical-path length of tasks to determine schedulability. This is the best known capacity augmentation bound for parallel tasks. By constructing example task sets, we further show that the lower bound on capacity augmentation of federated scheduling is also 2 for any m > 2. Hence, the gap is closed and bound 2 is a strict bound for federated scheduling. The federated scheduling algorithm is also a schedulability test that often admits task sets with utilization much greater than 50%m.

Comments

Permanent URL: http://dx.doi.org/10.7936/K73B5XCM

Recommended Citation

Li, Jing; Saifullah, Abusayeed; Agrawal, Kunal; and Gill, Christopher, "Capacity Augmentation Bound of Federated Scheduling for Parallel DAG Tasks" Report Number: WUCSE-2014-44 (2014). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/107