Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms

Abstract : This paper gives and proves correct a simulation interval for any schedule generated by a deterministic and memoryless scheduler (i.e., one where the scheduling decision is the same and unique for any two identical system states) for identical multiprocessor platforms. We first consider independent periodic tasks, then generalize the simulation interval to tasks sharing critical resources, and subject to precedence constraints or self-suspension. The simulation interval is based only on the periods, release times and deadlines, and is independent from any other parameters. It is proved large enough to cover any feasible schedule produced by any deterministic and memoryless scheduler on multiprocessor platforms, including non conservative schedulers. To the best of our knowledge, this simulation interval covers the largest class of task systems and scheduling algorithms on identical multiprocessor platforms ever studied. This simulation interval is used to derive a simulation algorithm using a linear space complexity. Finally, a generic exact schedulability test based on simulation is presented. This test can be applied only when sustainability is consistent with online variability of the tasks’ parameters.
Type de document :
Article dans une revue
Real-Time Systems, Springer Verlag, 2016, 52 (6), pp.808-832. <10.1007/s11241-016-9256-1>
Liste complète des métadonnées

https://hal.inria.fr/hal-01419704
Contributeur : Liliana Cucu <>
Soumis le : lundi 19 décembre 2016 - 18:15:56
Dernière modification le : samedi 28 janvier 2017 - 01:03:51

Identifiants

Collections

Citation

Goossens Joël, Emmanuel Grolleau, Liliana Cucu-Grosjean. Periodicity of real-time schedules for dependent periodic tasks on identical multiprocessor platforms. Real-Time Systems, Springer Verlag, 2016, 52 (6), pp.808-832. <10.1007/s11241-016-9256-1>. <hal-01419704>

Partager

Métriques

Consultations de la notice

63