View
256
Download
0
Category
Preview:
Citation preview
7/27/2019 Slides Ordonnancement Temps Reel
1/108
Chapitre : Les
Ordonnancements Temps rel
3 me Systmes Embarqus- ISIBen Fradj Hanene
Module: Conception de Systmestemps-rel
7/27/2019 Slides Ordonnancement Temps Reel
2/108
20/10/2013 Ben Fradj Hanene 2
Dfinition
Ordonnanceur Planificateurattribuer la ressource processeur aux tches au cours
du temps, selon une politique dordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
3/108
20/10/2013 Ben Fradj Hanene 3
Ordonnancement temps rel
lexcution des tches est soumise des contraintes temporelles cadence temps de rponse (chance, bout en bout)
le respect de ces contraintes temporelles est important
contraintes strictes, temps rel dur ( hard ) contraintes relatives, temps rel mou ( soft )
lordonnancement doit permettre le respect de ces contraintes
lordonnancement doit tre certifiable : la preuve du respect de
cescontraintes doit pouvoir tre apporte priori
ordonnanabilit, schedulability
7/27/2019 Slides Ordonnancement Temps Reel
4/108
20/10/2013 Ben Fradj Hanene 4
Les Types dordonnancement
Ordonnancement hors ligne
la squence dordonnancement estpr-calcule avant lexcution effective
lexcution, lordonnanceur est un simple squenceur( cyclic scheduler )
mise en uvre efficace mais rigidit
Ordonnancement en ligne
les dcisions dordonnancement sont prises au cours de lexcution
lexcution, lordonnanceur implmente un algorithme dordonnancement
surcots de mise en oeuvre mais flexibilit
7/27/2019 Slides Ordonnancement Temps Reel
5/108
20/10/2013 Ben Fradj Hanene 5
Ordonnancement non premptif / premptif
lexcution de la tche en cours ne peut tre interrompue
la tche en courspeutperdre involontairement le processeurau profit dune autre tche (juge plus urgente)
hybride
selon que les tches (ou des sections de tche) sont ou non
premptibles
Les Types dordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
6/108
20/10/2013 Ben Fradj Hanene 6
1. politique premier arriv, premier servi ,
2. politique plus court d abord ,
3. politique du tourniquet, round robin ,
4. politique conduite par lapriorit attache chaque tche
Priorits fixes (statiques) / dynamiques
indpendantes du temps fixes priori
voluent avec le tempssurcot lexcution
Les Types dordonnancement
Quasi tous les excutifs du march
7/27/2019 Slides Ordonnancement Temps Reel
7/108
20/10/2013 Ben Fradj Hanene 7
Temps partag avec politique du tourniquet (round robin):
- Tranche de temps de taille fixe (quantum)- Pas de prise en compte des contraintes de temps- souvent utilis en complment du mcanisme de priorit pour
les tches de priorits gales (quit entre ces tches)
Les Types dordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
8/108
Les ordonnancements
priorits: Plan Caractristiques des tches temps rel
Ordonnancement premptif priorit fixe Rate Monotonic (RM) Deadline Monotonic (DM)
Ordonnancements premptif priorit dynamique
Earliest deadline first (EDF)Vrification dordonnanabilit
7/27/2019 Slides Ordonnancement Temps Reel
9/108
20/10/2013 Ben Fradj Hanene 9
Les tches temps rel
Tches priodiques elles sont actives intervalles
de temps rguliers
Tches apriodiqueselles sont actives des instants alatoires
Tches sporadiquesune borne minimale de la dure sparant 2activations successives est connues
C i i d h
7/27/2019 Slides Ordonnancement Temps Reel
10/108
20/10/2013 Ben Fradj Hanene 10
Caractristiques des tches temps
rel
Oi : date dactivation initiale, phase initiale, offset Ci : dure dexcution sans premption Ti : priode dactivation Di : dlai critique, chance relative
Oi = Oj, (i,j) : tches synchrones Di = Ti : tche chance sur requte
Di ? Ti : tche chance arbitraire
7/27/2019 Slides Ordonnancement Temps Reel
11/108
20/10/2013 Ben Fradj Hanene 11
Ordo. premptif priorits fixes : RM
1. RM, Rate Monotonic
-Pour tches priodiques- Dfinition [Liu & Layland, 1973]
la priorit dune tche est inversement proportionnelle sa
priode (conflits rsolus arbitrairement)
- Proprit :
- optimal dans la classe des algorithmes priorits fixes,pour des configurations de tches priodiques, synchrones, chance sur requte et indpendantes
- l'utilisation de la priode limite l'utilisation aux seules tches chance sur requte (Si Di Pi)
7/27/2019 Slides Ordonnancement Temps Reel
12/108
20/10/2013 Ben Fradj Hanene 12
Ordo. premptif priorits fixes: RM
7/27/2019 Slides Ordonnancement Temps Reel
13/108
20/10/2013 Ben Fradj Hanene 13
Pour tches priodiques Dfinition [Leung & Whitehead, 1985]
La priorit dune tche est inversementproportionnelle son chance relative (conflitsrsolus arbitrairement)
Proprit
Optimal dans la classe des algorithmes priorits fixes pour destches priodiques indpendantes chance priode quivalent RMA dans le cas de tches chance sur
requte, meilleur dans les autres cas
Ordo. premptif priorits fixes: DM
2. DM, Deadline Monotonic
7/27/2019 Slides Ordonnancement Temps Reel
14/108
20/10/2013 Ben Fradj Hanene 14
T1(r0 = 0, C=3, D=7, P=20),T2 (r0 = 0, C=2, D=4, P=5),T3 (r0 = 0, C=2, D=9, P=10)
Ordo. premptif priorits fixes: DM
Exemple
O d if i i d i
7/27/2019 Slides Ordonnancement Temps Reel
15/108
20/10/2013 Ben Fradj Hanene 15
Ordo. premptif priorits dynamiques
: EDF
EDF, Earliest Deadline First
Dfinition : [Liu & Layland, 1973]
un instant donn, la tche la plus prioritaire (parmi
les tches prtes) est: celle dont lchance est laplus proche
Proprit : optimal dans la classe des
algorithmes priorits dynamiques, pour desconfigurations de tches indpendantespriodiques, chance priode et
O d if i i d i
7/27/2019 Slides Ordonnancement Temps Reel
16/108
20/10/2013 Ben Fradj Hanene 16
Ordo. premptif priorits dynamiques
: EDF
O d if i i d i
7/27/2019 Slides Ordonnancement Temps Reel
17/108
20/10/2013 Ben Fradj Hanene 17
Exercice :
Ordo. premptif priorits dynamiques
: EDF
7/27/2019 Slides Ordonnancement Temps Reel
18/108
20/10/2013 Ben Fradj Hanene 18
DfinitionLaxit: temps restant entre la fin d excution de la tche et son dlai critique,
Lmax = D C
un instant donn, la tche la plus prioritaire (parmi les tches prtes)est celle dont la laxit est la plus petite
Proprit
optimalit idem EDmais, nombre de premptions engendres suprieur
Ordo. premptif priorits dynamiques
: Least Laxity (LL)
Least Laxity (LL)
M dl d h
7/27/2019 Slides Ordonnancement Temps Reel
19/108
20/10/2013 Ben Fradj Hanene 19
4 temps d excution restant C(t) : C(t) = Cmax - Cexcut
4 dlai critique dynamique D(t) : temps restant avant la prochaine chance, D(t) = d - t
4 laxit dynamique L(t) : temps avant le dbut d excution de la tche, L(t) = D(t) - C(t) = d - t - C(t)
t
r
Diagramme temporel dexcution
D
d
D(t)
t
L(t)
C(t)
Cmax
Pendant l'excution de la tche ( un instant donn t)
Modle de tches : paramtresdynamiques
7/27/2019 Slides Ordonnancement Temps Reel
20/108
20/10/2013 Ben Fradj Hanene 20
Ordo. premptif priorits dynamiques
: Least Laxity (LL)
T1 (r0 = 0, C=3, , D=7, P=20), T2 (r0 = 0, C=2, D=4, P=5),T3 (r0 = 0, C=1, D=8, P=10)
7/27/2019 Slides Ordonnancement Temps Reel
21/108
Les ordonnancements
priorits: Plan Caractristiques des tches temps rel
Ordonnancement premptif priorit fixe Rate Monotonic (RM) Deadline Monotonic (DM)
Ordonnancements premptif priorit dynamique
Earliest deadline first (EDF)Vrification dordonnanabilit
7/27/2019 Slides Ordonnancement Temps Reel
22/108
20/10/2013 Ben Fradj Hanene 22
OrdonnanabilitRle Formules mathmatiques ou algorithmes permettant de vrifier
(prouver) que les tches respecteront leurs contraintes de tempsClassification
Vrification hors-ligne (avant excution): statique Critres analytiques calculables (CN, CS, CNS)
Simulation sur une dure finie : [0,PPCM (Ti)] si tches synchrones [min(Ok),max(Oi)+ 2*PPCM (Ti)]
Cibles = systmes temps-rel strict
Vrification en-ligne (pendant lexcution): dynamique Tests dacceptation en-ligne pour savoir si on accepte de nouvellestches
Cibles = systmes temps-rel souple
7/27/2019 Slides Ordonnancement Temps Reel
23/108
20/10/2013 Ben Fradj Hanene 23
Donnes dentre des mthodes de verification : modledu systme
Connaissance des informations sur les tches (modlede tches)
Arrive des tches: priodique, sporadique, apriodique (datesdarrives) Synchronisations : prcdences, exclusions entre tches Temps dexcution au pire-cas (WCET)
Sorties
Verdict sur le respect des contraintes de temps pourun algorithmedordonnancement donn
Ordonnanabilit
7/27/2019 Slides Ordonnancement Temps Reel
24/108
20/10/2013 Ben Fradj Hanene 24
Vrification : par simulation
Priodicit des tches ordonnancementcyclique (pas la peine de simuler linfini)
Dure de la priode dtude (hyperpriode)
Tches synchrones : [0,PPCM(Pi)] Tches chelonnes (au moins un offset Oi non nul)[min(Oi), max(Oi,Oj+Dj) + 2 * PPCM(Pi)]
Evaluation
Valide quel que soit lalgorithme dordonnancement Priode dtude peut tre trs longue selon lesrelations entre priodes
Adapt aux ordonnancements hors-ligne
7/27/2019 Slides Ordonnancement Temps Reel
25/108
20/10/2013 Ben Fradj Hanene 25
Condition ncessaire C Il faut que C soit vrifie pour que les contraintes de temps
soient respectes (systme faisable) C non vrifie systme non faisable C vrifie systme peut tre faisable (ou pas)
Condition suffisante Il suffit que C soit vrifie pour que le systme soit faisable C vrifie systme est faisable ( coup sr)
C non vrifie systme peut tre faisable (ou pas)
Condition ncessaire et suffisante C vrifie quivalent montrer la faisabilit du systme
Vrification : Critres analytiques
7/27/2019 Slides Ordonnancement Temps Reel
26/108
20/10/2013 Ben Fradj Hanene 26
Utilisation du Taux dutilisation du processeur (charge du proceseurpar N tches
Condition ncessaire dordonnanabilit : U 1
Cette condition nest pas une condition suffisante(pas pour tous les ordonnancements)
N
ii
i
T
cU
1
Vrification : Critres analytiques
7/27/2019 Slides Ordonnancement Temps Reel
27/108
20/10/2013 Ben Fradj Hanene 27
Vrification : Critres analytiques
1.Ordonnancement RM : pour que N tches soient ordonnanables Condition suffisante (CS)
Si condition vrifie avec Ci= WCETi de la tche alors la condition estvrifie avec Ci< WCETi
sapplique aussi quand les tches ne sont pas synchrones
Pour 3 tches: U 0,779
Pour n tches U (N : U 0,69
7/27/2019 Slides Ordonnancement Temps Reel
28/108
20/10/2013 Ben Fradj Hanene 28
Exercice: ces trois tches sont elles ordonnanables
selon la technique RM ?T1 (r0 = 0, C=3, P=20),
T2 (r0 = 0, C=2, P=5),
T3 (r0 = 0, C=2, P=10)
Vrification : Critres analytiques
7/27/2019 Slides Ordonnancement Temps Reel
29/108
20/10/2013 Ben Fradj Hanene 29
2. Ordonnancement DM : pour que N tches soient ordonnanables
Condition suffisante (CS)
12
1
1
N
N
ii
iN
D
cU
Vrification : Critres analytiques
7/27/2019 Slides Ordonnancement Temps Reel
30/108
20/10/2013 Ben Fradj Hanene 30
Exercice: ces trois tches sont elles ordonnanables
selon la technique DM (meme exemple)? T1 (r0 = 0, C=3, D=7, P=20),
T2 (r0 = 0, C=2, D=4, P=5),
T3 (r0 = 0, C=2, D=9, P=10)
Vrification : Critres analytiques
7/27/2019 Slides Ordonnancement Temps Reel
31/108
20/10/2013 Ben Fradj Hanene 31
3. Ordonnanancement EDF et LL
Vrification : Critres analytiques
7/27/2019 Slides Ordonnancement Temps Reel
32/108
20/10/2013 Ben Fradj Hanene 32
Vrification : Critres analytiques
Exemple
7/27/2019 Slides Ordonnancement Temps Reel
33/108
20/10/2013 Ben Fradj Hanene 33
Exercice: ces trois tches sont elles ordonnanables selon latechnique EDF ?
T1 (r0 = 0, C=3, D=7, P=20),
T2 (r0 = 0, C=2, D=4, P=5),
T3 (r0 = 0, C=1, D=8, P=10)
Vrification : Critres analytiques
V ifi ti Pi t d
7/27/2019 Slides Ordonnancement Temps Reel
34/108
20/10/2013 Ben Fradj Hanene 34
Response time analysis (RTA, analyse de temps derponse)
Applicable pour tous les ordonnancements prioritstatique, quel que soit lassignation des priorits (RM,
DM, autre) Condition ncessaire et suffisante
Vrification : Pire temps de rponse
V ifi ti Pi t d
7/27/2019 Slides Ordonnancement Temps Reel
35/108
20/10/2013 Ben Fradj Hanene 35
Vrification : Pire temps de rponse
Vrification : Pire temps de rponse
7/27/2019 Slides Ordonnancement Temps Reel
36/108
20/10/2013 Ben Fradj Hanene 36
Vrification : Pire temps de rponse
7/27/2019 Slides Ordonnancement Temps Reel
37/108
20/10/2013 Ben Fradj Hanene 37
Algorithme de calcul des Ri (itratif)
Quand la srie converge, on a calcul le temps de
rponse Ri Le systme est ordonnanable quand Ri Di
Vrification : Pire temps de rponse
Vrification : Pire temps de rponse
7/27/2019 Slides Ordonnancement Temps Reel
38/108
20/10/2013 Ben Fradj Hanene 38
Vrification : Pire temps de rponse
Exercice: ces trois tches sontelles ordonnanables selon cettetechnique dordonnancement ?
Vrification : Pire temps de rponse
7/27/2019 Slides Ordonnancement Temps Reel
39/108
20/10/2013 Ben Fradj Hanene 39
Vrification : Pire temps de rponse
Vrification : Pire temps de rponse
7/27/2019 Slides Ordonnancement Temps Reel
40/108
20/10/2013 Ben Fradj Hanene 40
Vrification : Pire temps de rponse
temps de rponse de la tche
temps de rponse de la tche
temps de rponse de la tche
7/27/2019 Slides Ordonnancement Temps Reel
41/108
Les ordonnancements
priorits: Plan Caractristiques des tches temps rel Ordonnancement premptif priorit fixe
Rate Monotonic (RM) Deadline Monotonic (DM)
Ordonnancements premptif priorit dynamique Earliest deadline first (EDF)
Vrification dordonnanabilit Ordonnancement de tches apriodique Ordonnancement de tches en prsence de ressourcespartages
7/27/2019 Slides Ordonnancement Temps Reel
42/108
20/10/2013 Ben Fradj Hanene 42
Ordonnancement des tches
apriodique
se distinguent des tches priodiques par le faitque l'on ne connat pas l'instant d'arrive de larequte de rveil
contraintes temporelles strictes ou relatives
buts atteindre : si contraintes relatives : minimiser le temps de
rponse si contraintes strictes : maximiser le nombre de
tches acceptes en respectant leurs contraintes 2 grandes catgories de traitement
traitement en arrire-plan traitement par serveurs
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
43/108
20/10/2013 Ben Fradj Hanene 43
Tches apriodiques contraintesrelatives
traitement d'arrire-plan le plus simple, mais le moins performant
tches apriodiques ordonnances quand le
processeur est oisif si plusieurs tches attendent, elles sont
traites en mode FIFO
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
44/108
20/10/2013 Ben Fradj Hanene 44
Tp1 (r0=0, C=2, P=5), Tp2 (r0=0, C=2, P=10)Ta3 (r=4, C=2),Ta4 (r=10, C=1),Ta5 (r=11, C=2)
Tches apriodiques contraintesrelatives
exemple de traitement d'arrire-plan
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
45/108
20/10/2013 Ben Fradj Hanene 45
Traitement par serveur un serveur est une tche priodique cre spcialement
pour prendre en compte les tches apriodiques serveur caractris par :
sa priode son temps d'excution : capacit du serveur serveur gnralement ordonnanc suivant le mme algorithme
que les autres tches priodiques une fois actif, le serveur sert les tches apriodiques dans la
limite de sa capacit. L'ordre de traitement des tchesapriodiques ne dpend pas de l'algorithme gnral
Tches apriodiques contraintesrelatives
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
46/108
20/10/2013 Ben Fradj Hanene 46
Serveurs par scrutation (polling) chaque activation, traitement des tches
jusqu' puisement de la capacit ou jusqu'
ce qu'il n'y ait plus de tches en attente si aucune tche n'est en attente ( l'activation
ou parce que la dernire tche a t traite) ,le serveur se suspend immdiatement et perdsa capacit qui peut tre rutilise par lestches priodiques
Tches apriodiques contraintesrelatives
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
47/108
20/10/2013 Ben Fradj Hanene 47
exemple de serveur par scrutation (ordonnancement RM)
2 tches priodiques : Tp1 (r0=0, C=3, P=20) Tp2 (r0=0, C=2, P=10) serveur : Tps(r0=0, C=2, P=5) tches apriodiques : Ta3 (r=4, C=2), Ta4 (r=10, C=1), Ta5 (r =11, C=2)
Tches apriodiques contraintesrelatives
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
48/108
20/10/2013 Ben Fradj Hanene 48
2 approches : les traiter comme de tches priodiques avec une
pseudo-priode reprsentant l'intervalle minimal entre2 occurrences utilis dans le cas RM mais difficile d'valuer la pseudo-priode engendre une sous-utilisation du processeur
ordonnancer les tches en EDF. A chaque nouvelletche apriodique, faire tourner une "routine degarantie" pour vrifier que toutes les contraintes
temporelles seront respectes. Si non, refuser latche. 2 politiques d'acceptation dynamique favorise les tches priodiques
Tches apriodiques contraintesstrictes
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
49/108
20/10/2013 Ben Fradj Hanene 49
acceptation dans les temps creux d'une squence rigidede tches ordonnancement EDF des tches priodiques les tches apriodiques acceptes sont ordonnances dans les
temps creux des tches priodiques (~ mthode d'arrire-plan)selon l'algorithme EDF
routine de garantie (au rveil d'une tche apriodique):1) teste l'existence d'un temps creux suffisant entre le rveil et
l'chance de la tche apriodique)2) vrifie que l'acceptation de la nouvelle tche ne remet pas en cause
le respect des contraintes temporelles des autres tchesapriodiques dj acceptes et non encore terminessi OK, la tche est ajoute la liste des tches apriodiques
Tches apriodiques contraintesstrictes
Tches apriodiques contraintes
7/27/2019 Slides Ordonnancement Temps Reel
50/108
20/10/2013 Ben Fradj Hanene 50
Tches apriodiques contraintes
strictes
exemple de l'acceptation dans les temps creux
Tp1 (r0=0, C=3, D=7, P=20), Tp2 (r0=0, C=2, D=4, P=5),Tp3 (r0=0, C=1, D=8, P=10)
Ta4 (r=4, C=2, d=10), Ta5 (r=10, C=1, d=18), Ta6 (r=11, C=2, d=16)
7/27/2019 Slides Ordonnancement Temps Reel
51/108
Les ordonnancements
priorits: Plan Caractristiques des tches temps rel Ordonnancement premptif priorit fixe
Rate Monotonic (RM) Deadline Monotonic (DM)
Ordonnancements premptif priorit dynamique Earliest deadline first (EDF)
Vrification dordonnanabilit
Ordonnancement de tches apriodique Ordonnancement de tches en prsence de ressourcespartages
O d d
7/27/2019 Slides Ordonnancement Temps Reel
52/108
20/10/2013 Ben Fradj Hanene 52
une ressource critique ne peut: tre utilise simultanment par plusieurs tches tre rquisitionne par une autre tche accs en exclusion mutuelle
notion de section critique squence d'instructions pendant lesquelles on utilise
une ressource critique sans problme dans le cas d'un ordonnancement non
premptif, mais c'est rarement le cas dans unenvironnement temps rel valuation du temps derponse trs difficile, sinon impossible
Ordo. en prsence de ressources partages
O d d
7/27/2019 Slides Ordonnancement Temps Reel
53/108
20/10/2013 Ben Fradj Hanene 53
ordonnancement premptif: ajout dun protocole de gestion desressources
1. phnomne dinterblocage (deadlock)
Ordo. en prsence de ressources partages
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
54/108
20/10/2013 Ben Fradj Hanene 54
Ordo. en prsence de ressources partages
2. phnomne dinversion de priorit
phnomne d la prsence simultane de priorits fixes et deressources accs exclusifdans un environnement premptif
Inversion de priorit non prvu entre T1 et T3 peut engendrer un non respectdchances (grave si temps rel stricte)
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
55/108
20/10/2013 Ben Fradj Hanene 55
le problme de lordonnancement de tches priodiquesen prsence de ressources critiques est NP-difficile.
il nexiste pas d algorithme dordonnancement en ligneoptimal
Protocole hritage de priorit,
Protocole priorit plafonne
Ordo. en prsence de ressources partages
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
56/108
20/10/2013 Ben Fradj Hanene 56
Ordo. en prsence de ressources partages
1. Protocole hritage de priorit, Priority Inheritance Protocol
- la tche qui possde la ressource critique prend (temporairement) laprioritde la tche en attente de cette mme ressource, si prio() > prio()
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
57/108
20/10/2013 Ben Fradj Hanene 57
Proprits :
- ne prvient pas les interblocages- permet dvaluer une borne suprieure (et
pessimiste) du temps de blocage au pire Bi des
tches
1. Protocole hritage de priorit, Priority Inheritance Protocol
Ordo. en prsence de ressources partages
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
58/108
20/10/2013 Ben Fradj Hanene 58
Ordo. en prsence de ressources partages
Dfinitions Priorit plafond(priority ceiling) dune
ressource (R) = priorit maximale des
tches qui lutilisent Priorit plafond courante (current priority
ceiling, ou ceiling) un instant t : (t) =maximum des priorits plafond des
ressources utilises en t
2. Protocole priorit plafonne, Priority Ceiling Protocol
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
59/108
20/10/2013 Ben Fradj Hanene 59
Ordo. en prsence de ressources partages
2. Protocole priorit plafonne, Priority Ceiling Protocol
Principe
1. chaque ressource R possde une priorit plafond associe
(R)= max des priorits des tches susceptibles dy accder
2. une tche T ne peut accder une ressource R que si sapriorit est suprieure aux priorits plafond des ressources
actuellement prises (t)
3.si la tche T bloque une tche T (plus prioritaire), T hritede la priorit de T
O d d t
7/27/2019 Slides Ordonnancement Temps Reel
60/108
20/10/2013 Ben Fradj Hanene 60
Exemple :
prio T1 > prio T2 > prio T3 partage de R entre T1, T3,P(R)= prio T1T2 utilise une ressource R, P(R)= prio T2
T3 commence son excution, rveil de T2 puis rveil de T1
Ordo. en prsence de ressources partages
T3
T2
T1
Prio
(t)1
2
T3 retrouve sapriorit nominaleT1 sexcute(avant T2, moinsprio
Bloqubien que Rlibre
T1 est bloquT3 hrite de la priorit de T1
Ordo en prsence de ressources partages
7/27/2019 Slides Ordonnancement Temps Reel
61/108
20/10/2013 Ben Fradj Hanene 61
Proprits :
- prvient les interblocages- permet dvaluer une borne suprieure (moins
pessimiste) du temps de blocage au pire Bi
des tches
2. Protocole priorit plafonne, Priority Ceiling Protocol
Ordo. en prsence de ressources partages
7/27/2019 Slides Ordonnancement Temps Reel
62/108
Exploration de Mars
Mission Pathfinder(NASA - juillet 1997)
La mission Pathfinder
7/27/2019 Slides Ordonnancement Temps Reel
63/108
20/10/2013 Ben Fradj Hanene 63
La mission Pathfinder
sonde sur Mars, arrive le 4 juillet 1997 robot mobile Sojourner charg dediffrentes tches:
Photos
relevs mto
prlvements
poids : 11.5kg
vitesse : 24m/h
puissance totale : 30W
liaison UHF avec la sonde Pathfinder
bug dans la gestion des ressourcescritiques perte de donnes importantes
Architecture matrielle
7/27/2019 Slides Ordonnancement Temps Reel
64/108
20/10/2013 Ben Fradj Hanene 64
Architecture matrielle
Processeur Mmoires
Sonde
Pathfinder
Interface 1 Interface 2
bus VMEInterface bus
bus 1553
interface 1coupleur interface 2 interface 3
interface 4
moteurs vannes capteur
solai re
analyseur
toi les
bus 1553
interface 5coupleur interface 6 interface 7
acclromtrealtimtreenregistreur
mto (ASI/MET)
Robot mobi le
Sojourner
camra
radio
MonoprocesseurRS6000 (RISC deIBM)
7/27/2019 Slides Ordonnancement Temps Reel
65/108
20/10/2013 Ben Fradj Hanene 65
Spcification fonctionnelle
le systme de gestion de la sonde communiqueavec l'extrieur par: la carte radio pour les liaisons avec la terre la carte de liaison avec la camra
l'interface avec le bus 1553 pour les autres capteurs/actionneurs
Architecture logicielle
7/27/2019 Slides Ordonnancement Temps Reel
66/108
20/10/2013 Ben Fradj Hanene 66
Architecture logicielle
multitche gre par le noyau Vxworks (WindRiver)
25 tches
priodiques (ex. : gestion du bus 1553) apriodiques (ex. : analyse des erreurs)
communication et synchronisation par des files demessages
suivant les phases de la mission (volinterplantaire, aterrissage, exploration par lerobot), toutes les tches ne sont pas utiles
Caractristiques des tches
7/27/2019 Slides Ordonnancement Temps Reel
67/108
20/10/2013 Ben Fradj Hanene 67
Caractristiques des tches
Liste des tches et priorits relatives :
7/27/2019 Slides Ordonnancement Temps Reel
68/108
20/10/2013 Ben Fradj Hanene 68
Architecture logicielle Architecture en tches
Utilisation du bus 1553
7/27/2019 Slides Ordonnancement Temps Reel
69/108
20/10/2013 Ben Fradj Hanene 69
Utilisation du bus 1553 la gestion du bus est pilote par une horloge 8 Hz (125ms)
2 tches pour rguler le transfert des donnes
1. ORDO_BUS priorit maximale vrifie que le transfert des donnes a tcorrectement effectu et prpare le transfert suivant
2. DISTRIBUTION_DONNES
2 me priorit collecte les donnes sur le bus et les place dans lammoire tampon
Caractristiques des tches
7/27/2019 Slides Ordonnancement Temps Reel
70/108
20/10/2013 Ben Fradj Hanene 70
Caractristiques des tches
pour CMTO = 2, U=0.72 et pour CMTO = 3, U=0.725 analyse Rate Monotonic pourrait s'appliquer (URM=0.729), mais partage de la ressource MMOIRE_TAMPON analyse dtaille
7/27/2019 Slides Ordonnancement Temps Reel
71/108
20/10/2013 Ben Fradj Hanene 71
Recherche dordonnacement
priode d'tude thorique : 5000msmais on peut se contenter d'tudier sur 250ms
en considrant que les tches MESURES etMTO viennent de se terminer et en se mettantsur la priode suivante
tude des cas CMTO = 2 et CMTO = 3
3.5. Exemple : Mission Mars
7/27/2019 Slides Ordonnancement Temps Reel
72/108
20/10/2013 Ben Fradj Hanene 72
: Tche sans ressource
: Tche avec ressource
Lgende des diagrammes de Gantt
R
R: Demande de ressource
: Libration de ressource
Simulat ions
3.5. Exemple : Mission MarsPathfinder
Diagramme d'excution des tches pour Cmto = 2
7/27/2019 Slides Ordonnancement Temps Reel
73/108
20/10/2013 Ben Fradj Hanene 73
inversion de priori t
inversion de priori t
RR
RRDISTRIBUTION
DONNEES
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
tORDO
BUS
TACHE
RADIO
TACHE
CAMERA
TACHE
M
ESURES
TACHE
METEO
: Tche sans ressource : Tche avec ressource
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
t
R
R
R R
R R
RR R
R
RR RR
RR
TACHE
PILOTAGE
alarmeDiagramme d'excution pour Cmto = 3
7/27/2019 Slides Ordonnancement Temps Reel
74/108
20/10/2013 Ben Fradj Hanene 74
alarme
R
R
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
t
?
inversion de priorit
inversion de priorit
R R
R R
RRR
R
R
RDISTRIB
UTION
DONNEE
S
ORDO
BUS
TACHE
RADIO
TACHE
CAMERA
TACHE
MESURE
S
TACHE
METEO
TACHE
PILOTAGE
7/27/2019 Slides Ordonnancement Temps Reel
75/108
20/10/2013 Ben Fradj Hanene 75
7/27/2019 Slides Ordonnancement Temps Reel
76/108
Les ordonnancements
priorits: Plan Caractristiques des tches temps rel Ordonnancement premptif priorit fixe
Rate Monotonic (RM) Deadline Monotonic (DM)
Ordonnancements premptif priorit dynamique Earliest deadline first (EDF)
Vrification dordonnanabilit Ordonnancement de tches apriodique
Ordonnancement de tches en prsence de ressources partagesOrdonnancement de tches dpendantes Ordonnancement de tches sur une architecture multiprocesseur
7/27/2019 Slides Ordonnancement Temps Reel
77/108
20/10/2013 Ben Fradj Hanene 77
Contraintes de prcdences
Contraintes de prcdence sur l'ordre d'excution des tches les unes par
rapport aux autres gnralement dcrites par un graphe
Ja < Jb indique que la tche Ja est un prdcesseur de Jb Ja Jb indique que la tche Ja est un prdcesseur
immdiat de Jb
C
7/27/2019 Slides Ordonnancement Temps Reel
78/108
20/10/2013 Ben Fradj Hanene 78
Contraintes de prcdences
Contraintes de prcdence sur l'ordre d'excution des tches les unes par
rapport aux autres gnralement dcrites par un graphe
Ja < Jb indique que la tche Ja est un prdcesseur de Jb Ja Jb indique que la tche Ja est un prdcesseur
immdiat de Jb
J1 < J2J1 J2J1 < J4J1 J4
C i d d
7/27/2019 Slides Ordonnancement Temps Reel
79/108
20/10/2013 Ben Fradj Hanene 79
8 tches : 2 acquisitions 2 traitements image analyse de forme analyse des diffrences calcul de hauteur reconnaissance finale
Contraintes de prcdences
Tches avec des contraintes de
7/27/2019 Slides Ordonnancement Temps Reel
80/108
20/10/2013 Ben Fradj Hanene 80
Tches avec des contraintes deprcdences
ici, seulement prcdence simple si Ti est priodique de priode Pi, alors Tj l'est aussi et Pj = Pi
principe de l'tablissement de l'ordonnancement :
transformer l'ensemble des tches dpendantes en unensemble de tches indpendantes que l'on ordonnancerapar un algorithme classique
par des modifications des paramtres des tches si Ti Tj alors la rgle de transformation doit respecter
rj ri
Prioi > Prioj validation de l'ordonnanabilit selon des critres utiliss pour
des tches indpendantes
Ordonnancement de tches
7/27/2019 Slides Ordonnancement Temps Reel
81/108
20/10/2013 Ben Fradj Hanene 81
Ordonnancement de tchesdpendantes
Contraintes de prcdence et DeadlineMonotonic la transformation s'opre hors ligne sur la
date de rveil et sur les chances r*i = Max{ri, r*j} pour tous les j tels que Tj Ti
D*i = Max{Di, D*j} pour tous les j tels que Tj Ti
si Ti Tj alors Prioi > Prioj dans le respect de la
rgle d'affectation des priorits par DM
Ordonnancement de tches
7/27/2019 Slides Ordonnancement Temps Reel
82/108
20/10/2013 Ben Fradj Hanene 82
Ordonnancement de tchesdpendantes
contraintes de prcdence et EDF modification des chances de faon ce qu'une
tche ait toujours un di infrieur celui de sessuccesseurs (algorithme de Chetto et al.)
une tche ne doit tre activable que si tous sesprdcesseurs ont termin leur excution
modification de la date de rveil et de l'chance r*i = Max{ri, Max{r*j + Cj}} pour tous les j tels que Tj Ti d*i = Min{di, Min{d*j - Cj}} pour tous les j tels que Ti Tj on itre sur les prdcesseurs et successeurs immdiats on commence les calculs par les tches qui n'ont pas de
prdcesseurs pour le calcul des r et par les tches qui n'ontpas de successeur pour le calcul des d
Ordonnancement de tches
7/27/2019 Slides Ordonnancement Temps Reel
83/108
20/10/2013 Ben Fradj Hanene 83
Ordonnancement de tchesdpendantes
Paramtres des tches EarliestDeadline
tche ri Ci di ri* Di*
T1 0 1 5
T2 5 2 7T3 0 2 5
T4 0 1 10
T5 0 3 12
T1
T5
T4
T3
T2
T1 na pas de prdcesseur
r1*=0
0
T2 na pas de prdcesseur
r2*=5
5
T3 a T1 pour prdcesseurr*3 = Max(r3, r*1+C1)
= Max(0,1)= 1
1
T4 a T1 et T2 pour prdcesseursr*4 = Max(r4, r*1+C1, r*2+C2)= Max(0,1, 7)= 7
7
T5 a T3 et T4 pour prdcesseursr*5 = Max(r5, r*3+C3, r*4+C4)= Max(0, 3, 8)= 8
8
Ordonnancement de tches
7/27/2019 Slides Ordonnancement Temps Reel
84/108
20/10/2013 Ben Fradj Hanene 84
T1
T5
T4
T3
T2
T5 n'a pas de successeurd*5 = 12
Paramtres des tches EarliestDeadline
tche ri Ci di ri* Di*
T1 0 1 5T2 5 2 7
T3 0 2 5
T4 0 1 10
T5 0 3 12
05
1
7
8 12
T4 a T5 pour successeurd*4 = Min(d4, d*5-C5)
= Min(10, 9)= 9
9
T3 a T5 pour successeurd*3 = Min(d3, d*5-C5)= Min(5, 9)= 5
5
T2 a T4 pour successeurd*2 = Min(d2, d*4-C4)= Min(7, 8) = 7
7
T1 a T3 et T4 pour successeursd*1 = Min(d1, d*3-C3, d*4-C4)
= Min(5, 3, 8) = 3
3
Ordonnancement de tchesdpendantes
Ordonnancement de tches
7/27/2019 Slides Ordonnancement Temps Reel
85/108
20/10/2013 Ben Fradj Hanene 85
Paramtres des tches EarliestDeadline
tche ri Ci di ri* Di*
T1 0 1 5
T2 5 2 7
T3 0 2 5T4 0 1 10
T5 0 3 12
0
5
17
8 12
95
7
3
Ordonnancement de tchesdpendantes
7/27/2019 Slides Ordonnancement Temps Reel
86/108
Les ordonnancements
priorits: Plan Caractristiques des tches temps rel Ordonnancement premptif priorit fixe
Rate Monotonic (RM) Deadline Monotonic (DM)
Ordonnancements premptif priorit dynamique Earliest deadline first (EDF)
Vrification dordonnanabilit Ordonnancement de tches apriodique
Ordonnancement de tches en prsence de ressources partages Ordonnancement de tches dpendantes Ordonnancement de tches sur une architecture multiprocesseur
Anomalie des ordonnancements
7/27/2019 Slides Ordonnancement Temps Reel
87/108
20/10/2013 Ben Fradj Hanene 87
Anomalie des ordonnancementsmultiprocesseurs
Thorme de Graham : si un ensemble detches est ordonnanc de faon optimalesur un systme multiprocesseur avec des
priorits assignes, des temps d'excutionfixes et des contraintes de prcdence,alors le fait d'augmenter le nombre deprocesseurs, de rduire les temps
d'excution ou de relaxer les contraintesde prcdence peut conduire dtriorerla dure d'excution de l'algorithme
Anomalie des ordonnancements
7/27/2019 Slides Ordonnancement Temps Reel
88/108
20/10/2013 Ben Fradj Hanene 88
multiprocesseurs
exemple 9 tches de priorits dcroissantes contraintes de prcdence et temps d'excution :
1
2
3
4
9
8
7
6
5
(3)
(2)
(2)
(2)
(9)
(4)
(4)
(4)
(4)
Priorit tche i > Priorit tche j (pour i
7/27/2019 Slides Ordonnancement Temps Reel
89/108
20/10/2013 Ben Fradj Hanene 89
gde processeurs
ordonnancement optimal sur un systme 3 processeurs
sur un systme 4 processeurs :
1
2
3
4 5
6
7
8
9 12P1
P2
P3
1
2
3
4
9
8
7
6
5
(3)
(2)
(2)
(2)
(9)
(4)
(4)
(4)
(4)
1
23
4
56
7
8
9
P1
P2P3
P4
15
Anomalie : diminuer le tempsd ti d t h
7/27/2019 Slides Ordonnancement Temps Reel
90/108
20/10/2013 Ben Fradj Hanene 90
12
3
4
9
8
7
6
5
(3)
(2)
(2)
(2)
(9)
(4)
(4)
(4)
(4)
1
2
3
4 5
6
7
8
9
12
Solution 3processeurs
1
2
3
4
5
6 8
7
916
Si temps tche 4 passe de 2 1
P1
P2
P3
P1
P2
P3
dexcution des tches
Anomalie : supprimer des
7/27/2019 Slides Ordonnancement Temps Reel
91/108
20/10/2013 Ben Fradj Hanene 91
en supprimant quelques relations de prcdence
ppprcdences
1
2
3
4
9
87
6
5
(3)
(2)
(2)
(2)
(9)
(4)
(4)
(4)
(4)
1
2
3
4 5
6
7
8
9
12
1
23
4 56
8
7
916
P1
P2
P3
P1
P2P3
1
2
3
4
9
8
7
6
5
(3)
(2)
(2)
(2)
(9)
(4)(4)
(4)
(4)
Anomalie : partage de ressources
7/27/2019 Slides Ordonnancement Temps Reel
92/108
20/10/2013 Ben Fradj Hanene 92
Exemple d'anomalie sur des contraintes de ressources 5 tches alloues statiquement 2 processeurs T2 et T4 partagent une ressource exclusive
si on rduit le temps d'excution de T1
3
1 2
4 517
P1
P2
3
1 2
4 5P1
P2
22
Anomalie : partage de ressources
deux approches dordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
93/108
20/10/2013 Ben Fradj Hanene 93
pp
multiprocesseur
On distingue en gnral deux types dapproche pour lordonnancement
multiprocesseur :
1. Partitionnement et ordonnancement distribu:
- Il sagit de partitionnerlensemble des n tches en m sous-ensembles disjoints :1, 2, . . . , m et dordonnancerensuite lensemble i sur le processeur Pi avecune stratgie dordonnancement locale monoprocesseur. Les tches ne sont
donc pas autorises migrer dun processeur lautre.
Systmes distribus
deux approches dordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
94/108
20/10/2013 Ben Fradj Hanene 94
2. Ordonnancement globale ou centralis :
- Appliquer globalement, sur la plate-forme multiprocesseur entire, unestratgie dordonnancement unique et dattribuer chaque instant les m
processeurs aux n tches les plus prioritaires. Par exemple en utilisant RM ouEDF.- Dans ce cas, outre la premption des tches, on autorise aussi la migrationde ces dernires ; c--d quune tche peut commencer son excution sur unprocesseur Pj , tre prempte et reprendre son excution ultrieurement surun autre processeur Pi
pp
multiprocesseur
1. Partitionnement et
7/27/2019 Slides Ordonnancement Temps Reel
95/108
20/10/2013 Ben Fradj Hanene 95
Dans ces systmes, il n'y a pas un unique mcanisme d'ordonnancement qui centraliseles informations et les dcisions d'ordonnancement, mais plusieurs:
- La difficult de maintenir une vision cohrente de l'tat du systme : En pratique,chaque Ordonnanceur s'occupe de grer un sous-ensemble identifi des tches dusystme, et en isolement des autres ordonnanceurs.
- Les cots de migration sont en gnral levs, ce qui entraine que la dcisiond'affectation est plus dterminante qu'en multiprocesseur, et qu'elle peut difficilement
tre remise en cause.
- Il est ncessaire de prendre en compte l'ordonnancement de la ressource decommunication (rseau) entre les processeurs.
ordonnancement distribu
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
96/108
20/10/2013 Ben Fradj Hanene 96
-Temps dexcution dune tche diffre dunprocesseur un autre (processeurs identiques ouhtrognes).
- Temps de communication entre les processeurs.
Une tape daffectation de tches aux processeurs sajoute:
allocation ou partitionnement
distribu
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
97/108
20/10/2013 Ben Fradj Hanene 97
distribu
4 grandes classes dalgorithmes de partitionnement:
algorithmes de regroupement:Ce type dalgorithme est souvent utilis pour minimiserlutilisation des liens de communications. Lalgorithme procde en deux temps. Tout
dabord, une phase dite de clustering regroupe les tches que lon souhaite partitionner
en modules ; pour cela, lalgorithme identifie les tches qui communiquent le plus entre
elles et les regroupent en clusters. Ensuite, chaquecluster est associ un processeur.
- lalgorithme de sac dos ou le Bin packing: il faut placer dans m botes de taillesidentiques, k objets de tailles diffrentes. Dans notre cas, les objets sont les tches,leurs tailles sont leurs taux dutilisations processeur U(i ), la taille de chaque bote est
lutilisation maximale que lon peut atteindre : ln 2 pour RM, 1 pour EDF.
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
98/108
20/10/2013 Ben Fradj Hanene 98
algorithmes de recuit simul:Le recuit simul est une mthode doptimisationqui part dune solution du problme et qui tente de lamliorer en explorantlespace de recherche par voisinages. Lalgorithme considre les solutions du
problme comme des tats denergie du systme et le but est de minimisercette nergie. A chaque itration, on fait diminuer la temprature qui reprsente
le paramtre cl de lalgorithme. Levaluation de la nouvelle solution obtenue est
sujette une probabilit dacceptation, de manire viter de rester pig dansun minimum local.
algorithmes gntiques : Les algorithmes gntiques reposent sur les principesfondamentaux de la gntique. un algorithme gntique est un algorithme itratifde recherche globale dont le but est doptimiser une certaine fonction. Dans le
problme du partitionnement des tches sur plusieurs processeurs, cetalgorithme ^gnre des solutions en minimisant une fonction cot ( par exempleles chances et les communications du systme).
distribu
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
99/108
20/10/2013 Ben Fradj Hanene 99
algorithmes gntiques :
Lalgorithme gntique se droule de la manire suivante :1. gnration de la premire population
2. valuation (critre darrt)3. slection pour la reproduction4. croisement et mutation, retour en 2.
distribu
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
100/108
20/10/2013 Ben Fradj Hanene 100
RM en partitionn
distribu
- Pour RM partitionn, il semble naturel dutiliser la condition U < n(21/n 1) afin devrifier lordonnanabilit des tches assignes au processeur p (ou n est le
nombre de tches assignes au processeur P).
- Cependant la borne nest pas assez serre pour dfinir une bonne stratgiemultiprocesseur. On peut perdre jusqu `a 50 % des ressources.
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
101/108
20/10/2013 Ben Fradj Hanene 101
EDF partitionn: FFDU
distribu
- LIU et LAYLAND ont montr que des tches chance surrequte sont ordonnanables par EDF sur un processeur si et seulement siU 1.- LOPEZ et al. ont montr que lutilisation de cette borne monoprocesseurpeut tre utilise pour dfinir une stratgie de partitionnementmultiprocesseur : First-Fit-Decreasing-Utilization (FFDU). I.e., que dans leproblme de bin packing on choisit chaque tape la premire boite quiconvient en considrant les tches par valeurs dcroissantes du facteurdutilisation.- Les mmes chercheurs ont dfini la condition dordonnanabilitsuivante :
1. Partitionnement et ordonnancement
7/27/2019 Slides Ordonnancement Temps Reel
102/108
20/10/2013 Ben Fradj Hanene 102
Thorme (FFDU EDF Utilisation):
un ensemble de tches priodiques avec
chance sur requte, est ordonnanable parlune des partitions FFDU (et EDF localementsur chaque processeur) si
U < (m + 1)/2
distribu
2. Ordonnancement globale oucentralis
7/27/2019 Slides Ordonnancement Temps Reel
103/108
20/10/2013 Ben Fradj Hanene 103
centralis
Ci Pi
T1 1 4
T2 3 5
T3 7 20
Exemple dordonnancement global RM :
2
1
16P2
P1 3 1
3 24 5 8 10
1
2
1
2
1
20
3
P et M
2. Ordonnancement globale oucentralis
7/27/2019 Slides Ordonnancement Temps Reel
104/108
20/10/2013 Ben Fradj Hanene 104
Algorithme de liste (List scheduling) :
- cest la technique la plus utilise quand il sagit dun ensemble de tchesdpendantes.
- Une tche devient prte pour excution quand tous ces prdcesseurs ontfini leur excution. La tche racine qui na aucune prcdence est actif linstant 0. Lalgorithme de list scheduling met les tches dans une file au fur
et mesure que les tches deviennent prtes pour excution et envoie lestches au processeur. Quand plus quune tche est active au mme instant,
trouv lordre optimal qui minimise le temps dexcution est un problme NP-difficile. Plusieurs heuristiques sont dveloppes parmi les quelles on trouvela tche la plus longue avant (ALAP), la tche la plus courte avant (ASAP),
centralis
2. Ordonnancement globale oucentralis
7/27/2019 Slides Ordonnancement Temps Reel
105/108
20/10/2013 Ben Fradj Hanene 105
Exercice 1 : ordonnancer cette application sur une architecture biprocesseur enutilisant lalgorithme de liste ASAP puis ALAP.
143
2
(2)
(4)
(3)
(1)
56
7
(3)
(2)
(3)
centralis
2. Ordonnancement globale oucentralis
7/27/2019 Slides Ordonnancement Temps Reel
106/108
20/10/2013 Ben Fradj Hanene 106
1
2
3
4
9
8
7
6
5
(3)
(4)
(1)
(2)
(9)
(2)
(1)
(3)
(5)
centralis
Conclusion
7/27/2019 Slides Ordonnancement Temps Reel
107/108
20/10/2013 Ben Fradj Hanene 107
Conclusion
La thorie de lordonnancement pour lessystmes temps rel monoprocesseurs est undomaine de recherche bien tabli ce jour, il y ade nombreux travaux solides qui couvrentlargement ce domaine de recherche.
En revanche, lordonnancement pour les
systmes temps rel multiprocesseurs est une
domaine de recherche relativement neuf, peu dersultats existent ce jour.
7/27/2019 Slides Ordonnancement Temps Reel
108/108
Recommended