HomePublicationsJournal Paper

Unified Overhead-aware Schedulability Analysis for Slot-based Task-splitting
Ref: CISTER-TR-130201       Publication Date: Jul 2014

Abstract:
Hard real-time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and migrative scheduling for the purposes of achieving efficient utilisation of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilisation bounds) and the number of preemptions/migrations involved.However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a unified schedulability theory for slot-based semi-partitioning in applicable to all known algorithms of this class. This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact thatmany unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of new theory are evaluated by an extensive set of experiments.

Paulo Baltarejo Sousa

,

Konstantinos Bletsas

,

Eduardo Tovar

,

Pedro Souto

,

Benny Åkesson

Document:

View
PDF Download
PDF