View
6
Download
0
Category
Preview:
Citation preview
TD d’ordonnancementPierre-Yves Duval (cppm)
Ecole d’informatique temps réel - La Londes les Maures 7-11 Octobre 2002
Méthode graphique/simulation
Construction graphique simple
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
Construction graphique simple
Faire le tableau ordonné des tâches
Boucle tant qu’on a pas traité la tâche la moins prioritaire
Etape 1 - Sélectionner la tâches de plus forte priorité avec un facteur de blocage non nul non traitée
Etape 2 - Tracer le diagramme exécution de cette tâche et des plus prioritaires jusqu’à la fin de leurs périodes d’activité
Etape 3 – Vérifier qu’elles se sont toutes terminées avant leurs échéances
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
Sélection de la première tache non traitée avec facteur de blocage t1
100
t1
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
Sélection de la seconde tâche non traitée avec facteur de blocage t2
100
t1
t2
200
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
Sélection de la seconde tâche non traitée avec facteur de blocage t2
100
t1
t2
200
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
100
t1
Plus de tâche non traitée avec facteur de blocage, on prend tout
200
t2
t3
300
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
100
t1
t2
Plus de tâche non traitée avec facteur de blocage, on prend tout
200
t3
300
250
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
100
t1
t2
Plus de tâche non traitée avec facteur de blocage, on prend tout
200
t3
300
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
100
t1
t2
Plus de tâche non traitée avec facteur de blocage, on prend tout
200
t3
300
3000L40250
20010M50200
10020H40100
échéanceBlocagePrioC calculT période
100
t1
t2
Plus de tâche non traitée avec facteur de blocage, on prend tout
200
t3
300
Construction graphique simple et périodes activité
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
Sélection de la première tâche non traitée avec facteur de blocage t1
0 100
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
1000 500400300200 700600
KO dépassement de 10
Méthodes algébriquesCalcul exacte des temps de
réponse
Cas où toutes les échéances sont inférieures ou égales à la périodes
Ri n+1 = Ci + ? Ri
n / Tj Cj
∀j ∈ hp(i)
Avec:Ri
n : délai de terminaison de la iéme tâche à la néme itération du calcul de ce délaihp(i) : ensemble des tâches plus prioritaires que la tâche iLa fonction x est la «fonction plafond» correspondant au plus petit entier supérieur ou égal à x ( 5.1 = 6, 5.9 = 6, 5 = 5).Ci : temps d’exécution de la iéme tâcheTi : période de la ième tâche
Méthodes algébriquesCalcul exacte des temps de
réponse
Calculer la première valeur nn inclus la tâches et les plus prioritaires R0 = ? Cj
j=1Tant que pas de convergence
Etape 2 - Calculer itération suivante R n+1 = f( R n )Etape 3 - Si R n+1 <= D et R n+1 < R n réitérer a étape 2
Sinon Si R n+1 > D la tâche a dépassé son échéance ERREUR D’ORDONNANCEMENT
Sinon R n+1 = R n = délai de terminaison de la tâcheFIN
3100350350C
240150150B
140100100A
P prioritésC calculD échéancesT périodestâches
Etape 1 calcul de la première itération n
R0 = ? Cj R0 = 100 + 40 + 40 = 180j=1
Etape 2 calcul de la première itération
Ri n+1 = Ci + ? Ri
n / Tj Cj R31 = 100+180 / 100 40 +180 / 150 40 = 260
∀j ∈ hp(i)Etape 3 analyser le résultat
R1<=350 et R1!=R0 alors on réitère l’étape 2.Etape 2 calcul de la seconde itération
Ri n+1 = Ci + ? Ri
n / Tj Cj R32 = 100+260 / 100 40 +260 / 150 40 = 300
∀j ∈ hp(i)Etape 3 analyser le résultat
R2<=350 et R2!=R1 alors on réitère l’étape 2.Etape 2 calcul de la troisième itération
Ri n+1 = Ci + ? Ri
n / Tj Cj R33 = 100+300 / 100 40 +300 / 150 40 = 300
∀j ∈ hp(i)Etape 3 analyser le résultat
R3<=350 et R3=R2Nous avons atteint le résultat, la durée de terminaison en cas pis est de 300 et est bien inférieure à l’échéance.
Justification graphique de l’algorithme
3100350350C
240150150B
140100100AP prioritésC calculD échéancesT périodestâches
0 100 200
Exécution prise en compte
Exécution non prise en compte
Nouvelles invocations pour exécution périodique
Première approximation
A
B
C
0 100 200
Exécution prise en compte
Exécution non prise en compte
Nouvelles invocations pour exécution périodique
Seconde approximation
A
B
C
0 100 200
Exécution prise en compte
Exécution non prise en compte
Nouvelles invocations pour exécution périodique
Troisième approximation
A
B
C
Méthodes algébriquesCalcul exacte des temps de
réponsePrise en compte du facteur de blocage
Ri n+1 = Ci + Bi + ? Ri
n / Tj Cj
∀j ∈ hp(i)
On retiendra que le facteur de blocage Bi est la plus longue durée de blocage de la tâche par une autre tâche de plus faible priorité. Les deux algorithmes vus en cours qui utilisent le concept de plafond de priorité garantissent en effet qu’une tâche ne peut-être bloquée pendant une période d’exécution que par au plus une tâche de plus faible priorité. On se place donc dans le cas pis où ce serait celle qui la bloque le plus longtemps.
Méthodes algébriquesCalcul exacte des temps de
réponseCas général avec échéances quelconques et facteur de blocage
Appliquer la formule itérative ci-dessous étudiée par Tindell et Lehoczky pour calculer le délai de terminaison de la tâche en cas pis.
n
Ri n+1 = kCi + Bi + ? Ri
n / Tj Cj
j=1
Etape 1- On calcule la première approximation du délai de terminaison n
R0 = Bi + ? Cj
j=1Boucle sur la période d’activitéEtape 2- On initialise un compteur k qui variera de 1 au nombre de traitements qui sont inclus dans la période d’activité
Boucle sur le traitementEtape 3- Appliquer la formule itérative ci-dessous étudiée par Tindell et Lehoczky (voir ref) pour calculer le délai de terminaison
de la tâche en cas pis.n
Ri n+1 = kCi + Bi + ? Ri
n / Tj Cjj=1
Etape 4- Analyser le résultat du kéme traitement:Si Rn+1 > ((k-1)*Ti+Di) l’échéance du traitement qu’on vient de calculer ne respecte pas la contrainte d’échéance de la tâche.
ERREUR D’ORDONNANCEMENTSinon si Rn+1!= Rn on REBOUCLE à l’étape 3
Sinon Rn+1=Rn on a trouvé la date fin du kième traitement on SORT DE LA BOUCLE
Fin boucle sur le traitement
Etape 5- Rn+1=Rn on a trouvé la date fin du kième traitement. Il faut calculer le délai de terminaison de ce kième traitement.E i,k = Rn – Ti (k-1)
Etape 6- On regarde si on est à la fin de la période d’activité, c’est à dire si le délai de terminaison de ce traitement est inférieur àla période de la tâche, si:
Ei,k <= TiSi ce n’est pas le cas on incrémente k de 1 (passe au traitement suivant) et on reprend à l’étape 3.Sinon on passe à l’étape suivante.
Fin boucle sur la période d’activité
Etape 7- Calcul pire temps de réponse.Le pire temps de réponse pour la tâche est la plus grande valeur des Ei,b (1<=b<=k) calculés a l’étape 5.
Exemple
0360350350C
20260160150B
0140100100A
Facteur de blocage
prioritésC calculD échéancesT périodestâches
Calcul du délai d’exécution en cas pire de la tâche B.Etape 1- R0 = B2 + C1 + C2 = 20 + 40 + 60 = 120Etape 2- Initialiser le compteur k=1Etape 3- calcul de n
Ri n+1 = kCi + Bi + ? Ri
n / Tj Cjj=1
R1 = B2 + 1*C2+ R0/T1*C1 = 20 + 1(60) + 120/100 *40 = 160Etape 4- 120 != 160 il faut réitérer le calcul
Etape 3- R2 = 20 + 1(60) + 160/100 *40 = 160Etape 4- 160=160 donc la convergence sur ce traitement est atteinteEtape 5- temps de réponse de la première exécution E i,k = Rn – Ti (k-1) E2,1= 160-150(0)=160 échéance OKEtape 6- Période de 150 et terminaison a 160 donc hors période activité, on continue dans la periode d’activite suivante
avec k = k+1 = 2on fixe R2 = 160+60 = 220 comme valeur de départ pour le calcul du traitement suivant
0 100 200
150
160
10 au delà de la période d’activation
supplément pour le facteur de blocage
A
B
Situation après 1 traitement
Exemple suite
Etape 3- calcul de n
Ri n+1 = kCi + Bi + ? Ri
n / Tj Cjj=1
R3 = B2 + 2*C2+ R2/T1*C1 = 20 + 2(60) + 220/100 *40 = 260Etape 4- 220 != 260 on est pas au point fixe sur ce traitementEtape 3- R2 = 20 + 2(60) + 260/100 *40 = 260Etape 4- 260=260 on est au point fixe du second traitementEtape 5- temps de réponse de la seconde exécution E i,k = Rn – Ti (k-1) E22 = 260-150(2-1)=110 délai exécution donc échéance OKEtape 6- 110 < 150 le second traitement se termine avant la fin de sa période,
c’est la fin de la période d’activité
Etape 7- détermination du plus long temps de réponseLes deux traitements analysés ont duré 160 et 110. L’exécution la plus longue a été 160 ce qui est inférieure ou égal à l’échéance. La tâche Best donc ordonnaçable dans cette configuration.
supplément pour le facteur de blocage
150300
marge
Situation après 2 traitements
durée 160 ms durée 110 ms
Délai pis de B = 160 ms car première latence 160ms et seconde 110 ms
A
B
Vérification algébrique des systèmes analysés graphiquement
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
Vérification algébrique de l’ordonnancement de la tache t2Exécution 1 : k=1R0 = 60 + 70 = 130
R1= 1 x 70 + 130/100 x 60 = 190 comme 190 <= (1-1) x 180 + 200 190<= 200 on est pas en dépassement d’échéanceMais R0 ≠ R1 130 ≠ 190on doit continuer car on est pas au point fixe
R2= 1 x 70 + 190/100 x 60 = 190R1 = R2 on a atteint le point fixe et la fin de l’exécution pour cette période est a 190 <= 200 l’échéance donc c’est correct
Vérification pour savoir si on est dans la période d’activitéE = 190 – 180( 1 – 1 ) = 190 la fin 190 > 180 durée de la période d’activité, il faudra donc analyser l’exécution suivante k = k+1
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
Vérification algébrique de l’ordonnancement de la tache t2Exécution 1 : k=2R0 = 190 + 70 = 260
R1= 2 x 70 + 260/100 x 60 = 320 comme 320 <= (2-1) x 180 + 200 320<= 380 on est pas en dépassement d’échéanceMais R0 ≠ R1 260 ≠ 320on doit continuer car on est pas au point fixe
R2= 2 x 70 + 320/100 x 60 = 380 comme 380 <= (2-1) x 180 + 200 380<= 380 on est pas en dépassement d’échéanceR1 ≠ R2 320 ≠ 380on doit continuer car on est pas au point fixe
R3= 2 x 70 + 380/100 x 60 = 380R2 = R3 on a atteint le point fixe et la fin de l’exécution pour cette période/traitement
Vérification pour savoir si on est dans la période d’activitéE = 380 – 180( 2 – 1 ) = 200 la fin 200 > 180 durée de la période d’activité, il faudra donc analyser l’exécution suivante k = k+1Mais 200 = 200 l’échéance est respectée
2000L70180t2
10020H60100t1
échéancesBlocagesPrioC calculsT périodestâches
Vérification algébrique de l’ordonnancement de la tâche t2Exécution 1 : k=3R0 = 380 + 70 = 450
R1= 3 x 70 + 450/100 x 60 = 510 comme 510 <= (3-1) x 180 + 200 510<= 560 on est pas en dépassement d’échéanceMais R0 ≠ R1 450 ≠ 510on doit continuer car on est pas au point fixe
R2= 3 x 70 + 510/100 x 60 = 570 problème car 570 !<= (3-1) x 180 + 200=560 570 > 560 on est en dépassement d’échéance de 10
La tâche t2 n’est pas ordonnançable.
Vérification d’une plus grande configuration
1S1177F
3S213333E
5S251057D
8S1205050C
5S110100100B
2S13201000A
prioritésdurées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
Condition nécessaire: Taux d’utilisation du CPU : 3/1000 + 10/100 + 20/50 + 5/57 + 1/33 + 1/7 = 0.764 76,4 % donc inférieur à 1condition satisfaite
Condition suffisante:doit être inférieure à n(2 1/n -1) = 0,73 donc condition non satisfaite
Priorités RM : F E C D B A
Priorités RM : F D A E C B
63201000A
510100100B
451057D
3205050C
213333E
1177F
prioritésdurées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
Ordre des priorités pour RM:
Vérification de F R0 = 1 et 1<7 donc OK
Vérification de ER0 = 1 + 1 = 2R1 = 1 + 1 2/7 = 1 + 1x1 = 2 2<33 donc OK
Vérification de CR0 = 1 + 1 + 20 = 22R1 = 20 + 1 22/7 + 1 22/33 = 20 + 4 + 1 = 25 25≠22R2 = 20 + 1 25/7 + 1 25/33 = 20 + 4 + 1 = 25 25=25 et 25<50 donc OK
63201000A
510100100B
451057D
3205050C
213333E
1177F
prioritésdurées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
Vérification de D
R0 = 1 + 1 + 20 + 5 = 27
R1 = 5 + 1 27/7 + 1 27/33 + 20 27/50 = 5 + 4 + 1 + 20 = 30 30≠27
R2 = 5 + 1 30/7 + 1 30/33 + 20 30/50 = 5 + 5 + 1 + 20 = 31 31 ≠31
R3 = 5 + 1 31/7 + 1 31/33 + 20 31/50 = 5 + 5 + 1 + 20 = 31 31 =31 mais 31<10 ErreurVérification de B
R0 = 1 + 1 + 20 + 5 + 10 = 37
R1 = 10 + 1 37/7 + 1 37/33 + 20 37/50 + 5 37/57 = 10 + 6 + 2 + 20 + 5= 43 43≠37
R2 = 10 + 1 43/7 + 1 43/33 + 20 43/50 + 5 43/57 = 10 + 7 + 2 + 20 + 5 = 44 44 ≠43
R3 = 10 + 1 44/7 + 1 44/33 + 20 44/50 + 5 44/57 = 10 + 7 + 2 + 20 + 5= 44 44=44 et 44<100 OK
63201000A
510100100B
451057D
3205050C
213333E
1177F
prioritésdurées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
Vérification de A
R0 = 1 + 1 + 20 + 5 + 10 + 3 = 40
R1 = 3 + 1 40/7 + 1 40/33 + 20 40/50 + 5 40/57 + 21 40/100 = 3 + 6 + 1 + 20 + 5 + 10 = 45 45≠40
R2 = 3 + 1 45/7 + 1 45/33 + 20 45/50 + 5 45/57 + 21 45/100 = 3 + 7 + 1 + 20 + 5 + 10 = 46 46 ≠45
R3 = 3 + 1 46/7 + 1 46/33 + 20 46/50 + 5 46/57 + 21 46/100 = 3 + 7 + 1 + 20 + 5 + 10= 46 46 =46 mais 20<46 donc Erreur
Problèmes dus au RM inadapté aux périodes grandes avec échéances courtes
610100100B
5205050C
413333E
33201000A
251057D
1177F
prioritésdurées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
Ordre des priorités pour DM:
Vérification de F R0 = 1 et 1<7 donc OK
Vérification de DR0 = 1 + 5 = 6R1 = 5 + 1 6/7 = 5 + 1 = 6 6<10 donc OK
Vérification de AR0 = 1 + 5 + 3 = 9R1 = 3 + 1 9/7 + 5 9/57 = 3 + 2 + 5 = 10 10≠9R2 = 3 + 1 10/7 + 5 10/57 = 3 + 2 + 5 = 10 10=10 et 10<20 donc OK
610100100B
5205050C
413333E
33201000A
251057D
1177F
prioritésdurées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
Vérification de ER0 = 1 + 5 + 3 + 1= 10R1 = 1 + 1 10/7 + 5 10/57 + 3 10/1000 = 1 + 2 + 5 +3= 11 10≠11R2 = 1 + 1 11/7 + 5 11/57 + 3 11/1000 = 1 + 2 + 5 +3= 11 11=11 et 11<33 donc OK
Vérification de CR0 = 1 + 5 + 3 + 1 + 20 = 30R1 = 20 + 1 30/7 + 5 30/57 + 3 30/1000 + 1 30/33 = 20 + 5 + 5 +3 +1= 34 30≠34R2 = 20 + 1 34/7 + 5 34/57 + 3 34/1000 + 1 34/33 = 20 + 5 + 5 +3 +2= 35 34≠35R3 = 20 + 1 35/7 + 5 35/57 + 3 35/1000 + 1 35/33 = 20 + 5 + 5 +3 +2= 35 35=35 et 35<50 OK
Vérification de BR0 = 1 + 5 + 3 + 1 + 20 + 10= 40R1 = 10 + 1 40/7 + 5 40/57 + 3 40/1000 + 1 40/33 + 20 40/50 = 10 + 6+ 5 +3 +2 +20= 46 40≠46R2 = 10 + 1 46/7 + 5 46/57 + 3 46/1000 + 1 46/33 + 20 46/50 = 10 + 7 + 5 +3 +2 +20= 47 46≠47R3 = 10 + 1 47/7 + 5 47/57 + 3 47/1000 + 1 47/33 + 20 47/50 = 10 + 7 + 5 +3 +2 +20= 47 47=47 et 35<50 OK
6 05S110100100B
5 58S1205050C
4 03S213333E
3 82S13201000A
2 35S251057D
1 81S1177F
PrioritésFacteur blocage
durées usage ms
sémaphoresduréesms
echéancesms
Périodesms
tâches
DM et prise en compte des sémaphores avec facteurs de blocage
Calcul du délai maximum exécution de DR0 = 1 + 5 +3 = 9R1 = 5 +3 + 1 9/7 = 8 + 1 = 9 9<10 donc OK
Calcul du délai maximum exécution de AR0 = 1 + 5 + 8 + 3 = 17R1 = 8 + 3 + 1 17/7 + 5 17/57 = 11 + 3 + 5 = 19 17≠19R2 = 8 + 3 + 1 19/7 + 5 19/57 = 11 + 3 + 5 = 19 19=19 et 19<20 donc OK
Comment appliquer aux réseaux temps réel
Analogie évidente:CPU ==è media a partagertaches d’une certaine durée ==è message d’une certaine longueurcouche MAC ==è ordonnanceur
Différences:- un message ne peut-être préempté il doit donc être transmis intégralement- éventuellement nombre limite de niveaux de priorités
Peut-on calculer le délai d’acheminement en cas pire de différents messages disposant d’attributs de priorité globale (réseau temps réel) qui accèdent concurremment au même réseau?
Comment appliquer aux réseaux temps réel
Non interruptibilité des messages.On peut adopter les mêmes formules avec les adaptations suivantes.
Un message très prioritaire qui veut accéder au media doit attendre la fin du message en cours de transmission.Celui-ci en cas pire sera le message le plus long de l’application qui vient juste d’obtenir le media.
Donc en cas pire avec une configuration ou il y a une priorité par message (exemple CAN) le délai en cas pired’acheminement d’un message i sera obtenu par:
Ri n+1 = kCi + Bi + ? Ri
n / Tj Cj
∀j ∈ hp(i)Cj délai de transmission du message de priorité jB durée de transmission du message le plus long du système temps réel
Comment appliquer aux réseaux temps réel
Plusieurs messages partageant le même niveau de priorité
K j est le nombre de messages de priorité i m i étant le message de priorité i pour lequel on calcule le délai en cas pire d’acheminement Ri( mi )Bi délai de transmission du plus long message, k indice dans la période d’activité
i Kj
Ri n+1( m i ) = kCi( mi ) + Bi + ? ? Ri
n ( m i ) / Tj ( m i ) Cj ( m i ) J=1 k j = 1
Occupation du réseau par les messages plus prioritaires et les messages de même priorité
How to use RapidRMA3 Use the
Schedulability Analyzer to analyze the model defined in the Task and Resource Graph. This can be a Single Node, Multi-Node or End-to-End architecture.
RapidRMA Single-Node Analysis Tool
1 Show Task Dependencies
• Show any dependencies between tasks• End-to-end analysis of a multi-node system is not possible
unless dependencies are defined
Worst Case Schedules
• You can see a timeline of the worst-case schedules for any resources and tasks on a selected node
SSystem for ystem for EExtraction of xtraction of TTiming iming IInformationnformation
SearchParameter
AnalysisTools
ExecutionEngine
PrimitiveEvents
RapidRMASystem Model
CompoundEvents
SETI
Termination Control
Using …..
Recommended