Document Type

Technical Report

Department

Computer Science and Engineering

Publication Date

2014

Filename

WUCSE-2014-44.pdf

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

Share

COinS