Temps RelJrme Pouiller Septembre 2011Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesQuatrime partie IVOrdonnancementJ. Pouiller
Temps Rel 76 / 197Quelques notions thoriques Algorithmes priorit
statique Algorithmes priorit dynamique Serveurs de tches
apriodiques9 Quelques notions thoriquesModle de tches10 Algorithmes
priorit statiqueThrome de linstant critiqueTemps de rponseRate
Monotonique (RM)Deadline Monotonic (DM)11 Algorithmes priorit
dynamiqueEarliest Deadline First (EDF)Least Slack Time (LST)12
Serveurs de tches apriodiquesExecution en arrire-planTraitement par
serveurServeur par scrutationServeur diffrServeur sporadiqueSlack
StealerOrdonnancement conjointJ. Pouiller Temps Rel 77 /
197Quelques notions thoriques Algorithmes priorit statique
Algorithmes priorit dynamique Serveurs de tches apriodiquesModle de
tchesParamtres dnissant une tche i :Date darrive de la tche dans le
systme : SiPremire date dactivation : RiPriode dactivation : TiDlai
critique ou deadline (Dlai maximum acceptable pour sonexcution) :
DiCapacit (Temps CPU ncessaire lxecution de la tche) : CiJ.
Pouiller Temps Rel 78 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesModle de tches0 1 2 3 4 5 6 7 8 9 10 11 12 13
14iSiRiTR1iDiTiTR2iDiTiTche Arrive Priode Capacit Dlaii 2 6 2 5J.
Pouiller Temps Rel 79 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesModle de tchesPar consquent :Tche priodique dnie par :
(Si, Ri, Ti, Di, Ci)Tche apriodique dnie par : (Si, Ri, 0, Di,
Ci)Trs souvent :Les tches sont connues dbut de lordonnacement : Si=
0Les tches priodique sont actives ds le dbut delordonnancement :
Ri= 0Le dlai critique des tches priodiques est leur priode : Di=
TiJ. Pouiller Temps Rel 80 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesParamtres statiquesParamtres statiques :Date de
rveil sur une priode k : rikEchance sur une priode k : dik= rik
+DiFacteur dutilisation du processeur : Ui= Ci/TiFacteur de charge
du processeur : CHi= Ci/Di(CHi= Uisidlai critique sur priodes)Laxit
(ou Slack) de la tche (retard maximum acceptable pourlexcution de
la tche) : Li= DiCiJ. Pouiller Temps Rel 81 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesParamtres
dynamiquesParamtres dynamiques (dpendant de lordonnancement)
:Priorit (peut tre dynamique ou statique) : PiDate du dbut de
lexcution dune priode k : sikDate de la n de lexcution dune priode
k :eikTemps de rponse de la tche TRik= eikrik(Nous verronscomment
le calculer)Dure dexcution rsiduelle la date t : Ci(t ) (0 Ci(t )
Ci)Dlai critique rsiduel la date t : Di(t ) = dikt (0 Di(t )
Di)Charge rsiduelle la date t : CHi(t ) = Ci(t )/Di(t )(0 CHi(t )
CHi)Laxit rsiduelle la date t : Li(t ) = Di(t ) Ci(t ) (0 Li(t )
Li)Laxit conditionnelle la date t (somme sur les tchesdclenches la
date t et qui sont devant i du point de vue delordonnancement) :
LCi(t ) =Di(t ) Pj>Pi Cj(t ) (0 LCi(t ) Li)J. Pouiller Temps Rel
82 / 197Quelques notions thoriques Algorithmes priorit statique
Algorithmes priorit dynamique Serveurs de tches
apriodiquesParamtres du systmeConguration : ensemble des tches
mises en jeu parlapplicationTaux dutilisation du processeur : U =i
UiTaux de charge du processeur : CH =i CHiIntervalle dtude :
intervalle de temps minimum pour prouverlordonnancabilit dune
congurationDans le cas de tches priodiques : ppcmi(Ti)Dans le cas
de tches apriodiques :[mini{Ri}, maxi{Ri +Di}+2ppcmi(Ti)]Laxit du
processeur : intervalle de temps pendant lequel leprocesseur peut
rester inactif tout en respectant les chances :LP(t ) = mini{LCi(t
)}J. Pouiller Temps Rel 83 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesEtats des tchesRunningWaitingInterruptedReadyJ.
Pouiller Temps Rel 84 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesTypologie des algorithmesOn distingue diverse typologie
dalgorithmes :on line ou off line : Choix dynamique ou prdni la
conception priorit statique ou dynamique : La priorit dune tche
est-ellexe ou une variable dpendante dautres paramtrespremptif ou
non premptif : Une tche peut-elle perdre leprocesseur (au prot dune
tche plus prioritaire) ou nonJ. Pouiller Temps Rel 85 / 197Quelques
notions thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesThorme de linstant
critiqueSi toutes les tches arrivent initialement dans le systme en
mmetemps et si elles respectent leur premire chance, alors toutes
leschances seront respectes par la suite, quel que soit
linstantdarrive des tches.Cest une condition ncessaire et sufsante
si toutes les tchesdu systme sont initialement prtes au mme
instant.Dans le cas contraire, cest une condition sufsanteJ.
Pouiller Temps Rel 86 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesTemps de rponseDlai entre lactivation dune tche et sa
terminaison.TRi= Ci +Pj>Pi
TRiTj
CjJ. Pouiller Temps Rel 87 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesCalcul du temps de rponseTechnique de calcul :
on value de facon itrativewn+1i= Ci +Pj>Pi
wniTj
CjOn dmarre avec w0i= CiEchec si wni>TiRussite si wn+1i=
wniJ. Pouiller Temps Rel 88 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesCalcul du temps de rponseExemple :Tche Arrive
Priode Capacit Dlai PrioritA 0 7 3 Fin de priode 1B 0 12 2 Fin de
priode 2C 0 20 5 Fin de priode 3w01= C1 = 3w02= C2 = 2w12= 2+3
27
= 5w22= 2+3
57
= 5w03= C3 = 5w13= 5+3
57
+2
512
= 10w23= 5+3
107
+2
1012
= 13w33= 5+3
137
+2
1312
= 15w43= 5+3
157
+2
1512
= 18w53= 5+3
187
+2
1812
= 18J. Pouiller Temps Rel 89 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesCalcul du temps de rponseExemple :Tche Arrive
Priode Capacit Dlai PrioritA 0 7 3 Fin de priode 1B 0 12 2 Fin de
priode 2C 0 20 5 Fin de priode 3w01= C1 = 3w02= C2 = 2w12= 2+3
27
= 5w22= 2+3
57
= 5w03= C3 = 5w13= 5+3
57
+2
512
= 10w23= 5+3
107
+2
1012
= 13w33= 5+3
137
+2
1312
= 15w43= 5+3
157
+2
1512
= 18w53= 5+3
187
+2
1812
= 18J. Pouiller Temps Rel 89 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesRate MonotoniqueAussi appell RMA (Rate
Monotonic AlgorithmOrdonnancement priorit statique o les priorit
sont inversementproportionnelles aux priodes des tches.Fonctionne
en version premptive. La version non-premptive nestpas garantie.Liu
et Layland ont dmontr quun systme est ordonnancable si letaux
doccupation du processeur U vrie la condition sufsante
(nonncessaire) suivante :U =niCiTin
21n 1
n limite doccupation1 100.0%2 82.8%3 78.0%4 75.7%5 74.3%10 71.9%
69.3%J. Pouiller Temps Rel 90 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesExemple 1Tche Arrive Priode Capacit DlaiA 0 20
8 Fin de priodeB 0 10 1 Fin de priodeC 0 4 1 Fin de priodeJ.
Pouiller Temps Rel 91 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple 1Tche Arrive Priode Capacit DlaiA 0 20 8 Fin de
priodeB 0 10 1 Fin de priodeC 0 4 1 Fin de priodeCharge du CPU :840
+110 + 14= 0.75J. Pouiller Temps Rel 91 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesExemple 1Tche Arrive Priode
Capacit DlaiA 0 20 8 Fin de priodeB 0 10 1 Fin de priodeC 0 4 1 Fin
de priodeMode premptif (ppcm(4, 10, 20) = 20)
:0ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABC17ABC18ABC19ABC20ABCJ.
Pouiller Temps Rel 91 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple 1Tche Arrive Priode Capacit DlaiA 0 20 8 Fin de
priodeB 0 10 1 Fin de priodeC 0 4 1 Fin de priodeMode non-premptif
:0ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABC17ABC18ABC19ABC20ABC
J. Pouiller Temps Rel 91 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesExemple 2Tche Arrive Priode Capacit DlaiA 0 16
8 Fin de priodeB 0 8 2 Fin de priodeC 0 4 1 Fin de priodeCharge du
CPU :816 + 28 + 14=
10ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABCJ.
Pouiller Temps Rel 92 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple 2Tche Arrive Priode Capacit DlaiA 0 16 8 Fin de
priodeB 0 8 2 Fin de priodeC 0 4 1 Fin de priodeCharge du CPU :816
+ 28 + 14=
10ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABCJ.
Pouiller Temps Rel 92 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple 2Tche Arrive Priode Capacit DlaiA 0 16 8 Fin de
priodeB 0 8 2 Fin de priodeC 0 4 1 Fin de priodeCharge du CPU :816
+ 28 + 14=
10ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABCJ.
Pouiller Temps Rel 92 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesDeadline Monotonic (DM)Aussi appell DMA (Deadline
Monotonic AlgorithmAlgorithme priorit statiqueGnralisation de Rate
Monotonic pour les tche avec Di1J. Pouiller Temps Rel 96 /
197Quelques notions thoriques Algorithmes priorit statique
Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleTche Arrive Priode Capacit DlaiA 0 20 3 7B 0 5 2
4C 0 10 2 8Par DM
:0ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABC17ABC18ABC19ABC20ABCJ.
Pouiller Temps Rel 96 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleTche Arrive Priode Capacit DlaiA 0 20 3 7B 0 5 2
4C 0 10 2 8Par EDF
:0ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABC15ABC16ABC17ABC18ABC19ABC20ABCJ.
Pouiller Temps Rel 96 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesLeast Slack Time (LST)Algorithme priorit dynamiqueAussi
appel Least Laxity First (LLF)Bas sur la laxit rsiduelle :La
priorit maximale est donne la tche qui a la plus petite
laxitrsiduelle : L(t ) = D(t ) C(t )Equivalent EDF si on ne calcule
la laxit quau rveil destchesOptimum trouver entre la granularit du
calcul et le nombre dechangements de contexte provoqusPermet dtre
parfois plus rsistant aux erreursDemande une connaissance de la
capacit des tchesGain discutablePeu utilis dans la pratiqueJ.
Pouiller Temps Rel 97 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleTche Arrive Priode Capacit DlaiA 0 20 1 7B 0 5 2
3C 0 10 3 8J. Pouiller Temps Rel 98 / 197Quelques notions thoriques
Algorithmes priorit statique Algorithmes priorit dynamique Serveurs
de tches apriodiquesExempleTche Arrive Priode Capacit DlaiA 0 20 1
7B 0 5 2 3C 0 10 3 8Par EDF
:0ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABCJ.
Pouiller Temps Rel 98 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleTche Arrive Priode Capacit DlaiA 0 20 1 7B 0 5 2
3C 0 10 3 8Par LST, en recalculant lalgorithme chaque priode
:0ABC1ABC2ABC3ABC4ABC5ABC6ABC7ABC8ABC9ABC10ABC11ABC12ABC13ABC14ABCJ.
Pouiller Temps Rel 98 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple - 2Tche Arrive Priode Capacit DlaiA 0 17 7 Fin
de priodeB 0 18 7 Fin de priodePar EDF
:0AB1AB2AB3AB4AB5AB6AB7AB8AB9AB10AB11AB12AB13AB14AB15AB16AB17AB18ABPar
LST, en recalculant lalgorithme chaque priode
:0AB1AB2AB3AB4AB5AB6AB7AB8AB9AB10AB11AB12AB13AB14AB15AB16AB17AB18ABJ.
Pouiller Temps Rel 99 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple - 2Tche Arrive Priode Capacit DlaiA 0 17 7 Fin
de priodeB 0 18 7 Fin de priodePar EDF
:0AB1AB2AB3AB4AB5AB6AB7AB8AB9AB10AB11AB12AB13AB14AB15AB16AB17AB18ABPar
LST, en recalculant lalgorithme chaque priode
:0AB1AB2AB3AB4AB5AB6AB7AB8AB9AB10AB11AB12AB13AB14AB15AB16AB17AB18ABJ.
Pouiller Temps Rel 99 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExemple - 2Tche Arrive Priode Capacit DlaiA 0 17 7 Fin
de priodeB 0 18 7 Fin de priodePar EDF
:0AB1AB2AB3AB4AB5AB6AB7AB8AB9AB10AB11AB12AB13AB14AB15AB16AB17AB18ABPar
LST, en recalculant lalgorithme chaque priode
:0AB1AB2AB3AB4AB5AB6AB7AB8AB9AB10AB11AB12AB13AB14AB15AB16AB17AB18ABJ.
Pouiller Temps Rel 99 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesTches apriodiquesTches prises en compte dans une
conguration comprenantdj des tches priodiquesA priori, on ne connat
pas linstant darrive de la requte derveil de la tche
apriodiqueContraintes temporelles strictes ou relativesButs
atteindre :Maintenir les garanties du temps relles sur les tches
djprsentes dans lordonnanceurSi contraintes relatives : minimiser
le temps de rponseSi contraintes strictes : maximiser le nombre de
tches acceptesen respectant leurs contraintesJ. Pouiller Temps Rel
100 / 197Quelques notions thoriques Algorithmes priorit statique
Algorithmes priorit dynamique Serveurs de tches
apriodiquesTraitement en arrire-planAussi appell backgound ou sur
temps creuxTches apriodiques ordonnances quand le processeur
estoisifLes tches priodiques restent les plus
prioritairesOrdonnancement relatif des tches apriodiques en mode
FIFOTraitement le plus simple, mais le moins performantPas de marge
de manoeuvre pour amliorer le temps derponse des tches apriodique.
Potentiellement, les tchesapriodique peuvent avoir des temps de
rponse long.J. Pouiller Temps Rel 101 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesTraitement en
arrire-planAvec ordonnancement RM des tches priodiques :Tche Arrive
Priode Capacit DlaiA 0 5 2 Fin de priodeB 0 10 2 Fin de priode1 0 3
2 Aucune2 0 10 1 Aucune3 0 11 2
Aucune0AB1231AB1232AB1233AB1234AB1235AB1236AB1237AB1238AB1239AB12310AB12311AB12312AB12313AB12314AB12315AB12316AB12317AB12318AB12319AB12320AB123J.
Pouiller Temps Rel 102 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesTraitement en arrire-planAvec ordonnancement RM des
tches priodiques :Tche Arrive Priode Capacit DlaiA 0 5 2 Fin de
priodeB 0 10 2 Fin de priode1 0 3 2 Aucune2 0 10 1 Aucune3 0 11 2
Aucune0AB1231AB1232AB1233AB1234AB1235AB1236AB1237AB1238AB1239AB12310AB12311AB12312AB12313AB12314AB12315AB12316AB12317AB12318AB12319AB12320AB123J.
Pouiller Temps Rel 102 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesTraitement en arrire-planAvec ordonnancement RM des
tches priodiques
:0AB1231AB1232AB1233AB1234AB1235AB1236AB1237AB1238AB1239AB12310AB12311AB12312AB12313AB12314AB12315AB12316AB12317AB12318AB12319AB12320AB123TR1
= 4TR2 = 5TR3 = 9J. Pouiller Temps Rel 103 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesTraitement par serveurUn
serveur est une tche priodique cre spcialement pourprendre en
compte les tches apriodiquesUn serveur caractris par :Sa priodeSon
temps dexcution : capacit du serveurUn serveur est gnralement
ordonnanc suivant le mmealgorithme que les autres tches
priodiquesTrs souvent, an de diminuer le temps de rpondes
tchesapriodique, la priorit du serveur est haute (sinon,
sesperformances sont identique au traitement sur temps creux)Une
fois actif, le serveur sert les tches apriodiques dans lalimite de
sa capacit.lordre de traitement des tches apriodiques ne dpend pas
delalgorithme gnralIl est possible de le combiner le traitement
avec un serveur avecun traitement en background (Temps de
rponse+,prdictabilit-)J. Pouiller Temps Rel 104 / 197Quelques
notions thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesServeur par scrutationAussi
appell pollingA chaque activation, traitement des tches en suspens
jusqupuisement de la capacit ou jusqu ce quil ny ait plus detches
en attenteSi aucune tche nest en attente ( lactivation ou parce que
ladernire tche a t traite) , le serveur se suspendimmdiatement et
perd sa capacit qui peut tre rutilise parles tches priodiquesQuand
une instance (un vnement) de tche apriodique arrive,elle attend
jusqu ce que la capacit du serveur soit disponible.Il est possible
de rendre la main au CPU si aucune tacheapriodique nest en attente
(TR des taches periodiques +,prdictabilit -)Dans le cas ou le
serveur la plus petite priorit, lalgorithmequivaut peu prs au
traitement en backgroundJ. Pouiller Temps Rel 105 / 197Quelques
notions thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesExempleA vide, avec
ordonnancement RM des tches priodiques :Tche Arrive Priode Capacit
DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de priodeS 0 5 2 Fin de
priode0ABS1ABS2ABS3ABS4ABS5ABS6ABS7ABS8ABS9ABS10ABS11ABS12ABS13ABS14ABS15ABS16ABS17ABS18ABS19ABS20ABSJ.
Pouiller Temps Rel 106 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleA vide, avec ordonnancement RM des tches
priodiques :Tche Arrive Priode Capacit DlaiA 0 20 3 Fin de priodeB
0 10 2 Fin de priodeS 0 5 2 Fin de
priode0ABS1ABS2ABS3ABS4ABS5ABS6ABS7ABS8ABS9ABS10ABS11ABS12ABS13ABS14ABS15ABS16ABS17ABS18ABS19ABS20ABSJ.
Pouiller Temps Rel 106 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleIdem avec les 3 tches apriodiques :Tche Arrive
Priode Capacit DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de priodeS 0
5 2 Fin de priode1 0 2 2 Aucune2 0 9 1 Aucune3 0 10 3
Aucune0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123J.
Pouiller Temps Rel 107 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleIdem avec les 3 tches apriodiques :Tche Arrive
Priode Capacit DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de priodeS 0
5 2 Fin de priode1 0 2 2 Aucune2 0 9 1 Aucune3 0 10 3
Aucune0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123J.
Pouiller Temps Rel 107 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleIdem avec les 3 tches apriodiques
:0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123TR1
= 5TR2 = 2TR3 = 7J. Pouiller Temps Rel 108 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesExempleIdem, en utilisant
les temps creux en plus :Tche Arrive Priode Capacit DlaiA 0 20 3
Fin de priodeB 0 10 2 Fin de priodeS 0 5 2 Fin de priode1 0 2 2
Aucune2 0 9 1 Aucune3 0 10 3
Aucune0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123J.
Pouiller Temps Rel 109 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleIdem, en utilisant les temps creux en plus :Tche
Arrive Priode Capacit DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de
priodeS 0 5 2 Fin de priode1 0 2 2 Aucune2 0 9 1 Aucune3 0 10 3
Aucune0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123J.
Pouiller Temps Rel 109 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleIdem, en utilisant les temps creux en plus
:0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123TR1
= 5TR2 = 1TR3 = 5J. Pouiller Temps Rel 110 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesLimitationLimitations du
serveur par scrutationperte de la capacit si aucune tche apriodique
en attentesi occurrence dune tche apriodique alors que le serveur
estsuspendu, il faut attendre la requte suivanteJ. Pouiller Temps
Rel 111 / 197Quelques notions thoriques Algorithmes priorit
statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesServeur diffrAussi appell serveur ajournableLa fausse
bonne ideMal gr, il provoque des erreur dordonnancementCas
dxecution dos dos du serveurJ. Pouiller Temps Rel 112 / 197Quelques
notions thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesExempleAvec ordonnancement
RM :Tche Arrive Priode Capacit DlaiA 0 7 2 Fin de priodeS 0 6 3 Fin
de priode1 21 0 6
Aucune0AS11AS12AS13AS14AS15AS16AS17AS18AS19AS110AS111AS112AS113AS114AS115AS116AS117AS118AS119AS120AS121AS122AS123AS124AS125AS126AS127AS128AS1J.
Pouiller Temps Rel 113 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleAvec ordonnancement RM :Tche Arrive Priode
Capacit DlaiA 0 7 2 Fin de priodeS 0 6 3 Fin de priode1 21 0 6
Aucune0AS11AS12AS13AS14AS15AS16AS17AS18AS19AS110AS111AS112AS113AS114AS115AS116AS117AS118AS119AS120AS121AS122AS123AS124AS125AS126AS127AS128AS1J.
Pouiller Temps Rel 113 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesServeur diffrTout de mme possible de lutiliser si :i
TPCiTilnUS +22US +1Grosso modo, on exige que le systme soit
ordonnancable avec unecapacit du serveur deux fois plus
importante.Dans le cas prcdant :27 0.286ln0.5+220.5+1=
ln1.250.22327 ln0.5+220.5+1J. Pouiller Temps Rel 114 / 197Quelques
notions thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesServeur diffrTout de mme
possible de lutiliser si :i TPCiTilnUS +22US +1Grosso modo, on
exige que le systme soit ordonnancable avec unecapacit du serveur
deux fois plus importante.Dans le cas prcdant :27
0.286ln0.5+220.5+1= ln1.250.22327 ln0.5+220.5+1J. Pouiller Temps
Rel 114 / 197Quelques notions thoriques Algorithmes priorit
statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesServeur sporadiqueAmliore le temps de rponse des tches
apriodiques sansdiminuer le taux dutilisation du processeur pour
les tchespriodiquesTrs utilis pour les IHM car permet une meilleure
exprienceutilisateurComme le serveur diffr maisNe retrouve pas sa
capacit priode xe, mais un instant derinitialisation gal la date
courante additionne de la priode derinitialisationLa capacit
retrouve est gale la capacit consommeJ. Pouiller Temps Rel 115 /
197Quelques notions thoriques Algorithmes priorit statique
Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleAvec ordonnancement RM :Tche Arrive Priode
Capacit DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de priodeS 0 5 2 Fin
de priode1 0 3 2 Aucune2 0 9 1 Aucune3 0 10 2
Aucune0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123J.
Pouiller Temps Rel 116 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleAvec ordonnancement RM :Tche Arrive Priode
Capacit DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de priodeS 0 5 2 Fin
de priode1 0 3 2 Aucune2 0 9 1 Aucune3 0 10 2
Aucune0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123J.
Pouiller Temps Rel 116 / 197Quelques notions thoriques Algorithmes
priorit statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleAvec ordonnancement RM
:0ABS1231ABS1232ABS1233ABS1234ABS1235ABS1236ABS1237ABS1238ABS1239ABS12310ABS12311ABS12312ABS12313ABS12314ABS12315ABS12316ABS12317ABS12318ABS12319ABS12320ABS123TR1
= 2TR2 = 1TR3 = 5J. Pouiller Temps Rel 117 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesSlack StealerOn alloue
miniLi(t ) priodes pour lxction des tcheapriodiquesOn recalcule
lalgorithme chaque activation dune tche(priodique ou apriodique)
dans le systmeJ. Pouiller Temps Rel 118 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesExempleTche Arrive Priode
Capacit DlaiA 0 20 3 Fin de priodeB 0 10 2 Fin de priodeS 0 5 2 Fin
de priode1 0 3 2 Aucune2 0 9 1 Aucune3 0 10 2 AucuneJ. Pouiller
Temps Rel 119 / 197Quelques notions thoriques Algorithmes priorit
statique Algorithmes priorit dynamique Serveurs de tches
apriodiquesExempleAvec ordonnancement RM
:0AB1231AB1232AB1233AB1234AB1235AB1236AB1237AB1238AB1239AB12310AB12311AB12312AB12313AB12314AB12315AB12316AB12317AB12318AB12319AB12320AB123LA(2)
= 183 = 15LB(2) = 80 = 8LA(9) = 110 = 11LB(9) = 10 = 1LA(10) = 100
= 10LB(10) = 102 = 8J. Pouiller Temps Rel 120 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesExempleAvec ordonnancement
RM
:0AB1231AB1232AB1233AB1234AB1235AB1236AB1237AB1238AB1239AB12310AB12311AB12312AB12313AB12314AB12315AB12316AB12317AB12318AB12319AB12320AB123TR1
= 2TR2 = 1TR3 = 3J. Pouiller Temps Rel 121 / 197Quelques notions
thoriques Algorithmes priorit statique Algorithmes priorit
dynamique Serveurs de tches apriodiquesOrdonnancemnet
conjointAlgorithme fonctionnant avec EDF et des tche apriodique
avecdes dlais critiquesOn ordonnance les tches apriodique de la mme
manire queles tche priodiquesAvant daccepter la tche, il faut vrier
le critre dacceptabilit(ce qui correspond valuer lalgorithme hors
ligne)J. Pouiller Temps Rel 122 / 197
