Composition of Schedulability Analyses for Real-Time Multiprocessor Systems

Cited 11 time in webofscience Cited 0 time in scopus
  • Hit : 303
  • Download : 0
With increasing popularity and deployment of multi-core chips in embedded systems, a number of real-time multiprocessor scheduling algorithms have been proposed along with their schedulability analyses (or tests), which verify temporal correctness under a specific algorithm. Each of these algorithms often comes with several different schedulability tests, especially when it is difficult to find exact schedulability tests for the algorithm. Such tests usually find different task sets deemed schedulable even under the same scheduling algorithm. While these different tests have been compared with each other in terms of schedulability performance, little has been done on how to combine such different tests to improve the overall schedulability of a given scheduling algorithm beyond a simple union of their individual schedulability. Motivated by this, we propose a composition theory for schedulability tests with two new methods. The first method composes task-level timing guarantees derived from different schedulability tests, and the second one derives system-level schedulability results from a single schedulability test. The unified composition theory with these two methods then utilizes existing schedulability tests effectively so as to cover additional schedulable task sets. The proposed composition theory is shown to be applicable to most existing preemptive/non-preemptive scheduling algorithms. We also present three case-studies, demonstrating how and by how much the theory can improve schedulability by composing existing schedulability tests. Our evaluation results also show that the composition theory makes it possible to cover up to 181.7 percent additional schedulable task sets for preemptive fpEDF, preemptive EDF and non-preemptive EDF scheduling algorithms beyond their existing tests.
Publisher
IEEE COMPUTER SOC
Issue Date
2015-04
Language
English
Article Type
Article
Keywords

GLOBAL EDF SCHEDULABILITY; PERIODIC TASK SYSTEMS; PLATFORMS; BOUNDS

Citation

IEEE TRANSACTIONS ON COMPUTERS, v.64, no.4, pp.941 - 954

ISSN
0018-9340
DOI
10.1109/TC.2014.2308183
URI
http://hdl.handle.net/10203/197721
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 11 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0