Unified overhead-aware schedulability analysis for slot-based task-splitting

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Paulo Baltarejo Sousa (Author) Other; Konstantinos Bletsas (Author) Other; Eduardo Tovar (Author) Other; Pedro Souto (Author) FEUP; Benny Akesson (Author) Other

Journal

Title: Real-Time Systems

Vol. 50 No. 5-6

Pages: 680-735

ISSN: 0922-6443

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 5 Citations

ISI Web of Science

Scopus - 7 Citations

COMPENDEX

INSPEC

Scientific classification

FOS: Engineering and technology > Electrical engineering, Electronic engineering, Information engineering

CORDIS: Physical sciences > Computer science > Computer systems

Other information

Authenticus ID: P-009-YGQ

DOI: 10.1007/s11241-014-9204-x

Abstract (EN): 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 global scheduling for the purposes of achieving efficient utilization 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 utilization 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 more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). 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 that many 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 this new theory are evaluated by an extensive set of experiments.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 56