Equivalence between schedule representations: theory and applications

Abstract : Multiprocessor scheduling problems are hard because of the numerous constraints on valid schedules to take into ac- count. This paper presents new schedule representations in order to overcome these difficulties, by allowing processors to be fractionally allocated. We prove that these represen- tations are equivalent to the standard representations when preemptive scheduling is allowed. This allows the creation of scheduling algorithms and the study of feasibility in the simpler representations. We apply this method throughout the paper. Then, we use it to provide new simple solutions to the previously solved implicit-deadline periodic schedul- ing problem. We also tackle the more general problem of scheduling arbitrary time-triggered tasks, and thus in par- ticular solve the open multiprocessor general periodic tasks scheduling problem. Contrary to previous solutions like the PFair class of algorithms, the proposed solution also works when processors have different speeds. We complete the method by providing an online schedule transformation algorithm, that allows the efficient handling of both time-triggered and event-triggered tasks, as well as the creation of online rate-based scheduling algorithms on multiprocessors.deadline periodic tasks on multiple identical processors cuts jobs at every time quanta and dispatches them on the multi- ple processors. g. Moreover, this property is true not only when time is modelled in a discrete way, but also in the more general continuous model of time; and we prove that it still works for uniform multi- processors, i.e. processors that have different (but constant)
Document type :
Conference papers
Complete list of metadatas

https://hal-supelec.archives-ouvertes.fr/hal-00292628
Contributor : Evelyne Faivre <>
Submitted on : Wednesday, July 2, 2008 - 10:57:50 AM
Last modification on : Wednesday, January 23, 2019 - 2:38:28 PM

Identifiers

  • HAL Id : hal-00292628, version 1

Collections

Citation

Matthieu Lemerre, Vincent David, Christophe Assaguès, Guy Vidal-Naquet. Equivalence between schedule representations: theory and applications. 14th IEEE Real-Time and Embedded Technology and Applications Symposium, Apr 2008, Saint Louis, United States. pp.237-247. ⟨hal-00292628⟩

Share

Metrics

Record views

180