Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TD temps réel 1 CORRIGE 1! INTRODUCTION : RM, EDF, LLF.........................

TD temps réel 1 CORRIGE 1! INTRODUCTION : RM, EDF, LLF...............................................................................................................................2! 1.1! QUESTION 1............................................................................................................................................................... 2! 2! THEOREME DE LA ZONE CRITIQUE ......................................................................................................................5! 2.1! CALCUL DE U............................................................................................................................................................ 5! 2.2! THEOREME DE LA ZONE CRITIQUE......................................................................................................................... 5! 3! RATE MONOTONIC OU EARLIEST DEADLINE ....................................................................................................6! 3.1! QUESTION 1............................................................................................................................................................... 6! 3.2! QUESTION 2............................................................................................................................................................... 6! 3.3! QUESTION 3............................................................................................................................................................... 6! 4! TEMPS DE REPONSE DE BOUT EN BOUT...............................................................................................................7! 4.1! RAPPELS .................................................................................................................................................................... 7! 4.2! EXEMPLE ................................................................................................................................................................... 8! 4.2.1! Initialisations...................................................................................................................................................... 8! 4.2.2! Itération 1 ........................................................................................................................................................... 9! 4.2.3! Itération 2 ........................................................................................................................................................... 9! 4.2.4! Itération 3 ......................................................................................................................................................... 10! 4.2.5! Résultat ............................................................................................................................................................. 10! 4.3! EXEMPLE 2 .............................................................................................................................................................. 11! 4.3.1! Bus CAN ........................................................................................................................................................... 11! 4.3.2! Initialisations.................................................................................................................................................... 12! 4.3.3! Itération 1 ......................................................................................................................................................... 12! 4.3.4! Itération 2 ......................................................................................................................................................... 12! 4.3.5! Itération 3 ......................................................................................................................................................... 13! 4.3.6! Itération 4 ......................................................................................................................................................... 13! 4.3.7! Itération 5 ......................................................................................................................................................... 14! 4.3.8! Résultat ............................................................................................................................................................. 14! 5! SERVEUR DIFFERE.....................................................................................................................................................15! 5.1! QUESTION 1............................................................................................................................................................. 15! 6! SERVEUR DE SCRUTATION .....................................................................................................................................16! 6.1! QUESTION 1............................................................................................................................................................. 16! 6.2! QUESTION 2............................................................................................................................................................. 17! 2 TD Temps réel (1) Corrigé 1 Introduction : RM, EDF, LLF Trois tâches, prêtes à t = 0 : T1 : (C=1, D=P=3) T2 : (C=1, D=P=4) T3 : (C=2, D=P=6) 1.1 Question 1 Calcul de U U = 1/3 +1/4 + 2/6 = 0,33 + 0,25 + 0,33 = 0, 91. Le coefficient U est inférieur à 1: l’ensemble des tâches est ordonnançable par EDF. Il est supérieur à 0,78 : on ne peut rien dire pour RMS : en effet U inférieur ou égal à N(21/N-1) est une condition suffisante pour RMS. Remarques : - RMS : priorité fixe, - EDF : priorité dynamique, moins de « temps morts » que RMS, mais moins bon comportement en cas de surcharge. Plus coûteux à implémenter. - LLF prend en compte le coefficient C, ce qui n’est fait ni par RMS, ni par EDF. Encore plus coûteux à implanter que EDF. Rappel : dans tous les cas le calcul d’ordonnancement n’est fait que pour les tâches qui ont été activées ou réactivées… Schémas d’ordonnancement On rappelle la valeur du PPCM des périodes : 12. 1.1.1.1 Ordonnancement RMS La décision d’ordonnancement est prise à chaque activation de tâche. Schéma d’ordonnancement en appliquant RMS : Date 1 2 3 4 5 6 7 8 9 10 11 12 T1 T2 T3 Commentaire : Bien que la condition suffisante ne soit pas satisfaite, on constate sur le schéma que l’ensemble des trois tâches est ordonnançable par RMS. Il reste un créneau libre en 11 : aucune tâche n’a été réactivée, la prochaine date d’activation est 12 pour toutes les tâches. 3 TD Temps réel (1) Corrigé 1.1.1.2 Ordonnancement EDF (1) La décision d’ordonnancement est prise à chaque activation de tâche. Schéma d’ordonnancement en appliquant EDF : Date 1 2 3 4 5 6 7 8 9 10 11 12 T1 T2 T3 Commentaires : Au temps 3, deux tâches ont leur échéance pour la date 6 : - T1, qui a besoin d’une unité de temps pour sa deuxième période, - T3, qui a besoin d’une seconde unité de temps pour sa première période. On peut choisir : - T1, parce qu’elle est la première dans l’ordre de la numérotation (sa période est plus courte), - T3, pour éviter de faire un changement de contexte, Ici, on choisit T1. T3 est réordonnancée en 5 pour sa seconde unité de temps. Au temps 9, deux tâches ont leur échéance pour la date 12 : - T2, qui a besoin d’une unité de temps pour sa deuxième période, - T3, qui a besoin d’une seconde unité de temps pour sa deuxième période. Comme précédemment, on peut choisir : - T2, parce qu’elle est la première dans l’ordre de la numérotation (sa période est plus courte), - T3, pour éviter de faire un changement de contexte, Ici, on choisit T2. T1 s’insère alors, puis T3 consomme sa seconde unité de temps. Il reste un créneau libre en 11 : aucune tâche n’a été réactivée, la prochaine date d’activation est 12 pour toutes les tâches. 1.1.1.3 Ordonnancement EDF (2) Reprenons le scénario, en choisissant maintenant de toujours réduire le nombre de changements de contexte : Date 1 2 3 4 5 6 7 8 9 10 11 12 T1 T2 T3 Au temps 4, on choisit T3. Au temps 7, on peut choisir T1 ou T3, on choisit T1 Au temps 9, on peut choisir T2 ou T3, on choisit T3 qui est déjà active, pour éviter le changement de contexte. Il reste un créneau libre en 11 : aucune tâche n’a été réactivée, la prochaine date d’activation est 12 pour toutes les tâches. Remarque : 4 TD Temps réel (1) Corrigé EDF, comme RMS, ne prend pas en compte le coefficient C pour calculer les priorités. 1.1.1.4 Ordonnancement LLF On donne maintenant un schéma d’ordonnancement en appliquant l’algorithme LLF (Least Laxity First), algorithme qui prend en compte la capacité C demandée par une tâche à chacune de ses activations. Rappel : La tâche qui sera ordonnancée est celle dont la « laxité », ou marge, est la plus petite, sachant que : marge = échéance – temps de calcul restant – date courante. Le calcul d’ordonnancement peut être fait à chaque incrément d’horloge (uniquement pour les tâches actives), ou bien à chaque activation de tâche. Dans le premier cas il y a plus de changements de contexte. Date 0 1 2 3 4 5 6 7 8 9 10 11 T1 2 2 2 2 T2 2 2 3 T3 2 1 3 1 Pour chaque date, on visualise les calculs pour toutes les tâches actives : date Tâche 1 marge échéance C restant Tâche 2 marge échéance C restant Tâche 3 marge échéance C restant Ce qui donne : Dat e 0 1 2 3 4 5 6 T1 2 3 1 2 6 1 2 9 1 T2 3 4 1 2 4 1 3 8 1 2 8 1 T3 4 6 2 3 6 2 2 6 2 2 6 1 1 6 1 4 12 2 En 3, on peut choisir T1 ou T3, on choisit T1 qui vient de se réveiller et qui est la plus prioritaire choisir T3 entraînerait moins de changements de contexte. On pourrait introduire la notion de critcité. Dat e 7 8 9 10 11 T1 2 12 1 T2 3 12 1 T3 3 12 2 3 12 1 2 12 1 1 12 1 En 8, on peut choisir T2 ou T3, on choisit T2 qui vient de se réveiller et qui est la plus prioritaire, choisir T3 entraînerait moins de changements de contexte. De même, on choisit T1 en 9. T3 est de plus en plus retardée… Il reste un créneau libre en 11 : aucune tâche n’a été réactivée, la prochaine date d’activation est 12 pour toutes les tâches. 5 TD Temps réel (1) Corrigé 2 Théorème de la zone critique Trois tâches, prêtes à t = 0 : T1 : (C=25, D=P=100) T2 : (C=50, D=P=200) T3 : (C=100, D=P=300) 2.1 Calcul de U Calcul de U : U = 25/100 +50/200 + 100/300 = 0,25 + 0,25 + 0,33 = 0, 83. U est donc > 0,78, on ne peut rien dire pour RMS. 2.2 Théorème de la zone critique Rappel de la formule : Wi(t) = !(j=1) i Cj*!t/Tj" - Wi(t) est alors la consommation de temps cpu demandée à la date t par les i premiers processus, ceux-ci étant numéroté par ordre de priorité croissante : priorité(Pn) > priorité(Pn+1) - !t/Tj" donne le nombre d’activations de la tâche j, de période Tj, dans la fenêtre de temps de taille t, - !t/Tj" *Cj, est donc le temps cpu consommé par Tj dans cette fenêtre, - !(j=1) (i-1) Cj*!t/Tj" est le retard imposé à la tâche Ti par les tâches d’indices inférieurs,donc plus prioritaires. Notions corrélées : période d’activité On va chercher si on peut trouver Wi(t) = t On initialise avec Wi(0) = !(j=1) i Cj , c’est à dire t0 = " Calcul pour i = 1 : W1(0) = 25 W1(25) = 25!25/100" = 25 # OK Calcul pour i = 2 : W2(0) = 25 + 50 = 75 W2(75) = 25 !75/100" + 50 !75/200" = 75 # OK Calcul pour i = 3 : W3(0) = 25 + 50 + 100 = 175 W3(175) = 25 !175/100" + 50!175/200"+ 100 !175/300" = 25*2 = 50 *1 + 100 *1 = 200 W3(200) = 25 !200/100"+ 50 !200/200"+ 100 !200/300" = 25*2 = 50 *1 + 100 *1 = 200 # OK 6 TD Temps réel (1) Corrigé 3 Rate monotonic ou Earliest deadline 3.1 Question 1 3.1.1.1 Liste des tâches Liste des tâches : T1 : (C=10, T =40) T2 : (C=20, T =60) T3 : (C=20, T =80) U = 1/4 + 2/6 + 2/8 = 0,25 + 0,33 + 0,25 = 0, 83 U est donc supérieur à 0, 78 : on ne peut rien dire pour RM, l’ordonnancement EDF est possible. PPCM = 240 3.1.1.2 Diagramme uploads/Management/ td1-tempsreel-corr.pdf