Brevet FR3015067A1 — publié le 20150619

PROCEDE DE COMPOSITION ET D'EXECUTION D'UN PLAN DE SEQUENCEMENT DE TACHES TEMPS-REEL Domaine technique de l'invention L'invention est relative aux systèmes multitâches temps-réel critiques, tels que les 5 systèmes de contrôle-commande utilisés dans les domaines des transports (automobile, ferroviaire, naval, aéronautique), des automates industriels, de l'énergie, ainsi que d'autres systèmes pour lesquels l'allocation maîtrisée des ressources est importante, comme dans les réseaux de communications. L'invention concerne aussi bien les systèmes temps-réel pour lesquels un haut niveau de performance dans la mise en 10 oeuvre est requis que les systèmes critiques pour lesquels un haut niveau de garantie est exigé quant à l'utilisation des ressources matérielles d'exécution allouées pour chaque tâche du système. Arrière-plan de l'invention Dans les systèmes temps-réel critiques, c'est-à-dire qui ne peuvent tolérer aucune 15 violation d'échéance par une mise en retard de l'exécution d'une opération, les tâches sont souvent exécutées selon des méthodes d'ordonnancement statique. On construit alors hors-ligne une allocation temporelle statique du besoin d'utilisation des ressources d'exécution, ce qui permet de démontrer l'indépendance temporelle des tâches entre elles en ce qui concerne l'utilisation des ressources, et en particulier du processeur. Une 20 telle approche est décrite, par exemple, dans l'article ["A method and a technique to model and ensure timeliness in safety critical real-time systems", C. Aussaguès, V. David, Fourth IEEE International Conference on Engineering of Complex Computer Systems, 1998], et dans les demandes de brevet W02006-050967 et US2010-0199280. Cependant, ce type d'approche impose de ne considérer qu'un plan de séquencement 25 unique pour toutes les activités, donc de ne considérer qu'une seule base de temps pour déterminer les échéances. Cela rend difficile une mise en oeuvre sans interférence, sur un même processeur, de tâches ayant des bases de temps non-corrélées, comme une tâche utilisant une horloge pour déterminer ses échéances et une tâche utilisant une position d'un objet de vitesse variable pour déterminer ses échéances. Il faudrait pour 30 cela construire deux plans de séquencement cadencés par une même base de temps pour pouvoir les composer en un seul plan de séquencement sans interférences entre tâches. Cela n'est en pratique réalisable que si les ressources d'exécution sont largement surdimensionnées pour pouvoir envisager le pire-cas de chaque situation. Dans les systèmes temps-réel à haut degré de performance, qui ne sont pas dits « critiques » car ils peuvent tolérer des violations d'échéance dans une certaine marge, la composition de deux plans de séquencement cadencés par des bases de temps différentes est réalisée par des algorithmes d'ordonnancement dynamiques. De tels algorithmes sont décrits, par exemple, dans ["Scheduling algorithms for multiprogramming in a hard real-time environment", C. Liu, J. Layland, Journal of the ACM, vol. 20, no. 1, pp. 46-61] et ["Foundations of Real-Time Computing: Scheduling and Resource Management", edited by André M. Van Tilborg, Gary M. Koob, 1991, Kluwer Academic Publishers], et également dans ["A method and a technique to model and ensure timeliness in safety critical real-time systems", C. Aussaguès, V. David, Fourth IEEE International Conference on Engineering of Complex Computer Systems, 1998]. Avec ces algorithmes, des préemptions sont inévitables, c'est-à-dire que le système d'exploitation peut interrompre une opération en cours pour exécuter une opération plus urgente. L'ordonnancement étant dynamique, le nombre et la durée des préemptions n'est pas déterminable, et chaque préemption consomme un temps système pour effectuer un changement de contexte. Cela crée des interférences entre tâches, de sorte que les systèmes sont plus difficiles à dimensionner, moins prédictibles et non reproductibles sur des architectures de processeurs complexes. Les concepteurs de ces systèmes rencontrent en outre des difficultés pour régler correctement les priorités des tâches ou les échéances dans un système avec deux bases de temps différentes. Les options choisies, comme la variation des besoins d'exécution selon la valeur de paramètres applicatifs, rend très complexes et non maitrisables les systèmes construits de la sorte. Résumé de l'invention On souhaite ainsi disposer d'une technique permettant d'exécuter en temps partagé deux plans de séquencement sans interférence, et cela même si les bases de temps des deux plans sont différentes. On tend à satisfaire ce besoin en prévoyant un procédé d'exécution de deux tâches en temps partagé, comprenant les étapes consistant à décomposer hors-ligne chaque tâche en une séquence répétitive de trames successives, où chaque trame est associée à une opération atomique ayant un besoin d'exécution, et définit une date de début à partir de laquelle l'opération peut commencer et une date d'échéance à laquelle l'opération doit être terminée, d'où il résulte que chaque trame définit une marge de temps dans laquelle l'opération peut démarrer ; vérifier pour chaque trame d'une première des séquences répétitives que l'opération correspondante peut être exécutée entre deux opérations successives quelconques d'un groupe de trames de la deuxième séquence répétitive, chevauchant la trame (Fai) de la première séquence répétitive, tout en respectant les dates de début et les échéances des opérations ; et si la vérification est satisfaite, autoriser l'exécution des deux tâches. Les opérations des deux tâches sont alors ordonnancées selon les cas suivants évalués à chaque date clé, où une date clé survient à chaque échéance, chaque date de début, et chaque fin d'exécution d'opération : si deux opérations peuvent démarrer, exécuter celle qui a l'échéance la plus courte ; et si une seule opération peut démarrer, l'exécuter seulement si son besoin d'exécution est inférieur à la durée restant jusqu'à la date de début de la prochaine trame de l'autre séquence, augmentée de la marge de temps associée à ladite prochaine trame de l'autre séquence. Selon un mode de mise en oeuvre, chaque trame comprend en outre un intervalle de 15 temps de réserve pouvant être nul, situé après l'échéance de la trame ou avant la date de début de la trame, les intervalles de temps de réserve de l'une quelconque des séquences répétitives pouvant être pris pour exécuter une opération de l'autre séquence répétitive. Selon un mode de mise en oeuvre, l'étape de vérification comprend les étapes suivantes : 20 - pour chaque trame Fai de la première séquence répétitive, évaluer les conditions suivantes pour chaque trame Fbi de la deuxième séquence répétitive : [A.1] Dai Selon un mode de mise en oeuvre, les bases de temps déterminant les durées des trames sont variables de sorte que les marges de temps T et les réserves de temps R varient d'un facteur 1 à za pour les trames Fa et de 1 à zb pour les trames Fb, l'étape de vérification comprenant alors les étapes suivantes : - si la condition [A.1] est fausse, évaluer la condition suivante : [A.2] Dai Selon un mode de mise en oeuvre, l'étape de vérification comprend les étapes suivantes : - si la condition [B.1] est fausse, évaluer avant la condition [B.2] la condition suivante : [B.1.1] Dai La figure 2 représente la structure temporelle d'une trame F. Le début de la trame correspond à la date à partir de laquelle l'opération peut commencer. La trame définit une échéance E à laquelle l'opération doit être terminée. L'opération est supposée atomique, c'est-à-dire qu'elle ne peut pas être suspendue pour exécuter une autre opération. L'échéance E peut être séparée de la fin de la trame par un intervalle de temps de réserve R optionnel, c'est-à-dire pouvant être nul. Un intervalle de temps D est le besoin d'exécution de l'opération associée à la trame. Le besoin d'exécution D correspond, par exemple, au nombre de cycles d'horloge de processeur requis pour exécuter l'opération - il peut ainsi être exprimé en un temps fixe en fonction des caractéristiques du processeur du système cible. Un intervalle T correspond à la marge de temps entre le début de la trame et l'échéance E pour exécuter l'opération. Ainsi, comme le représente la figure 2, l'opération D peut commencer à tout instant entre le début de la trame, où l'intervalle T sépare la fin de l'opération et l'échéance, et une durée T après le début de la trame, où l'opération se termine juste à l'échéance E. Pour les situations intermédiaires, on note qT l'intervalle entre la fin de l'opération et l'échéance, avec 0 La somme des intervalles de réserve R correspond, par exemple, à un temps que le programmeur alloue au système pour effectuer des opérations non temps-réel, comme des entrées/sorties. Deux tâches que l'on souhaite exécuter en temps partagé sur un système temps-réel critique sont ainsi décomposées en séquences répétitives de trames. Pour que les tâches puissent être exécutées sans interférence, c'est-à-dire en respectant l'atomicité des opérations, on cherche à composer les séquences de sorte que chaque opération d'une séquence puisse à tout moment être exécutée entre deux opérations successives de l'autre séquence, tout en respectant les contraintes des trames des deux séquences, à savoir les échéances et les débuts de trame. Les figures 3A à 3C représentent différentes situations pouvant être rencontrées au déroulement de deux séquences RSFa et RSFb. On suppose, pour simplifier les explications, que les intervalles de réserve R sont nuls. A la figure 3A, à titre d'exemple, la séquence RSFa comprend trois trames Fai à Fa3 de paramètres respectifs (Dai = 3, Tai = 6), (Da2 = 4, Tag =1), et (Da3 = 1, Tai = 1), où les valeurs de temps sont exprimées en unités normalisées. La séquence RSFb commence 3 unités après le début de la trame Fal et elle comprend deux trames Fbi et Fb2 de paramètres respectifs (Dbi = 4, Tb' = 5) et (Db2 = 3, Tb2 = 4). L'opération Dai commence une unité après le début de la trame correspondante. A la fin de l'opération Dai, on ne peut pas encore démarrer l'opération Da2, mais on peut démarrer l'opération Dbi. A la fin de l'opération Dbi, aucune opération n'est prête à être exécutée. On attend le début de la trame Fat, ici l'échéance Eal, pour démarrer l'opération Da2. A la fin de l'opération Da2, l'opération Db2 est prête pour exécution, mais on ne peut pas la lancer. En effet, si l'opération Db2 était lancée tout de suite, elle se terminerait juste à l'échéance Ea3, de sorte que l'opération Da3 ne pourrait pas s'exécuter avant cette échéance. Dans ce cas, on attend le début de la trame Fa3 pour lancer l'opération Da3. Enfin, à la fin de l'opération Da3, on peut démarrer l'opération Db2. A la figure 3B, les mêmes paramètres sont conservés, sauf que l'opération Dai démarre trois unités après le début de la trame. Les opérations Dbi et Da2 se trouvent retardées de deux unités par rapport à la figure 3A, tout en respectant les contraintes des trames correspondantes. L'opération Da2 se termine juste à son échéance Ea2. A la figure 3C, les mêmes paramètres sont conservés, sauf que l'opération Dai démarre 10 quatre unités après le début de la trame. Les opérations Dbi et Da2 se trouvent retardées de trois unités par rapport à la figure 3A. L'opération Dbi peut encore être exécutée en respectant son échéance Ebi, mais l'opération Da2 viole son échéance Ea2. Une première étape commune aux techniques visées ici est la composition, pour deux tâches à exécuter en temps partagé, de deux séquences répétitives RSFa et RSFb qui 15 puissent être déroulées dans les conditions de la figure 3A ou 3B, quel que soit le décalage temporel entre les débuts des séquences. Cette composition est statique, c'est-à-dire faite hors-ligne par le programmeur. Une deuxième étape est la vérification que deux séquences quelconques sont compatibles, c'est-à-dire qu'elles peuvent être déroulées de sorte que chaque opération 20 puisse être exécutée en respectant ses contraintes, comme aux figures 3A et 3B. Cette vérification de compatibilité peut être mise en oeuvre dans un outil de développement permettant au programmeur de composer les séquences par essais successifs. Elle est de préférence mise en oeuvre également dans le système temps-réel lui-même, au chargement pour exécution des plans de séquencement définis par les 25 deux séquences répétitives. Le système peut alors être configuré pour refuser de démarrer si les séquences sont détectées comme incompatibles. Une troisième étape est l'ordonnancement sur le système temps-réel des opérations des deux séquences. Comme le montrent les figures, il ne suffit pas d'alterner les opérations de la première séquence avec les opérations de la deuxième séquence ou de démarrer 30 une opération dès qu'elle est prête pour exécution. L'ordonnancement est effectué selon les cas suivants, évalués à chaque date clé. Les dates clés sont les débuts de trame des deux séquences, les échéances, et les fins d'opération. Lorsque les intervalles de temps de réserve R (figure 2) sont nuls, comme c'est le cas dans les exemples présentés, les échéances coïncident avec des débuts de trame. Pour une date clé donnée associée à une première des séquences, on appelle « trame concurrente » la trame en cours de la deuxième séquence. 1) Aucune opération ne peut démarrer. Ce cas se produit lorsqu'une opération est déjà en cours (comme à l'échéance Ebi de la figure 3A), ou bien à la fin d'une opération qui s'est exécutée entre l'opération de la trame concurrente et son échéance, comme pour l'opération Dbi de la figure 3A. Dans ce cas, on attend la date clé suivante. 2) Deux opérations peuvent démarrer. Ce cas se produit généralement lorsque débute une trame et qu'une opération est en attente dans la trame concurrente, comme c'est le cas à l'échéance Ea2 des figures 3A et 3B. On exécute alors l'opération qui a l'échéance la plus courte (Da3 dans les figures 3A et 3B). Le cas se produit également lorsque deux trames concurrentes débutent en même temps. 3) Une seule opération peut démarrer. Ce cas se produit généralement à la fin d'une opération (Dai), ou au début d'une trame lorsque l'opération de la trame concurrente a terminé (Eai, figure 3A). On exécute alors l'opération seulement si son besoin d'exécution est inférieur ou égal à la durée restant jusqu'au début de la prochaine trame concurrente, augmentée de la marge de temps associée à cette trame concurrente. Par exemple, à la figure 3A, l'opération Da2 est prête à démarrer à l'échéance Eal, il reste 3 unités jusqu'au début de la trame Fb2, et Tb2 = 4. L'opération Da2 est démarrée car Da2 = 4 1 + 1. On définit maintenant des critères de compatibilité entre deux séquences répétitives RSFa et RSFb quelconques servant à définir des plans de séquencement pour un système temps-réel. Une vérification de compatibilité exhaustive consisterait à examiner toutes les combinaisons possibles de positions des opérations dans leurs trames et toutes les positions possibles d'une des séquences par rapport à l'autre, avec une granularité d'un cycle d'horloge, pour évaluer si les opérations concurrentes peuvent être exécutées selon les contraintes imposées. Une telle vérification exhaustive serait difficile à réaliser dans un temps raisonnable. On cherche des critères simplifiés qui puissent être évalués en ligne sur le système temps-réel au moment du chargement des plans de séquencement accompagnant le code exécutable des tâches. Pour cela, on envisage trois hypothèses générales de 5 positionnement de chaque trame de l'une des séquences par rapport à chaque trame de l'autre séquence. Pour chaque hypothèse, on cherche à vérifier que l'opération de la trame considérée Fai peut être exécutée dans un intervalle libre laissé par les trames concurrentes Fbi, Fbi_pi... chevauchant la trame Fai. Deux trames Fai et Fbi sont considérées comme compatibles lorsque la vérification est satisfaite pour chacune des 10 trois hypothèses. - Hypothèse (A) : la trame considérée Fai débute alors que l'opération Dbi de la première trame concurrente Fbi a été exécutée. - Hypothèse (B) : l'opération de la première trame concurrente est en cours d'exécution. 15 - Hypothèse (C) : l'opération de la trame concurrente n'a pas démarré. Pour chaque hypothèse on cherche des critères indépendants de la position relative des trames. Pour cela, de façon générale, on minore les intervalles de temps inconnus servant à trouver des créneaux pour exécuter les opérations, et on majore les intervalles de temps inconnus servant à vérifier le respect des échéances. 20 Les figures 4A à 4C illustrent des exemples de trames pouvant servir à l'élaboration de critères de compatibilité selon l'hypothèse (A). La trame considérée Fa, démarre pendant la trame concurrente Fbj, alors que l'opération Dbj de cette trame concurrente est terminée. La trame Fa, chevauche la trame concurrente suivante Fbrpi. Tout ce qu'on sait du début de la trame Fa, est qu'il est situé dans un intervalle qTbj suivant la fin de 25 l'opération Dbj, où 0 qi, on est certain que l'exécution sur le système réel a lieu selon la figure 4C et que l'on n'est pas amené à considérer la situation de la figure 4B. Le pire cas pour la 25 figure 4B est alors q = ql, de sorte que : + Dbj+i Les conditions résultant de la situation de la figure 4B sont donc : Dai D'après la figure 5A, on a : Dai La vérification de la compatibilité de deux séquences répétitives RSFa et RSFb, ayant respectivement Na et Nb trames, peut être résumée par le pseudo-code suivant. Dans ce pseudo-code, on a condensé des conditions alternatives dans des expressions min(x, y) du côté gauche des inéquations, et max(x, y) du côté droit des inéquations, et on a 5 condensé des conditions nécessaires dans des expressions min(x, y) du côté droit des inéquations, et max(x, y) du côté gauche des inéquations. On a prévu des conditions A.3 et B.3, mentionnées précédemment, pour tenir compte de l'éventualité où la trame Far chevaucherait quatre trames Fbi à Fbi+3. Les opérations sur les indices i et j sont bien entendu effectuées modulo la valeur maximale de l'indice (Na pour i, et Nb pour j), 10 puisque les séquences de trames sont répétables à l'infini. Pour chaque i entre 0 et Na-1 faire : Pour chaque j entre 0 et Nb-1 faire : [A. 1] si Da, 1 ou Th/ = 0 alors qi := 1 si Da, 1 ou Tb; = 0 alors qi := 1 et continuer en [B. 2] Ti:Ta7.1(1-q)Tb; 35 si Db1_i Dans cette boucle, selon une variante par rapport a ce qui a été décrit précédemment, avant de passer à l'évaluation de la condition B.2, on évalue une condition B.1.1. La figure 7 illustre un exemple de succession de trames servant à établir la condition B.1.1. Les trames Fa, et Fb, sont dans les mêmes conditions qu'à la figure 4A, mais au lieu de démarrer l'opération au début de la trame Fbi+1, on suppose qu'on peut la démarrer immédiatement après l'opération Dbi, et on cherche dans les trames précédentes Fa,_, et Fb,_, les conditions générales qui le permettent avec q = qi. La condition B.1.1, comme la condition B.1, est basée sur l'hypothèse que la trame Fa, chevauche deux trames (Fb, et Fbi+,), ce qui correspond à une situation plus probable à rencontrer que celle où la trame Fa, chevauche trois trames ou plus. Comme on l'a précédemment indiqué, les trames peuvent incorporer un temps de réserve R pouvant être pris par le système pour effectuer des tâches non temps-réel. Un tel temps de réserve peut être pris pour exécuter des opérations temps-réel. Il vient s'ajouter aux marges de temps T d'une séquence pour favoriser l'exécution des opérations D de l'autre séquence, mais il peut durcir les conditions de respect des échéances. Des temps de réserve R non-nuls peuvent notamment assouplir la condition C.1. La figure 8 illustre un exemple de succession de trames servant à établir une contrainte assouplie dans le cas où la condition C.1 n'est pas satisfaite, c'est-à-dire si Db, > Ta,. Dans le cadre de l'hypothèse C, on suppose que l'opération Db, n'a pas encore démarré 35 au début de la trame Fa,. L'opération Da' ayant l'échéance la plus courte, est démarrée dès le début de la trame Fai. La trame Fbi démarre avant la trame Fat, on suppose pendant l'intervalle Raki de la trame Fai4. On note kRai4 l'intervalle entre le début de la trame Fbi et le début de la trame Fai, avec 0 kRai_ + On note 1(1 la valeur limite de k telle que Dbj = + Tai, soit k1= (Dbi-Tai)/Rai4. Si k > k1, on est sûr que l'opération Dbj peut être ordonnancée avant le début de la trame Fa, - ce cas n'est pas à considérer, car il ne correspond pas à l'hypothèse C. On ne considère alors que les valeurs de k comprises entre 0 et k1. Pour que Dai puisse s'exécuter, il faut que Dai Pour chaque i entre 0 et Na-1 faire : Pour chaque j entre 0 et Nb-1 faire : [A.1] si Dai 1 ou Th/ + Rh/ = 0 alors qi := 1 si Dai 1 ou Tb; = 0 alors qi := 1 et continuer en [B.2] [B.1.1] Tai_I - (1-q)Th; + Rai_I si Dbi_i 1 pour chaque séquence répétitive, za et zb respectivement pour les séquences RSFa et RSFb. Les coefficients za et zb sont fixes et représentent le ralentissement maximal subi par les intervalles T et R dans les deux séquences. En supposant que les notations utilisées dans les relations précédentes représentent les valeurs minimales des intervalles, chacune des valeurs T et R peut ainsi prendre deux valeurs, T ou zT et R ou zR. Les besoins d'exécution D sont fixes, car ils dépendent seulement de l'horloge du système. Dans les relations précédentes, lorsqu'un intervalle sert à trouver un créneau pour exécuter une opération, on garde sa valeur minorée T ou R. Lorsque l'intervalle sert à vérifier le respect d'une échéance, on prend sa valeur majorée zT ou zR. On obtient alors le pseudo-code suivant. Pour chaque i entre 0 et Na-1 faire : Pour chaque j entre 0 et Nb-1 faire : [A.1] si Da, 1 ou Tbi + = 0 alors qi := 1 si Da, 1 ou Tb; = 0 alors qi := 1 et continuer en [B.2] T1 Tai_I - (1-q)Tb; + Rai_I si Dbi_i REVENDICATIONS1. Procédé d'exécution de deux tâches en temps partagé, comprenant les étapes suivantes : - décomposer hors-ligne chaque tâche en une séquence répétitive de trames successives (RSF), où chaque trame (F) est associée à une opération atomique ayant un besoin d'exécution (D), et définit une date de début à partir de laquelle l'opération peut commencer et une date d'échéance (E) à laquelle l'opération doit être terminée, d'où il résulte que chaque trame définit une marge de temps (T) dans laquelle l'opération peut démarrer ; - vérifier pour chaque trame (Far) d'une première des séquences répétitives (RSFa) que l'opération correspondante (Dai) peut être exécutée entre deux opérations successives quelconques d'un groupe de trames (Fbi, Fbi+i) de la deuxième séquence répétitive (RSFb), chevauchant la trame (Far) de la première séquence répétitive, tout en respectant les dates de début et les échéances des opérations ; et - si la vérification est satisfaite, autoriser l'exécution des deux tâches et ordonnancer les opérations des deux tâches selon les cas suivants évalués à chaque date clé, où une date clé survient à chaque échéance, chaque date de début, et chaque fin d'exécution d'opération : - si deux opérations (Da3, Db2) peuvent démarrer, exécuter celle (Da3) qui a l'échéance la plus courte ; et si une seule opération peut démarrer, l'exécuter seulement si son besoin d'exécution est inférieur à la durée restant jusqu'à la date de début de la prochaine trame de l'autre séquence, augmentée de la marge de temps (T) associée à ladite prochaine trame de l'autre séquence. 2. Procédé selon la revendication 1, dans lequel chaque trame (F) comprend en outre un intervalle de temps de réserve (R) pouvant être nul, situé après l'échéance (E) de la trame ou avant la date de début de la trame, les intervalles de temps de réserve de l'une quelconque des séquences répétitives pouvant être pris pour exécuter une opération de l'autre séquence répétitive. 3. Procédé selon la revendication 2, dans lequel l'étape de vérification comprend les étapes suivantes :- pour chaque trame Fai de la première séquence répétitive, évaluer les conditions suivantes pour chaque trame Fbj de la deuxième séquence répétitive : [A.1] Dai 4. Procédé selon la revendication 3, dans lequel l'étape de vérification comprend les étapes suivantes : - si la condition [A.1] est fausse, évaluer la condition suivante : [A.2] Dai 5. Procédé selon la revendication 3, dans lequel les bases de temps déterminant les durées des trames sont variables de sorte que les marges de temps T et les réservesde temps R varient d'un facteur 1 à za pour les trames Fa et de 1 à zb pour les trames Fb, l'étape de vérification comprenant alors les étapes suivantes : - si la condition [A.1] est fausse, évaluer la condition suivante : [A.2] Dai 6. Procédé selon la revendication 5, dans lequel l'étape de vérification comprend les étapes suivantes : - si la condition [B.1] est fausse, évaluer avant la condition [B.2] la condition suivante : [B.1.1] Dai