Algorithmes d’ordonnancement à priorité dynamique au niveau des travaux

Télécharger le fichier pdf d’un mémoire de fin d’études

Ordonnancement

L’ordonnancement d’un système consiste à définir une allocation du ou des processeurs aux travaux de sorte à ce que toutes les contraintes qui peuvent accompagner leur exécution soient satisfaites au mieux. Ce problème peut être considéré comme un cas particulier de planification et un vaste choix de méthodes est disponible pour planifier à l’avance l’ordonnancement des tâches. Ce type d’ordonnancement est appelé hors-ligne car il se fait avant l’exécution du système. Les travaux présentés ici concernent des approches en-ligne qui décident de l’ordonnancement pendant l’exécution du système.

Une exécution en-ligne est plus souple et permet de tenir compte de paramètres variables au cours de l’exécution (travail qui se termine plus tôt, activation arbitraire d’une nouvelle tâche, etc).

Ordonnançabilité

Les études d’ordonnançabilité visent à déterminer si un système est ordonnançable par une politique d’ordonnancement sur une architecture matérielle donnée.

Définition 1.1. Un système S est fiablement ordonnancé par un algorithme d’ordonnan-cement A, si et seulement si la séquence produite par A est valide.

Définition 1.2. Un système S est ordonnançable s’il existe un algorithme qui l’ordonnance

fiablement.

Un ensemble de conditions suﬃsantes et/ou nécessaires permettent de déterminer, dans certains cas, si un système est ordonnançable (condition suﬃsante satisfaite), ou s’il ne l’est pas (condition nécessaire non satisfaite).

Définition 1.3. Lorsqu’un système respecte une condition suﬃsante de l’algorithme d’or-donnancement utilisé, alors il est ordonnançable par cet algorithme.

Définition 1.4. Lorsqu’un système ne respecte pas une condition nécessaire de l’algo-rithme d’ordonnancement utilisé, alors il n’est pas ordonnançable par cet algorithme.

De nombreux travaux sur l’ordonnancement visent à fournir des algorithmes optimaux (Définition 1.5), mais cette optimalité n’est atteinte que dans un cadre précis (restriction sur le type de tâches et sur l’architecture matérielle) et sous certaines hypothèses (exemple : coût des préemptions ou des prises de décision nulles).

Définition 1.5. Un algorithme d’ordonnancement A est dit optimal pour une classe de systèmes et selon les hypothèses posées, parmi une classe de politiques d’ordonnancement, si et seulement si, il peut ordonnancer fiablement tout système ordonnançable par une politique de cette classe.

Un algorithme A domine un algorithme B si tout système ordonnançable par B l’est par A et s’il existe au moins un système ordonnançable par A et qui ne l’est pas par B. S’il existe des systèmes ordonnançables par l’un et non par l’autre et inversement, on dit que ces politiques ne sont pas comparables (Définition 1.6).

Définition 1.6. Deux algorithmes A et B sont dits non comparables si et seulement si :

il existe un système ordonnançable par A et non ordonnançable par B ; et il existe un système ordonnançable par B et non ordonnançable par A.

Ordonnancement conduit par le temps ou les évènements

Deux grandes façons d’implémenter un ordonnanceur existent. La première est conduite par le temps (tick-driven) et consiste à appeler l’ordonnanceur périodiquement. L’ordon-nanceur prend une décision d’ordonnancement qui sera alors appliquée par le système d’exploitation. L’autre méthode est conduite par les évènements (event-driven) et consiste

réagir aux évènements tels que des activations ou terminaisons de tâche. L’utilisation de l’une ou l’autre de ces méthodes est fortement liée à l’architecture du système d’exploita-tion.

Ordonnancement avec préemptions

Si un système permet d’interrompre un travail, d’en mémoriser l’état, et de le relancer plus tard, on dit que le système est préemptif (Définition 1.7). Cette interruption s’appelle une préemption et provoque un changement de contexte si une autre tâche s’exécute à la place.

Définition 1.7. Si un ordonnanceur peut interrompre l’exécution d’un travail pour en exécuter un autre, alors le système est préemptif.

La possibilité de provoquer des préemptions permet d’ordonnancer correctement un nombre d’ensembles de tâches bien plus grand. Cependant, pour certains systèmes et avec une même politique d’ordonnancement, un système ordonnançable en non-préemptif peut ne plus l’être en autorisant des préemptions.

Dans la suite de ce chapitre, seuls des systèmes préemptifs sont considérés. De plus, la plupart des travaux qui seront présentés supposent une durée de préemption nulle ou déjà intégrée dans le calcul du pire temps d’exécution (WCET).

Ordonnancement conservatif

Un ordonnanceur conservatif, ou work-conserving, est un ordonnanceur qui ne laisse pas des tâches prêtes en attente si un processeur est disponible pour l’exécuter (Définition 1.8). Dans la partie consacrée à la présentation de politiques d’ordonnancement, nous verrons qu’un certain nombre de politiques ne sont pas conservatives. Généralement, une politique work-conserving permet de réduire les temps de réponse et s’adapte mieux à des durées d’exécution eﬀectives inférieures au WCET.

Définition 1.8. Un ordonnanceur conservatif a comme particularité de ne jamais laisser un processeur dans un état oisif (idle) s’il reste des travaux prêts à s’exécuter. Au contraire, un ordonnanceur non-conservatif peut introduire des laps de temps pendant lesquels aucun travail actif ne s’exécute.

Anomalies et prédictabilité

Définition 1.9. Une anomalie d’ordonnancement apparaît lorsqu’un changement dans les paramètres du système engendre des eﬀets contre-intuitifs [DB11].

Ces anomalies peuvent apparaître dans le cas de systèmes non-préemptifs ou dans le cas de systèmes multiprocesseurs. Un exemple est l’augmentation de la période d’une tâche, soit une baisse du taux d’utilisation, qui devrait intuitivement améliorer l’ordonnançabilité, mais qui en pratique peut rendre un ensemble de tâches non ordonnançable. Andersson étudie en détail cette problématique dans le chapitre 5 de sa thèse [And03].

Définition 1.10. Un algorithme d’ordonnancement est dit prédictible si les temps de réponse des travaux ne peuvent pas être augmentés par une réduction de leur durée d’exé-cution, avec tous les autres paramètres constants [HL94].

Cette propriété est importante car la durée d’exécution des travaux est seulement modé-lisée par une durée maximale (WCET). Ainsi l’ordonnançabilité d’un système prédictible est garantie, si elle est vérifiée sur le modèle avec WCET. Nous verrons cependant que se limiter à une durée fixe peut conduire à des évaluations biaisées du comportement des algorithmes d’ordonnancement (voir chapitres 3 et 4).

Définition 1.11. Un algorithme d’ordonnancement est dit viable (sustainable) pour un modèle de système, si et seulement si l’ordonnançabilité d’un ensemble de tâches conforme

ce modèle reste inchangée après une réduction des durées d’exécution, une augmentation des périodes ou des dates d’inter-arrivée, ou une augmentation des échéances.

Ordonnancement monoprocesseur

Les politiques d’ordonnancement temps réel les plus connues sont très certainement Rate Monotonic et Earliest Deadline First. Il en existe cependant d’autres, dont l’utilité dépend du type de système. Classiquement, on considère que l’ordonnanceur choisit d’exécuter les travaux les plus prioritaires à tout moment. La gestion de ces priorités peut être distinguée de trois manières diﬀérentes [CFH+04] :

Les algorithmes à priorité fixe au niveau des tâches, pour lesquels les tâches et les travaux partagent la même priorité. Exemple : Rate Monotonic.

Les algorithmes à priorité fixe au niveau des travaux qui attribuent aux travaux des priorités fixes pendant l’exécution. Ainsi, les travaux d’une même tâche peuvent avoir des priorités diﬀérentes, mais cette priorité ne varie pas pendant l’exécution d’un travail. Exemple : Earliest Deadline First. Les algorithmes à priorité dynamique au niveau des travaux qui définissent à chaque instant une priorité pour chaque travail. Exemple : Least Laxity First.

Il est cependant courant que les deux dernières catégories soient regroupées sous le terme d’algorithme à priorité dynamique. Cette classification demeure valide dans le cas multi-processeur.

Enfin, notons que pour toutes les politiques d’ordonnancement monoprocesseur, la condi-tion nécessaire d’ordonnançabilité suivante doit être satisfaite : n X ui ≤ 1 (1.5)

Algorithme d’ordonnancement à priorité fixe au niveau des travaux

Un algorithme à priorité fixe au niveau des travaux est un algorithme pour lequel la priorité des tâches peut varier d’un travail à un autre mais la priorité d’un travail ne change pas. Ces algorithmes sont cependant parfois appelés algorithmes à priorité dynamique dans le sens où la priorité d’une tâche peut varier.

Earliest Deadline First

Earliest Deadline First (EDF) est un ordonnanceur tel que la priorité d’un travail est plus forte lorsque son échéance absolue est plus proche. Généralement, EDF est utilisé avec préemption : si une nouvelle tâche arrive et que sa date d’échéance absolue est plus rapprochée, alors la tâche en cours d’exécution est préemptée et la nouvelle tâche est exécutée.

Pour des tâches périodiques, indépendantes et à échéances contraintes, on retiendra que EDF est un algorithme d’ordonnancement optimal [BG03b]. EDF oﬀre de meilleures per-formances que RM en terme d’ordonnançabilité [But05]. La condition nécessaire et suﬃ- sante dans ce cas est : Pn ui ≤ 1 i=1.

Algorithmes d’ordonnancement à priorité dynamique au niveau des travaux

Un algorithme à priorité dynamique au niveau des travaux est un algorithme qui peut modifier le niveau de priorité d’un travail à tout moment.

Least Laxity First

La laxité dynamique d’un travail à un instant donné est le temps maximum pendant lequel son exécution peut être retardée sans manquer son échéance. La laxité dynamique est définie par : d − (tcur + cret) avec d la date d’échéance absolue, tcur la date actuelle et cret le temps d’exécution restant du travail (voir Figure 1.3).

L’algorithme Least Laxity First (LLF) rend prioritaire les travaux dont la laxité dynamique est la plus faible. C’est donc un algorithme avec priorité dynamique au niveau des travaux car la priorité d’un travail évolue dans le temps (la priorité de chaque travail non exécuté augmente au fil du temps tandis qu’elle reste constante pour les autres).

Contrairement à un algorithme à priorité fixe pour les travaux tel que EDF, il est nécessaire pour LLF de mettre à jour fréquemment les priorités des travaux alors que pour EDF ce n’est fait qu’à l’activation de la tâche.

LLF est optimal pour l’ordonnancement de tâches préemptives périodiques ou sporadiques, mais perd son optimalité pour l’ordonnancement de tâches non-préemptives [Mok83].

Cet algorithme peut cependant engendrer de nombreux changements de contexte. C’est en particulier le cas lorsque plusieurs travaux ont la même laxité. Dans ce cas, l’algorithme LLF provoque une situation dite de « task thrashing ». En eﬀet, soit le cas de deux travaux (notons a et b) avec la même laxité (laxity-tie) : si on choisit d’exécuter a alors la priorité de b augmente et dépasse donc la priorité de a, donc b préempte a et la situation inverse se produit alors. La figure 1.4 montre ce phénomène avec deux tâches quelconques et une mise à jour des priorités toutes les unités de temps. Bien évidemment, plus le nombre de tâches est important, plus ce problème risque de survenir.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela clepfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

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 RM-US[ξ], EDF-US[ξ], EDF(k) et fpEDF
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
iv4.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