EFFICIENT FEASIBILITY ANALYSIS OF REAL-TIME ASYNCHRONOUS TASK SETS

[Total: 0    Average: 0/5]

Several schedulability tests for real-time periodic task sets scheduled under the Earliest Deadline First algorithm have been proposed in literature, including analyses for precedence and resource constraints. However, all available tests consider synchronous task sets only, that are task sets in which all tasks are initially activated at the same time. In fact, every necessary and sufficient feasibility condition for asynchronous task sets, also known as task sets with offsets, is proven to be NP-complete in the number of tasks. We propose a new schedulability test for asynchronous task sets that, while being only sufficient, performs extremely better than available tests at the cost of a slight complexity increase. The test is further extended to task sets with resource constraints, and we discuss the importance of task offsets on the problems of feasibility and release jitter. We then show how our methodology can be extended in order to account for precedence constraints and multiprocessor and distributed computation applying holistic response time analysis to a real-time transaction-based model. This analysis is finally applied to asymmetric multiprocessor systems where it is able to achieve a dramatic performance increase over existing schedulability tests.