Journal
REAL-TIME SYSTEMS
Volume 48, Issue 3, Pages 223-263Publisher
SPRINGER
DOI: 10.1007/s11241-011-9144-7
Keywords
Compositional real-time systems; Schedulability analysis; Periodic resource model; Sporadic tasks; Earliest-deadline first; Approximation algorithms
Categories
Funding
- National Science Foundation [CNS-0953585]
- Wayne State University's Office of Vice President of Research
- Direct For Computer & Info Scie & Enginr
- Division Of Computer and Network Systems [0953585] Funding Source: National Science Foundation
Ask authors/readers for more resources
Allocation of bandwidth among components is a fundamental problem in compositional real-time systems. State-of-the-art algorithms for bandwidth allocation use either exponential-time or pseudo-polynomial-time techniques for exact allocation, or linear-time, utilization-based techniques which may over-provision bandwidth. In this paper, we propose research into a third possible approach: parametric approximation algorithms for bandwidth allocation in compositional real-time systems. We develop a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth for sporadic task systems scheduled by earliest-deadline first (EDF) upon an Explicit-Deadline Periodic (EDP) resource. Our algorithm takes, as parameters, the task system and an accuracy parameter I mu > 0, and returns a bandwidth which is guaranteed to be at most a factor (1+I mu) more than the optimal minimum bandwidth required to successfully schedule the task system. Furthermore, the algorithm has time complexity that is polynomial in the number of tasks and 1/I mu.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available