Journal
ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS
Volume 13, Issue 4, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2560038
Keywords
Theory; Design; Algorithms; Compositional real-time systems; bandwidth allocation; FPTAS; fixed-priority scheduling
Funding
- National Science Foundation [CNS-0953585]
- Wayne State University's Office
- Direct For Computer & Info Scie & Enginr
- Division Of Computer and Network Systems [0953585] Funding Source: National Science Foundation
Ask authors/readers for more resources
Recent research in compositional real-time systems has focused on determination of a component's real-time interface parameters. An important objective in interface-parameter determination is minimizing the bandwidth allocated to each component of the system while simultaneously guaranteeing component schedulability. With this goal in mind, in this article, we explore fixed-priority schedulability in compositional setting. First we derive an efficient exact test based on iterative convergence for sporadic task systems scheduled by fixed-priority (e.g., deadline monotonic, rate monotonic) upon an explicit-deadline periodic (EDP) resource. Then we address the time complexity of the exact test by developing a fully-polynomial-time approximation scheme (FPTAS) for allocating bandwidth to components. Our parametric algorithm takes the task system and an accuracy parameter is an element of > 0 as input and returns a bandwidth which is guaranteed to be at most a factor (1 + is an element of) times the optimal minimum bandwidth required to successfully schedule the task system. We perform thorough simulation over synthetically generated task systems to compare the performance of our proposed efficient-exact and the approximate algorithm and observe a significant decrease in runtime and a very small relative error when comparing the approximate algorithm with the exact algorithm and the sufficient algorithm.
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