A Formal Correctness Proof for an EDF ...
Type de document :
Communication dans un congrès avec actes
Titre :
A Formal Correctness Proof for an EDF Scheduler Implementation
Auteur(s) :
Vanhems, Florian [Auteur]
Rusu, Vlad [Auteur]
Analyse symbolique et conception orientée composants pour des systèmes embarqués temps-réel modulaires [SYCOMORES]
Nowak, David [Auteur]
Centre National de la Recherche Scientifique [CNRS]
Grimaud, Gilles [Auteur]
Rusu, Vlad [Auteur]
Analyse symbolique et conception orientée composants pour des systèmes embarqués temps-réel modulaires [SYCOMORES]
Nowak, David [Auteur]
Centre National de la Recherche Scientifique [CNRS]
Grimaud, Gilles [Auteur]
Titre de la manifestation scientifique :
RTAS 2022: 28th IEEE Real-Time and Embedded Technology and Applications Symposium
Ville :
Milan
Pays :
Italie
Date de début de la manifestation scientifique :
2022-05-04
Titre de l’ouvrage :
Proc. 28th IEEE Real-Time and Embedded Technology and Applications Symposium
Discipline(s) HAL :
Informatique [cs]/Systèmes embarqués
Résumé en anglais : [en]
The scheduler is a critical piece of software inreal-time systems. A failure in the scheduler can have seriousconsequences; therefore, it is important to provide strong cor-rectness guarantees for it. In this paper we ...
Lire la suite >The scheduler is a critical piece of software inreal-time systems. A failure in the scheduler can have seriousconsequences; therefore, it is important to provide strong cor-rectness guarantees for it. In this paper we propose a formalproof methodology that we apply to an Earliest Deadline First(EDF) scheduler. It consists first in proving the correctness of theelection function algorithm and then lifting this proof up to theimplementation through refinements. The proofs are formalizedin the Coq proof assistant, ensuring that they are free of humanerrors and that all cases are considered. Our methodology isgeneral enough to be applied to other schedulers or other typesof system code. To the best of our knowledge, this is the first timethat an implementation of EDF applicable to arbitrary sequencesof jobs has been proven correct.Lire moins >
Lire la suite >The scheduler is a critical piece of software inreal-time systems. A failure in the scheduler can have seriousconsequences; therefore, it is important to provide strong cor-rectness guarantees for it. In this paper we propose a formalproof methodology that we apply to an Earliest Deadline First(EDF) scheduler. It consists first in proving the correctness of theelection function algorithm and then lifting this proof up to theimplementation through refinements. The proofs are formalizedin the Coq proof assistant, ensuring that they are free of humanerrors and that all cases are considered. Our methodology isgeneral enough to be applied to other schedulers or other typesof system code. To the best of our knowledge, this is the first timethat an implementation of EDF applicable to arbitrary sequencesof jobs has been proven correct.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.inria.fr/hal-03671598/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03671598/document
- Accès libre
- Accéder au document
- https://hal.inria.fr/hal-03671598/document
- Accès libre
- Accéder au document