Brevet FR2839371A1 — publié le 20031107

partie, lesdits moyens d'immobilisation (7). La presente invention concerne un procede d'ordonnancement de taches issues d'une liste a laquelle de nouvelles taches peuvent etre ajoutees apres le choix d'une tache, et ce au cours de l'ordonnancement. Wile s'applique notamment a l'ordonnancement de pointages d'un radar, d'un sonar ou d'un lidar. Dans un radar a balayage electronique, les taches a ordonnancer vent les pointages du radar. Un radar a balayage electronique peut depointer son faisceau de fa,con instantanee dans un cone d'axe perpendiculaire au plan de l'antenne. II existe des radars multifonctions. Un radar multifonction possede differents modes de fonctionnement (antenne tournante, antenne arretee, mode mixte, antenne multi-dales...) et effectue plusieurs types de pointages. Ces differents types de pointages correspondent a differentes missions operationnelles: la detection (pointages de veille), le pistage de cibles (pointages de pour-quite), I'identification, le guidage de missiles... Un radar comprend generalement un generateur de requetes, qui traduit les missions en pointages. A une mission de veille correspondent des pointages permettant de mailler un espace de veille. A une mission de pour-quite correspond un ou plusieurs pointages permettant de suivre une piste. Les pointages des missions de veille et des missions de pour-quite vent destines a etre executes de maniere periodique. II existe aussi des pointages dont liexecution est sporadique, notamment les pointages de confirmation (suite a une detection lors d'une veille) et les pointages de re-acquisition (suite a une non detection lors d'une pour-quite). Ces pointages sporadiques peuvent etre prioritaires par rapport aux pointages periodiques. L'ordonnancement est la determination de l'ordre d'execution des pointages, periodiques ou sporadiques. Afin d'ordonnancer les pointages, on peut construire des frames de longueurs temporelles determinees. Lorsqu'une frame est en train de se construire, la precedente est executee par le radar. Cet ordonnancement fonctionne done en temps reel, car le temps necessaire a la construction d'une frame doit etre inferieur a la duree d'execution de la precedente par le radar. A cet effet, il est necessaire d'utiliser un algorithme rapide, base sur une politique d'ordonnancement simple. Ceci permet a cet algorithme de fonctionner en un temps restraint, compatible avec les contraintes imposees par ['execution en temps reel. Toutefois, cette maniere d'ordonnancer les pointages ne permet pas, pendant la duree de construction d'une frame, de prendre en compte de nouveaux pointages. II existe done un temps de latence proportionnel a la longueur d'une frame. 11 est done souhaitable de diminuer ce temps de latence. Or ceci reduit d'autant le temps disponible pour effectuer l'ordonnancement. Or l'ordonnancement temporel des pointages est un probleme d'optimisation multicritere, qui consiste a la fois a maximiser la charge (c'est a dire executer un maximum de pointages) du radar et a executer les pointages les plus importants. Etant donne la combinatoire exponentielle de ce probleme, il n'existe pas d'algorithme permettant, en un temps restraint, de donner une solution optimale. Par ses caracteristiques, telles qu'elles seront decrites et revendiquees ci-apres, I'invention vise a ordonnancer des taches de fa,con rapide pour diminuer le temps de latence, et ce sans executer de tache moins prioritaire au detriment d'une tache plus prioritaire. Pour satisfaire a cet objectif et obtenir d'autres avantages qui ressortiront plus loin, I'invention a pour objet un procede d'ordonnancement de taches. Ce procede permet de prendre en compte de nouvelles taches des qu'une tache est ordonnancee. Selon ce procede: - on realise au moins un premier filtrage, ce filtrage etant applique a une premiere liste contenant des taches destinees a etre ordonnancees, le resultat de ce filtrage etant une seconde liste ne contenant que les taches de la premiere liste de priorite maximale ou dont la duree d'execution est inferieure ou egale a une duree maximale theorique, ladite duree maximale theorique pour une tache donnee etant le minimum de la quantite E[ i] - D[ i] - H0 ou i est l'indice d'une tache appartenant a un ensemble de taches determine, ledit ensemble de taches etant constitue par les t3ches de la premiere liste dont la priorite est superieure strictement a celle de ladite tache donnee, ou E[ i] et D[ i] representent respectivement la date d'echeance et la duree de la tache d'indice i, ou H0 represente le prochain temps libre pour ['execution d'une tache; - si la seconde liste contient au moins une tache, on realise au moins un second filtrage applique a la seconde liste ou une partie de celle-ci, le resultat de ce second filtrage etant une troisieme liste ne contenant que les taches dont la date d'activation est inferieure ou egale au prochain temps libre HO pour ['execution d'une tache; - si la troisieme liste contient au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste. L'invention concerne aussi un procede d'ordonnancement dans lequel: - on realise au moins les deux premiers filtrages precedents; - si la troisieme liste contient au moins une tache, on realise au moins un troisieme filtrage applique a la troisieme liste ou une partie de celle- ci, le io resultat de ce troisieme filtrage etant une quatrieme liste ne contenant que les taches dont la priorite est superieure ou egale a une priorite determinee; - on choisit la prochaine tache a executer parmi les taches de la quatrieme liste. L'invention concerne aussi un procede d'ordonnancement dans lequel: - on realise au moins les trots premiers filtrages precedents; - on realise au moins un quatrieme filtrage applique a la quatrieme liste ou une partie de celle-ci, le resultat de ce quatrieme filtrage etant une cinquieme liste ne contenant que les taches dont les contraintes temporelles respectent un critere determine; - si la cinquieme liste contient au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste. Si la quatrieme liste ou la partie de celle-ci a laquelle est applique 2s le quatrieme filtrage ne contient que des taches periodiques, ce critere determine peut etre tel que le resultat du quatrieme filtrage ne contient que les taches dont le rapport entre le delai jusqu'a la derriere date d'execution d'une part, et la periode de la tache d'autre part, est le plus grand. L' i nvention sera mai ntenant d ecrite de ma n iere plus deta il lee dans le cadre d'un exemple particulier de mise en ceuvre pratique appliquee a un radar. Dans le cours de cette description, on fera reference aux figures des dessins annexes, parmi lesquelles: - la figure 1, un chronogramme, represente un exemple de taches destinees a etre ordonnancees; - la figure 2, un diagramme fonctionnel, represente des etapes d'un exemple de procede selon ['invention. On distingue les taches de nature sporadique des taches de nature periodique. Les taches de nature sporadique vent destinees a etre executees entre deux dates. La premiere date est appelee la date d'activation de la tache. Le debut d'execution d'une tache sporadique suit normalement la date d'activation de cette tache. En d'autres termes, la date d'activation d'une tache sporadique est la date a partir de laquelle la tache devient eligible. La seconde date est appelee la date d'echeance de la tache. La fin d'execution d'une tache sporadique precede normalement la date d'echeance de cette tache. Les taches de nature periodique vent destinees a etre executees a intervalle de temps regulier. On associe a chaque tache periodique, par analogie avec les taches sporadiques, une date d'activation et une date d'echeance. Ces dates d'activation et d'echeance vent determinees pour cheque periode, c'est a dire pour cheque occurrence de la tache. Une tache est soumise a des contraintes temporelles plus ou moins fortes. On distingue les taches urgentes des taches non urgentes. Une t3che urgente est une tache devant imperativement etre executees entre sa date d'activation et sa date d'echeance. Une tache non urgente est une tache pouvant etre executee en dehors de sa date d'activation et de sa date d'echeance. En d'autres termes, le debut z5 d'execution d'une tache non urgente peut preceder sa date d'activation, et la fin d'execution d'une tache non urgente peut suivre sa date d'echeance. En general, les taches urgentes vent de nature sporadique et les taches non urgentes vent de nature periodique. En d'autres termes, les contraintes temporelles des taches periodiques vent generalement moins strictes que celles des taches sporadiques. II est done possible d'executer une tache periodique avant sa date d'activation ou apres sa date d'echeance. On attribue a cheque tache un degre de priorite. Ce degre de priorite peut etre represente par un nombre entier. Par exemple, une valeur basse correspond a une tache peu prioritaire, une valeur elevee correspond a une tache tres prioritaire. Selon ['invention, les taches vent ordonnancees une a une, et on prend en compte les nouvelles taches a chaque fois qu'une tache est ordonnancee, c'est a dire des que la prochaine tache a executer est choisie. On se refere aux figures 1 a 2. Le procede d'ordonnancement selon ['invention permet de s'affranchir du temps de latence lie a la construction de frames. Les taches a ordonnancer forment une premiere liste o L1 de taches. La liste L1 peut etre modifiee des qu'une tache est ordonnancee, c'est a dire des le choix de la prochaine tache a executer. Cette tache choisie peut s'executer directement, c'est a dire au prochain temps libre d'execution H0. Le prochain temps libre d'execution H0 est la premiere date a partir de laquelle il est possible d'executer une tache. Cette tache peut aussi s'executer apres un temps mort, c'est a dire apres un intervalle de temps pendant lequel aucune tache niest executee. Le choix de la prochaine tache a executer peut etre realise en appliquant des filtrages successifs F1, F2, F3, F4 selon des regles determinees. Ces filtrages permettent de reduire peu a peu le nombre de taches eligibles pour n'en obtenir qu'une au bout du compte ou aucune. Si aucune tache n'est retenue apres ces filtrages successifs, on peut generer un temps mort. Selon ['invention, on applique a la liste des taches a ordonnancer un premier filtrage F1 des taches non genantes. Les taches genantes vent celles qui si elles etaient executees au prochain temps libre H0 pourraient gener ['execution d'une autre tache plus prioritaire (de degre de priorite plus eleve) de la liste L1. Afin d'effectuer le premier filtrage F1 des taches non genantes, on selectionne successivement chaque tache T5 de la liste L1 contenant les taches destinees a etre ordonnancees. Si la priorite de la tache selectionnee est superieure ou egale a celle de toutes les taches de la liste L1, on retient la tache selectionnee. Sinon, on determine une du ree maxi male d'execution theorique de la tache selectionnee. Par exemple pour la tache T5 representee sur la figure 1, on considere les taches T1, T2, T3, T4 de priorite superieure strictement a celle de la tache T5. On note E1, E2, E3 et E4 leurs dates d'echeance. On note D1, D2, D3 et D4 leurs durees. La duree maximale d'execution theorique S5 de la tache T5 est le minimum des durees de ['ensemble suivant: { E1 - D1 - H0; E2 - D2 - H0; E2 - D2 - H0; E3 - D3- H0; E4 - D4 - H0} Plus generalement, la duree maximale d'execution theorique d'une tache selectionnee est la plus petite valeur de la quantite suivante: E[i]-D[i]H0 L'indice i represente l'une des taches dont la priorite est superieure strictement a la tache selectionnee; ou E[ i] represente la date d'echeance de la tache d'indice i; ou D[ i] represente la duree de la tache d'indice i. La quantite E[ i] - D[ i] - H0 represente la duree que ne doit pas depasser une tache dont ['execution debute a partir du temps H0, pour que la tache d'indice i puisse s'executer apres sans depasser son echeance. Si la duree de la tache selectionnee T5 est inferieure ou egale a la duree maximale d'execution theorique S5, on retient ladite tache selection nee. S i non, la tache se lection nee n 'est pas reten u e (ce q u i est le cas sur la figure 1). Apres avoir selectionne toutes les taches de la liste L1, on choisit la prochaine tache a executer parmi les taches retenues. Avantageusement, on selectionne les taches de la liste L1 par ordre de priorite decroissante. De cette maniere, la determination de la duree maximale theorique d'une tache peut se faire en utilisant la duree maximale theorique determinee pour la tache precedente. Apres le filtrage F1 des taches non genantes, on realise un second filtrage F2. Ce second filtrage peut etre effectue directement apres le premier filtrage F1. Bien entendu, il est possible d'effectuer un ou plusieurs filtrages intermediaires entre les filtrages F1 et F2. En d'autres termes, le filtrage F1 est applique a la seconde liste L2 ou une partie de celle-ci (le resultat d'un autre filtrage par exemple). Le second filtrage F2 vise a eliminer les taches inactives, c'est a dire celles dont la date d'activation est superieure strictement au prochain temps libre HO pour l'execution d'une tache. En d'autres termes, on realise un second filtrage F2, le resultat de ce second filtrage etant une troisieme liste L3 ne contenant que les taches dont la date d'activation A1, A2, A3, A4 est inferieure ou egale au prochain temps libre HO pour l'execution d'une 1 o tache. En effectuant le premier et le second filtrage dans cet ordre, on evite de choisir une tache dont l'execution pourrait empecher l'execution d'une tache plus prioritaire, meme si cette tache plus prioritaire est inactive au moment de ce choix. Avantageusement, apres le filtrage F2 des taches actives, s'il reste plusieurs taches dans la liste L3, on peut realiser un troisieme filtrage F3. Ce troisieme filtrage F3 vise a eliminer les taches non prioritaires. En d'autres termes, on peut realiser un troisieme filtrage F3, applique a la troisieme liste L3 ou une partie de celle-ci. Le resultat de ce troisieme filtrage est une quatrieme liste L4 qui ne contient que les taches dont la priorite est superieure a une priorite determinee. Cette priorite determinee peut etre par exemple 80% de la priorite la plus haute des taches auquel est applique ce filtrage F3. Avantageusement, cette priorite determinee est la priorite la plus haute des taches auquel est applique ce filtrage F3. En d'autres termes, le resultat de ce filtrage sur les priorites ne contient que les taches dont la priorite est maximale. Avantageusement, apres le filtrage F3 des taches prioritaires, on peut realiser un quatrieme filtrage F4. Ce quatrieme filtrage vise a eliminer les taches a partir de contraintes temporelles. Ce filtrage peut etre applique a la quatrieme liste L4 ou a une partie de celle-ci. Le resultat de ce quatrieme filtrage est une cinquieme liste L5 qui ne contient que les taches dont les contraintes temporelles respectent un critere determine. Ce critere peut etre par exemple celui de la date d'echeance la plus proche. Dans ce cas, le filtrage F4 consiste a ne retenir que les taches dont la date d'echeance est la plus proche. Avantageusement, si la liste L4 ne contient que des taches periodiques, le critere peut par exemple etre de minimiser l'ecart avec la periode nominale. Dans ce cas, le filtrage F4 consiste a ne retenir que les taches dont le rapport entre le delai jusqu'a la derriere date d'execution diune part, et la periode de la tache d'autre part, est le plus grand. Apres le filtrage F2 et le cas echeant d'autres filtrages F3, F4, plusieurs cas vent possibles. S'il ne reste qu'une seule tache, ceffe tache est choisie. S'il reste plusieurs taches, on peut en choisir une indifferemment. S'il ne reste aucune tache, on peut generer un temps mort TM. Apres avoir choisi une tache on peut: - si cette tache est une tache periodique: mettre a jour sa date d'activation et sa date d'echeance pour sa prochaine execution, et le cas echeant d'autres donnees; - si cette tache est une tache sporadique: la supprimer de la liste L1. Les taches sporadiques dont la date d'echeance est depassee peuvent etre aussi supprimees de la liste L1. On peut ajouter de nouvelles taches a la liste L1. On peut alors choisir la prochaine tache a executer dans la liste L1 ainsi modifiee en appliquant a nouveau le procede selon ['invention. REVENDICATIONS 1. Procede d'ordonnancement de taches caracterise en ce que: - on realise au moins un premier filtrage (F1), ce filtrage etant applique a une premibre liste (L1) contenant des taches destinees a etre ordonnancees, le resultat de ce filtrage etant une seconde liste (L2) ne contenant que les taches de la premiere liste (L1) de priorite maximale ou dont la duree d'execution (D5) est inferieure ou egale a une duree maximale theorique (S5), ladite duree maximale theorique (S5) pour une tache donnee (T5) etant le minimum de la quantite E[ i] - D[ i] - H0 ou i est l'indice d'une tache appartenant a un ensemble de taches (T1, T2,T3, T4) determine, ledit ensemble de taches etant constitue par les taches de la premiere liste (L1) dont la priorite est superieure strictement a celle de ladite tache donnee, ou E[ i] et D[ i] representent respectivement la date d'echeance et la duree de la tache d'indice i, ou H0 represente le prochain temps libre pour ['execution d'une tache; - si la seconde liste (L2) contient au moins une tache, on realise au moins un second filtrage (F2) applique a la seconde liste (L2)ou une partie de celle-ci, le resultat de ce second filtrage etant une troisieme liste (L3) ne contenant que les taches dont la date d'activation (A1, A3) est inferieure ou egale au prochain temps libre H0 pour ['execution d'une tache; - si la troisieme liste (L3) contient au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste. 2. Procede d'ordonnancement de tAches caracterise en ce que: - on realise au moins les deux premiers filtrages (F1, F2) selon la revendication 1; si la troisieme liste (L3) contient au moins une tache, on realise au moins un troisieme filtrage (F3) applique a la troisieme liste (L3)ou une partie de celle-ci, le resultat de ce troisieme filtrage etant une quatrieme liste (L4) ne contenant que les taches dont la priorite est superieure ou egale a une priorite determinee; - on choisit la prochaine tache a executer parmi les taches de la quatrieme liste (L4). 3. Procede d'ordonnancement selon la revendication 2 caracterise en ce que le resultat du troisieme filtrage (F3) ne contient que les taches dont la priorite est maximale. 4. Procede d'ordonnancement de taches caracterise en ce que: - on realise au moins les trots premiers filtrages (F1, F2, F3) selon l'une quelconque des revendications 2 et 3; - on realise au moins un quatrieme filtrage (F4) applique a la quatrieme liste (L4) ou une partie de celle-ci, le resultat de ce quatrieme filtrage etant une cinquieme liste (L5) ne contenant que les taches dont les contraintes temporelles respectent un critere determine; - si la cinquieme liste (L5) contient au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste. 5. Procede d'ordonnancement de taches selon la revendication 4, caracterise en ce que si la quatrieme liste (L4) ou la partie de celle-ci a laquelle est applique le quatrieme filtrage (F4) ne contient que des taches periodiques, le resultat du quatrieme filtrage ne contient que les taches dont le rapport entre le delai jusqu'a la derriere date d'execution d'une part, et la periode de la tache d'autre part, est le plus grand.