<!-- Slide number: 1 -->
cole Nationale des Sciences de lInformatique
Chapitre 2Gestion des processus dans les syst mes dexploitation temps r el
Module : Syst mes dexploitation temps r el
Niveau : II2 Fili re Syst mes et Logiciels Embarqu s
AU : 2011/2012
<!-- Slide number: 2 -->
Plan
Aper u sur lordonnancement temps r el
Ordonnancement par horloge
Ordonnancement par priorit s
Ordonnancement avec prise en charge des ressources
Gestion des interruptions
2
<!-- Slide number: 3 -->
Hypoth ses
Lordonnancement par horloge est applicable aux syst mes d terministes
Mod le de t ches p riodiques restreint:
les param tres de toutes les t ches p riodiques sont connus a priori
pour chaque mode de fonctionnement, le syst me a un nombre fixe n de processus p riodiques
pour le processus Ti , chaque t che Ji,k est pr te pour l'ex cution son temps darriv e ri,k, et arrive pi unit s de temps apr s la t che pr c dente de Ti tel que ri,k = ri, k-1 + pi
les t ches ap riodiques peuvent exister
nous admettons que le syst me maintient une file d'attente simple pour les t ches ap riodiques
Lorsque le processeur est la disposition des t ches ap riodiques, la t che en t te de cette file d'attente est ex cut e
Il n'y a pas de t ches sporadiques
Rappel : les t ches sporadique ont des d lais dures, par opposition aux t ches ap riodiques
3
<!-- Slide number: 4 -->
Notation
Le 4-tuple Ti = (Fi, pi, ei, Di) se rapporte un processus p riodique Ti , de phase Fi, de p riode pi, de temps d'ex cution ei, et de d lai relatif Di
la phase par d faut de Ti est Fi = 0, le d lai relatif par d faut est la p riode Di = pi
Les valeurs par d faut ne sont pas mentionn es dans le tuple
Exemples :
4
<!-- Slide number: 5 -->
Ordonnancement statique cyclique par horloge
Puisque les param tres de toutes les t ches d lais dures sont connus, on peut construire une planification cyclique et statique l'avance
le temps processeur assign une t che est gal son temps d'ex cution maximum
Lordonnanceur dispatche les t ches selon la planification statique, tout en r p tant chaque hyper-p riode
Le planning statique garantit que chaque t che s'accomplit par son d lai
Aucune t che ne d passe son ex cution les d lais sont respect s
Lordonnancement est calcul offline possibilit dutilisation dalgorithmes complexes
Le temps d'ex cution de l'algorithme nest pas important
Possibilit de recherche dune planification qui optimise un certain crit re
Publicité
Ex: un programme o les p riodes vides sont presque p riodiques ; servant ainsi les t ches ap riodiques
5
<!-- Slide number: 6 -->
Exemple dordonnancement cyclique
Consid rons un syst me avec 4 processus p riodiques ind pendants:
Hyper-p riode H = 20 (ppcm (4, 5, 20, 20))
Possibilit de construire un ordonnancement statique arbitraire pour respecter les d lais
6
<!-- Slide number: 7 -->
Impl mentation dun ordonnancement cyclique
Sauvegarde de la planification pr -calcul dans une table
Le syst me cr e toutes les t ches qui seront ex cut es :
Alloue la m moire pour le code et les donn es de chaque t che
Apporte le code ex cut par la t che dans la m moire
Lordonnanceur configure le timer mat riel pour g n rer des interruptions la premi re d cision, tk=0
chaque interruption du timer linstant tk :
Lordonnanceur configure linterruption du timer pour expirer tk+1
Si T(tk) = I et une t che ap riodique est en attente, alors d marrer la t che ap riodique
Sinon, d marrer la prochaine t che du processus T(tk)
7
<!-- Slide number: 8 -->
Impl mentation dun ordonnancement cyclique
8
<!-- Slide number: 9 -->
Ordonnancement cyclique structur
Lordonnancement cyclique arbitraire table driven est flexibles, mais inefficace
N cessite des interruptions pr cises du timer
bas e sur le temps d'ex cution des t ches
En imposant une structure, limpl mentation devient plus facile
les d cisions de planification sont r alis es des intervalles p riodiques (frames) de longueur f
Ex cution dune liste fixe de t ches chaque frame, la pr emption nest prise en compte quaux limites des frames
la phase de chaque t che p riodique doit tre un multiple non n gatif du frame
La premi re t che de chaque processus est lib r e au d but d'un frame
Deux avantages :
Lordonnanceur peut facilement v rifier les d passements et les d lais manqu s la fin de chaque frame
Il est possible dutiliser des interruptions p riodiques d'horloge, plut t quun timer programmable
9
<!-- Slide number: 10 -->
Ordonnancement cyclique structur
D cision d'ordonnancement prise p riodiquement
De fa on p riodique
Publicité
Choisir la t che ex cuter
Effectuer les op ration de contr le et de suivi
Cycle principal: tendues durant une hyper-p riode
frame f
Points de d cision
10
Notes:
<!-- Slide number: 11 -->
Contraintes de la taille du frame
Soit f la longueur de l' tendue.
Comment choisir f ?
Chaque t che doit pouvoir commencer et terminer son ex cution durant le frame :
vite la pr emption
f divise l'hyper-p riode (lcm(p1, .. , pn)). Donc, f doit diviser la p riode d'au moins une t che :
r duit au minimum le nombre des entr es de lordonnancement cyclique
11
<!-- Slide number: 12 -->
Contraintes de la taille du frame
Pour permettre lordonnanceur de v rifier que les t ches finissent leurs d lais, il doit y avoir au moins une limite dans le frame entre le temps darriv e dune t che et son d lai.
Il y a au moins une tendue entre l'arriv e et le d lai de chaque t che
12
<!-- Slide number: 13 -->
Contraintes de la taille du frame
Les trois contraintes doivent tre satisfaites
13
Notes:
<!-- Slide number: 14 -->
Exemple 1 :
14
Notes:
<!-- Slide number: 15 -->
Exemple 2 :
T che P riode D lai Temps d'ex cution
i Ti Di Ci
------------------------------------------------------------
1 15 14 1
2 20 26 2
Publicité
3 22 22 3
Premi re contrainte => f est au moins 3.
Deuxi me contrainte => f est 3, 4, 5, 10, 11, 15, 20 ou 22.
Troisi me contrainte => f est 3, 4, 5, 10 ou 11.
15
Notes:
<!-- Slide number: 16 -->
D coupage de t ches
D couper T3
16
Notes:
<!-- Slide number: 17 -->
Noyau cyclique (cyclic executive)
17
Notes:
<!-- Slide number: 18 -->
Planification des t ches ap riodiques
Pour le moment, les t ches ap riodiques sont planifi es la fin des frames, apr s que toutes les t ches avec d lais durs programm es dans le frame soient accomplies
Ceci retarde l'ex cution des t ches ap riodiques en faveur des t ches p riodiques
Cependant,
g n ralement, il n'y a pas davantage accomplir une t che temps r el dure t t,
et puisqu'une t che ap riodique est r active un v nement particulier, le plus t t cette t che fini, meilleur est la r ponse du syst me
Par cons quent, r duire le temps de r ponse du syst me pour les t ches ap riodiques est typiquement un but inh rent lordonnancement temps r el
18
<!-- Slide number: 19 -->
Exemple :
Trep moyen = 4.5
Trep moyen = 2.5
19
<!-- Slide number: 20 -->
Planification des t ches ap riodiques : Slack Stealing
Les t ches p riodiques sont ordonnanc es dans les frames qui compl tent avant leurs d lais ; il peut y avoir du temps perdu (slack time) dans le frame apr s la fin dex cution des t ches p riodiques
Puisquon connait lavance le temps d'ex cution des t ches p riodiques, on peut d placer ce temps perdu au d but du frame, ex cutant les t ches p riodiques juste temps pour satisfaire leurs d lais
Ex cution des t ches ap riodiques pendant le temps perdu, avant les t ches p riodiques:
Le noyau cyclique garde le temps perdu de chaque frame pour lex cution des t ches ap riodiques, les pr empte pour lancer les t ches p riodiques lorsque le temps perdu est fini
Tant quil reste du temps perdu, dans le frame, le noyau cyclique revoie la file des t ches ap riodiques apr s la fin de chaque slice (unit )
Ceci permet de r duire le temps de r ponse des t ches ap riodiques, mais n cessite des timers tr s pr cis.
Publicité
20
<!-- Slide number: 21 -->
Ordonnancement des t ches sporadiques
Que faire si on veut prendre en consid rations les t ches sporadiques ?
Les t ches sporadiques ont des d lais durs, le temps darriv e et le temps dex cution ne sont pas connus lavance:
Par cons quent, lordonnancement par horloge ne peut pas garantir a priori que les t ches sporadiques saccomplissent dans les d lais
Cependant, le planificateur peut d terminer si une t che sporadique est planifiable quand elle arrive
R alise un test dacceptation pour v rifier si la nouvelle t che sporadique peut tre planifi e avec toutes les t ches dans le syst me
S'il y a suffisant de temps perdu dans les frames avant le d lai de la nouvelle t che, cette derni re est accept e, sinon rejet e
Si plusieurs t ches sporadique arrivent en m me temps, elles doivent tre mises dans une file dattente dans lordre EDF pour le test dacceptation
21
<!-- Slide number: 22 -->
Consid rations pratiques
Prise en compte des d passements :
Les t ches sont planifi es selon leur temps dex cution maximum, mais des checs pourraient causer des d passements
Un syst me robuste tiendra compte de cela par
Soit arr ter la t che qui d passe et g n rer une t che de r cup ration
Ou bien pr empte la t che et la planifie comme tant une t che ap riodique.
Ceci d pend de lutilit des r sultats en retard, les d pendances entre les t ches, etc...
Des processeurs multiples
Peut tre r alis , mais la g n ration de la table de planification off-line est plus complexe
22
<!-- Slide number: 23 -->
Avantages de lordonnancement par horloge
Simplicit de la conception
Il est possible de consid rer des d pendances complexes, des d lais de communication, des conflits sur les ressources lors de la construction de lordonnancement statique, tout en garantissant labsence de blocage et les d lais impr dictibles
Lordonnancement entier est retenu dans une table statique
Des modes de fonctionnement diff rents peuvent tre repr sent s par diff rentes tables
Il ny a pas besoin de contr le de concurrence ou de synchronisation
Lorsque la charge de travail est la plupart du temps p riodique et lordonnancement est cyclique, les contraintes de temps peuvent tre v rifi es chaque limite de frame
Le choix de la taille du frame peut minimiser les d passements dus aux changements de contexte et les d passements de communications
L ordonnancement r alis est relativement facile valider, tester et certifier
23
<!-- Slide number: 24 -->
Inconv nients de lordonnancement par horloge
Non flexible
Toute modification du mat riel cause la re-g n ration de la table
Convient aux syst mes qui sont rarement modifi s une fois construits
Autres inconv nients :
Le temps darriv e de toutes les t ches doit tre fix
Toutes les combinaisons possibles des t ches p riodiques qui sex cutent en m me temps doivent tre connus lavance, ainsi lordonnancement combin peut tre pr -calcul
Le traitement des t ches ap riodiques est tr s primitif
24