Systèmes temps réel

Représentation des systèmes temps réel

Nous distinguons entre le temps réel strict et le temps réel souple. Pour un système temps réel strict*, aucun dépassement d’échéance n’est toléré. Il s’agit là des systèmes critiques pour lesquels une défaillance peut avoir des conséquences graves. Dans un système temps réel souple*, le dépassement de certaines contraintes temporelles est acceptable dans la mesure où la qualité du service fourni par l’application est correcte. Cette qualité de service peut par exemple s’exprimer par une borne maximale sur le dépassement des échéances [LA10]. Il s’agit des systèmes de visioconférence, ou encore de jeux en réseau. Comme nous l’avons introduit dans la section 1.1, nous nous focalisons sur l’étude des systèmes temps réel stricts. Lorsqu’on étudie l’ordonnancement d’un système temps réel, il est primordial de spécifier les hypothèses qui sont faites sur ce système. Notamment, il convient de spécifier les modèles considérés car l’analyse du système dépend de ces modèles. Il existe différents modèles de tâches, ainsi que différents modèles de plates-formes multiprocesseurs. Nous présentons ici les modèles couramment rencontrés dans la littérature en précisant ceux que nous considérons dans ce manuscrit. 

Modèles de tâches Modèle d’activation

L’analyse d’un système temps réel implique la connaissance du modèle d’activation des tâches. Trois modèles sont couramment rencontrés dans la littérature. Le premier est celui des tâches apériodiques. Une tâche apériodique est une tâche pour laquelle la période d’activation n’est pas connue. Il est donc difficile d’analyser de manière stricte un système composé de ce type de tâches sans faire d’hypothèse sur la probabilité de leur arrivée. Les deux autres modèles d’arrivée sont respectivement ceux des tâches  sporadiques* et des tâches périodiques*. La durée séparant deux activations d’une tâche τi est appelée période* dans le cas où τi est une tâche périodique. Dans le cas où τi est une tâche sporadique, la durée séparant deux activations n’est pas fixe. Néanmoins, la période minimale entre deux activations est connue, ce qui permet de pouvoir analyser ces tâches dans le pire cas. Cette période d’inter-arrivé minimale* est, par souci d’homogénéité avec le modèle périodique, couramment appelée période. La période d’une tâche τi constitue un de ses paramètres temporels et nous la notons Ti . Nous portons notre attention sur l’étude des tâches sporadiques et des tâches périodiques. Le lecteur intéressé par la gestion des tâches apériodiques dans les systèmes temps réel pourra toutefois se reporter entre autres à la thèse de Masson [Mas08]. Instance Une tâche périodique (ou sporadique) correspond à l’exécution d’un ensemble d’instructions qui se répète. Afin de distinguer les différentes occurrences d’une même tâche, nous employons le terme d’instance* d’une tâche (aussi appelée requête). Nous notons Ji,k la k ième instance de la tâche τi en commençant la numérotation à 1. Ainsi, la première instance de la tâche τ1 est donc notée J1,1. Lorsque nous faisons référence à une instance quelconque de la tâche τi , nous notons celle-ci Ji . Instant d’activation L’instant d’activation* d’une tâche est l’instant auquel une instance de cette tâche est prête à être ordonnancée. L’instant d’activation d’une tâche correspond à un décalage par rapport à une origine des temps fixée à l’instant t = 0. L’instant d’activation d’une instance est appelé release time dans la littérature anglophone. Nous notons par conséquent cet instant d’activation ri,k pour l’instance Ji,k et ri pour une instance quelconque Ji . Nous notons Oi l’instant d’activation de la première instance de la tâche τi . Dans le cas d’une tâche périodique, l’instant ri,k est défini par ri,k = Oi + (k − 1)Ti . Échéance L’échéance* d’une tâche temps réel est l’instant auquel cette tâche doit avoir terminé son exécution. C’est un paramètre commun à toutes les tâches temps réel, quel que soit le modèle considéré. Une tâche τi est caractérisée par son échéance relative*, qui correspond, pour toute instance Ji,k de τi , à une durée constante entre sa date d’activation ri,k et la date à laquelle son exécution doit être terminée. Nous notons Di l’échéance relative d’une tâche τi . L’échéance absolue* de Ji,k, que nous notons di,k, correspond à la durée entre l’instant 0 et l’instant où cette instance doit être terminée. Nous notons également di l’échéance absolue d’une instance quelconque Ji . Dans le cas d’une tâche périodique, l’instant di,k est défini par di,k = 0i + (k − 1)Ti + Di . Pour les tâches sporadiques ou les tâches périodiques, on différencie les modèles de tâches grâce à laelation entre l’échéance et la période. Les trois principaux modèles référencés dans la littérature sont : – les tâches à échéances implicites* (ou à échéances sur requêtes) pour lesquelles Di = Ti , pour toute tâche τi , comme étudiées dans [LL73] ; – les tâches à échéan-ces contraintes* pour lesquelles Di ≤ Ti , pour toute tâche τi , comme étudiées dans [Mok83] ; – les tâches à échéances arbitraires* pour lesquelles l’échéance Di n’est plus contrainte par la période Ti . Dans ce manuscrit, nous concentrons notre attention sur l’étude des ensembles de tâches à échéances contraintes. Avec ce modèle de tâche, il est possible de représenter la majeure partie des applications. De plus, les tâches à échéances arbitraires sont plus complexes à analyser. Il convient de noter que les tâches à échéances contraintes incluent les tâches à échéances implicites. Durée d’exécution Une tâche temps réel τi est caractérisée par sa durée d’exécution pire cas (Worst Case Execution Time) (WCET). Il s’agit de la plus longue durée pendant laquelle une instance de τi peut s’exécuter. En effet, l’une des motivations majeures de l’étude des systèmes temps réel est de garantir que toutes les tâches respectent leur échéance. Il est donc nécessaire de connaître quelle sera la pire durée d’exécution des tâches. Pour cela, toutes les tâches sont étudiées indépendamment. Leur WCET est estimé soit en les exécutant un grand nombre de fois (analyse dynamique), soit par étude du code (analyse statique) [CP01]. Nous notons Ci le WCET de la tâche τi . Nous notons également ei,k la durée d’exécution de l’instance Ji,k et ei la durée d’exécution d’une instance Ji . Cette notation nous permet de distinguer deux instances avec des durées d’exécution différentes. Notations Dans ce manuscrit, nous considérons les ensembles de tâches périodiques et les ensembles de tâches sporadiques. Une tâche τi sera alors caractérisée par le quadruplet (Oi , Ci , Di , Ti), où : – Oi correspond à l’instant d’activation de la première instance de la tâche τi par rapport à l’instant 0 ; – Ci correspond au WCET de la tâche τi ; – Di correspond à l’échéance relative de la tâche τi ; – Ti correspond à la période de la tâche τi . De la même manière, l’instance Ji,k de la tâche τi sera caractérisée par le triplet (ri,k, ei,k, di,k), où : – ri,k correspond à l’instant d’activation de l’instance Ji,k ,  – ei,k correspond au coût d’exécution de l’instance Ji,k , – di,k correspond à l’échéance absolue de l’instance Ji,k. Lorsque nous faisons référence à une instance quelconque de la tâche τi , nous employons la notation Ji caractérisée par le triplet (ri , ei , di). Définition 1.6 (Utilisation d’une tâche). L’utilisation Ui d’une tâche τi représente la fraction du temps processeur nécessaire pour pouvoir exécuter τi dans le pire cas et est définie par : Ui = Ci Ti Par exemple, une tâche caractérisée par (Oi = 0, Ci = 2, Di = 6, Ti = 10) a une utilisation de 0.2. En effet, elle nécessite dans le pire cas 20% de la capacité de calcul d’un processeur pour pouvoir être exécutée. Définition 1.7 (Utilisation d’un ensemble de tâches). L’utilisation U(τ ) d’un ensemble de tâches τ représente la capacité de calcul nécessaire pour pouvoir exécuter τ dans le pire cas et est définie par : U(τ ) = Xn i=1 Ui Indépendance Une hypothèse souvent rencontrée dans la littérature est celle de l’indépendance des tâches. Cela signifie que les seules ressources pour lesquelles une tâche du système est en concurrence sont l’ensemble des processeurs en charge de l’exécuter. Pourtant, lorsque l’on considère une application réelle, il est fort probable que les différentes tâches qui la composent ne soient pas indépendantes. En effet, il peut exister des contraintes de précédences entre des tâches, c’est-à-dire qu’une tâche requiert qu’une autre ait terminé son exécution avant de commencer la sienne. L’application peut aussi nécessiter que des ressources (autres que les processeurs) soient partagées entre les différentes tâches. Dans ce manuscrit, nous considérons principalement des modèles de tâches indépendantes. Le problème du partage de ressource est toutefois abordé dans le chapitre 4.