FR2965947A1

FR2965947A1 - Procede et dispositif d'ordonnancement de taches semi-periodiques dans un systeme multitache temps reel

Info

Publication number: FR2965947A1
Application number: FR1058226A
Authority: FR
Inventors: Christian Valpard
Original assignee: Sagem Defense Securite SA
Current assignee: Safran Electronics and Defense SAS
Priority date: 2010-10-11
Filing date: 2010-10-11
Publication date: 2012-04-13
Anticipated expiration: 2030-10-11
Also published as: FR2965947B1; WO2012049082A1; EP2628079A1

Abstract

L'invention vise un procédé d'ordonnancement de tâches semi-périodiques. Ces tâches doivent respecter une séquence de lancements périodique. Pour chaque tâche est définie une période d'ordonnancement. Au sein de chaque période est déclarée la séquence des moments de lancement de la tâche. Ainsi, la tâche peut être lancée en respectant une séquence de lancements non périodique. Cette séquence étant, elle, répétée de manière périodique.

Description

La présente invention concerne le domaine des noyaux temps réel et plus particulièrement un procédé d'ordonnancement de tâches semi-périodiques dans un système multitâche temps réel. On s'intéresse en particulier aux systèmes permettant le lancement régulier de tâches. De tels systèmes sont basés sur une base de temps périodique. Lors de chaque période de la base de temps, le noyau détermine les tâches devant être lancées parmi les tâches déclarées dans le système. De tels environnements sont par exemple le domaine des logiciels embarqués dans les avions, les centrales nucléaires ou les systèmes militaires.

On appelle tâche, une fonction logicielle s'exécutant sur un processeur et typiquement constituée d'une succession de cycles de calcul. Une telle tâche est lancée lors d'une période particulière de la base de temps. Elle s'exécute ensuite sur le processeur du système pendant un certain nombre de périodes. Elle se termine ensuite. Le noyau temps réel est chargé de la relancer de manière régulière.

De tels noyaux temps réel sont généralement limités à un mécanisme permettant d'initialiser les tâches de manière périodique. Cette limitation entraîne que des tâches qui ne suivent pas strictement cette logique de lancement périodique vont devoir être, par exemple, dupliquées pour permettre leur gestion par un noyau d'ordonnancement purement périodique. Cette duplication entraîne une gestion dispendieuse des ressources et de la capacité de calcul du processeur du système. L'invention vise à résoudre les problèmes précédents par un procédé d'ordonnancement de tâches semi-périodiques. Ces tâches doivent respecter une séquence de lancements périodique. Pour chaque tâche est définie une période d'ordonnancement. Au sein de chaque période est déclarée la séquence des moments de lancement de la tâche. Ainsi, la tâche peut être lancée en respectant une séquence de lancements non périodique, cette séquence étant, elle, répétée de manière périodique. L'invention concerne un dispositif de traitement d'information temps réel, disposant de moyens d'ordonnancement d'au moins une tâche, le temps étant découpé de manière périodique pour définir une période d'ordonnancement, qui comporte des moyens pour définir pour chaque tâche une période de lancement constituée d'un nombre entier de périodes d'ordonnancement ; des moyens pour définir pour chaque tâche des périodes d'ordonnancement particulières au sein de la période de lancement durant lesquelles ladite tâche doit être lancée et des moyens pour déterminer, lors de chaque période d'ordonnancement, les tâches devant être lancées sachant que pour chaque tâche chaque séquence de lancements définie se répète de manière périodique. Selon un mode de réalisation particulier de l'invention, le dispositif comporte en outre des moyens de stocker une table contenant pour chaque tâche la durée de la période de lancement exprimée sous la forme d'un nombre entier de périodes d'ordonnancement et une liste des moments de lancement de la tâche exprimés sous la forme d'indexes des périodes d'ordonnancement lors desquelles la tâche doit être lancée au sein de la période de lancement. Selon un mode de réalisation particulier de l'invention, la valeur -1 affectée à 10 une période de lancement correspond à une période infinie permettant de gérer une tâche apériodique. L'invention concerne également un procédé d'ordonnancement d'au moins une tâche au sein d'un dispositif de traitement d'information temps réel, le temps étant découpé de manière périodique pour définir une période d'ordonnancement, qui 15 comporte une étape de définition pour chaque tâche d'une période de lancement constituée d'un nombre entier de périodes d'ordonnancement ; une étape de définition pour chaque tâche des périodes d'ordonnancement particulières au sein de la période de lancement durant lesquelles ladite tâche doit être lancée et lors de chaque période d'ordonnancement, une étape de détermination des tâches devant être lancées sachant 20 que pour chaque tâche chaque séquence de lancement définie se répète de manière périodique. Les caractéristiques de l'invention mentionnées ci-dessus, ainsi que d'autres, apparaîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation, ladite description étant faite en relation avec les dessins joints, parmi 25 lesquels : La Fig. 1 illustre l'ordonnancement d'un ensemble de tâches périodiques. La Fig. 2 illustre l'ordonnancement d'un exemple de tâche semi-périodique. Les systèmes multitâches temps réel sont utilisés dans nombre d'environnements où il est nécessaire de maîtriser le fonctionnement d'un système 30 d'information. Ils sont utilisés par exemple dans les domaines où la sécurité de fonctionnement du système est primordiale comme le pilotage de sites sensibles tels que les centrales nucléaires ou encore la gestion électronique d'un avion. Ces systèmes sont multitâches dans le sens où une pluralité de fonctions logicielles indépendantes s'exécute sur le même système. Ils sont temps réel, dans la mesure où les moments d'exécution de ces tâches sont connus. I1 dérive de ces contraintes que les tâches doivent avoir un temps d'exécution borné et ne doivent pas, même en cas de problème de programmation, pouvoir consommer les ressources du système hors des allocations qui ont été faites, ces ressources comprenant l'utilisation du processeur, des périphériques et aussi du temps. Les tâches utilisées dans ces systèmes ont donc une durée d'exécution maximale connue. Elles doivent typiquement être exécutées régulièrement. Exceptionnellement, certaines tâches spécifiques ont un fonctionnement permanent. Le fonctionnement de ces systèmes est basé sur une découpe périodique du temps. Cette découpe périodique définit donc une horloge de fonctionnement. Le temps entre deux tops de cette horloge est appelé ici un intervalle temporel (time slot en anglais). On s'intéresse ici à la détermination des moments de lancement des différentes tâches devant s'exécuter sur le système, c'est-à-dire à l'ordonnancement de ces tâches.

L'ordonnancement est basé sur une horloge d'ordonnancement périodique, l'intervalle temporel associé définit la période d'ordonnancement. Il est connu de définir pour chacune des tâches devant être exécutées dans le système une période de lancement. Cette période s'exprime généralement en un nombre entier de périodes d'ordonnancement. Cette période de lancement est choisie supérieure à la durée maximale connue d'exécution de la tâche. Le lancement de la tâche est alors déclenché lors d'une période d'ordonnancement et répété périodiquement lors des périodes d'ordonnancement correspondant à la période de lancement. Avantageusement, ces systèmes définissent également pour chaque tâche périodique un décalage (offset en anglais) qui est le nombre de périodes d'ordonnancement que l'on doit attendre au démarrage du système pour lancer la première occurrence de la tâche. La Fig. 1 illustre un tel système. L'horloge d'ordonnancement 1.1 est située en bas, douze périodes d'ordonnancement étant figurées. La Fig. 1 illustre les moments de lancement de trois tâches périodiques. La tâche TO possède un décalage de 0 et une période de 3. Elle est donc lancée aux périodes d'ordonnancement 0, 3, 6, 9 et 12. La tâche Tl possède un décalage de 1 et une période de 3. Elle est donc lancée aux périodes d'ordonnancement 1, 4, 7 et 10. La tâche T2 possède un décalage de 2 et une période de 4. Elle est donc lancée aux périodes d'ordonnancement 2, 6 et 10.

Le problème se pose de la gestion de tâches qui ne suivraient pas strictement un schéma de lancement périodique. On s'intéresse plus particulièrement à des tâches qualifiées de semi-périodiques. Concernant ces tâches, le lancement n'est pas périodique. Par contre, il est possible d'identifier une séquence de moments de lancement qui elle est périodique. Un exemple d'une telle tâche est illustré Fig. 2. La tâche TO doit être lancée aux périodes d'ordonnancement 0, 2, 6, 8 12, etc. I1 est possible de réaliser cet ordonnancement avec les systèmes connus. Il faut alors considérer qu'il y a deux tâches, TO et Tl auxquelles on affecte une période de 6 intervalles et un décalage de 0 pour la première et de deux pour la seconde. La tâche TO est donc lancée aux périodes d'ordonnancement 0, 6, 12, tandis que la tâche Tl est lancée aux périodes 2 et 8. L'ordonnancement d'une seule et même tâche consomme alors les ressources de deux tâches au sein du noyau temps réel. Pour permettre l'ordonnancement de telles tâches, l'invention se propose de définir pour chaque tâche une période de lancement. Cette période de lancement est le nombre de périodes d'ordonnancement qui permet d'avoir une séquence de lancement de la tâche qui se répète à l'identique. Pour la tâche illustrée à la Fig. 2, elle est typiquement de 6 périodes d'ordonnancement. Une fois cette période de lancement définie, il faut indiquer à quelle période d'ordonnancement la tâche doit être lancée.

On définit alors une liste des index, au sein de la séquence, des périodes d'ordonnancement auxquelles la tâche doit être lancée. Pour la tâche illustrée Fig. 2, il s'agit des index 1 et 3, signifiant que la tâche doit être lancée lors de la première période d'ordonnancement de la séquence et lors de la troisième. Avantageusement, ces informations sont mémorisées par le noyau temps réel au sein d'une table qui contient une entrée pour chaque tâche du système. Cette entrée est constituée au moins de l'indication de la période de lancement et de la liste des index des périodes d'ordonnancement auxquelles la tâche doit être lancée au sein de la période. Le noyau fonctionne alors en effectuant une étape de détermination des tâches devant être lancées lors de chaque période d'ordonnancement. Un exemple de réalisation de cette étape de détermination consiste à maintenir pour chaque tâche un compteur d'index de la période d'ordonnancement au sein de la séquence de lancement. Ce compteur est initialisé à 1 et s'incrémente lors de chaque tâche d'ordonnancement. Lorsque sa valeur est égale à la période plus un, on réinitialise le compteur à 1. Le compteur est comparé aux index de la liste associée à la tâche. Si l'index est compris dans la liste, on lance la tâche. Alternativement, on peut aussi calculer l'index directement par une division d'un index global croissant modulo la période de la tâche. Le reste de cette division donne l'index au sein de la séquence de lancement. Avantageusement, une tâche ayant une période négative ne sera jamais relancée. On peut ainsi gérer des tâches apériodiques, c'est-à-dire continues, en sus des tâches semi-périodiques dans le système. Avantageusement, la fin de la liste des index de lancement au sein de la 10 séquence est indiquée par une valeur nulle. Ce procédé d'ordonnancement permet de gérer les tâches semi-périodiques efficacement. Il ne nécessite qu'une entrée par tâche dans la table de gestion.

Claims

REVENDICATIONS1/ Dispositif de traitement d'information temps réel, disposant de moyens d'ordonnancement d'au moins une tâche, le temps étant découpé de manière périodique pour définir une période d'ordonnancement, caractérisé en ce qu'il comporte : - des moyens pour définir pour chaque tâche une période de lancement constituée d'un nombre entier de périodes d'ordonnancement ; - des moyens pour définir pour chaque tâche des périodes d'ordonnancement 10 particulières au sein de la période de lancement durant lesquelles ladite tâche doit être lancée ; - des moyens pour déterminer, lors de chaque période d'ordonnancement, les tâches devant être lancées sachant que pour chaque tâche chaque séquence de lancement définie se répète de manière périodique. 15 2/ Dispositif selon la revendication 1, caractérisé en ce qu'il comporte en outre des moyens de stocker une table contenant pour chaque tâche : - la durée de la période de lancement exprimée sous la forme d'un nombre entier de périodes d'ordonnancement ; 20 - une liste des moments de lancement de la tâche exprimés sous le forme d'un index de la période d'ordonnancement lors de laquelle la tâche doit être lancée au sein de la période de lancement. 3/ Dispositif selon la revendication 2, caractérisé en ce que la valeur -1 affectée 25 à une période de lancement corresponde à une période infinie permettant de gérer une tâche apériodique. 4/ Procédé d'ordonnancement d'au moins une tâche au sein d'un dispositif de traitement d'information temps réel, le temps étant découpé de manière périodique 30 pour définir une période d'ordonnancement, caractérisé en ce qu'il comporte les étapes suivantes : - une étape de définition pour chaque tâche d'une période de lancement constituée d'un nombre entier de périodes d'ordonnancement ;- une étape de définition pour chaque tâche des périodes d'ordonnancement particulières au sein de la période de lancement durant lesquelles ladite tâche doit être lancée ; - lors de chaque période d'ordonnancement, une étape de détermination des 5 tâches devant être lancées sachant que pour chaque tâche chaque séquence de lancement définie se répète de manière périodique.