Étude et évaluation des politiques d’ordonnancement temps réel multiprocesseur
Modélisation et vocabulaire
Dans cette première partie, le modèle de tâches temps réel le plus fréquemment employé dans le domaine est présenté. Il permettra ensuite d’asseoir l’exposé des politiques introduites dans la suite de ce chapitre. Quelques définitions relatives à l’ordonnancement sont formulées dans un second temps. Ceci permet également d’introduire le vocabulaire lié au domaine.
Modélisation des applications
Une application temps réel est constituée d’un ensemble de tâches (tasks). Une tâche contrôle le flot d’exécution d’un programme. Les instructions exécutées forment ce que l’on appelle un travail (job). Ainsi, une tâche, si elle est récurrente, donne lieu à une succession de travaux, parfois appelés les instances de la tâche. Les travaux d’une application temps réel doivent respecter un certain nombre de contraintes temporelles qui seront présentées par la suite. 7 8 Chapitre 1. Ordonnancement temps réel multiprocesseur Le modèle de tâches décrit ici a été initialement formulé par Liu et Layland [LL73]. Ce modèle permet de traiter le cas de tâches périodiques mais il a ensuite été généralisé aux tâches sporadiques [Mok83, LW82]. Notons cependant l’existence d’autres modèles tels que le modèle multiframe [MC96] et sa généralisation [BCGM99] qui tentent de prendre en considération les variations de durées d’exécution des tâches afin d’affiner les analyses d’ordonnançabilité, les transactions [Tin94] qui introduisent des dépendances temporelles entre les tâches, le modèle de tâches récurrentes [Bar03] qui modélise explicitement les branchements conditionnels ou encore le modèle digraph [SEGY11] où le comportement des travaux est modélisé par un graphe acyclique. Nous ne considérerons pas ces modèles dans la suite car ils sont très peu traités par les algorithmes multiprocesseurs, nous nous focaliserons uniquement sur le modèle initial de Liu et Layland. a) Modélisation des travaux Soit un travail activé à l’instant a et devant se terminer avant l’instant d. Ce travail s’exécute pendant e unités de temps sur l’intervalle [a, d]. Ces grandeurs, représentées à travers un exemple par la figure 1.1, permettent de caractériser un travail par le triplet (a, e, d) : • a l’instant d’activation (release time) ; • e le temps d’exécution (computation time) ; • d l’échéance absolue (absolute deadline). On dit d’un travail qu’il est actif à l’instant t si les conditions suivantes sont réunies : • le travail est arrivé (a ≤ t) ; • l’échéance n’est pas dépassée (t < d) ; • le travail n’a pas fini son exécution. t 0 5 10 a d actif e Activation Ech ´ eance ´ Fin d’execution ´ Figure 1.1 – Schéma représentatif d’un travail et de ses paramètres. Certains modèles permettent à des travaux de s’exécuter en parallèle sur plusieurs processeurs dans le cas de programmation par multithreading. Nous prendrons ici pour hypothèse qu’un travail ne peut s’exécuter que sur un seul processeur à la fois. b) Modélisation des tâches L’activation d’une tâche engendre la création d’un travail dans l’état actif. La manière dont les travaux sont générés par une tâche permet de faire la distinction entre trois natures de tâches : • les tâches périodiques sont activées régulièrement à période fixe ; • les tâches sporadiques sont activées de manière irrégulière mais avec toutefois au moins une propriété sur la durée minimum entre l’arrivée de deux travaux consécutifs ; • les tâches apériodiques sont activées de manière irrégulière. Un système temps réel τ est constitué d’une ensemble fini de tâches : τ = {τ1, …, τn}. Chaque tâche τi étant constituée d’une suite infinie de travaux, on note : τi = {τi,1, τi,2, …} où τi,j est le jème travail de la tâche τi . Une tâche τi périodique ou sporadique est caractérisée par le quadruplet (Oi , Ci , Ti , Di) : • Oi , la date d’activation du premier travail de la tâche τi (0 si non précisé) ; • la durée d’exécution Ci dans le pire cas (Worst-Case Execution Time, WCET) de chaque travail de la tâche τi ; • sa période d’activation Ti . Dans le cas de tâches sporadiques, c’est la durée minimale entre ses activations successives ; • son échéance relative ou délai critique Di . C’est la durée entre l’arrivée d’un travail et son échéance (un travail qui arrive à l’instant t doit se terminer avant l’instant t+Di). Le taux d’utilisation d’une tâche correspond à la fraction de temps que la tâche consomme sur un processeur pour s’exécuter. Cette grandeur est très utilisée dans les tests d’ordonnançabilité, ainsi que la somme totale des taux d’utilisation ou encore le plus grand taux d’utilisation du système. Une tâche dont le taux d’utilisation est grand sera qualifiée de tâche lourde, et au contraire une tâche dont le taux d’utilisation est faible sera qualifiée de tâche légère. Le seuil à partir duquel une tâche est dite lourde ou légère dépend du contexte (généralement 0.5). • Taux d’utilisation d’une tâche τi : ui def = Ci Ti (1.1) • Utilisation totale du système : usum def = Xn i=1 ui (1.2) • Taux d’utilisation moyen d’un processeur : usum m , avec m le nombre de processeurs (1.3) • Plus grand taux d’utilisation du système : umax def = max{u1, …, un} (1.4) Une distinction importante entre les tâches est faite sur leur type d’échéance : 10 Chapitre 1. Ordonnancement temps réel multiprocesseur • si Di = Ti , on parle de tâche à échéance implicite ou échéance sur requête (Implicitdeadline) ; • si Di < Ti , on parle de tâche à échéance contrainte (Constrained-deadline) ; • sinon, on parle de tâche à échéance arbitraire (Arbitrary-deadline). Enfin, si les tâches démarrent au même instant (∀i, Oi = 0), on parle de système de tâches à départ simultané ou tâches synchrones (synchronous task system).
Introduction générale |
Télécharger le document complet
