Skip to Main content Skip to Navigation
New interface
Journal articles

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

Goossens Joël 1 Emmanuel Grolleau 2 Liliana Cucu-Grosjean 3 
3 AOSTE - Models and methods of analysis and optimization for systems with real-time and embedding constraints
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, Inria de Paris
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.
Document type :
Journal articles
Complete list of metadata
Contributor : Liliana Cucu-Grosjean Connect in order to contact the contributor
Submitted on : Monday, December 19, 2016 - 6:15:56 PM
Last modification on : Friday, August 5, 2022 - 12:43:58 PM



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



Record views