SÛRETÉ TEMPORELLE

Introduction

Nous nous intéressons à la sûreté temporelle dans les systèmes temps réel multiprocesseurs. Nous devons donc définir précisément en quoi consiste cette sûreté temporelle. Tout d’abord, nous rappelons que les tâches temps réel sont des tâches contraintes par leurs échéances temporelles et que la validité du résultat calculé par une tâche dépend du respect de cette échéance. Pour pouvoir analyser l’ordonnancement d’un ensemble de tâches, il est nécessaire de connaître certains paramètres. Les deux principaux paramètres connus sont le WCET et la période. Nous définissons alors la sûreté temporelle de la manière suivante : Définition 2.1 (Sûreté temporelle). Soit un algorithme d’ordonnancement A respectivement à un modèle de tâche donnée. La sûreté temporelle associée à un intervalle de variations I est la propriété pour A de pouvoir garantir le respect des échéances lorsque les paramètres temporels des tâches subissent des variations comprises dans I. Une des propriétés de la sûreté temporelle est la capacité qu’a un algorithme à tolérer des variations négatives sur les paramètres temporels des tâches. Nous parlons dans ce cas de robustesse temporelle. Définition 2.2 (Variation négative). Soit A un algorithme d’ordonnancement. Soit τ un ensemble de tâches ordonnançable avec A. Une variation négative sur un paramètre temporel d’une tâche de τ est une variation qui rend τ « plus difficilement ordonnançable » avec A. Une variation négative pour une tâche τi peut donc être l’augmentation de son WCET Ci ou une diminution de sa période Ti . Pour illustrer ce que nous entendons par « plus difficilement ordonnançable », considérons les deux tâches suivantes ordonnancées en FTP : – τ1 (C1 = 2, T1 = 4) est la plus prioritaire.

Terminologie et notations

Nous notons J k i un ensemble de k instances de la tâche τi J k i = {Ji,1, . . . , Ji,k}. Nous notons également Ji(p) l’ensemble des p instances les plus prioritaires Ji(p) = {Ji,1, . . . , Ji,p} avec p < k et p, k ∈ N. Pour rappel, nous notons Ji une instance de la tâche τi . Cette instance est caractérisée par le triplet (ri , ei , di) où ri est l’instant de son activation, ei est sa durée d’exécution et di son échéance absolue. Nous notons J + i une instance de la tâche τi caractérisée par (ri , e+ i , di) où e + i est la durée d’exécution le plus grand parmi toutes les instances de la tâche τi . De la même manière, nous notons J − i une instance de la tâche τi caractérisée par (ri , e− i , di) où e − i est la durée d’exécution le plus petit. Ainsi, nous notons J + i (p) l’ensemble {J + i,1 , . . . , J + i,p} et J − i (p) l’ensemble {J − i,1 , . . . , J − i,p}. Nous notons l’instant où démarre l’instance la moins prioritaire de J k i par S(J k i ). De la même manière, nous notons l’instant où termine l’instance la moins prioritaire de J k i par F(J k i ). L’ensemble de ces notations est résumé dans la table 2.1. 19 CHAPITRE 2. SÛRETÉ TEMPORELLE Notation Définition πj Le processeur d’indice j τ Un ensemble de tâches τ (πj ) L’ensemble des tâches allouées sur le processeur πj τi La tâche d’indice i Ci Le WCET de τi Di L’échéance relative de τi U(τ ) L’utilisation processeur de l’ensemble de tâches τ J k i Un ensemble de k instances de τi Ji Une instance de τi J(p) L’ensemble des p premières instances de plus haute priorité ri L’instant d’activation d’une instance Ji ei La durée d’exécution d’une instance Ji (ei ≤ Di) e + i La durée d’exécution maximale d’une instance Ji e − i La durée d’exécution minimale d’une instance Ji di L’échéance absolue d’une instance Ji J + i (p) L’ensemble des p premières instances ayant une durée d’exécution maximale J − i (p) L’ensemble des p premières instances ayant une durée d’exécution minimale S(J) L’instant où démarre l’instance la moins prioritaire de J F(J) L’instant où termine l’instance la moins prioritaire de J processeur πj hp(i) L’ensemble des tâches plus prioritaires que τi lp(i) L’ensemble des tâches moins prioritaires que τi Wi Le temps de réponse pire cas de la tâche τi TABLE 2.1 – Notations employées dans le chapitre 2.

Augmentation des paramètres temporels

La notion de tolérance aux variations négatives des paramètres temporels a été récemment abordée par Davis et Burns [DB07]. Ils se sont intéressés à proposer une assignation des priorités qui maximise la tolérance aux variations négatives de WCET dans le cas d’un algorithme d’ordonnancement FTP. En effet, les tâches temps réel peuvent être sujettes à des interférences additionnelles qui peuvent être dues : – aux interruptions matérielles ; – aux latences du système d’exploitation temps réel qui seraient mal spécifiées ou inconnues ; – à une mauvaise estimation des WCET ; – à du temps de calcul qui serait détourné par des contrôleurs de périphériques ; – à des erreurs se produisant à une fréquence non prévisible, causant ainsi la réexécution d’instructions de code différentes. Dans cette section, nous présentons des travaux dont la synthèse est faite par George dans [Geo08]. Nous rappelons ces solutions algorithmiques qui permettent de calculer les variations négatives pouvant être tolérées par un algorithme d’ordonnancement  Nous avons défini ces variations négatives comme étant l’augmentation de WCET ou la réduction de période.