Brevet FR2839367A1 — publié le 20031107

ledit eapteur DP (10). La presente invention concerne un procede d'ordonnancement de taches en deux passes. 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 facon 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 ['execution 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 prioritai res par rapport a ux poi ntages period iqu es. 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 diordonnancement 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. II est done souhaitable de diminuer ce temps de latence. Or ceci reduit d'autant le temps disponible pour effectuer l'ordonnancement. Or I'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 en evitant de generer des temps morts. 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 une premiere passe, cette premiere passe etant appliquee a une premiere liste contenant des taches destinees a etre ordonnancees, cette premiere passe comprenant au moins un filtrage, un filtrage de cette premiere passe consistent a ne retenir que les taches dont la date d'activation est inferieure ou egale au prochain temps libre H0 pour ['execution d'une tache; 2 - si a ['issue de cette premiere passe on obtient une liste contenant au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste; - sinon, on realise une deuxieme passe, cette deuxieme passe etant appliquee a la premiere liste, la seconde passe comprenant au moins un filtrage, un filtrage de la seconde passe etant un filtrage sur des secondes dates d'activations consistent a ne retenir que les taches dont la seconde date d'activation est inferieure ou egale au prochain temps libre H0 pour ['execution diune tache, ces secondes dates d'activations pour les taches non urgentes etant inferieures aux dates d'activations utilisees lors de la premiere passe; si a ['issue de cette deuxieme passe on obtient une liste contenant au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste. Avantageusement, lors de la seconde passe on realise un filtrage, ce filtrage etant applique a la premiere liste ou a une partie de celle-ci, le resultat de ce filtrage etant une liste ne contenant que des taches non urgentes. Avantageusement, pour chaque tache periodique, la seconde date d'activation est determinee par la relation: Tact2 = Texec + (1 - ú) X Trec OU Tac2 represente la seconde date d'activation de la tache; Texec represente la derriere date d'execution de la tache; s represente un coefficient de fluctuation par rapport a la periode nominale de la tache, ce coefficient etant strictement inferieur a 1; Trec represente la periode nominale de recurrence de la tache. Avantageusement, lors de la premiere passe on realise un filtrage sur les priorites, ce filtrage etant applique a la premiere liste ou a une partie de celle-ci, le resultat de ce filtrage etant une liste ne contenant que les taches dont la priorite est superieure ou egale a une priorite determinee. Avantageusement, le resultat de ce filtrage sur les priorites ne contient que les taches dont la priorite est maximale. Avantageusement, lors de la premiere passe ou de la seconde passe on realise un filtrage temporel, ce filtrage etant applique a la premiere liste ou a une partie de celle-ci, le resultat de ce filtrage etant une liste ne contenant que les taches dont les contraintes temporelles respectent un critere determine. Avantageusement, si toutes les taches auxquelles est applique le filtrage temporel vent des taches periodiques, le resultat de ce 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. Avantageusement, la seconde passe ne comprend pas de filtrage sur les priorites. L' invention sera maintenant decrite de maniere plus detaillee dans le cadre d'un exemple particulier de mise en couvre 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 diagramme fonctionnel, represente des etapes de filtrage d'un exemple de procede selon ['invention; - la figure 2, un diagramme d'ensembles, represente des listes de taches resultant d'une mise en ceuvre a un instant donne du procede illustre figure 1. 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 chaque periode, c'est a dire pour chaque 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 tache 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 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 chaque 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. On se refere aux figures 1 a 2. Le procede d'ordonnancement selon ['invention permet de choisir la prochaine tache a executer dans une liste L1, cette liste L1 contenant les taches destinees a etre ordonnancees. Le choix de la prochaine tache a executer peut etre realise en appliquant des filtrages successifs F1, F2, F3... selon des regles determinees. Ces filtrages permettent de reduire peu a peu le nombre de taches eligibles. On obtient au bout du compte tres peu de taches (voire une seule) ou aucune. Selon ['invention, on realise une premiere passe P1. La premiere passe P1 comprend au moins un filtrage. Cette premiere passe est appliquee a une premiere liste L2. Cette premiere liste L2 contient des taches destinees a etre ordonnancees. Cette premiere liste peut etre la liste des taches destinGes a etre ordonnancees L1. Cette premiere liste peut aussi (tel qu'illustre sur la figure 1) etre une partie de celle-ci, resultant par exemple de 2s la realisation d'autres filtrages F1, ces autres filtrages F1 etant appliques a la liste des taches destinees a etre ordonnancees L1. Un filtrage F2 de cette premiere passe P1 vise a eliminer les taches inactives. II consiste a ne retenir que les taches dont la date d'activation est inferieure ou egale au prochain temps libre H0 pour I'execution d'une tache. Le prochain temps libre d'execution H0 est la premiere date a partir de laquelle il est possible d'executer une tache. Le resultat de ce filtrage F2 est une liste de taches actives L3, c'est a dire une liste qui ne comprend que des taches (provenant de la liste auquel est applique le filtrage F2) dont la date d'activation est inferieure ou egale au prochain temps libre H0 pour ['execution d'une tache. Avantageusement, la premiere passe peut comprendre d'autres filtrages. On peut realiser par exemple un filtrage F3 qui vise a eliminer les taches non prioritaires. Avantageusement, le filtrage F3 peut etre realise apres le filtrage F2 s'il reste plusieurs taches dans la liste de taches actives L3. En d'autres termes, le filtrage F3 peut etre applique a la liste de taches actives L3 ou une partie de celle-ci. Le resultat de ce filtrage est une liste de taches prioritaires L4, c'est a dire une liste qui ne comprend que des 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. De preference, on realise le filtrage F2 qui vise a eliminer les taches inactives avant le filtrage F3 qui vise a eliminer les taches non prioritaires. On peut realiser par exemple un filtrage F4 qui vise a eliminer les taches a partir de contraintes temporelles. Avantageusement, le filtrage F4 peut etre realise apres le filtrage F3 s'il reste plusieurs taches dans la liste de taches prioritaires L4. En d'autres termes, le filtrage F4 peut etre applique a la liste de taches prioritaires L4 ou a une partie de celle-ci. Le resultat de ce quatrieme filtrage est une liste L5 ne comprenant que des taches dont les contraintes temporelles respectent un critere determine. Ce critere peut etre par exemple 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 d'une part, et la periode de la tache d'autre part, est le plus grand. Si a ['issue de cette premiere passe P1 on obtient une liste L5 contenant au moins une t3che, on choisit dans cette liste la prochaine tache a executer. S'il reste plusieurs taches, on peut en choisir une indifferemment. Cette tache pourra s'executer directement, c'est a dire au prochain temps libre H0 pour ['execution d'une tache. Sinon (il ne reste aucune tache), aucune tache ne peut etre choisie a ['issue de la premiere passe P1. Plutot que de generer un temps mort, c'est a dire apres un intervalle de temps pendant lequel aucune tache n'est executee, on realise une deuxieme passe P2. La deuxieme passe est differente de la premiere passe. Wile est appliquee a la premiere liste L2. Cette deuxieme passe comprend au moins un filtrage. Un filtrage F6 de cette deuxieme passe vise a eliminer les taches inactives en utilisant des secondes dates d'activations plus couples, de maniere a retenir davantage de taches. Pour les taches non urgentes, il est possible en effet de ['executer avant sa date d'activation. On determine done des secondes dates d'activations inferieures aux dates d'activations normales (celles utilisees lors de la premiere passe P1). Pour les taches urgentes en revanche, les dates d'activations ne pouvant pas etre modifiees, les secondes dates d'activations et les dates d'activations normales se confondent (on utilise les memes dates d'activations lors des deux passes P1, P2). Le resultat de ce filtrage F6 est une liste de taches actives pour la deuxieme passe L7, c'est a dire une liste qui ne comprend que des taches dont la seconde date d'activation est inferieure ou egale au prochain temps libre H0 pour ['execution d'une tache. Par exemple, pour chaque tache periodique, la premiere date d'activation peut etre determinee par la relation: Tact1 = Texec + Trec ou Tac represente la premiere date d'activation de la tache, Texec represente la derriere date d'execution de la tache, Trec represente la periode nominale de recurrence de la tache. Avantageusement, pour chaque tache periodique, la seconde date d'activation est determinee par la relation: Tact2 = Texec + (1 - ú)X Trec ou Tac2 represente la seconde date d'activation de la tache; s represente un coefficient de fluctuation par rapport a la periode nominale de la tache, ce coefficient etant strictement inferieur a 1. Le coefficient de fluctuation est un parametre de contrGle. II permet de contrGier la fluctuation induite autour de la periode nominale. II est possible d'utiliser une meme valeur du coefficient de fluctuation pour toutes les taches periodiques de maniere a modifier de maniere uniforme o l'avancement relatif (a la periode nominale) des dates d'activation. Avantageusement, la seconde passe P2 peut comprendre d'autres filtrages. On peut realiser par exemple un filtrage F5 qui vise a eliminer les taches urgentes. En d'autres termes, le resultat du filtrage F5 est une liste ne contenant que des taches non urgentes. Avantageusement, le filtrage F5 peut etre realise avant le filtrage F6. En d'autres termes, le filtrage F6 peut etre applique a la liste L6, resultat du filtrage F5, c'est a dire uniquement a des taches non urgentes (dons la date d'activation pourra etre modifiee). Avantageusement, pour augmenter les chances de selectionner une tache lors de la seconde passe P2, la seconde passe P2 ne comprend aucun filtrage sur les priorites. Ceci permet d'augmenter la chance de selectionner les taches de falble priorite. On peut realiser par exemple un filtrage F7 qui vise a eliminer les taches a partir de contraintes temporelles. Ce filtrage F7 de la seconde passe P2 est equivalent au filtrage F4 de la premiere passe. Avantageusement, le filtrage F7 peut etre realise apres le filtrage F6 s'il reste plusieurs taches. En d'autres termes, le filtrage F7 peut etre applique a la liste de taches actives pour la deuxieme passe L7 ou a une partie de celle-ci. Le resultat de ce filtrage F7 est une liste L8 ne comprenant que des taches dont les contraintes temporelles respectent un critere determine, tel que pour le filtrage F4. Lorsque toutes les taches non urgentes vent des taches periodiques, le filtrage F5 a pour effet de ne retenir que des taches periodiques. Par consequent, il est possible dans le filtrage temporel F7 d'appliquer le critere de minimisation l'ecart avec la periode nominale (delai relatif le plus grand). Si a ['issue de cette deuxieme passe P2 on obtient une liste L8 contenant au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste L8. S'il reste plusieurs taches, on peut en choisir une indifferemment. Cette tache pourra s'executer directement, c'est a dire au prochain temps libre H0 pour ['execution d'une tache. Sinon, on pourra generer un temps mort ou effectuer d'autres passes telles que la seconde passe P2. 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. o L'invention permet ainsi de s'affranchir du temps de latence lie a la construction de frames. Les taches etant ordonnancees une a une, on peut prendre en compte de nouvelles taches a chaque fois qu'une tache est ordonnancee, c'est a dire des que la prochaine tache a executer est choisie. REVENDICATIONS 1. Procede d'ordonnancement de taches caracterise en ce que: - on realise une premiere passe (P1), cette premiere passe etant appliquee a une premiere liste (L2) contenant des taches destinees a etre ordonnancees, cette premiere passe comprenant au moins un filtrage (F2,F3,F4), un filtrage (F2) de cette premiere passe (P1) consistent a ne retenir que les taches dont la date d'activation est inferieure ou egale au prochain temps libre H0 pour ['execution d'une tache; - si a ['issue de cette premiere passe (P1) on obtient une liste (L5) contenant au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste (L5); - sinon, on realise une deuxieme passe (P2), cette deuxieme passe etant appliquee a la premiere liste (L2), la seconde passe comprenant au moins un filtrage (F5, F6, F7), un filtrage (F6) de la seconde passe (P2) etant un filtrage sur des secondes dates d'activations consistent a ne retenir que les taches dont la seconde date d'activation est inferieure ou egale au prochain temps libre H0 pour ['execution d'une tache, ces second es dates d 'activations pou r les tach es non u rgentes eta nt inferieures aux dates d'activations utilisees lors de la premiere passe (P1); - si a ['issue de cette deuxieme passe (P2) on obtient une liste (L8) contenant au moins une tache, on choisit la prochaine tache a executer parmi les taches de cette liste (L8). 2. Procede d'ordonnancement de taches selon la revendication 1, caracterise en ce que lors de la seconde passe (P2) on realise un filtrage (F5), ce filtrage etant applique a la premiere liste (L2)ou a une partie de celle-ci, le resultat de ce filtrage etant une liste (L6) ne contenant que des taches non urgentes. 3. Procede d'ordonnancement de taches selon l'une quelconque des revendications precedentes, caracterise en ce que pour chaque tache periodique, la seconde date d'activation est determinee par la relation: Tact2 = Texec + (1 - ú)X Trec ou Tac2 represente la seconde date d'activation de la tache; Texec represente la derriere date d'execution de la tache; s represente un coefficient de fluctuation par rapport a la periode nominale de la tache, ce coefficient etant strictement inferieur a 1; Trec represente la periode nominale de recurrence de la tache. 4. Procede d'ordonnancement de taches selon l'une quelconque des revendications precedentes, caracterise en ce que lors de la premiere passe (P1) on realise un filtrage sur les priorites (F3), ce filtrage etant applique a la premiere liste (L2) ou a une partie (L3) de celle-ci, le resultat de ce filtrage etant une liste (L4) ne contenant que les taches dont la priorite est superieure ou egale a une priorite determinee. 5. Procede d'ordonnancement de taches selon la revendication 4, caracterise en ce que le resultat du filtrage sur les priorites (F3) ne contient que les taches dont la priorite est maximale. 6. Procede d'ordonnancement de taches selon l'une quelconque des revendications precedentes, caracterise en ce que lors de la premiere passe (P1) ou de la seconde passe (P2) on realise un filtrage temporel (F4 ou F7), ce filtrage etant applique a la premiere liste (L2) ou a une partie (L3,L4 ou L6, L7) de celle-ci, le resultat de ce filtrage etant une liste (L5 ou L8) ne contenant que les taches dont les contraintes temporelles respectent un critere determine. 7. Procede d'ordonnancement de taches selon la revendication 6, caracterise en ce que si toutes les taches auxquelles est applique le filtrage temporel vent des taches periodiques, le resultat de ce filtrage temporel ne contient o 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. 8. ProcAdA ordonnancement de tAches sewn l'une queiconque des revendlcadons prAcAdentes, camctAMsA en ce qua seconds passe (P2) ne