Soutenance mémoire
L’environnement et la sécurité sont deux préoccupations actuelles majeures du secteur automobile. La première pousse les industriels vers des solutions de motorisation toujours plus élaborées : moteurs hybrides, contrôle de l’injection [38], récupération d’énergie au freinage, stop and start, etc. Concernant la seconde, on peut noter que sur les routes de France, l’ONISR déplorait encore en 2009 plus de 74 000 accidents et près de 4 500 décès. Or, dans 95% des cas, la responsabilité du conducteur est engagée. La logique voudrait qu’à l’avenir l’industrie et les pouvoirs publics travaillent au remplacement de l’élémentdéfaillant du système – le conducteur – par un système automatisé plus fiable [47]. La multiplication des systèmes d’aide à la conduite participent de cet effort : freinage d’urgence (BAS), antipatinage (ABS), contrôle de trajectoire (ESP), protection en cas d’accident (Airbag), contrôle de distance de sécurité (ACC) etc. Mais pour aller plus loin, c’est-à-dire pour automatiser la conduite, les véhicules devront non seulement communiquer avec l’infrastructure routière et des serveurs de trafic mais également échanger des informations entre eux.
L’an 2000 annonçait une révolution robotique dans notre quotidien. Dix ans après, deux constats s’imposent : l’humanoïde grand public a encore un peu de difficultés à tenir debout [61] mais la « technologie » avance tout de même à pas de géant. Tandis que les aspirateurs automatiques envahissent petit à petit les maisons individuelles [70], on parvient à cartographier un territoire inconnu à l’aide de robots totalement autonomes [8]. Pour le futur, les idées d’applications robotiques ne manquent pas : applications chirurgicales, militaires, spatiales, industrielles, etc. L’actualité nous fait rêver à des robots capables d’interventions en milieu fortement radioactif ; les militaires réfléchissent à des robots capables d’intervenir sur le champ de bataille ; on envisage des systèmes capables de prendre en partie en charge la dépendance des personnes, etc. Notre environnement s’automatise et se robotise de plus en plus. A l’avenir, il ne s’agira plus seulement de concevoir un robot capable d’effectuer une tâche donnée mais d’inscrire chaque nouveau système dans un schéma d’interaction global ou interviennent l’environnement, l’être humain et les autres systèmes robotiques. Plus encore, certaines tâches complexes seront prises en charge par des systèmes robotisés coopératifs .
UN MODÈLE D’EXÉCUTION TEMPS-RÉEL DISTRIBUÉ DÉTERMINISTE
L’ORDONNANCEMENT ÉVÈNEMENTIEL TEMPS-RÉEL PEUT-IL ÊTRE DÉTERMINISTE ?
Pour Kopetz [43], les systèmes temps-réel distribués sont répartis en deux mondes selon que leur ordonnancement est de type temporel ou de type évènementiel. L’ordonnancement temporel (Time Triggered), [44], [9], consiste à partager statiquement le temps disponible entre les tâches allouées à une même cible matérielle en tenant compte des communications nécessaires entre les différentes cibles. Dans ce type d’ordonnancement, toutes les tâches sont ordonnancées de façon périodiques selon une horloge globale à toutes les cibles du système. Tout (tâches, communications, utilisation des ressources, etc.) est alors planifié de façon statique sur une échelle de temps globale et cyclique, si bien que, moyennant une allocation suffisante de temps à chaque tâche et à chaque échange d’information, le comportement du système est parfaitement prévisible et ses délais de réaction sont totalement maitrisés. Le système peut donc être qualifié de sûr. La difficulté principale de ce type d’ordonnancement réside justement dans la détermination du temps à allouer à chaque tâche. Pour garantir le fonctionnement du système dans tous les cas, un majorant du temps d’exécution dans le pire cas de figure (Worst Case Execution Time) doit être connu pour chaque tâche et chaque échange de données. Ce temps est particulièrement difficile à déterminer à cause, d’une part, des architectures matérielles actuelles compte-tenu des caches mémoire, des pipelines et de l’architecture des réseaux de communications [90], [67], [5] et, d’autre part, de la complexité des algorithmes mis en oeuvre. Par ailleurs, l’ajout d’une tâche suppose de revoir la synchronisation globale du système. Rappelons que dans notre contexte, toute étude statique de l’ensemble del’application est proscrite du fait du caractère dynamique de l’architecture des applications que l’on vise. Ce point exclut, de fait, un ordonnancement purement temporel.
L’ordonnancement évènementiel (Event Triggered) consiste à associer le déclenchement de l’activité des tâches à des évènements internes (sémaphore, message, etc. [22]) ou externes (interruption) au système. Pour permettre aux actions les plus critiques d’être effectuées sans délai, l’ordonnancement mis en œuvre est dynamique. La politique adoptée repose en général sur l’attribution d’une priorité constante à chaque tâche [52]. Lorsqu’une tâche est déclenchée par un évènement, elle est exécutée si sa priorité est plus importante que la tâche en cours d’exécution, cette dernière est donc préemptée. Dans le cas contraire, elle est mise en attente d’exécution jusqu’à ce qu’elle devienne la tâche active la plus prioritaire. Ajouter une tâche conduit à intercaler la priorité de cette nouvelle tâche dans la table des priorités de la cible. La contrepartie de cette relative simplicité est qu’il est bien difficile de prévoir avec certitude le comportement de l’application [50], tant en termes de comportement que de respect des contraintes temps-réel, en particulier dans les cas de charges exceptionnelles du système. L’ordre d’exécution des tâches ainsi que les instants d’accès aux données ne sont pas prévisibles à priori compte-tenu des évènements externes, des préemptions possibles et des exclusions mutuelles. Il en résulte une forte indétermination sur la disponibilité temporelle exacte des différentes données du système. Autrement dit, la causalité de la production des données n’est pas assurée ce qui conduit au nondéterminisme comportemental global du système. Concernant le respect des contraintes temps-réel, les cas de charges exceptionnelles du système montrent de façon évidente les limites de ce type d’approche. A moins de prendre des marges colossales dans le dimensionnement des cibles matérielles, le dépassement de capacité est toujours une éventualité à envisager. La préoccupation de pouvoir prouver le respect des contraintes temps-réel a fait émerger une classe particulière de systèmes où toutes les tâches critiques sont de nature périodique. Il est alors possible de prouver que, sous certaines conditions, les contraintes temps réel sont garanties [73]. Ce type de système domine largement les applications de contrôle car il est à la fois souple et relativement sûr, bien qu’il ne soit pas déterministe.
Kopetz conclut que l’ordonnancement temporel sera donc préféré dans des contextes où la principale exigence est la sûreté de fonctionnement, c’est-à-dire le respect strict des contraintes temps-réel et le déterminisme comportemental, tandis que l’ordonnancement évènementiel trouvera naturellement sa place dans des systèmes moins critiques où l’on recherche plus d’agilité dans la conception et la maintenance du système.
La comparaison frontale que Kopetz effectue entre les deux approches laisse entrevoir l’intérêt de trouver le meilleur compromis entre souplesse et sûreté de fonctionnement. Il est entendu que le respect des contraintes temps-réel ne peut plus être prouvé en pratique dès lors que le déclenchement des tâches s’écarte d’un modèle périodique [73]. S’orienter vers un système réellement évènementiel, c’està-dire acceptant des tâches critiques non-périodiques, condamne de ce point de vue à l’expression de contraintes temps-réel tout au plus probabilistes. Le temps réel dur n’est véritablement accessible qu’aux systèmes périodiques, quelque soit la nature de l’ordonnancement. Pour autant, on peut se demander si le déterminisme comportemental, au sens des données produites par les traitements, ne reste pas néanmoins accessible. Lee [49] pense l’objectif tout a fait atteignable à condition de remettre en cause radicalement les fondements même de la discipline. Le problème sous-jacent est celui du respect de la causalité dans l’ordonnancement des tâches et la mise à jour des données. C’est donc plus un problème de principe d’ordonnancement que de nature (évènementielle ou temporelle) de l’activation des tâches.
De l’origine du non-déterminisme
Les systèmes à ordonnancement évènementiel ne sont pas prévisibles. Ce point a été évoqué dans l’introduction de ce chapitre. Ce non-déterminisme trouve sa source dans le principe même de l’ordonnancement par priorité utilisé classiquement dans les systèmes temps-réel évènementiels.
Où l’on analyse l’origine du non-déterminisme comportemental
Les systèmes temps-réel évènementiels, tels qu’ils sont classiquement implémentés, reposent sur un ordonnancement préemptif à priorités. Chaque tâche se voit attribuer une priorité d’exécution qui lui permet d’être exécutée préférentiellement aux tâches de niveau inférieur, éventuellement en interrompant l’exécution de celles-ci.
Raisonnons sur le cas simple à trois tâches présenté figure 6. La tâche B consomme des données produites par les tâches A et C. Elle est synchronisée sur la tâche A ; la relation entre C et B est supposée non bloquante. Les priorités respectives de ces trois tâches sont définies de la façon suivante : la tâche A est la plus prioritaire, vient ensuite la tâche B, puis la tâche C. Examinons le cas de figure où la tâche C est activée avant la tâche A. La durée d’activation de la tâche C n’étant pas constante , deux cas peuvent se présenter : dans le premier cas, la tâche C se termine avant l’activation de la tâche A ; dans le second cas, la tâche C n’est pas terminée lorsque la tâche A est activée, elle est donc préemptée par cette dernière, puis par la tâche B.
|
Table des matières
INTRODUCTION
CHAPITRE 1 L’ORDONNANCEMENT ÉVÈNEMENTIEL TEMPS-RÉEL PEUT-IL ÊTRE DÉTERMINISTE ?
1 De l’origine du non-déterminisme
1.1 Où l’on analyse l’origine du non-déterminisme comportemental
1.2 Où l’on fixe la durée apparente d’exécution des tâches – Le temps logique d’exécution
1.3 Le temps, la cause et la conséquence
2 La causalité au cœur de l’exécution – La simulation distribuée à évènements discrets
2.1 Parallélisme et causalité – Principe de la simulation à évènements discrets
2.2 La simulation distribuée conservative
2.3 L’optimisme de Jefferson et la distorsion du temps
3 De la simulation à l’exécution temps-réel
3.1 Un modèle d’exécution distribuée conservatif
3.2 Les protocoles optimistes sont-ils ordonnançables ?
3.3 La synchronisation temps-réel des simulateurs distribués optimistes
CHAPITRE 2 VERS UN MODÈLE ÉVÈNEMENTIEL TEMPS-RÉEL DÉTERMINISTE
1 Principe de synchronisation temps-réel
1.1 Le cadre exécutif : des tâches, des signaux, des processus et des messages
1.2 Deux types de tâches : les tâches temps-virtuel et les tâches temps-réel
1.3 Rôle de la latence
2 Politique d’ordonnancement
2.1 Comment trop d’avance peut compromettre le respect des contraintes temps-réel
2.2 Le délai de garde
2.3 Estimation du délai de garde en temps-réel
3 Vers l’ordonnancement temporel
3.1 Une comparaison avec l’ordonnancement temporel
3.2 Vers l’ordonnancement temporel
CHAPITRE 3 LE PROTOCOLE DE SYNCHRONISATION
1 Des tâches au temps
1.1 Du modèle structurel au modèle d’exécution
1.2 Les problèmes de propagation, de convergence et de causalité : deux cas tordus
1.3 De la définition du temps
2 Le graphe causal et le protocole de synchronisation
2.1 Topologie du graphe causal
2.2 Le retour arrière
2.3 Nettoyage de la mémoire
3 Quand rien ne va plus
3.1 Découpler les niveaux hiérarchiques de l’application
3.2 Respecter la latence des tâches temps-réel
3.3 Fiabiliser l’exécution des tâches critiques
CHAPITRE 4 COMPOSANTS, TÂCHES, VARIABLES – LE MODÈLE STRUCTUREL
1 Des composants qui hébergent des variables et des tâches
1.1 Deux familles d’objets : les conteneurs et les terminaux
1.2 Des propriétés et des paramètres communs
1.3 Portée et durée de vie des objets
2 Le composant est l’objet structurel de base
2.1 Le port d’entrées/sorties relie le composant à son environnement
2.2 Les propriétés et paramètres renseignent sur l’état du composant
2.3 Le corps décrit la structure ou le comportement du composant
2.4 Héritage entre composants
3 Les variables, leur type et leur comportement
3.1 Le typage des variables est dynamique
3.2 Comportement temporel de l’affectation des variables
3.3 Connectivité et variable de port d’entrées/sorties
3.4 Propriétés et paramètres des variables
4 Les propriétés et les paramètres
4.1 Définition et politique d’accès des propriétés et paramètres
4.2 Association d’une propriété à une variable
4.3 Définition de paramètre de composant ou de canal
5 Les tâches portent le code actif de l’application
5.1 Quatre variantes de tâches : les tâches temps-réel, les tâches temps-virtuel, les boites d’horloges et boites de découplage
5.2 Déclenchement sur évènement interne
5.3 Déclenchement sur évènement externe
5.4 Déclenchement temporel : Timeout et Timeslot
5.5 Un corps en trois blocs : initial, final et always
5.6 La latence des tâches temps-réel
6 Des méthodes pour abstraire les échanges d’informations
6.1 Définition
6.2 Topologie
6.3 Appel
7 Les canaux structurent les interconnexions
7.1 Principe topologique et définition
7.2 Les protocoles
CONCLUSION
