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

• Tipo: Artigo em Revista Científica Internacional
• Data: 2014

Autores

Paulo Baltarejo Sousa (Autor) Outra; Konstantinos Bletsas (Autor) Outra; Eduardo Tovar (Autor) Outra; Pedro Souto (Autor) FEUP; Benny Akesson (Autor) Outra

Revista

Título: Real-Time Systems

Vol. 50 Nº 5-6

Páginas: 680-735

ISSN: 0922-6443

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 5 Citações

ISI Web of Science

Scopus - 7 Citações

COMPENDEX

INSPEC

Classificação Científica

FOS: Ciências da engenharia e tecnologias > Engenharia electrotécnica, electrónica e informática

CORDIS: Ciências Físicas > Ciência de computadores > Sistema de computadores

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 56