Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems

Abstract : Systems in many safety-critical application domains are subject to certification requirements. For any given system, however, it may be the case that only a subset of its functionality is safety-critical and hence subject to certification; the rest of the functionality is non-safety-critical and does not need to be certified, or is certified to lower levels of assurance. The certification-cognizant runtime scheduling of such mixed-criticality systems is considered. An algorithm called EDF-VD (for Earliest Deadline First with Virtual Deadlines) is presented: this algorithm can schedule systems for which any number of criticality levels are defined. Efficient implementations of EDF-VD, as well as associated schedulability tests for determining whether a task system can be correctly scheduled using EDF-VD, are presented. For up to 13 criticality levels, analyses of EDF-VD, based on metrics such as processor speedup factor and utilization bounds, are derived, and conditions under which EDF-VD is optimal with respect to these metrics are identified. Finally, two extensions of EDF-VD are discussed that enhance its applicability. The extensions are aimed at scheduling a wider range of task sets, while preserving the favorable worst-case resource usage guarantees of the basic algorithm.
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2015, 62 (2), pp.14. 〈10.1145/2699435〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01249091
Contributeur : Marie-France Sagot <>
Soumis le : jeudi 29 juin 2017 - 11:23:00
Dernière modification le : mercredi 11 avril 2018 - 01:53:20
Document(s) archivé(s) le : jeudi 18 janvier 2018 - 02:31:27

Fichier

baruah2015.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sanjoy Baruah, Vincenzo Bonifaci, Gianlorenzo D'Angelo, Haohan Li, Alberto Marchetti-Spaccamela, et al.. Preemptive Uniprocessor Scheduling of Mixed-Criticality Sporadic Task Systems. Journal of the ACM (JACM), Association for Computing Machinery, 2015, 62 (2), pp.14. 〈10.1145/2699435〉. 〈hal-01249091〉

Partager

Métriques

Consultations de la notice

113

Téléchargements de fichiers

43