Étude et évaluation des politiques d’ordonnancement temps réel multiprocesseur

É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).

Table des matières

Introduction générale
Partie I Contexte et Motivations
1 Ordonnancement temps réel multiprocesseur
1.1 Modélisation et vocabulaire
1.1.1 Modélisation des applications
1.1.2 Modélisation de l’architecture matérielle
1.1.3 Ordonnancement
1.2 Ordonnancement monoprocesseur
1.2.1 Algorithmes d’ordonnancement à priorité fixe au niveau des tâches
1.2.2 Algorithme d’ordonnancement à priorité fixe au niveau des travaux
1.2.3 Algorithmes d’ordonnancement à priorité dynamique au niveau des travaux
1.3 Ordonnancement multiprocesseur
1.3.1 Ordonnancement par partitionnement
1.3.2 Ordonnancement global
1.3.3 Ordonnancement semi-partitionné
1.3.4 Autres approches
1.4 Généralisation des algorithmes monoprocesseurs
1.4.1 Algorithmes
1.4.2 Algorithme Global-Fair Lateness
1.4.3 Algorithmes d’ordonnancement à laxité nulle (Zero Laxity)
1.4.4 Algorithme Global-Least Laxity First
1.4.5 Algorithme U-EDF
1.5 Ordonnancement global dit équitable
1.5.1 Ordonnancement PFair
1.5.2 Ordonnancement global DP-Fair
1.6 Approches hybrides
1.6.1 Ordonnancement semi-partitionné
1.6.2 Algorithme RUN
1.7 Conclusion
2 Principe et fonctionnement des mémoires caches
2.1 Fonctionnement d’un processeur
2.1.1 Exécution d’un programme
2.1.2 Exemple de programme
2.1.3 Mémoire cache
2.1.4 Types d’architectures
2.1.5 Optimisations
2.2 Principe d’une mémoire cache
2.2.1 Technologies de mémoire
2.2.2 Principe de localité
2.2.3 Hiérarchie mémoire
2.3 Fonctionnement d’un cache
2.3.1 Associativité
2.3.2 Protocoles de cohérence
2.4 Sources de défauts de cache
2.4.1 Types de défauts de cache
2.4.2 Préemption et « context switch misses »
2.4.3 Partage de cache et « cache thrashing »
2.4.4 Bilan
2.5 Caractérisation du comportement mémoire d’une tâche
2.5.1 Working Set Size
2.5.2 Nombre de cycles par instruction
2.5.3 Fréquence d’accès au cache
2.5.4 Stack distance
2.5.5 Reuse distance
2.5.6 Récapitulatif
2.6 Prise en compte des caches dans les systèmes ordonnancés
2.6.1 Sauvegarde du cache
2.6.2 Partitionnement du cache
2.6.3 Verrouillage du cache
2.6.4 Co-ordonnancement
2.7 Conclusion
3 Motivations
3.1 Constats
3.1.1 De nombreuses politiques d’ordonnancement
3.1.2 Quelles approches pour l’évaluation de ces politiques ?
3.1.3 Des difficultés pour combiner les résultats existants
3.1.4 Et des aspects opérationnels oubliés ou au second plan
3.2 Objectifs
3.3 Besoins
3.4 Évaluation des outils disponibles
3.4.1 MAST
3.4.2 Cheddar
3.4.3 STORM
3.4.4 Yartiss
3.4.5 Conclusion sur les simulateurs
3.5 Conclusion
Partie II Simulation d’ordonnancement
4 SimSo : un outil pour la simulation d’ordonnancement
4.1 Présentation générale
4.2 Architecture
4.2.1 Simulation à événements discrets
4.2.2 Structures de données pour les paramètres de simulation
4.2.3 Classes pour la simulation
4.2.4 Modèle de temps d’exécution
4.3 Ordonnanceurs
4.3.1 Fonctionnement et interface d’un ordonnanceur
4.3.2 Difficultés liées à la mise en œuvre d’ordonnanceurs
4.3.3 Ordonnanceurs disponibles
4.3.4 Exemple
4.4 Génération de tâches
4.4.1 Choix des taux d’utilisation
4.4.2 Choix des périodes
4.4.3 Tâches sporadiques
4.5 Valeurs mesurées
4.5.1 Préemptions et migrations
4.5.2 Dépassements d’échéance
4.5.3 Temps de réponse et laxité normalisée
4.5.4 Appels à l’ordonnanceur
4.5.5 Récapitulatif des mesures disponibles
4.6 Utilisation de Simso
4.6.1 Interface graphique
4.6.2 Mode script
4.7 Conclusion
5 Évaluation des politiques d’ordonnancement
5.1 Mise en place de l’évaluation
5.1.1 Comparaison des méthodes de génération
5.1.2 Génération des systèmes et simulations
5.1.3 Valeurs mesurées
5.2 Évaluation des politiques de type G-EDF
5.2.1 Test d’ordonnançabilité GFB
5.2.2 Comparaison des algorithmes de type G-EDF
5.3 Ordonnancement partitionné
5.3.1 Systèmes partitionnables
5.3.2 Impact du placement des tâches
5.3.3 Comparaison G-EDF et P-EDF
5.4 Comparaison des politiques DP-Fair
5.4.1 Comparaison de LRE-TL et LLREF
5.4.2 DP-WRAP
5.5 Comparaison des politiques U-EDF, RUN et EKG
5.6 Usage du WCET
5.6.1 Simulation d’ordonnancement avec durées aléatoires des travaux
5.6.2 Évaluation basée sur le WCET
5.6.3 Ordonnancement d’un système en surcharge
5.7 Avantages liés aux politiques conservatives
5.7.1 Ordonnancement ER-Fair
5.7.2 Algorithme d’ordonnancement NVNLF
5.7.3 Combiner G-EDF à des politiques non conservatives
5.8 Conclusion
Partie III Simulation avec impact des caches
6 Modèles de cache
6.1 Contexte
6.1.1 Besoin pour la simulation
6.1.2 Entrées disponibles
6.1.3 Hypothèses
6.2 Présentation des modèles
6.2.1 Évaluation du CPI
6.2.2 Défauts de cache pour une tâche isolée
6.2.3 Défauts de cache pour une tâche avec un cache partagé
6.2.4 Estimation des coûts de préemption
6.2.5 Estimation des défauts de cache suite à une migration
6.3 Évaluation des modèles
6.3.1 Choix des outils et benchmarks
6.3.2 Caractérisation du comportement mémoire des programmes
6.3.3 Caches N-Way et fully-associative
6.3.4 Évaluation du comportement des tâches en isolation
6.3.5 Partage de cache
6.3.6 Coûts des préemptions
6.3.7 Conclusion
7 Prise en compte des surcoûts temporels dans SimSo
7.1 Prise en compte des aspects opérationnels dans SimSo
7.1.1 Intégration des pénalités temporelles
7.1.2 Intégration de modèles de cache dans SimSo
7.2 Expérimentations
7.2.1 Comparaison de G-EDF et P-EDF avec pénalités temporelles
7.2.2 Variation des offsets avec prise en compte des caches
7.2.3 Impact du placement des tâches
7.2.4 Pénalités de préemption et migration
7.3 Conclusion
Conclusion
A Boite à outils pour l’évaluation
A.1 Simulation d’ordonnancement
A.1.1 STRESS et PERTS
A.1.2 GHOST et RTSIM
A.1.3 FORTISSIMO
A.1.4 FORTAS
A.1.5 RealtssMP
A.2 Exécutions réelles
A.2.1 Linux
A.2.2 LITMUSRT
A.2.3 RESCH
A.2.4 ChronOS Linux
A.3 Simulateurs d’architecture
A.3.1 Gem5
A.3.2 Simics
A.3.3 SESC et ESESC
A.3.4 MARSSx86 et PTLSim
A.3.5 Autres
A.4 Mesure de SDP et analyse des caches
A.4.1 MICA
A.4.2 Cachegrind
A.4.3 Stressmark Workload
A.4.4 StatStack
A.5 Benchmarks
A.5.1 Benchmarks orientés temps réel
A.5.2 Benchmarks orientés embarqués
A.5.3 Benchmarks orientés WCET
A.5.4 Conclusion sur les benchmarks
Bibliographie