Article

1 - ARCHITECTURES DES APPLICATIONS TEMPS RÉEL

2 - TESTS D’ORDONNANÇABILITÉ

Article de référence | Réf : S8055 v2

Ordonnancement temps réel - Ordonnancement monoprocesseur

Auteur(s) : Emmanuel GROLLEAU, Michaël RICHARD, Pascal RICHARD, Frédéric RIDOUARD

Relu et validé le 15 sept. 2023

Pour explorer cet article
Télécharger l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !

Sommaire

Présentation

RÉSUMÉ

L'ordonnancement temps réel est en charge d'assurer que tous les traitements parallèles en charge du contrôle d'un procédé critique s'exécutant à temps. Cet ordonnancement a lieu dans un certain contexte qui dépend de l’architecture matérielle et logicielle, et de l’exécutif temps réel. Il doit intégrer les problématiques de la validation temporelle. Les tests d'ordonnançabilité sont présentés pour les tâches à priorités fixes et pour les tâches indépendantes, puis en prenant en compte les facteurs pratiques tels que communications ou exclusions mutuelles.

Lire cet article issu d'une ressource documentaire complète, actualisée et validée par des comités scientifiques.

Lire l’article

ABSTRACT

Real-time scheduling - Mono-processor scheduling

Real-time scheduling must ensure that all the parallel processes put in place of the control of a critical process are executed promptly. This scheduling occurs in a particular context that depends on the material and software architecture and of the real-time executive. It must integrate the problems of temporal validation. Schedulability tests are presented for fixed-priority tasks and for independent tasks and then by the taking into account of practical factors such as communications or mutual exclusions.

Auteur(s)

  • Emmanuel GROLLEAU : Professeur des universités en Informatique à l’ISAE-ENSMA (Chasseneuil du Poitou)

  • Michaël RICHARD : Maître de conférences en Informatique à l’ISAE-ENSMA (Chasseneuil du Poitou)

  • Pascal RICHARD : Professeur des universités en Informatique à l’université de Poitiers

  • Frédéric RIDOUARD : Maître de conférences en Informatique à l’université de Poitiers

INTRODUCTION

Les systèmes informatiques peuvent être classés en trois catégories : les systèmes transformationnels, les systèmes réactifs et les systèmes interactifs. Les systèmes transformationnels transforment des données d’entrée en données de sortie à leur propre rythme, sans interaction avec leur environnement. Les systèmes interactifs représentent typiquement la classe des programmes avec une interface graphique. Ils répondent aux demandes d’un utilisateur, et il est bienvenu qu’ils y répondent rapidement. Les systèmes réactifs sont en charge de contrôler des procédés. Un procédé est un système physique à contrôler, possédant son propre environnement. Par conséquent, le système réactif doit réagir suffisamment rapidement par rapport à la dynamique du procédé contrôlé et de son environnement. Contrairement aux autres catégories, les systèmes réactifs ne présentent pas de comportements récurrents : le procédé évoluant avec sa propre dynamique dans un environnement souvent complexe, il est rare que des scénarios d’exécution système réactif/évolution du procédé dans son environnement soient reproductibles.

Les systèmes informatiques contrôlant des procédés physiques critiques, notamment dans le domaine du transport, de l’exploration autonome, etc., sont typiquement embarqués sur le procédé lui-même. On parle alors de système embarqué critique. De tels systèmes sont souvent soumis à des contraintes de temps inhérentes à la dynamique du procédé contrôlé. On dit alors qu’ils sont temps réel. Un système temps réel est un système réactif, en charge de s'assurer du maintien d’un procédé (drone, système automobile ou avionique, etc.) dans un état désiré, tout en assurant une réactivité du système qui soit cohérente avec les contraintes de temps inhérentes au procédé et à son environnement. Malgré l’accroissement de la puissance des calculateurs, d’abord en fréquence, puis en nombre de cœurs de calcul depuis le début des années 2000, les calculateurs embarqués sont dimensionnés au plus juste des besoins en puissance de calcul de façon, notamment, à minimiser l’énergie consommée, et donc l’autonomie du procédé.

Deux hypothèses sont communément à la base d’un partitionnement au niveau des modèles, des méthodes et des problématiques traités : l’hypothèse synchrone et l’hypothèse asynchrone. L’hypothèse synchrone considère que les traitements sont déclenchés directement par l’arrivée d’événements. Les traitements sont considérés comme ayant une durée nulle, ou en tout cas inférieure à l’écart minimal séparant deux événements déclencheurs successifs. L’hypothèse asynchrone se repose sur le paradigme de programmation multitâche : des événements peuvent, comme dans le cas synchrone, déclencher des traitements. Cependant, les traitements sont considérés de durée non nulle. Par conséquent, un traitement peut être préempté par un autre, c’est-à-dire interrompu, et mis en attente, pour affecter les ressources de calcul à un autre traitement plus prioritaire par exemple.

Dans le cadre de cet article, nous considérons l’hypothèse asynchrone. Nous considérons que cette hypothèse est réaliste, notamment dans le cas des systèmes embarqués. Dans ce cas, les ressources de calcul se doivent d’être dimensionnées au plus juste de façon à maximiser l’autonomie énergétique du système. L’un des points centraux sous-jacents à l’hypothèse asynchrone est la gestion des ressources de calcul, et notamment du processeur. En fonction des traitements à exécuter à un instant donné, que nous appellerons des tâches, c’est le rôle de l’ordonnanceur de décider quelle tâche est exécutée sur le processeur, en fonction d’une stratégie d’ordonnancement.

L’ordonnanceur est l’entité centrale du noyau, cœur de l’exécutif ou système d’exploitation en charge de la gestion des ressources matérielles. Parmi les tâches prêtes à être exécutées, il choisit la tâche à exécuter suivant une certaine stratégie. Il y a deux grandes familles d’ordonnanceur : les ordonnanceurs en-ligne connaissent l’état courant des tâches actives, et se basent souvent sur des priorités pour choisir la tâche à élire. Les ordonnanceurs hors-ligne, souvent appelés séquenceurs, se basent sur la connaissance totale du système actuel, et de son futur, qui a permis, hors-ligne, de bâtir à l’avance une séquence d’ordonnancement qui est suivie à l’exécution. Dans cet article, nous parlerons principalement d’ordonnancement en-ligne qui est le type d’ordonnancement le plus répandu.

Le système de contrôle est donc multitâche, et les tâches sont ordonnancées par l’ordonnanceur. Il s'informe de l'état courant du procédé contrôlé à l'aide de capteurs, et agit sur celui-ci à l'aide d'actionneurs. Les contraintes de temps peuvent être de deux natures : les contraintes de bout-en-bout concernent une chaîne de traitement partant d'un ensemble de capteurs et se terminant à un ensemble d'actionneurs ; des contraintes locales dues à des limitations matérielles. Ainsi, lorsqu’un capteur fournit des informations au système en utilisant un bus de communication, sans l’aide d’un dispositif de mémorisation (de type buffer), le système doit lire des données entrantes avant qu’elles ne soient écrasées par les suivantes. Il arrive aussi qu’une commande envoyée à un actionneur doive absolument être rafraîchie à un certain rythme. De façon générale, dans la théorie utilisée pour la validation temporelle, toutes les contraintes temporelles, qu’elles soient locales ou de bout-en-bout, sont traduites sous forme de contraintes locales sur les tâches.

Le respect des contraintes temporelles est plus ou moins important : la violation de certaines contraintes peut mettre le système ou bien son environnement en péril : on parle alors de contraintes strictes. Au contraire, certaines contraintes concernent uniquement la qualité du service rendu par le système, dans ce cas on parle de contraintes relatives. Par exemple, l’attitude d’un aéronef peut être instable si le contrôle d’attitude (tangage, roulis) ne peut être exécuté une fois toutes les 50 millisecondes. Les contraintes de temps appliquées aux tâches du contrôle d’attitude sont strictes. On parle de contraintes fermes lorsque, sur une fenêtre temporelle donnée, un certain nombre de contraintes doivent être respectées afin de garantir l’intégrité du système. Respecter toutes les contraintes de temps augmente dans ce cas la qualité de service de l’application. On trouve peu de contraintes relatives dans le domaine du transport, mais on peut en trouver dans les applications non critiques telles les applications multimédia, ou le jeu vidéo. Dans cet article, seules les contraintes strictes sont considérées.

La problématique qui nous intéresse ici est comment assurer qu’étant donné un système de tâches partageant des ressources de calcul, toutes les contraintes temporelles seront toujours respectées : c’est la validation temporelle, qui repose sur une étude d’ordonnançabilité. Résoudre ce problème permet aussi de répondre à la question du dimensionnement : quelles ressources de calcul sont-elles nécessaires à une application temps réel donnée ?

Il est important de garder à l’esprit que « temps réel » ne signifie pas « rapidité », mais « temporellement déterministe ». Ainsi, on privilégie toujours le déterminisme à la vitesse d’exécution moyenne. La validation temporelle repose en effet sur le fonctionnement pire cas du système : il est primordial, sur un système critique, que le système ne se comporte jamais de manière erronée, et il est généralement intolérable que le système ne se comporte très bien qu’en moyenne, en étant parfois erroné. La validation des systèmes critiques se base donc sur les pires comportements du système : elle se doit donc d’être conservative, on parle aussi de pire cas.

Cet article est structuré de la façon suivante : afin de présenter le contexte global dans lequel la problématique de l’ordonnancement est soulevée, le chapitre 1 introduit les architectures matérielles et logicielles des applications. Nous verrons en particulier le fonctionnement de base des systèmes d’exploitation temps réel. Après avoir introduit les principes fondamentaux de l’ordonnancement temps réel, nous présentons les modèles temporels des tâches, qui seront utilisés lors de la validation temporelle. Ce chapitre introduit enfin les principaux types d’algorithmes d’ordonnancement, et les propriétés et mesures permettant de les caractériser.

Le chapitre 2 se focalise sur les tests d’ordonnançabilité, c’est-à-dire sur les moyens utilisés pour montrer qu’un système ordonnancé par un ordonnanceur respectera toujours toutes ses contraintes de temps. Nous commençons par les modèles les plus simples (tâches indépendantes), pour lesquels nous montrons les types de tests, classés par familles d’algorithmes d’ordonnancement considérées. Nous élargissons ensuite ces tests au cas de tâches communicantes ou se synchronisant.

Les derniers chapitres introduisent des outils liés à l’analyse d’ordonnançabilité et des points d’entrée vers des travaux plus spécifiques. Tout au long de cet article, certains points d’entrée de références bibliographiques seront cités. Le lecteur est invité à consulter [Doc. S 8 055v2] pour trouver les références complètes des travaux cités.

Cet article est réservé aux abonnés.
Il vous reste 94% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

KEYWORDS

survey   |   problems   |   solving technics   |   transport   |   energy   |   real-time systems   |   embedded and critical systems

VERSIONS

Il existe d'autres versions de cet article :

DOI (Digital Object Identifier)

https://doi.org/10.51257/a-v2-s8055


Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Cet article est réservé aux abonnés.
Il vous reste 95% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS

Sommaire
Sommaire

BIBLIOGRAPHIE

  • (1) - BINI (E.), DI NATALE (M.), BUTTAZZO (G.) -   « Sensitivity analysis for fixed-priority real-time systems »  -  Real-Time Systems, vol. 39, n° 11-3, pp. 5-30 (2008).

  • (2) - WILHELM (R.), ENGBLOM (J.), ERMEDAHL (A.), HOLSTI (N.), THESING (S.), WHALLEY (D.B.), BERNAT (G.), FERDINAND (C.), HECKMANN (R.), MITRA (T.), MUELLER (F.), PUAUT (I.), PUSCHNER (P.P.), STASCHULAT (J.), STENSTROM (P.) -   « The worst-case execution-time problem – overview of methods and survey of tools »  -  ACM Transactions in Embedded Computing Systems, vol. 7, n° 13, pp. 1-53 (2008).

  • (3) - AXER (P.), ERNST (R.), FALK (H.), GIRAULT (A.), GRUND (D.), GUAN (N.), JONSSON (B.), MARWEDEL (P.), REINEKE (J.), ROCHANGE (C.), SEBASTIAN (M.), VON HANXLEDEN (R.), WILHELM (R.), YI (W.) -   « Building Timing Predictable Embedded Systems »  -  ACM Transactions on Embedded Computing Systems (2012).

  • (4) - EISENBRAND (F.), ROTHVOß (T.) -   *  -  . – « Static-priority Real-time Scheduling : Response Time Computation is NP-hard », chez Proc. 29th Real-Time Systems Symposium, Barcelona, Spain (2008).

  • (5)...

1 Outils logiciels

Différents outils d’aide à l’ordonnancement existent ; certains d’entre eux peuvent être téléchargés gratuitement sur Internet. Les deux outils gratuits les plus répandus sont universitaires :

  • MAST (Modeling and Analysis Suite for Real-Time Applications) est un outil développé par l’université de Cantabria en Espagne. Il permet notamment de calculer des pires temps de réponse sur des systèmes monocœurs, centralisés ou répartis. MAST peut être trouvé à l’adresse http://mast.unican.ess

  • Cheddar est un outil développé par l’université de Brest ; il propose des simulations, ainsi que des calculs de pire temps de réponse dans le cas monocœur, et partiellement multicœurpartitionné, dans le cas centralisé et réparti. Cheddar peut être trouvé à l’adresse http://beru.univ-brest.fr/cheddar/

HAUT DE PAGE

Cet article est réservé aux abonnés.
Il vous reste 92% à découvrir.

Pour explorer cet article
Téléchargez l'extrait gratuit

Vous êtes déjà abonné ?Connectez-vous !


L'expertise technique et scientifique de référence

La plus importante ressource documentaire technique et scientifique en langue française, avec + de 1 200 auteurs et 100 conseillers scientifiques.
+ de 10 000 articles et 1 000 fiches pratiques opérationnelles, + de 800 articles nouveaux ou mis à jours chaque année.
De la conception au prototypage, jusqu'à l'industrialisation, la référence pour sécuriser le développement de vos projets industriels.

Cet article fait partie de l’offre

Automatique et ingénierie système

(140 articles en ce moment)

Cette offre vous donne accès à :

Une base complète d’articles

Actualisée et enrichie d’articles validés par nos comités scientifiques

Des services

Un ensemble d'outils exclusifs en complément des ressources

Un Parcours Pratique

Opérationnel et didactique, pour garantir l'acquisition des compétences transverses

Doc & Quiz

Des articles interactifs avec des quiz, pour une lecture constructive

ABONNEZ-VOUS