Brevet FR2949876A1 — publié le 20110311

PROCEDE D'ORDONNANCEMENT TEMPS REEL D'UN ENSEMBLE DE TACHES MULTI-TRAMES NON CYCLIQUES La présente invention a pour objet un procédé d'ordonnancement temps réel de tâches logicielles multi-trames. Elle concerne le domaine des processeurs temps-réels, par exemple des processeurs de traitement de signal, sur lesquels sont exécutées une pluralité de fonctions, encore appelées tâches logicielles, qui peuvent être concurrentes, c'est-à-dire être appelées simultanément. L'invention concerne plus particulièrement la ~o problématique de l'ordonnancement temps réel des tâches logicielles exécutées par une ou plusieurs applications logicielles sur un ou plusieurs processeurs en parallèle. Une tâche multi-trames désigne une tâche ou fonction logicielle qui exécute un traitement sur une pluralité de trames de données auxquelles 15 sont associées un temps d'exécution, une échéance ainsi qu'un temps de garde vis-à-vis de la trame suivante. Le temps d'exécution C est le temps nécessaire pour exécuter, sur ladite trame de données, le traitement fonctionnel défini par la tâche correspondante sur un processeur donné. Il dépend à la fois de la complexité du traitement à exécuter et des ressources 20 du processeur, notamment de sa fréquence de fonctionnement. L'échéance D correspond au temps relatif qui s'écoule entre l'activation d'une tâche et le temps au bout duquel l'exécution de cette tâche doit être finalisée. L'échéance dépend notamment de contraintes temporelles liées à l'application logicielle ou au système mis en oeuvre qui utilise cette 25 application. Le temps de garde P correspond au temps minimum qui s'écoule entre deux appels successifs à une même tâche. Un des problèmes que cherche à résoudre l'invention est de garantir la faisabilité temps réelle de l'implémentation d'un ensemble de tâches mufti- 30 trames, qui définissent ensemble une application ou un système, ayant des paramètres de temps d'exécution, d'échéance et de temps de garde donnés sur un processeur donné. A cet effet, le problème technique à résoudre concerne l'ordonnancement temps réel de ces tâches sur ce processeur. Afin de garantir que la conception des tâches logicielles est valide d'une implémentation temps-réelle, il est nécessaire de tester si les limites temporelles ne sont jamais dépassées en vérifiant notamment que chaque tâche s'exécute bien avant son échéance. La résolution de ce problème technique permet de valider le bon fonctionnement de l'ordonnanceur qui est mis en oeuvre par le système d'exploitation associé au processeur. Un ordonnanceur est un composant du système d'exploitation qui a pour fonction de déterminer l'ordre dans lequel les tâches ou processus vont être exécutés sur un processeur de façon à respecter le temps-réel. L'utilisation d'un ordonnanceur permet d'exécuter en parallèle plusieurs tâches ou processus sur un seul processeur en partageant ses ressources temporellement. De cette façon, l'exécution en temps réel des tâches est possible. Cependant, il existe des cas de figure où la spécification des tâches logicielles à exécuter est telle qu'elle ne permet pas leur exécution simultanée en temps réel, dans ce cas l'ordonnanceur ne pourra pas fonctionner correctement car il sera amené à résoudre un problème qui ne possède pas de solution. Ces scénarios ne sont pas forcément aisément détectables et évitables notamment dans le cas d'applications complexes qui utilisent plusieurs tâches concurrentes elles mêmes exécutant un traitement sur plusieurs trames de données ayant des contraintes d'exécution bornées dans le temps. II est donc important de pouvoir détecter ces cas de figure pendant la phase de conception de l'architecture globale du système afin de redéfinir les paramètres des tâches logicielles que l'on souhaite déployer sur un processeur donné si ceux-ci ne sont pas compatibles d'une exécution temps réelle. Une politique d'ordonnancement connue de l'Homme du métier est la méthode d'ordonnancement à priorité dynamique connue sous l'abréviation anglo-saxonne EDF (� Earliest Deadline First �). Cette méthode consiste à attribuer une priorité dynamique à chaque tâche ou processus en fonction de l'échéance de ce dernier. Plus l'échéance d'une tâche est proche, plus sa priorité est grande. L'invention se positionne notamment dans le cadre de cette méthode d'ordonnancement. Le document [1] décrit le concept de tâches multi-trames et propose de modéliser un ensemble de tâches logicielles temps-réelles à l'aide de ce concept. Une tâche multi-trame est une tâche ou fonction logicielle qui exécute un traitement sur une pluralité de trames de données caractérisées 1 o par les trois paramètres de temps d'exécution E, échéance D, et temps de garde P introduits précédemment dans ce document, et pour lesquelles, de plus, le temps d'exécution E est variable d'une trame à une autre. Le document [2] reprend ce concept en le généralisant à un ensemble de tâches multi-trames pour lesquelles l'échéance D et le temps de garde P 15 sont également variables. Un test de faisabilité associé à une méthode d'ordonnancement à priorité dynamique (telle que la méthode EDF) est proposée dans le document [2]. Cette méthode est basée sur la construction d'une fonction d'exigence bornée dépendant des paramètres E,D et P et permettant de valider la faisabilité de l'exécution temps-réelle d'une pluralité 20 de tâches logicielles sur un processeur donné. La solution proposée par le document [2] se limite au cas particulier où il existe une périodicité, encore appelée cycle, dans l'appel successif des tâches et l'enchaînement temporel du traitement des trames. Dans ce cas, il 25 est possible de trouver un motif de répétition qui définit entièrement le séquencement temporel de l'exécution d'une tâche sur une période de temps donnée. Un exemple d'un tel cas de figure est décrit sur la figure 1. Une tâche logicielle i qui exécute un traitement sur trois types de trames de données différentes caractérisées chacune par les trois paramètres de temps 30 d'exécution C,', C,z, Cl3 , d'échéance Di', D,Z, Dt3 entre l'instant où la tâche est activée et l'instant où elle doit avoir terminé le traitement de la trame pour respecter les contraintes de temps-réel et de temps de garde P', P2 entre deux appels successifs à cette tâche. Au bout d'un temps de cycle T = P' + P2 + P3 , le motif temporel d'exécution de la tâche i se répète périodiquement comme illustré sur la figure 1. La tâche i est alors qualifiée 5 de tâche multi-trames cyclique. Un tel cas de figure correspond, par exemple, au cas d'un dispositif de compression vidéo de type MPEG (Motion Picture Expert Group) qui peut manipuler trois types de trames de données différentes connues de l'Homme du métier sous l'identifiant trames I, P ou B, et qui sont transmises le plus 10 souvent selon un motif temporel cyclique. La fonction d'exigence introduite dans [2] et permettant de tester la faisabilité d'un ensemble de tâches multi-trames utilise la période ou cycle T pour résoudre le problème d'ordonnancement des tâches et se limite donc au cas de tâches cycliques. 15 L'invention propose une solution permettant de résoudre le problème de faisabilité d'un ensemble de tâches logicielles multi-trames lorsque celles-ci ne présentent aucun motif de répétition temporel. En particulier ce cas de figure correspond à un traitement aléatoire des trames de données lorsqu'on 20 ne connaît pas à l'avance leur instant d'arrivée. Un exemple d'un tel scénario est schématisé sur la figure 2. La même tâche logicielle i que celle illustrée à la figure 1 est représentée mais cette fois dans un cas d'application pour lequel les trois types de trames de données ne sont pas traitées selon un schéma temporel cyclique car elles arrivent dans un ordre aléatoire. Ce cas 25 de figure correspond, par exemple, à un dispositif de modulation OFDMA (Orthogonal Frequency Division Multiple Access) qui génère des trames de données allouées à différents utilisateurs et possédant donc des caractéristiques différentes et qui sont transmises dans un ordre non prédictible. A cet effet l'invention a pour objet un procédé d'ordonnancement temps-réel d'une application exécutée sur au moins un processeur, la dite application étant composée d'une pluralité m de tâches logicielles exécutant au moins un traitement sur une pluralité N de trames de données successives, chacune desdites tâches i étant définies au moins, pour chacune desdites trames j, par un temps d'exécution Ci] , une échéance d'exécution Di' et un temps de garde P vis-à-vis de la trame j+1 suivante, ledit temps de garde P étant supérieur ou égal à ladite échéance Di' , ledit procédé étant caractérisé en ce qu'il comprend au 10 moins les étapes suivantes: C i' o Pour chaque tâche i, calculer les rapports D > entre le temps d'exécution C iJ de chaque trame j et la deadline correspondante D i , o Pour chaque tâche i, rechercher le maximum sur l'ensemble C 1' 15 desdites trames j desdits rapports max( D ~) , m-1 Comparer la somme E maxN-1 Dans un mode de réalisation de l'invention, un seul processeur à fréquence variable est utilisé et ledit procédé comporte en plus les étapes suivantes m-1 C o Si l'inégalité suivante max 1 ( ) 5- n'est pas i=o 0 dispositif étant caractérisé en ce qu'il comporte des moyens pour mettre en oeuvre le procédé d'ordonnancement décrit précédemment. D'autres caractéristiques apparaîtront à la lecture de la description 5 détaillée donnée à titre d'exemple et non limitative qui suit faite en regard de dessins annexés qui représentent : La figure 1, un schéma d'un exemple de tâches multi-trames cycliques et de leur exécution au cours du temps, La figure 2, un schéma d'un exemple de tâches multi-trames non 10 cycliques et de leur exécution au cours du temps, La figure 3, un synoptique du procédé selon l'invention, La figure 4, un exemple d'architecture d'un système temps-réel pour lequel l'invention s'applique. La figure 5, un exemple de dispositif d'ordonnancement selon 15 l'invention utilisé pour garantir la sureté de fonctionnement temps réel d'une application s'exécutant sur une plateforme comprenant plusieurs processeurs identiques. La figure 3 schématise un diagramme représentant les étapes du 20 procédé d'ordonnancement de tâches logicielles selon l'invention. Le procédé s'intègre dans le cadre d'un système temps-réel exécutant notamment les tâches logicielles que l'on souhaite ordonnancer sur un processeur donné. Le système temps-réel spécifié 301 permet de définir un ensemble de tâches logicielles qui correspondent à des fonctions exécutant 25 chacune un sous ensemble des traitements nécessaires au fonctionnement dudit système. La décomposition du système en tâches est généralement faite lors d'une phase de conception et dépend notamment des spécifications du système, en particulier le type de traitements à effectuer et leurs contraintes temporelles. Les tâches composant le système doivent être 30 exécutées sur un processeur, par exemple un processeur de traitement de signal de type DSP (� Digital Signal Processing �), qui comporte également 2949876 des caractéristiques 302 intrinsèques, par exemple sa fréquence de fonctionnement ou vitesse d'exécution, lesquelles impactent également la conception des tâches. Une étape 303 de définition des tâches permet donc de générer un ensemble de tâches i pour lesquelles trois paramètres sont définis pour chaque trame de données j manipulée par la tâche multi-trame i. Ces paramètres sont le temps d'exécution C/ de la tâche i pour la trame de donnée j, son échéance D/ et son temps de garde P' . Un test de faisabilité 304 selon l'invention, est ensuite appliqué afin de déterminer si l'ensemble des tâches conçues lors de l'étape 303 est ordonnançable sur le processeur choisi selon la politique d'ordonnancement EDF. Pour un nombre m de tâches, chacune générant un nombre N de trames de données, le test de faisabilité consiste à vérifier la relation suivante : m -1 C max ( lé i=0 0 20 Dans le cas contraire, une redéfinition 306 des tâches est nécessaire. De façon dynamique, le procédé selon l'invention s'applique également lorsqu'une nouvelle tâche est créée et que l'on souhaite valider sa faisabilité conjointement à l'ensemble de tâches déjà conçues. L'application du test selon la relation (1) en intégrant cette nouvelle tâche permet de valider son 25 intégration ou au contraire de la rejeter et de redéfinir ses caractéristiques afin que les paramètres (C/ , D/ , P') respectent la relation (1). Le temps d'exécution C/ peut être déterminé soit en estimant à priori la complexité des traitements exécutés par la tâche i sur la trame j soit en15 mesurant, unitairement, le temps nécessaire à l'exécution de cette tâche seule sur le processeur choisi. Un moyen d'adapter le temps d'exécution afin de permettre à la tâche i de respecter la relation (1) et donc d'être ordonnançable, est d'optimiser la mise en oeuvre des traitements algorithmiques afin d'accélérer leur vitesse d'exécution. La relation (1) est une condition suffisante pour que l'ensemble des tâches qui satisfont cette relation soit ordonnancable selon une politique d'ordonnancement EDF, c'est-à-dire que la priorité la plus élevée est accordée à la tâche qui présente l'échéance la plus proche. Le paragraphe ~o suivant vise à démontrer que la vérification de la relation (1) suffit à assurer la faisabilité d'une implémentation temps-réelle des tâches multi-trames non cycliques et suffit donc à résoudre le problème technique mentionné au début de ce document. 15 Pour s'assurer du respect de l'exécution temps-réelle d'une pluralité de tâches concurrentes qui peuvent s'exécuter à des instants non prédictibles, il suffit de se placer dans le pire cas pour lequel toutes les tâches sont activées en même temps à un instant to. Ce cas représente la situation la plus contraignante puisque le processeur est sollicité par toutes 20 les tâches en même temps. En considérant uniquement le premier appel de chaque tâche correspondant à la première trame à traiter on vérifie alors que si le temps réel est respecté pour cette première activation alors il le sera aussi pour les appels suivants qui n'auront pas lieu simultanément et donc représenteront une situation moins contraignante. 25 Pour le premier appel de chaque tâche, on considère tout d'abord la configuration pour laquelle chaque tâche traite une trame x; correspondant à la plus grande criticité ou urgence d'exécution ce qui se traduit par une maximisation du rapport entre le temps nécessaire pour exécuter le so traitement associé à cette trame et l'échéance d'exécution: = max ` 0 20 Dans une seconde étape, on considère la configuration pour laquelle lors du premier appel, chaque tâche traite une trame quelconque y; moins critique que la trame x;, et qui vérifie donc la relation: (6) 15 C, Cx t D Y1 ≤ (8) i=o i et on peut ensuite appliquer le même raisonnement que précédemment pour démontrer que la relation (8) implique la relation suivante : Ck k De façon similaire, le test de faisabilité définit par la relation (1) peut être étendu à l'exécution de m tâches logicielles sur un nombre p, au moins égal à 2, de processeurs identiques fonctionnant en parallèle au sein d'un dispositif multi-processeurs. Dans ce cas, le test de faisabilité garantissant l'ordonnancement temps réel de m tâches multi-trames sur p processeurs fonctionnant en parallèle est déterminé en vérifiant la relation suivante m-1 C J max o5, La relation (9) se démontre de façon analogue à la relation (1). Une condition suffisante pour que toutes les tâches soient ordonnançables sur les p processeurs disponibles est obtenue en vérifiant la relation suivante pour tout i Un dispositif d'ordonnancement 501 a pour fonction de garantir l'exécution temps-réelle d'une ou plusieurs applications logicielles 503,504. A un instant donné, une application 504 crée 511 une tâche logicielle dont les caractéristiques de temps d'exécution, échéance d'exécution et temps de garde sont transmises au dispositif d'ordonnancement 501. Ce dernier exécute le procédé selon l'invention tel que décrit précédemment en prenant en compte la création 511 de cette nouvelle tâche ainsi que l'ensemble des tâches 51,52,53 déjà exécutées sur un ensemble de processeurs Proc1,Proc2,ProcP disponibles. Si le dispositif d'ordonnancement 501 conclue à la non faisabilité d'une exécution temps-réelle de la nouvelle tâche créée 511, il rejette 512 cette tâche dans le but de garantir la sureté de fonctionnement de l'application 504 et renvoi un message à ladite application 504 afin de lui permettre de redéfinir les caractéristiques de ladite tâche 511. Si au contraire, le dispositif d'ordonnancement 501 conclue à la faisabilité de l'exécution temps-réelle de la tâche 511, il autorise 513 l'ajout de cette nouvelle tâche et communique cette information à un dispositif d'allocation 502 qui positionne la tâche 511 pour une exécution sur l'un des processeurs disponibles selon une politique d'ordonnancement de type EDF, c'est-à-dire, qu'à un instant donné, un processeur dont les ressources sont disponibles sélectionne parmi toutes les tâches à exécuter, celle dont l'échéance d'exécution est la plus proche. Dans une variante de réalisation de l'invention pour laquelle un seul processeur est utilisé, et que ce processeur possède la capacité d'avoir une fréquence variable permettant le changement de cette fréquence pendant l'exécution des tâches, le procédé selon l'invention contient de plus les étapes suivantes. ' Si la relation (1) n'est pas respectée, on note S = E max C ( °≤;≤N-' D' , 8 est donc supérieur à un. Afin de garantir le respect du temps-réel, le dispositif 30 d'ordonnancement 501 déclenche 514 la multiplication par un facteur 8 de la fréquence courante de fonctionnement du processeur. Si la nouvelle fréquence obtenue ne dépasse pas la fréquence maximale de fonctionnement du processeur, il autorise 513 l'ajout de la nouvelle tâche. En effet, la multiplication par un facteur b de la fréquence d'exécution du processeur est équivalente à la division de tous les temps d'exécution C~' m -1 C J par cette même quantité S. De ce fait, la somme E omax (D devient alors égale à 1 et respecte donc l'inégalité (1). D'une façon plus générale, on voit que pour respecter l'inégalité (1) il suffit d'augmenter la fréquence du processeur d'un facteur au moins égal à S. Le procédé selon l'invention s'applique notamment pour la conception de systèmes de communications multi utilisateurs. Un système de transmission est, la plupart du temps, utilisé par plusieurs utilisateurs et permet de véhiculer également une pluralité de services différents possédant des caractéristiques dont l'impact, notamment, sur les trames de données et le temps d'exécution des tâches est différent. Une application de transmission de contenus vidéo peut par exemple utiliser des trames de données de longueur plus importantes qu'une application de messagerie textuelle. La taille des trames a un impact sur le temps d'exécution de la tâche associée. De plus, l'instant d'arrivée, et donc de traitement, des trames de données dans un système de communication bidirectionnel est le plus souvent aléatoire car déterminé par des évènements déclenchés par les utilisateurs. Cette diversité de caractéristiques des trames de données permet d'appliquer pour la conception d'une architecture d'un système de communications, un modèle de tâches multi-trames ainsi que le procédé d'ordonnancement selon l'invention utilisant ce modèle. Un exemple d'une architecture de système temps-réel pour lequel l'invention s'applique est illustré à la figure 4. Un système de communication temps-réel entre plusieurs utilisateurs A,B,C,D est représenté comportant 3 processeurs Po,P1,P2. On s'intéresse à l'ordonnancement des tâches exécutées sur le processeur Po. Ce dernier exécute un ensemble de tâches 41,42,43,44 associées à des fonctions élémentaires d'une chaine de réception de données émises par les utilisateurs C et D par l'intermédiaire d'une application 402 vers les utilisateurs A et B. La chaine de réception composée des tâches 41,42,43,44 reçoit des paquets de données dans un ordre aléatoire, la réception de ces paquets déclenche des appels successifs aux tâches de réception 41,42,43,44 qui exécutent, par exemple, des traitements de démodulation et/ou de décodage canal des données avant de les transmettre à l'application réceptrice 401. En parallèle de cette première chaine de transmission, une chaine d'émission est également implémentée sur le processeur Po pour permettre aux utilisateurs A et B de communiquer à leur tour avec les utilisateurs C et D. Un ensemble de tâches 45,46,47,48 exécutent des traitements permettant de mettre en forme les données à émettre, par exemple une fonction de modulation de données ou de codage canal. Les tâches 45,46,47,48 composant la chaîne d'émission sont exécutées de façon indépendantes et asynchrones aux tâches 41,42,43,44 de la chaine de réception. De même un lien de signalisation permet de transmettre des informations relatives au contrôle et à la mise en oeuvre des moyens d'émission/réception. Ce lien est implémenté entre deux applications 405,406 et fait intervenir l'exécution de deux tâches 49,50 sur le processeur Po. Le procédé selon l'invention s'applique à ce type de système temps-réel puisque chaque tâche est multi-trames et est exécutée dans un ordre non 25 prédictible du point de vue du processeur Po sur lequel elles s'exécutent. Un autre cas d'application pour lequel l'invention s'applique est le cas où une tâche exécute un traitement sur un seul type de trame de données, mais le processeur sur lequel s'exécute cette tâche possède la capacité de 30 moduler sa consommation, par exemple en faisant varier sa fréquence d'exécution. Dans ce cas, si plusieurs modes de consommation sont disponibles, le temps d'exécution d'une même trame de données sera différent pour chacun de ces modes. Le passage d'un mode de consommation à un autre peut être effectué au cours du temps de façon non prédictible, notamment en fonction de contraintes liées au système. Le procédé selon l'invention décrit précédemment s'applique bien dans ce cas de figure puisqu'on est en présence d'une ou plusieurs tâches logicielles qui exécute un traitement sur une trame de données dont le temps d'exécution, notamment, va varier au cours du temps en fonction du mode de consommation du processeur. La conception d'un tel système peut être validée et son exécution temps réelle garantie à l'aide de l'invention. De façon générale, l'invention s'applique à tout ensemble de tâches logicielles concurrentes provenant de sources différentes et exécutant dans un ordre non prédictible un traitement sur un ensemble de trames de données dont les temps d'exécution, d'échéance et les temps de garde sont variables. L'invention présente notamment l'avantage de permettre la validation des choix de conception d'une application ou d'un système temps-réel et de garantir la faisabilité de l'exécution de ce système dans les contraintes de délai auquel il est soumis. En particulier l'invention permet de garantir le bon fonctionnement d'un ordonnanceur à priorité dynamique tel qu'un ordonnanceur exécutant la méthode EDF et en particulier de garantir que le système ne sera jamais surchargé, c'est-à-dire que son taux d'utilisation ne sera jamais supérieur à 100%. Références [1] A.K.Mok et D.Chen. A multiframe model for real time tasks. Proceedings of IEEE International Realtime System Symposium, pages 22-29,December 1996. [2] S. Baruah,D.Chen,S.Gorinsky,A.Mok. Generalized multiframe tasks. 1996. REVENDICATIONS1. Procédé d'ordonnancement temps-réel d'une application exécutée sur au moins un processeur, la dite application étant composée d'une pluralité m de tâches logicielles exécutant au moins un traitement sur une pluralité N de trames de données successives, chacune desdites tâches i étant définies au moins, pour chacune desdites trames j, par un temps d'exécution C iJ , une échéance d'exécution Di , et un temps de garde Pi vis-à-vis de la trame j+1 suivante, ledit temps de garde Fi étant supérieur ou égal à ladite échéance D i , ledit procédé étant caractérisé en ce qu'il comprend au moins les étapes suivantes: Ci' o Pour chaque tâche i, calculer les rapports D i entre le temps d'exécution CiJ de chaque trame j et la deadline correspondante D iJ , o Pour chaque tâche i, rechercher le maximum sur l'ensemble C ,� D' m- o Comparer la somme max (` ) sur toutes lesdites 0 2. Procédé d'ordonnancement selon la revendication 1 caractérisé en ce qu'il comprend en plus les étapes suivantes : m-1 C ' o Si ladite somme E omaN 1( `;) est inférieure ou égale au t=o nombre p de processeurs, associer une priorité dynamique ~o d'exécution à la tâche i en fonction de son échéance d'exécution Di) de façon à ce qu'à un instant donné, la tâche qui possède la priorité la plus élevée est celle dont l'échéance Di J est la plus proche temporellement, m-1 C l o Si ladite somme omaN 1(D `,) est strictement supérieure 15 au nombre p de processeurs, rejeter la tâche i et/ou redéfinir ses paramètres de temps d'exécution C iJ et d'échéance d'exécution Dis de façon à satisfaire l'inégalité mù1 C max ( )p. i=00 3. Procédé d'ordonnancement selon l'une des revendications 1 à 2 caractérisé en ce que lesdites trames de données sont séquencées dans un ordre aléatoire et sans respecter un motif temporel cyclique.5 4. Procédé d'ordonnancement selon l'une des revendications 1 à 3 caractérisé en ce que lesdites tâches exécutent sur lesdites trames de données des fonctions de traitement de signal et que lesdits processeurs sont des processeurs numériques de signal (DSP). 5. Procédé d'ordonnancement selon l'une des revendications 1 à 4 caractérisé en ce qu'un seul processeur à fréquence variable est utilisé et que ledit procédé comporte en plus les étapes suivantes : in-1 C o Si l'inégalité suivante E ~max 1( `) 1 n'est pas i=0 DI respectée alors multiplier par un facteur Ô au moins égal à m-1 CJ E omax 1(D) la fréquence dudit processeur, o Si ladite fréquence multipliée par ledit facteur 8 est inférieure ou égale à la fréquence maximale de fonctionnement dudit processeur alors associer une priorité dynamique d'exécution à la tâche i en fonction de son échéance d'exécution Di' de façon à ce qu'à un instant donné, la tâche qui possède la priorité la plus élevée est celle dont l'échéance D l~ est la plus proche temporellement, o Si ladite fréquence multipliée par ledit facteur 8 est supérieure 20 à la fréquence maximale de fonctionnement dudit processeur alors rejeter la tâche i et/ou redéfinir ses paramètres de temps d'exécution Cl' et d'échéance d'exécution DiJ de façon à m-1 C J satisfaire l'inégalité E max ( ) 6. Dispositif d'ordonnancement (501) pour une application temps-réelle (503,504) exécutée sur au moins un processeur à fréquence de fonctionnement fixe ou variable, la dite application étant composée d'une pluralité m de tâches logicielles exécutant au moins une fonction sur une pluralité N de trames de données successives, ledit dispositif (501) étant caractérisé en ce qu'il comporte des moyens pour mettre en oeuvre le procédé d'ordonnancement selon l'une des revendications 1 à 5.10