Exact Schedulability Tests for Real-Time Scheduling of Periodic Tasks on Unrelated Multiprocessor Platforms"

Liliana Cucu-Grosjean 1 Joël Goossens 2
1 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we study the global scheduling of periodic task systems on unrelated multiprocessor platforms. We first show two general properties which are well known for uniprocessor platforms and which are also true for unrelated multiprocessor platforms: (i) under few and not so restrictive assumptions, we prove that feasible schedules of periodic task systems are periodic starting from some point in time with a period equal to the least common multiple of the task periods and (ii) for the specific case of synchronous periodic task systems, we prove that feasible schedules repeat from their origin. We then present our main result: we characterize, for task-level fixed-priority schedulers and for asynchronous constrained or arbitrary deadline periodic task models, upper bounds of the first time-instant where the schedule repeats. For task-level fixed-priority schedulers, based on the upper bounds and the predictability property, we provide exact schedulability tests for asynchronous constrained or arbitrary deadline periodic task sets. Finally, we provide an exact schedulability test as well for the job-level fixed-priority Earliest Deadline First (EDF) scheduler, for which such an upper bound is unknown.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-00646576
Contributor : Liliana Cucu-Grosjean <>
Submitted on : Wednesday, November 30, 2011 - 12:07:30 PM
Last modification on : Thursday, January 11, 2018 - 6:20:05 AM

Links full text

Identifiers

Collections

Citation

Liliana Cucu-Grosjean, Joël Goossens. Exact Schedulability Tests for Real-Time Scheduling of Periodic Tasks on Unrelated Multiprocessor Platforms". Journal of Systems Architecture, Elsevier, 2011, Special Issue on Multiprocessor Systems, 57 (5), pp.561-569. ⟨10.1016/j.sysarc.2011.02.007⟩. ⟨hal-00646576⟩

Share

Metrics

Record views

240