Brevet FR2723653A1 — publié le 19960216

Procédé pour ordonnancer des tâches successives oui ne subissent que des contraintes du type délais. L'invention concerne un procédé pour ordonnancer des tâches successives, au moyen d'un ordinateur, en déterminant un ordre d'exécution de ces tâches et un instant de début d'exécution pour chaque tâche, deux tâches ne devant jamais être exécutées simultanément. Cet ordonnancement est réalisé en fonction d'une pluralité de contraintes que doivent satisfaire les tâches. Ce procédé concerne plus10 particulièrement les applications o il n'y qu'un seul type de contrainte, des contraintes de délais: l'exécution d'une tâche doit commencer à un instant compris dans au moins un intervalle de temps prédéterminé par rapport à un instant de référence absolue. Il n'y a pas de contraintes portant15 directement sur l'ordre des tâches. Naturellement, ce procédé concerne aussi les applications o toutes les contraintes peuvent être considérées comme équivalentes à des contraintes de type délais par rapport à une référence absolue.20 Le procédé selon l'invention est applicable notamment à des tâches qui doivent être exécutées successivement parce qu'elles sont exécutées par un moyen unique capable de n'exécuter qu'une seule tâche à la fois, par exemple: une machine outil, un bus informatique, ou une équipe de25 travailleurs. Dans le domaine de l'informatique, il peut être appliqué à la gestion d'une pluralité de tâches prédéterminées à exécuter successivement dans un même processeur ou sur un même bus. Dans le domaine du contrôle- commande industriel, il peut être appliqué notamment à la30 gestion d'un bus dit de terrain, utilisé pour transmettre des informations successivement selon un ordonnancement prédéterminé. De nombreux procédés d'ordonnancement sont déjà connus: - les méthodes dites pôlynomiales ou de circuits critiques; - les méthodes de programmation linéaire, notamment la méthode du simplex, sur laquelle est fondée le langage PROLOG III; - les méthodes de programmation dynamique, qui ne peuvent être appliquées qu'à des problèmes de taille assez faible; - et les méthodes heuristiques, qui utilisent certains algorithmes des méthodes citées ci-dessus, mais qui consistent en outre à réduire le nombre de cas à vérifier,10 en simplifiant certaines contraintes; la solution obtenue étant alors non optimale. Les procédés connus ont deux inconvénients: ils nécessitent une durée de calcul importante parce qu'ils vérifient systématiquement un très grand nombre de15 permutations avant de fournir une solution. La durée de calcul est généralement proportionnelle à la fonction factorielle du nombre de tâches à ordonnancer. Pour ordonnancer des tâches répétitives, les procédés connus déterminent la durée d'un macro-cycle égal au plus petit commun multiple de toutes les périodes des tâches, et déterminent la durée d'un micro-cycle égal au plus grand commun diviseur de toutes les périodes des tâches, puis ils cherchent une permutation des tâches telle que toutes les contraintes soient satisfaites simultanément, en essayant25 toutes les permutations possibles jusqu'à en trouver une vérifiant cette condition, en faisant les vérifications micro-cycle par micro-cycle. Lorsqu'un conflit apparaît dans un micro-cycle la permutation en cours de vérification est abandonnée, et une autre est essayée. Le travail effectué30 pour la vérification de cette permutation pendant les microcycles précédents devient inutile parce que toutes les contraintes satisfaites précédemment sont remises en cause. Les procédés connus sont donc peu pratiques à mettre en oeuvre dans des applications industrielles. Le but de l'invention est de proposer un procédé d'ordonnancement qui n'ait pas ces inconvénients, afin d'obtenir plus rapidement une solution à un problème d'ordonnancement statique, mais aussi pour permettre de traiter des problèmes d'ordonnancement dynamique, c'est-à- dire redéterminer un ordonnancement au fur et à mesure de 5 l'évolution du nombre de tâches à ordonnancer et de l'évolution des contraintes portant sur ces tâches. Un tel ordonnancement dynamique peut être utile par exemple pour ordonnancer des tâches d'usinage sur une machine outil, lorsque les produits à fabriquer sont très diversifiés; pour10 ordonnancer les décollages ou les atterrissages d'avions sur une piste d'aéroport; pour ordonnancer des tâches sur un bus ou un processeur informatique; etc. L'objet de l'invention est un procédé pour ordonnancer des tâches successives au moyen d'un ordinateur, certaines tâches devant satisfaire des contraintes; chaque contrainte consistant en ce que l'instant tKeb de début d'exécution doit être compris dans au moins un intervalle de temps [tKmin, tKmax] prédéterminé par rapport à un instant de référence absolue;20 caractérisé en ce qu'il consiste à: - considérer que toutes les tâches sont répétitives, et à réduire l'intervalle de temps sur lequel l'ordonnancement est à déterminer, en réduisant cet intervalle à un micro-cycle dont la durée est égale au plus25 grand commun diviseur de toutes les périodes de répétition des tâches; et en recherchant un ordonnancement tel que si toutes les tâches sont exécutées au cours d'un même micro- cycle elles satisfassent toutes les contraintes; - calculer, pour chaque tâche, les bornes tmin et tmax de l'intervalle o doit commencer l'exécution de cette tâche pour satisfaire toutes les contraintes portant sur cette tâche; - constituer une première suite dans laquelle toutes les tâches sont ordonnées selon les valeurs de tmin croissantes; - constituer une seconde suite dans laquelle toutes les tâches sont ordonnées selon les valeurs de tmax croissantes; - constituer une permutation dite initiale, en ordonnançant les tâches dans l'ordre de la première suite; - vérifier si la permutation initiale satisfait toutes les contraintes portant sur toutes les tâches; - conclure que l'ordonnancement est un succès si toutes les contraintes sont satisfaites; - sinon, déterminer dans la permutation initiale la première tâche, dite mal placée, pour laquelle une contrainte n'est pas satisfaite; déterminer dans la seconde suite une tâche dite candidate qui précède immédiatement la tâche mal placée, dans cette seconde suite et qui précède aussi la tâche mal placée, dans la permutation courante; - vérifier que, si la tâche candidate est déplacée dans la permutation courante pour être placée immédiatement après la tâche mal placée, toutes les contraintes portant20 sur les tâches ainsi déplacées sont alors satisfaites; et -- si au moins une contrainte n'est pas satisfaite, conclure que la tâche candidate ne convient pas, puis déterminer dans la seconde suite une autre tâche candidate et réitérer la vérification précédente; et si, ce25 n'est pas possible, conclure que l'ordonnancement a échoué; -- si toutes les contraintes sont satisfaites, conclure que l'ordonnancement est un succès. Le procédé ainsi caractérisé présente l'avantage d'être particulièrement rapide parce qu'en cas d'échec pour l'ordonnancement d'une tâche, il consiste à déplacer une ou plusieurs tâches précédant la tâche o l'ordonnancement est en échec, sans remettre en cause systématiquement toutes les contraintes déjà satisfaites, et donc sans remettre en cause l'intégralité du travail effectué précédemment. Cette35 caractéristique réduit considérablement le temps de calcul par rapport à tout procédé qui consisterait à explorer systématiquement toutes les possibilités d'ordonnancement. D'autre part, ce procédé est plus rapide que les procédés connus, lorsqu'il y a des tâches répétitives, car les permutation sont vérifiées sur un seul microcycle. Enfin, ce procédé est applicable à l'ordonnancement d'un système dans lequel plusieurs tâches peuvent être effectivement réalisées en parallèle. Il consiste alors à décomposer ce système en plusieurs sous-systèmes parallèles10 dans lesquels les tâches doivent toutes être exécutées successivement; et en appliquant le procédé selon l'invention pour chacun des sous-systèmes ainsi déterminés. Le procédé selon l'invention sera mieux compris et d'autres caractéristiques apparaitront à l'aide de la description ci-dessous d'un exemple de mise en oeuvre, et des figures l'accompagnant: - la figure 1 représente le schéma synoptique d'un système dans lequel le procédé selon l'invention est mis en oeuvre pour déterminer dynamiquement un ordonnancement;20 - les figures 2 et 3 illustrent une étape du procédé selon l'invention, pour prendre en compte le caractère périodique de certaines tâches; - les figures 4 à 7 illustrent les principes de base du procédé selon l'invention; - la figure 8 représente l'organigramme d'un exemple de mise en oeuvre du procédé selon l'invention; - les figures 9 à 16 représentent des chronogrammes illustrant la mise en oeuvre de l'organigramme représenté sur la figure 8;30 - les figures 17 à 26 illustrent la mise en oeuvre du procédé selon l'invention pour ordonnancer un exemple de tâches. Le procédé selon l'invention peut être mis en oeuvre aussi bien pour déterminer un ordonnancement statique, que pour déterminer un ordonnancement dynamique. Mais la réduction de la durée de calcul qu'il procure est particulièrement avantageuse pour déterminer un ordonnancement dynamique, puisqu'elle permet de prendre en compte en temps réel des changements de contraintes ou de tâche. 5 La figure 1 représente le schéma synoptique d'un exemple de dispositif mettant en oeuvre le procédé selon l'invention pour l'ordonnancement dynamique de tâches de production industrielle par exemple. Ce dispositif comporte un ordinateur OR couplé à un système de production SY. Ce système de production SY fournit à une entrée de l'ordinateur SY les paramètres nécessaires pour déterminer un ordonnancement: l'identité IDK de chaque tâche, et la période éventuelle TK de chaque tâche, et la définition RL de chaque contrainte à15 satisfaire. Ces paramètres sont fournis chaque fois qu'un changement intervient dans la nature des tâches à exécuter ou dans les contraintes. L'ordinateur détermine alors une nouvelle permutation PER, et le système de production SY exécute ensuite les tâches conformément à cette nouvelle permutation. Les tâches sont généralement exécutées par différents dispositifs que comporte le système SY. L'ordinateur OR doit être programmé aussi pour transmettre à chaque dispositif une information lui indiquant les instants o il peut exécuter une tâche. La programmation de l'ordinateur OR pour le mettre en oeuvre le procédé selon l'invention et pour la transmission à chaque dispositif d'une information est à la portée de l'Homme de l'Art, et ne sera pas décrite au-delà de la description du procédé lui-même. De même, les moyens30 matériels pour coupler un ordinateur OR à un système SY comportant différents dispositifs aptes à réaliser respectivement différentes tâches, est à la portée de l'Homme de l'Art. Le procédé selon l'invention n'est pas limité aux applications o l'ordonnancement est statique. Les mêmes étapes permettent de déterminer en temps réel un ordonnancement dynamique. Chaque contrainte porte seulement sur l'instant de début d'exécution, qui doit être compris dans un intervalle donné [tmin, tmax]. L'exécution peut continuer au- delà de la borne d'un intervalle, elle doit seulement respecter la durée fixée. Lorsque plusieurs contraintes de type délais portent sur une même tâche, elles peuvent être remplacées par une seule contrainte dont l'intervalle [tmin,10 tmax] est l'intersection des intervalles correspondant respectivement à ces contraintes. Une étape préliminaire du procédé selon l'invention consiste à réduire le nombre de permutations à vérifier, en ne vérifiant l'ordonnancement des tâches que pendant un15 micro-cycle qui est le plus grand commun diviseur de toutes les périodes de répétition des tâches. En effet, si on arrive à trouver une permutation telle que si toutes les tâches sont exécutées au cours d'un même micro-cycle et qu'elles satisfassent toutes les contraintes, alors cette20 permutation ne provoquera aucun conflit au cours d'aucun des micro-cycle constituant un macro-cycle, puisque le cas le pire est celui o toutes les tâches tombent dans un même micro-cycle à cause de la coïncidence des multiples de leurs périodes.25 Les figures 2 et 3 illustrent cette étape préliminaire du procédé selon l'invention. Il est à noter que dans le cas o une ou plusieurs tâches ne sont pas considérées à priori comme répétitive, il suffit de leur attribuer une valeur de période commune choisie arbitrairement mais telle qu'elle30 facilite la détermination d'un micro- cycle. Il suffit donc de déterminer la valeur du plus grand commun diviseur des périodes des tâches répétitives puis de choisir un multiple de cette valeur pour constituer une période commune à toutes les tâches non répétitives.35 Les figure 2 et 3 illustrent un exemple o il faut ordonnancer 6 tâches T1,..., T6 périodiques, respectivement avec des périodes égales à 10 ms, 20 ms, 30 ms, 40 ms, 50 ms, 40 ms. La durée d'exécution est uniforme pour toutes les tâches et est égale à 1 ms. La figure 2 représente en grisé les intervalles de temps [tmin, tmax] pour chacune de ces tâches. Ces intervalles sont les suivants: TA1 [tmin, tmax] = [O, 4 ms] modulo 10 ms TA2 [10, 13 ms] modulo 20 ms TA3 [20, 23 ms] modulo 30 ms TA4 [30, 32 ms] modulo 40 ms TA5 [40, 41 ms] modulo 50 ms TA6 [20, 22 ms] modulo 40 ms Ces tâches ont un macro-cycle égal au plus petit commun multiple de leur période, c'est-à-dire 600 ms. Un macro-cycle peut être découpé en 60 micro- cycles de 10 ms. Deux tâches répétitives peuvent être en conflit si elles sont à exécuter au cours d'un même micro-cycle. Par exemple, les tâches TA1, TA3, TA6 doivent être exécutées au cours d'un même microcycle [20ms, 30ms] puis [12Oms, 14Oms], etc.20 Pour déterminer un ordonnancement qui conviennent dans le pire cas, il suffit de considérer un micro-cycle o toutes les tâches sans exception devraient être exécutées une fois. En pratique, les tâches ne tombent pas toutes dans un même micro-cycle. On considère un cas fictif o cet25 évènement serait réalisé. Une translation temporelle peut ramener l'instant d'exécution de chaque tâche dans l'intervalle d'un même micro-cycle [O, 10ms]. Elle est définie par la formule: t Kfictif K tdeb = tdeb - k.PGCD o tKfictif est l'instant fictif de début d'exécution deb d'une tâche K; K o tdeb est l'instant réel de début d'exécution de la tâche K; o PGCD est la durée d'un micro-cycle, c'est-a-dire le plus grand commun diviseur des périodes; et o k est un nombre entier tel que l'instant fictif tKfictif de début d'exécution de la tâche K est ramené dans deb le micro-cycle choisi, en l'occurence [0,10 ms]. L'intervalle [tKmin, tKmax] défini par toutes les contraintes portant sur la tâche K est donc translaté lui aussi de -k.PGCD. Le procédé d'ordonnancement selon l'invention est ensuite appliqué dans cet intervalle [O, lOms]. Lorsqu'une permutation satisfaisant toutes les contraintes a été déterminée, les instants d'exécution réels tKdeb sont15 déduits des instants fictifs de début d'exécution, par la formule tKeb = tKfictif + k.PGCD modulo la période de la deb deb tâche K. La figure 3 représente l'ordonnancement des tâches ainsi obtenu, sur l'intervalle O à 100 ms, l'intervalle à 600 ms n'étant pas représenté mais ayant un ordonnancement analogue. Chaque intervalle d'exécution est représenté en noir. Considérons à titre d'exemple l'intervalle 20 à 30 ms dans lequel il peut y avoir conflit25 entre les tâches TA1, TA3, et TA6. La tâche TAi est exécutée pendant l'intervalle 23 à 24 ms. La tâche TA3 est exécutée pendant l'intervalle 22 à 23 ms. La tâche TA6 est exécutée pendant l'intervalle 21 à 22 ms. Ainsi il n'y a jamais exécution simultanée de TA1 et TA3 ou TA6, quel que soit le30 micro-cycle considéré, parmi les 60 micro-cycles constituant le macro-cycle [O, 600ms]. D'autre part, si dans une application certaines tâches peuvent être exécutées simultanément, cette étape préliminaire consiste en outre à rassembler les tâches en35 plusieurs sous-ensembles indépendants, si c'est possible, chaque sous-ensemble ne rassemblant que des tâches liées entre elles par des contraintes. Le fait d'ordonnancer plusieurs sous- ensembles indépendamment, est plus rapide que d'ordonnancer un seul ensemble plus complexe. 5 Les figures 4 à 7 illustrent les principes de base du procédé selon l'invention pour ordonnancer toutes les tâches d'un ensemble de tâches en minimisant le nombre de permutations à vérifier. Cette procédure s'achève avec succès si elle a déterminé une permutation constituant un10 ordonnancement satisfaisant toutes les contraintes portant sur ces tâches. La figure 4 représente un chronogramme illustrant un premier principe de base du procédé selon l'invention. Ce premier principe impose d'exécuter en priorité les tâches15 pour lesquelles l'intervalle de temps commence le plus tôt, c'est-à-dire avec une valeur tmin la plus petite. En pratique, la permutation initiale des tâches, c'est-à-dire la première permutation à vérifier, sera constituée par une suite référencée MINSUITE, dans laquelle les tâches sont20 rangées selon l'ordre croissant des valeurs de tmin. La figure 4 représente par des rectangles IDA et IDB deux intervalles de temps attribués respectivement à l'exécution d'une tâche A et à l'exécution d'une tâche B. Des contraintes imposent que la tâche A commence à être25 exécutée à l'intérieur d'un intervalle [tAmin, tAmax] ou, à la limite, à l'instant tAmax. Elles imposent que la tâche B commence à être exécutée à l'intérieur d'un intervalle [tBmin, tBmax] ou, à la limite, à l'instant tBmax. Dans cet exemple tAmin est inférieur à tBmin. Le premier principe de base consiste à exécuter la tâche A en premier, en décalant l'intervalle pendant lequel dure cette exécution, le plus près possible de la borne inférieure tAmin; puis à exécuter la tâche B pendant un intervalle IDB commencant le plus près possible de la borne inférieure tBmin sans chevaucher35 l'intervalle IDA. Dans cet exemple, l'intervalle IDA a une durée 8A qui déborde sur l'intervalle [tBmin, tBmax], par conséquent les intervalles IDA et IDB seront le plus rapprochés possible en choisissant: tBdeb = tAmin + 6 La figure 5 représente, sur le même exemple, les conséquences d'une non-application de ce principe de base, c'est-à-dire faire exécuter la tâche B avant la tâche A. L'intervalle d'exécution IDB débute alors le plus tôt possible c'est-à-dire à la borne inférieure de l'intervalle [tBmin, tBmax]. L'intervalle d'exécution IDA10 devrait commencer après la fin de l'intervalle d'exécution IDB pour ne pas chevaucher l'intervalle IDA, mais dans cet exemple l'intervalle d'exécution IDB a une longueur telle qu'il dépasse l'instant tAmax qui constitue la borne supérieure de l'intervalle o il est permis de commencer15 l'exécution de la tâche A. Au mieux, la tâche A pourrait commencer à l'instant tAdeb = tAmax, mais alors il y a chevauchement des deux intervalles d'exécution IDB et IDA. La zone de chevauchement est hâchurée sur la figure 5. Il apparaît donc dans cet exemple que le non-respect du premier principe augmente la probabilité de ne pas satisfaire certaines contraintes. La figure 6 représente un chronogramme illustrant un deuxième principe de base du procédé selon l'invention. Ce principe de base permet de choisir quelle est la tâche à25 exécuter en priorité parmi plusieurs tâches pour lesquelles la borne inférieure tmin a la même valeur. Ce second principe impose, dans ce cas, d'exécuter en priorité la tâche pour laquelle la borne supérieure tmax est la plus petite.30 Dans l'exemple représenté sur la figure 6, deux tâches A et B ont la même borne inférieure tAmin = tBmin, pour l'intervalle de temps dans lequel doit commencer l'exécution. Par ailleurs, des contraintes imposées par l'existence d'autres intervalles d'exécution non35 représentés, interdisent l'exécution des tâches A et B avant un instant to postérieur à tAmin = tBmin, dans un intervalle de temps représenté par des hâchures. Les intervalles d'exécution IDA et IDB ne peuvent donc commencer qu'à partir de cet instant to. Pour la tâche B, la borne supérieure tBmax est supérieure à la borne supérieure tAmax 5 correspondant à la tâche A. Selon le deuxième principe de base, il faut exécuter en priorité la tâche A. La tâche B est exécutée ensuite à partir d'un instant: tBdeb = tAmin + SA. Ainsi les deux intervalles d'exécution IDA et IDB se succèdent sans problème particulier dû à la borne supérieure tBmax- La figure 7 illustre sur le même exemple, un conflit qui a plus de chance de se produire si le deuxième principe n'est pas respecté. La tâche B est exécutée en premier, à15 partir de l'instant tBdeb qui coïncide avec la fin to de l'intervalle interdit représenté par des hachures. Ensuite la tâche A devrait être exécutée à partir d'un instant tAdeb = tBmin + 8A pour éviter un chevauchement des intervalles IDA et IDB, mais cet instant tAdeb se trouverait20 alors dans une zone interdite, hâchurée sur la figure, située après la borne supérieure tAmax de l'intervalle o doit commencer cette exécution. Il y a donc une contrainte qui n'est pas satisfaite. Il apparait donc dans cet exemple que le non-respect du deuxième principe augmente la25 probabilité de ne pas satisfaire certaines contraintes. La figure 8 représente un organigramme d'un exemple préférentiel de mise en oeuvre du procédé selon l'invention. Il consiste tout d'abord en une étape E21 consistant à déterminer la suite MIN-SUITE constituée de toutes les30 tâches ordonnées selon les valeurs croissantes de la borne inférieure tmin. Cette suite sera utilisée pour appliquer le premier principe énoncé précédemment. Pour maximiser la probabilité d'arriver rapidement à trouver une permutation qui satisfasse toutes les contraintes portant sur toutes les35 tâches, la permutation initiale est constituée par MIN- SUITE; et les permutation qui seront vérifiées ensuite, en cas d'échec, seront déduites de MIN-SUITE, par des modifications successives. D'autre part, l'étape E21 consiste à déterminer la suite MAX-SUITE, constituée de toutes les tâches ordonnées selon les valeurs croissantes de la borne supérieure tmax. Cette suite sera utilisée pour appliquer le second principe énoncé précédemment, lorsqu'il faudra modifier la permutation initiale. Puis une étape E22 consiste à vérifier la permutation courante, c'est-àdire vérifier si elle satisfait toutes les contraintes portant sur toutes les tâches. Au début, la permutation courante est constituée par la permutation initiale déterminée par l'étape E21. Cette vérification consiste à prendre successivement chaque tâche dans l'ordre de la permutation courante et à vérifier que l'intervalle d'exécution [tdeb, tfin] imposé par la position occupée par cette tâche dans la permutation courante est compatible avec l'intervalle de temps [tmin, tmax] imposé par les20 contraintes qui portent sur cette tâche. La tâche pour laquelle cette vérification est en cours est appelée tâche courante. Si cette vérification est positive pour chacune des tâches, cela signifie que la permutation courante est un succès, noté S.25 Si la vérification rencontre au moins une tâche dont la position dans la permutation impose de commencer l'exécution à un instant tdeb qui n'est pas dans l'intervalle de temps [tmin, tmax] imposé par les contraintes, cette tâche est considérée comme mal placée,30 puisqu'il y a un conflit entre deux contraintes. Quand l'étape E22 trouve une tâche, notée X, qui est la première mal placée dans la permutation courante, elle tire la conclusion, notée R, qu'il est nécessaire de chercher une tâche candidate à un déplacement pour constituer une35 nouvelle permutation. Le procédé consiste alors à exécuter une étape E23 qui recherche la tâche précédant immédiatement la tâche courante X dans la suite MAX- SUITE. S'il n'existe pas une telle tâche, l'étape E23 se termine par un échec, noté F. Si l'étape E23 trouve une tâche candidate Q précédant immédiatement la tâche courante X dans la suite MAX-SUITE, le procédé consiste ensuite en une étape E24 vérifiant que cette tâche Q a déjà été considérée comme bien placée, au cours.d'une étape E21 antérieure. Toutes les tâches qui sont considérées comme bien placées sont celles qui ont un rang10 inférieur à celui de la tâche courante X, puisque la vérification de l'étape E22 est faite selon les rangs croissants dans la permutation courante. Par conséquent, l'étape E24 consiste tout simplement à vérifier que la tâche candidate Q précède la tâche courante X dans la permutation15 courante. Si l'étape E24 détermine que la tâche Q n'a pas été considérée comme bien placée, l'étape E23 est réitérée pour rechercher une autre tâche candidate, précédant immédiatement la tâche Q dans MAX-SUITE. Au contraire, si la tâche candidate Q a été considérée comme bien placée, le procédé consiste à exécuter une étape E25 qui consiste à comparer l'instant tQdeb du début d'exécution de la tâche Q à l'instant tXmax qui est la borne supérieure de l'intervalle de temps correspondant à la tâche courante X.25 Si tQdeb 2 tXmax, c'est le cas noté a. L'étape suivante est alors une étape E29 consistant à déplacer la tâche Q dans la permutation courante, pour l'insérer entre la tâche courante X et la tâche suivant la tâche X dans la permutation courante. Les tâches qui étaient placées entre Q30 et X, et la tâche X elle-même, sont décalées d'un rang, vers les rangs inférieurs, pour combler la place laissée libre par Q. Par conséquent, la tâche Q occupe désormais la position qui était celle de X. Le procédé consiste ensuite à réitérer l'étape E22 pour vérifier si la nouvelle35 permutation courante ainsi obtenue satisfait toutes les contraintes. Il est à noter que la tâche Q et toutes les autres tâches qui la suivaient ont été déplacées. Elles ne peuvent plus être considérées comme ayant été bien placées car elles ne satisfont pas forcément toutes les contraintes dans leurs nouvelles positions respectives. Les tâches de 5 rang inférieur à Q gardent la même position, donc il n'est pas nécessaire de vérifier qu'elles satisfont toutes les contraintes portant sur elles, le travail de vérification de ces contraintes n'est donc pas refait. Si tQdeb loin et le procédé consiste ensuite en une étape E26. La figure 9 illustre par un exemple le cas a. Les intervalles d'exécution sont représentés en pointillés lorsqu'un conflit empêche une exécution, et en traits continus dans le cas contraire.15 Considérons une tâche X qui est dans une position PSi de la permutation courante, et une tâche Q considérée comme bien placée, qui est dans une position PSj de la permutation courante. La position PSi impose le début de l'exécution de la tâche X à un instant tdeb(PSi) qui est au-delà de la20 borne tXmax. La position PSj impose le début de l'exécution de la tâche Q à un instant tdeb (PSj) qui est, dans cet exemple, au-delà de l'instant tXmax. L'instant tQdeb(PSj) étant au- delà de l'instant tXmax, la borne tQmax est donc à fortiori supérieure ou égale à TXmax, et a donc des chances d'être plus proche de tdeb(PSi), l'idéal étant que tdeb(PSi) tombe en deçà de tQmax. La figure 10 montre qu'en déplaçant les tâches Q et X respectivement dans les positions PSi_1 et PSj, la probabilité que l'instant tdeb(PSil) tombe dans la30 l'intervalle [tXmin, tXmax] est plus grande que la probabilité qu'avait l'instant tdeb(Psi) de tomber dans ce même intervalle, car tdeb croit systématiquement avec le rang de la position PS. La figure montre que l'extrémité tXmax du segment correspondant à la tâche X s'est rapprochée35 d'un intervalle d'exécution, celui qui commence à l'instant tdeb(PSi-1), et a donc plus de chances d'avoir une intersection avec un tel intervalle. D'autre part, l'extrémité tQmax du segment correspondant à la tâche Q a des chances non nulles d'avoir une intersection avec le rectangle représentant l'intervalle d'exécution commençant à l'instant tdeb(PSi). Par conséquent, la nouvelle permutation a plus de chance que l'ancienne de satisfaire toutes les contraintes et il est donc utile d'essayer cette nouvelle permutation. Dans10 l'exemple représenté, tdeb(PSil) tombe au-delà de tmax, il y a donc encore un conflit pour la tâche X. Il est donc nécessaire de faire encore une ou plusieurs autres modifications de la permutation courante. Dans cet exemple, tdeb(PSi) tombe au-delà de tQmax donc il y a aussi un conflit pour la tâche Q après le déplacement. Mais dans d'autres exemples correspondant au cas a il peut arriver que les contraintes portant sur X, et celles portant sur Q, soient satisfaites simultanément. Par conséquent il est utile de vérifier toute nouvelle20 permutation correspondant au cas a. Dans le cas a, au contraire, d'autres vérifications sont nécessaires avant de pouvoir conclure que la tâche Q est une tâche candidate intéressante. Le procédé consiste alors à réaliser l'étape E26. Celle- ci consiste à comparer25 l'instant tQfin de la fin d'exécution de la tâche Q, à l'instant tXmax qui est la borne supérieure de l'intervalle o doit comnencer l'exécution de la tâche X. Si tQfin > tXmax, ce cas est noté 5, et le procédé consiste ensuite à réaliser l'étape E30 qui déplace la tâche Q et l'insère30 après la tâche X. Le cas contraire est noté p. D'autres vérifications sont nécessaires avant de pouvoir conclure que la tâche Q est une tâche candidate intéressante. Les figures 11 et 12 illustrent le cas 3. La figure 11 représente une tâche X dans la position PSi et une tâche Q dans la position PSj, telles que le cas a et le cas g sont réalisés: l'instant tQfin de la fin d'exécution de la tâche Q, c'est-à-dire l'instant tfin(PSj) imposé par la position PSj de Q dans la permutation courante, est situé au-delà de l'instant tXmax. La figure 12 montre qu'en déplaçant les tâches Q et X respectivement dans les positions PSi_1 et PSj, la probabilité que l'instant tdeb(PSi-1) tombe dans l'intervalle [tXmin, tXmax] est plus grande que la probabilité qu'avait l'instant tdeb(PSi) de tomber dans ce même intervalle, car tdeb croit systématiquement avec le10 rang de la position PS. Par ailleurs, l'instant tQfin= tfin(PSj) est au-delà de la borne tXmax et il n'y a pas de conflit. Ceci signifie que tQmax est soit supérieur à tXmax, soit un peu inférieure à tXmax, en étant au plus à une distance égale à l'intervalle [tdeb(PSj), tfin(PSj)]. Il15 y a donc quelques chances que tQmax soit supérieur à tXmax, et donc ce cas, il y a quelques chances que tQmax tombe au- delà de tdeb(PSi) après le déplacement. Il est donc utile d'essayer une permutation correspondant au cas g, ce n'est pas forcément du temps perdu.20 Dans l'exemple représenté sur la figure 12, le déplacement de Q et X ne suffit pas pour que toutes les contraintes sur Q et X soient satisfaites. Il sera nécessaire de modifier un peu plus la permutation courante. Dans le cas f, l'étape E27 consiste à comparer l'instant tQmax qui est la borne supérieure de l'intervalle de temps o doit commencer l'exécution de la tâche Q, à l'instant tXmax qui est la borne supérieure de l'intervalle de temps o doit commencer l'exécution de la tâche X. Si tQmax > tXmax, ce cas est noté R, et le procédé consiste,30 alors ensuite à réaliser une étape E28. Le cas contraire est noté ô, et le procédé consiste alors à réitérer l'étape E23 car la tâche candidate Q n'a aucune chance d'être intéressante. Les figures 13 et 14 illustrent par un exemple le cas q. Dans cet exemple, la borne tQmax est strictement inférieure à l'instant tXmax. La figure 13 représente les tâches X et Q déplacées respectivement dans les positions PSi_1 et Psi. Cette figure montre que l'instant tQmax devient plus proche de l'instant t(PSi)deb qu'il n'était de l'instant t(PSJ)deb mais la tâche 5 Q n'a aucune chance de pouvoir être exécutée car tQmax est encore plus éloigné de t(PSi)deb que ne l'était tQmax- Puisque la tâche Q a 100 % de chances d'être mal placée, il est inutile d'essayer une telle modification de la permutation courante, c'est pourquoi l'étape suivante est10 une étape E23 de recherche d'une autre tâche candidate pour un déplacement. Dans le cas À, l'étape E28 consiste à comparer l'instant tQmin qui est la borne inférieure de l'intervalle dans lequel doit commencer l'exécution de la tâche Q, avec15 l'instant tXmin qui est la borne inférieure de l'intervalle de temps dans lequel doit commencer l'exécution de la tâche X. Le but de cette étape E28 est de vérifier que la tâche Q est placée avant la tâche courant X dans la suite MIN- SUITE, pour pouvoir déplacer la tâche Q après la tâche X. Dans le cas contraire, noté a, l'étape suivante est une étape E23 de recherche d'une autre tâche candidate pour un déplacement. Dans le cas X, l'étape suivante est une étape E29 déplaçant la tâche Q après la tâche X; puis une étape E22 est réitérée pour vérifier si toutes les contraintes portant sur les tâches de la couche courante sont satisfaites. La figue 15 illustre un exemple o les cas a, A, X, R, sont réalisées simultanément. La figure 16 représente les tâches X et Q déplacées respectivement dans les positions PSi-l et PSi, dans un exemple o les contraintes sont telles qu'elles sont effectivement satisfaites après ce déplacement: tdeb(PSi) tombe dans l'intervalle [tQmin, tQmax] et tdeb(PSi-l) tombe35 dans l'intervalle [tXmin, tXmax] Les figures 17 à 26 illustrent la réalisation de l'étape E2 pour ordonnancer un exemple de couche comportant 13 tâches: A, B, C, D, E, G, J, K, L, N, P, S, T. La figure 17 représente sur une échelle de temps de O à 14 ms, la position des intervalles d'exécution correspondant respectivement à 13 positions PS1,..., PS13. Les tâches sont exécutées dans l'ordre des positions PS1,. , PS13, et chaque intervalle d'exécution a une durée..DTD: égale à 1 ms. Chaque tâche doit satisfaire une ou plusieurs contraintes qui résultent en une seule contrainte: le début de l'intervalle d'exécution (rectangle noir sur la figure 17) doit être situé dans un intervalle de temps donné (segments noirs sur la figure 18). Dans un cas limite il peut commencer à la borne supérieure. L'étape E21 consiste à déterminer la suite MIN-SUITE constituée de toutes les tâches de la couche courante, ordonnées selon les valeurs croissantes de la borne inférieure tmin.20 MIN-SUITE = N, J, S, D, E, B, T, A, K, P, L, C, G. Sur la figure 18 les 13 tâches sont représentées dans l'ordre de MIN-SUITE, selon le sens d'orientation de l'axe des ordonnées. Pour maximiser la probabilité d'arriver rapidement à trouver une permutation qui satisfasse toutes25 les contraintes portant sur les tâches de la couche considérée, la permutation dite initiale qui sera vérifiée en premier sera celle constituée par MIN-SUITE; et celles qui seront vérifiées ensuite, en cas d'échec, seront déduites de MIN-SUITE par des modifications successives.30 D'autre part, l'étape E21 consiste à déterminer la suite MAX-SUITE, constituée de toutes les tâches de la couche courante, ordonnées selon les valeurs de tmax croissantes. Cette suite sera utilisée pour appliquer le second principe énoncé précédemment, lorsqu'il faudra35 modifier la permutation initiale. Dans cet exemple, MAX-SUITE = N, S, J, T, G, C, L, B, P, K, A, D, E. Puis une étape E22 consiste à vérifier la permutation courante, c'està-dire vérifier si elle satisfait toutes les contraintes portant sur les tâches de la couche considérée. Au début de l'étape E2, la permutation courante est 5 constituée par la permutation initiale déterminée par l'étape E21. La vérification est faite successivement pour chaque tâche, dans l'ordre de la permutation courante: N, J, S, D, E,..., G. Si la vérification est positive pour une tâche10 celle-ci est considérée comme bien placée dans la permutation, mais son placement peut être remis en cause ultérieurement si cela est nécessaire pour satisfaire d'autres contraintes. La comparaison des figures 17 et 18 permet de conclure qu'il n'y a pas de problème pour exécuter les tâches N,J,S, et D, respectivement pendant les intervalles d'exécution représentés sur la figure 17. Elles sont donc considérées comme bien placées. La permutation courante est: NJS D E B T A K P L C G o les tâches considérées comme bien placées sont soulignées. La figure 19 illustre le premier conflit rencontré au cours de la vérification de la permutation initiale. Sur la figure 19, des rectangles noirs représentent des intervalles25 d'exécution pour lesquels il n'y a pas de conflit entre les contraintes, et un rectangle blanc en pointillés représente l'intervalle d'exécution qui est cause d'un conflit. Il correspond à la position PS5, occupée actuellement par la tâche E. Cet intervalle d'exécution n'a aucun point commun30 avec l'intervalle dans lequel doit commencer l'exécution de la tâche E. L'étape E23 consiste alors à rechercher dans la suite MAX-SUITE une tâche précédant la tâche E, c'est-à-dire telle que la borne tmax a une valeur plus élevée. MAX-SUITE = N, S, J, T, G, C, L, B, P, K, A, D, E. L'étape E23 trouve la tâche D. L'étape E24 vérifie qu'elle est considérée comme bien placée, en vérifiant qu'elle a un rang inférieur au rang de la tâche courante E, dans la permutation courante. Puis l'étape E25 tire une conclusion a. Puis l'étape E26 tire une conclusion p. L'étape E29 déplace alors D dans la position POS5 et E 5 recule dans la position POS4. L'étape E22 vérifie que les contraintes portant sur E et les tâches suivantes sont satisfaites mais constate que les contraintes portant sur D ne sont plus satisfaites. La permutation essayée ne convient pas. Elle n'est pas retenue comme nouvelle permutation10 courante. Comme le montre la figure 19, cette modification ne pouvait pas être un succès car l'intervalle correspondant à D a une borne supérieure qui n'est pas supérieure à celle de l'intervalle correspondant à E. Ils sont mêmes strictement15 identiques. Pour éviter de vérifier inutilement de nouvelles permutations il est possible de prendre des précautions lors de la constitution de MAX-SUITE, au cours de l'étape E21: Lorsque deux tâches de la même couche ont pour contrainte un même intervalle de temps [tmin, tmax], il est possible de les20 mettre dans deux positions différentes respectivement dans la suite MIN-SUITE qui constitue la permutation initiale, et dans la suite MAX-SUITE. Dans l'exemple illustré sur les figures 17 à 26, il y a au moins deux possibilités pour constituer la suite MAX-SUITE puisqu'il est possible de25 permuter D et E: N, S, J, T, G, C, L, B, P, K, A, E, D ou N, S, J, T, G, C, L, B, P, K, A, D, E. Il aurait été préférable de choisir l'ordre E, D qui est l'ordre inverse de l'ordre D, E dans lequel elles sont prises pour constituer la permutation initiale MIN-SUITE = N, J, S, D, E, B, T, A, K, P, L, C, G. L'étape E23 trouverait alors comme tâche candidate successivement: A, K, P, B, L, C, G, T, J; et l'étape E24 retiendrait la tâche J.35 On démontre qu'en règle générale, si les tâches de la couche à ordonner n'ont à satisfaire que des contraintes du type délais, il est préférable de placer dans un ordre inverse, SUITE, toutes les tâches ayant le même intervalle [tmin, tmax] quel que soit leur nombre. Par contre, s'il y a à la fois des contraintes de type délais et 5 des contraintes de type après, il est préférable de les placer dans un même ordre. Considérons la suite de cet exemple, en conservant le choix initial de MAX-SUITE: N, S, J, T, G, C, L, B, P, K, A, P. La permutation courante est: N JS E DB T AK P L CG Après cette tentative malheureuse de modification de la permutation, l'étape E23 trouve comme tâche candidate successivement A, K, P, B, L, C, G, T, qui sont rejetées par15 l'étape E24. Puis l'étape E23 trouve la tâche J. La figure 20 illustre cette nouvelle tentative de modification. L'étape E24 vérifie que la tâche J est considérée comme bien placée. L'étape E25 arrive à la conclusion a. L'étape E26 arrive à la conclusion p. Les20 étapes E27 et E28 arrivent à la conclusion n et X- Par conséquent l'étape E29 place la tâche J dans la position PS5, à la place de E. Les tâches E, D et S reculent d'une place, S se trouvant dans la position PS2, D dans la position PS3, et E dans la position PS4. Les autres tâches25 ne changent pas de place. L'étape E22 consiste à vérifier ensuite que les tâches qui ont été déplacées vérifient toutes les contraintes portant sur elles, en commençant par la tâche de rang le plus bas parmi celles déplacées: S, puis E, puis D, puis J.30 Elle vérifie ensuite qu'il n'y a pas de conflit entre les contraintes successivement pour les tâches B, T, A, K. La figure 21 illustre la nouvelle permutation courante. Il est à remarquer que pour la tâche K l'intervalle d'exécution commence à l'instant exact o se35 termine l'intervalle dans lequel doit commencer l'exécution de la tâche K. Il n'y a pas de conflit, mais les contraintes sont satisfaites de justesse. L'état de la permutation courante est: N, S, E, Di J, B, T, A, R, P, L, C, G. La figure 22 montre qu'il apparait un conflit pour la tâche P. L'étape E23 est alors réitérée pour déterminer dans la suite MAX-SUITE la tâche précédant immédiatement la tâche P dans cette suite. Elle trouve la tâche B. L'étape E24 vérifie que la tâche B fait partie des tâches qui sont considérées comme bien placées. Les étapes E25 et E26 tirent10 les conclusions a puis p. L'étape E27 est alors réalisée. Celle-ci constate que tBmax = tPmax, par conséquent elle en tire la conclusion ô. L'étape E23 est alors réitérée pour rechercher une autre tâche candidate dans la suite MAX- SUITE. En effet, le segment représentant l'intervalle de15 temps correspondant à B n'aurait aucun point d'intersection avec l'intervalle d'exécution [ 9 ms, loms] correspondant à la position POS10, si la tâche B était déplacée à cette position. Par conséquent les contraintes portant sur B ne seraient pas satisfaites.20 L'étape E23 trouve alors successivement les tâches L, C, G mais l'étape E24 les rejette car elles ne sont pas considérées comme bien placées dans la permutation. Finalement les étapes E23 et E24 trouvent la tâche T. Les étapes E25 à E28 tirent successivement les conclusions a,, À, X- L'étape E29 déplace T à la position POS10. Les tâches P, K, A reculent respectivement dans les positions POS9, POS8, POS7. L'étape E22 vérifie ensuite que les contraintes portant sur les tâches déplacées A, K, P, T, et les suivantes, sont satisfaites. La nouvelle permutation courante est: N, S, E, D, J, B, A, K, P, T, L, C, G Comme le montre la figure 23, l'étape E22 constate ensuite que les contraintes portant sur la tâche L ne sont pas satisfaites. L'étape E23 trouve ensuite la tâche T et l'étape E24 vérifie qu'elle est considérée comme bien placée. L'étape E25 et les suivantes peuvent donc être exécutées. Elles tirent les conclusions a, puis f, puis I et XL'étape E29 5 peut alors être exécutée. Elle place la tâche T dans la position PS 11 qui était occupée par la tâche L. La tâche L recule d'une place. L'étape E22 vérifie que les contraintes portant sur les tâches déplacées L et T sont satisfaites. Par conséquent la permutation courante devient:10 N, S, E, D, J, V, A, R, P, L, T, C, G Comme le montre la figure 24, il y a un conflit entre les contraintes portant sur la tâche C. L'étape E23 détermine la tâche précédant la tâche C dans la suite MAXSUITE. Elle trouve la tâche G mais l'étape E24 constate que15 cette tâche G n'est pas considérée comme bien placée dans la permutation. L'étape E23 est réitérée et elle détermine une autre tâche, T, précédant la tâche C dans la suite MAX- SUITE. L'étape E24 vérifie que la tâche T est considérée comme bien placée dans la permutation. L'étape E25 tire la20 conclusion a puisque tTdeb = tCmax. L'étape E29 est donc réalisée immédiatement et elle place donc la tâche T après la tâche.C dans la permutation, ce qui revient à permuter les positions de C et de T. L'étape E22 vérifie ensuite que toutes les contraintes portant sur les tâches déplacées C et25 T sont satisfaites. La nouvelle permutation courante est: N. S. E. D, J. B. A, R. P. L, C, T, G Comme le montre la figure 25, l'étape E22 constate qu'il y a un conflit entre les contraintes portant sur la tâche G. L'étape E23 détermine une tâche, T, qui précède la tâche G immédiatement dans la suite MAX-SUITE. L'étape E24 vérifie que la tâche T est considérée comme bien placée dans la permutation. L'étape E25 tire la conclusion a puisque tTdeb = tGmax. L'étape E29 déplace T après G dans la35 permutation, ce qui revient à permuter T et G. Puis l'étape E22 vérifie que toutes les contraintes portant sur les tâches déplacées G et T sont satisfaites. La nouvelle permutation courante est: Ni S. E. D, J. B. Al R. P. Li CI G. T. Toutes les tâches sont considérées comme bien placéess car toutes les contraintes sont satisfaites, comme le montre la figure 26, par conséquent la réalisation de l'étape E2 se termine par un succès S. REVENDICATION UNIQUE Procédé pour ordonnancer des tâches successives (ID1i,..., ID20) au moyen d'un ordinateur (OR), ces tâches ne subissant que des contraintes du type délais; une tâche du type délais consistant en ce que l'instant tKdeb de début d'exécution doit être compris dans au moins un intervalle de temps [tKmin, tKmax] prédéterminé par rapport à un instant de référence absolue (DM); caractérisé en ce qu'il consiste, successivement et dans cet ordre, à: - calculer (E6), pour chaque tâche, les bornes tmin et tmax de l'intervalle o doit commencer l'exécution de cette tâche; - constituer (E21) une première suite (MIN-SUITE) dans laquelle toutes les tâches sont ordonnées selon les valeurs de tmin croissantes; - constituer (E21) une seconde suite (MAX-SUITE) dans laquelle toutes les tâches sont ordonnées selon les valeurs de tmax croissantes;20 - constituer (E21) une permutation dite initiale en ordonnant toutes les tâches dans l'ordre de la première suite (MIN-SUITE); - vérifier (E22) si la permutation initiale satisfait toutes les contraintes portant sur les tâches; - conclure (S) que l'ordonnancement est un succès si toutes les contraintes sont satisfaites; - sinon, déterminer (E22) dans la permutation initiale la première tâche (X), dite mal placée, pour laquelle une contrainte n'est pas satisfaite;30 - déterminer (E23, E24) dans la seconde suite (MAXSUITE) une tâche dite candidate (Q) qui précède immédiatement la tâche mal placée (X), dans cette seconde suite, et qui précède aussi la tâche mal placée (X), dans la permutation courante;35 - vérifier (E25,..., E29, E22) que, si la tâche candidate (Q) est déplacée dans la permutation courante pour être placée immédiatement après la tâche mal placée (X), toutes les contraintes portant sur toutes les tâches ainsi déplacées sont alors satisfaites; et -- si au moins une contrainte n'est pas satisfaite, conclure (R) que la tâche candidate ne convient pas, puis déterminer (E23, E24) dans la seconde suite (MAX- SUITE) une autre tâche candidate et réitérer la vérification précédente (E25,..., E29, E22); et si, ce n'est pas possible, conclure (F) que l'ordonnancement à échoué;10 -- si toutes les contraintes sont satisfaites, conclure (S) que l'ordonnancement est un succès.