Soutenance mémoire
Modèles de tâches
Nous détaillons maintenant les modèles de tâches les plus couramment utilisés dans le contexte de l’ordonnancement temps réel. Une tâche est une modélisation d’un processus informatique qui correspond à un programme à exécuter. Le modèle de tâches le plus élémentaire est le modèle périodique. Celui-ci permet de définir une tâche dont les instances sont activées à intervalles réguliers.
Définition 1 (Jeu de tâches) : Un jeu de tâches est un ensemble de tâches noté τ. Chaque tâche du jeu de tâches est ainsi notée τi où i va de 1 à n pour un système à n tâches.
Définition 2 (Instance de tâche) : Une instance de tâche est créée à chaque nouvelle activation de la tâche. C’est donc une succession d’instances de tâches qui sont exécutées par la machine.
Définition 3 (Activation d’une tâche) : L’activation d’une tâche génère une nouvelle instance de tâche qui sera ensuite exécutée en fonction de l’algorithme d’ordonnancement du système.
Définition 4 (Tâche concrète et tâche non concrète) : Une tâche concrète est une tâche dont l’instant de première activation de sa première instance est connu. Sinon, elle est dite non-concrète.
Définition 5 (Jeu de tâches synchrone) : Un jeu de tâches est dit synchrone s’il existe un instant dans la vie du système où toutes les tâches ont une instance activée en même temps.
Nous considérons dans cette thèse des tâches non concrètes (sauf dans le cas particulier du Chapitre 6 sur l’ordonnancement Dual Priority où les tâches sont supposées synchrones et concrètes).
Définition 6 (Tâche périodique) : Une tâche périodique τi(Ci, Ti, Di) est une tâche qui génère des instances de tâches dont : (i) la durée d’exécution pire cas Worst Case Execution Time (WCET) est notée Ci , l’interarrivée entre deux instances successives est égale à Ti et où Di est l’échéance relative associée à toute instance de la tâche τi. En exemple de tâche périodique, nous pouvons citer la lecture des données recueillies par un capteur. En effet, il est fréquent que ces données soient lues et traitées à intervalles réguliers.
Définition 7 (Tâche apériodique) : Une tâche apériodique est une tâche qui ne s’exécute qu’une fois pendant la durée de vie du système. Contrairement aux tâches périodiques, elle n’est donc définie que par sa durée d’exécution pire cas WCET et son échéance relative. Dans le cas d’une tâche concrète, sa date peut également être précisée.
Définition 8 (Tâche sporadique) : Une tâche sporadique, τi(Ci, Ti, Di), est une tâche pour laquelle, contrairement à la tâche périodique, Ti est une borne minimale sur l’inter-arrivée entre deux instances successives de la tâche. Les autres paramètres sont identiques au modèle périodique. Par définition, une tâche sporadique est forcément non concrète. Nous donnons maintenant des notations supplémentaires liés aux tâches périodiques ou sporadiques.
Définition 9 (Utilisation d’une tâche) : L’utilisation Ui de la tâche τi(Ci , Ti , Di) est définie par Ui = CiTi . Elle correspond à la charge induite par la tâche au processeur.
Définition 10 (Utilisation d’un jeu de tâches) : L’utilisation d’un jeu de tâches correspond à la somme des utilisations des tâches. Pour un jeu de tâches τ de n tâches, l’utilisation du jeu de tâches U se définit ainsi : U = ∑ Ui, ∀τi ∈ τ
La relation entre les échéances relatives des tâches et leur inter arrivée détermine le modèle d’échéance du jeu de tâches associé. Nous distinguons les modèles à échéance sur requête, à échéance contrainte et à échéance arbitraire.
Définition 11 (Échéance sur requête) : Un jeu de tâches est à échéance sur requête si pour toute tâche τi du jeu de tâches, Di = Ti.
Définition 12 (Échéance contrainte) : Un jeu de tâches est à échéance contrainte si pour toute tâche τi du jeu de tâches, Di ≤ Ti.
Définition 13 (Échéance arbitraire) : Un jeu de tâches est à échéance arbitraire s’il n’existe pas une relation imposée entre Ti et Di pour toutes les tâches (l’échéance d’une tâche peut être inférieure, égale ou supérieure à l’inter-arrivée de la tâche). Nous considérons dans cette thèse des jeux de tâches à échéances sur requête. Un des plus simples modèles que l’on retrouve dans la littérature de l’état de l’art est celui des tâches périodiques. Il a été initialement défini dans [117]. Les auteurs proposent une analyse du système en considérant des algorithmes d’ordonnancement qui seront vus dans la Section 2.1.3. Ce modèle impose que les tâches soient activées avec une inter-arrivée constante. Cette hypothèse est parfois trop contraignante et peut même s’avérer irréalisable pour certains systèmes qui réagissent à des événements externes au système. C’est pourquoi le modèle de tâche sporadique a été introduit [125]. Ce modèle reprend les mêmes paramètres que le modèle périodique, mais la période devient une période d’inter-arrivée minimale. Cela signifie que la tâche ne peut pas être réactivée avant un certain temps qui correspond à la période d’inter-arrivée minimale. Pour donner un exemple de tâche sporadique dans un système temps réel, nous pouvons prendre celui des entrées clavier. Si l’utilisateur appuie trop rapidement, les données ne sont plus prises en compte. En revanche, si l’utilisateur appuie avec un intervalle de temps minimum entre deux appuis, les données sont prises en compte. L’utilisateur peut également ne pas appuyer du tout. Le temps entre deux activations de la tâche n’est donc pas connu a priori. L’inter-arrivée est donc une borne inférieure sur les instants d’activation entre deux instances successives de la tâche, il n’y a pas de borne supérieure. La tâche peut ainsi ne jamais se réactiver comme être réactivée à la période d’inter-arrivée minimale suivante.Mais cette fois la tâche est sporadique : sa période devient donc une période d’inter-arrivée minimale. La flèche vers le haut en pointillés indique la période d’inter-arrivée minimale. Ici, la date de la deuxième activation se fait à la date 6, bien que sa période d’inter-arrivée minimale ne soit que de 5. La seconde échéance est ainsi retardée : au lieu de se faire à la date 9, elle se fait ainsi en 10 (seconde date d’activation = 6 + échéance = 4). Les modèles périodiques et sporadiques sont les modèles fondamentaux puisqu’ils sont utilisés la plupart du temps comme base pour les autres modèles. Cela est dû aux systèmes temps réels. En effet, la plupart des systèmes temps réels sont des systèmes embarquant un grand nombre de capteurs et d’actionneurs, il faut donc pouvoir traiter les informations reçues par les capteurs et agir à intervalles réguliers, ce qui génère donc des modèles périodiques et sporadiques. Nous présentons maintenant une première extension, le modèle périodique avec offset ([73]). Un offset s’applique au modèle de tâches concrètes, il consiste à décaler la date de première activation d’une tâche d’un délai fixé, défini en paramètre de la tâche. Grâce à l’offset, il devient, par exemple, possible de retarder la lecture d’un capteur de façon à empêcher la lecture dès le démarrage du système.
Définition 14 (Offset) : L’offset est un délai imposé pour la date de première activation d’une tâche par rapport à la date de démarrage du système. Ce délai retardera toutes les activations suivantes. La première activation d’une tâche périodique τi(Ci, Ti, Di) est ainsi faite à Oi, et les activations suivantes à Oi + k × Ti où k ∈ N. Une tâche périodique avec offset s’écrit ainsi : τi(Ci, Ti, Di, Oi) Un exemple est donné dans la Figure 2.3. Dans cet exemple, l’offset est fixé à 1. La première activation de la tâche ne se fait donc qu’à la date 1, et non plus dès le démarrage du système (à la date 0). Dans la Figure 2.3, la première instance de la tâche τi ne commence donc qu’à la date 1, et la suivante à 6. Son échéance est également décalée aux dates 5 et 10.
Définition 15 (Surcoût – Overhead) : Le surcoût est une borne sur le coût système supplémentaire ajouté à l’exécution d’une instance d’une tâche. Il peut intervenir à chaque début d’exécution de l’instance d’une tâche. Ce coût intègre un coût de changement du contexte de l’instance lorsqu’elle est sélectionnée pour être exécutée, auquel s’ajoute un coût de préemption maximum pour l’instance. Le coût de préemption maximum est égal à la somme des coûts de préemption liés aux instances des tâches plus prioritaires qui s’activent pendant la période d’activation de l’instance. Dans cette thèse, nous ne prenons pas en compte les surcoûts des tâches, ils sont supposés être intégrés aux WCETs des tâches. En revanche, cette notion de surcoût sera par contre prise en compte dans le Chapitre 4, dans le contexte de l’activation de Virtual Machine (VM) par un hyperviseur temps réel. Maintenant que nous avons vu ce que nous cherchons à ordonnancer, à savoir les tâches, nous décrivons les différents modèles d’architectures en charge de les exécuter.
Algorithmes d’ordonnancement à priorité dynamique
Un exemple d’algorithme à priorité dynamique, parmi les plus standards est le Least Laxity First (LLF) ([49], [125], [127], [86], [83]). Pour calculer la priorité à chaque instant, cet algorithme utilise le slack, ou la laxité. Cela correspond pour une instance de tâche τi activée à l’instant ti , au temps restant avant la prochaine échéance absolue de l’instance de la tâche à l’instant t moins la durée d’exécution de l’instance de tâche restante. La laxité à l’instant t, Li(t) d’une instance de tâche τi se calcule ainsi : Li(t) = ti + Di − t − Cremi Où ti + Di est l’échéance absolue de la tâche τi , t correspond à l’instant où l’ordonnanceur est appelé, et C remi est le temps d’exécution restant de la tâche τi à l’instant t. Avec cet algorithme d’ordonnancement, l’instance de tâche avec la plus petite laxité Li est celle qui sera ordonnancée. Comme pour EDF, en cas d’égalité, une règle fixe sera utilisée. Une bonne façon de procéder est encore une fois, en cas d’égalité, de continuer l’exécution de l’instance de tâche qui était précédemment exécutée, plutôt que d’exécuter une instance de tâche totalement aléatoire. Ainsi, la priorité d’une instance de tâche peut changer à chaque instant.
Optimalité :
• LLF est optimal en contexte préemptif pour l’ordonnancement de tâches périodiques ou sporadiques à échéances arbitraires. Une condition d’ordonnançabilité pour des tâches périodiques ou sporadiques à échéance sur requête est que l’utilisation du jeu de tâches soit inférieure à 100% (U ≤ 1). Un exemple est donné dans la Figure 2.7. Au niveau de l’exécution, cet algorithme d’ordonnancement ressemble à EDF : la première différence, se fait à partir de l’unité de temps 16. En effet, cette fois la tâche τ2 ne continue pas son exécution et celle-ci est interrompue par τ1. Nous montrons, via la Table 2.1, les valeurs de laxité des différentes tâches à partir de l’unité de temps 16, soit à partir du moment où LLF diffère de EDF. Comme indiqué, à partir de l’unité de temps 16, la laxité de τ1 passe à 2, alors que la laxité de la tâche τ2 est de 3, celle-ci ayant déjà été exécutée une fois et n’ayant plus qu’une unité de temps à exécuter (20 − 16 − 1). La tâche τ1 devient alors plus prioritaire et préempte la tâche τ2. À l’unité de temps 17, les trois tâches peuvent être exécutées, celles-ci ayant une laxité de 2. Ici, la tâche τ1 ayant déjà commencé son exécution, il est alors plus judicieux de la laisser continuer pour qu’elle puisse se terminer. Les préemptions sont ainsi minimisées. Un des principaux inconvénients de LLF est qu’il conduit à un grand nombre de préemptions lorsque deux tâches ont la même laxité à un instant donné, ce qui le rend peu compatible avec un ordonnancement de VMs étant donné le coût des changements de contexte dans ce cas. Nous présentons maintenant un dernier algorithme à priorité dynamique : P-fair ([23]). Cet algorithme est dans un premier temps théorique : il définit un ordonnancement fluide pour les tâches en utilisant un quantum de temps minimum infiniment petit. Ainsi, en une seule unité de temps classique, toutes les tâches peuvent avoir été exécutées pendant une proportion de cette unité de temps en fonction de leur utilisation. Dans cette thèse, une implémentation en-ligne pour un ordonnancement en temps discret sera ensuite proposée, basée sur le concept de lag. Le lag est le retard qu’a pris une instance de tâche en raison de l’ordonnancement en temps discret des instances des tâches. L’objectif de P-Fair est de minimiser le lag des instances des tâches pour reproduire le plus possible un ordonnancement fluide. Cet algorithme sera plus détaillé dans le Chapitre 5 où nous proposons une adaptation hors-ligne de cet algorithme pour construire la table d’ordonnancement de VMs non harmoniques.
Optimalité :
• P-Fair est optimal en contexte préemptif pour l’ordonnancement multi-processeurs (processeurs identiques) pour des tâches périodiques ou sporadiques à échéances sur requête. Une condition d’ordonnançabilité pour des tâches périodiques ou sporadiques à échéances sur requête est que l’utilisation du jeu de tâches soit inférieure à m (nombre de processeurs : U ≤ m) et que sur chaque processeur l’utilisation des tâches affectées au processeur soit inférieure ou égale à 1. Nous avons maintenant vu les bases essentielles pour l’ordonnancement temps réel. Mais il nous reste à voir ce qu’il en est des systèmes réels, utilisables dans l’industrie.
Modèle avec serveur au premier niveau
Ce premier modèle est plus ancien, et ne concerne pas uniquement des modèles hypervisés. Ce type de modèle peut être utilisé plus largement, sans la nécessité de machine virtuelle. En effet, dans ce modèle, il s’agit de serveurs pour le premier niveau d’ordonnancement. Les serveurs, sont malgré tout, similaires à des machines virtuelles : ils contiennent des tâches à ordonnancer et sont ordonnancés selon des algorithmes d’ordonnancement, mais ceux-ci sont tous exécutés sur le même OS ou, dans ce cas précis RTOS. La principale différence est que le type de serveur va définir comment celui-ci est ordonnancé mais également comment celui-ci va ordonnancer les tâches. Ainsi, ce sont les serveurs qui définissent tout l’ordonnancement : ils s’ordonnancent selon certaines règles pré-définies, que ce soit les serveurs eux-mêmes ou les tâches au sein des serveurs. Un tel type de système est souvent utilisé pour ordonnancer différents types d’applications qui sont alors liées aux serveurs. Cela permet d’avoir des applications temps réel, et des applications non temps réel sur le même système, ce qui, à l’époque de leur étude, était un premier pas pour des systèmes plus ouverts. Les premiers articles utilisant de tels systèmes parlaient alors de « systèmes ouverts », puisque plusieurs types d’applications pouvaient alors être ordonnancées en concurrence dans les différents serveurs. Un autre avantage des serveurs est de pouvoir garantir le respect des échéances des applications au sein de chaque serveur, serveur par serveur. Les serveurs avaient déjà été utilisés pour d’autres objectifs : ordonnancer des tâches apériodiques au mieux. Cela se faisait aux moyens de serveurs de tâches apériodiques ou bien de serveurs « polling » ([72] et [48]). Dans un tel système, il existait donc deux types d’éléments : des tâches temps réel périodiques et un serveur. Le serveur est donc en charge d’exécuter les tâches apériodiques. Pour le serveur de tâches apériodiques, une première proposition était de l’utiliser en tant que serveur exécuté en tâche de fond. Cela signifie que si le serveur est considéré comme une tâche, il a alors un WCET infini, une période infinie et une priorité minimale par rapport à toutes les autres tâches. Ainsi, il est exécuté dès que les tâches temps réel ont terminé leur exécution et donc dès que le système est censé être inactif. Son fonctionnement est ainsi très simple : les tâches apériodiques à exécuter sont contenues dans une liste et chaque tâche apériodique est traitée dans, par exemple, l’ordre d’arrivée, ou selon des priorités si ces tâches en ont. Ce choix dépendra de l’implémentation choisie et des tâches apériodiques du système. Une autre implémentation proposée dans ce même papier est le serveur « polling ». Cette fois, le serveur est considéré comme une tâche temps réel périodique avec une échéance égale à la période. L’équivalent de son WCET est un budget de temps d’exécution. Ainsi, à chaque nouvelle période, ce budget est entièrement rechargé. Le serveur ne peut s’exécuter qu’une seule fois par période. Lors de son exécution, il va exécuter les différentes tâches apériodiques, selon son budget de temps d’exécution restant. En revanche, si son budget arrive à 0, peu importe si les tâches apériodiques ont terminé leur exécution ou non, elles devront alors attendre la prochaine exécution du serveur. Si aucune tâche apériodique n’est présente lors de l’exécution du serveur, celui-ci met automatiquement son budget à 0 pour se recharger à la prochaine période. Il faut également savoir que ces deux serveurs étaient proposés dans un contexte où l’algorithme d’ordonnancement pour les tâches (et donc le serveur) ne pouvait être que EDF. Cette contrainte étant forte, puisqu’à l’époque peu d’OSs ou RTOSs proposaient l’algorithme d’ordonnancement EDF, de nouvelles propositions utilisant comme algorithme d’ordonnancement RM ont été faites. De plus, cette fois, le système peut fonctionner avec plusieurs serveurs et non plus un seul, créant un modèle hiérarchique à deux niveaux ([103]). Ce papier définit les serveurs sporadiques déjà définis dans la thèse [151] en plus de tests d’ordonnançabilité pour des applications temps réel ordonnancées dans des serveurs ordonnancés via EDF et RM. Comme indiqué dans le nom, au départ, les serveurs sporadiques étaient utilisés pour gérer les tâches sporadiques d’un système. Ce fonctionnement a ensuite été détourné pour exécuter des tâches périodiques ou sporadiques. Le fonctionnement du serveur sporadique requiert une priorité, qui dépend de sa période. L’algorithme d’ordonnancement utilisé est RM pour les serveurs, et un budget de temps d’exécution, comme pour le serveur « polling ». Cette fois-ci, en revanche, ce budget se recharge quand le serveur est inactif ou que son budget passe à 0. Le budget se recharge alors du montant de la tâche à exécuter par le serveur. Ainsi, il ne manque jamais de budget pour exécuter les tâches qui lui sont attribuées. Avec un tel modèle, une nouvelle question est soulevée : «comment déterminer les paramètres des serveurs (que ce soit la période ou leur budget) pour que les applications aux seins des serveurs soient ordonnançables ?». Pour répondre à cette question, de nombreux algorithmes ont été proposés ([2], [153], [111] et [72]). Dans ce contexte, le serveur utilisé est un serveur périodique. Ce serveur peut être vu comme une tâche temps réel classique avec période, et comme équivalent du WCET, une quantité de temps d’exécution. Ainsi, le serveur est ordonnancé exactement comme une tâche temps réel, et ira lui-même ordonnancer les tâches temps réel contenues par le serveur pour que l’application soit exécutée.
|
Table des matières
1 Introduction
1.1 Problématique
1.2 Projet CEOS
1.3 Organisation
2 État de l’art
2.1 Modèles pour le temps réel
2.1.1 Modèles de tâches
2.1.2 Modèles d’architecture matérielle
2.1.3 Modèles d’algorithme d’ordonnancement
2.2 Algorithmes d’ordonnancement
2.2.1 Algorithmes d’ordonnancement à priorité fixe au niveau des tâches
2.2.2 Algorithmes d’ordonnancement à priorité fixe au niveau des
instances
2.2.3 Algorithmes d’ordonnancement à priorité dynamique
2.3 Implémentation de systèmes temps réel
2.3.1 Système d’exploitation temps réel
Définition
Normes
Certifications
Exemples de systèmes d’exploitation
2.3.2 Virtualisation
Définition
Temps réel et hypervision
Certifications
Exemples d’hyperviseurs
2.4 Modèle d’ordonnancement hiérarchique à deux niveaux
2.4.1 Modèle avec serveur au premier niveau
2.4.2 Modèle sans serveur dit arbitraire
2.5 Criticité
2.5.1 Notre approche à criticité multiple
2.6 Dual Priority
2.7 Résumé des modèles et notations utilisées
3 Ordonnançabilité des tâches dans une VM hypervisée : comment définir l’ordonnaçabilité des tâches dans une hiérarchie à deux niveaux ?
3.1 Contexte
3.2 Concept de candidats d’instant critique
3.3 Temps de réponse pire cas de VMs strictement périodiques
3.4 Temps de réponse pire cas dans le cas général
3.5 Conditions d’ordonnançabilité
4 Ordonnancement de VMs hypervisées harmoniques : comment ordonnancer facilement les VMs sans nuire à l’ordonnançabilité ?
4.1 Harmonicité
4.2 Déduction des paramètres de la VM la plus critique
4.3 Déduction des paramètres des autres VMs par ordre de criticité décroissante
4.4 Ordonnancement harmonique des VMs
4.5 Exemple d’un système où les paramètres des VMs sont inconnus
5 Ordonnancement de VMs hypervisées non harmoniques : comment ordonnancer les VMs non harmoniques ?
5.1 Ordonnancement proportionnel (P-fair)
5.2 Implémentations de P-fair
5.2.1 Cas des ressources de calcul infinies
5.2.2 Algorithme proportionnel itératif
5.3 Optimisations de l’algorithme itératif
5.4 Combinaison des approches P-fair et harmonique
6 Amélioration de l’ordonnançabilité des tâches dans des VMs hypervisées : Dual Priority (en agissant sur le second niveau uniquement)
6.1 Concept de Dual Priority
6.2 Algorithme FDMS avec RM/RM pour les priorités
6.3 Algorithme RM−1/RM avec RML pour les priorités
6.4 Gains obtenus avec Dual Priority
7 Outils logiciels et expérimentations
7.1 Outil de génération de jeux de tâches
7.2 Outil de simulation d’ordonnancement temps réel
7.2.1 Historique de l’outil de simulation
7.2.2 Algorithme de simulation
7.2.3 Expériences
7.3 Outil de configuration des VMs
8 Conclusion et perspectives
8.1 Modèle hiérarchique à deux niveaux
8.2 Ordonnancement des VMs
8.3 Ordonnancement des tâches
8.4 Perspectives
8.5 Liste des publications
Bibliographie
Télécharger le rapport complet
