Cours4-SIC-Ordo-TAper (1).pdf

Ordonnancement temps réel (tâches apériodiques) Maria ZRIKEM Ensa de Marrakech Ensa de Marrakech, Ordonnancement temps réel 1 Inclusion des tâches apériodiques ⇒ les tâches à contraintes d’échéances dures ont été modélisées sous formes de tâches périodiques afin de déterminer des tests de faisabilité d’ordonnancement. ⇒ il faut intégrer les tâches moins critiques tout en leur permettant de bénéficier d’un traitement non trop pénalisant sans mettre en cause l’ordonnancement. Ces tâches sont assimilées à des processus apériodiques. ⇒ on ne peut pas les considérer comme les moins prioritaires. Ensa de Marrakech, Ordonnancement temps réel 2 Inclusion des tâches apériodiques ⇒ Se distinguent des t ches p riodiques par le fait que l'on ne conna t pas l'instant d'arriv e de la requ te de r veil ⇒ Contraintes temporelles strictes ou relatives ⇒ Buts atteindre: ⇒ si contraintes relatives : minimiser le temps de r ponse ⇒ si contraintes strictes : maximiser le nombre de t ches accept es en respectant leurs contrainte Ensa de Marrakech, Ordonnancement temps réel 3 à é é â é ê é é â î Inclusion des tâches apériodiques Solutions 1. Traitement d’arrière plan 2. Une tâche périodique spéciale qui contient elle-même un ordonnanceur de tâches apériodiques (serveur). La capacité et la priorité de cette tâches pouvant être réglée au mieux en garantissant l’ordonnançabilite des autres. Souvent on lui donne la priorité la plus forte. Ensa de Marrakech, Ordonnancement temps réel 4 Tâches apériodiques à contraintes relatives Traitement en arrière plan BG (background processing) ⇒ Simple réaliser et peu couteuse. ⇒ Les taches apériodiques avec une priorité toujours inférieure celles des taches périodiques. ⇒ Les tâches apériodiques sont ordonnancées lorsqu’il n’y a aucune tâche périodique prête à s’exécuter. Si plusieurs tâches apériodiques sont en attente, elles sont traitées selon leurs ordre de réveil (FIFO). ⇒ Permet de garantir l’exécution des tâches périodiques dans le respect de leurs contraintes temporelles ⇒ Le temps de réponse des tâches apériodiques peuvent s’av rer très grands surtout quand la charge des tâches périodiques devient importante et s’approche de 1 Ensa de Marrakech, Ordonnancement temps réel 5 à é à Inclusion des tâches apériodiques à contraintes relatives Traitement en arrière plan BG (background processing) Exemple : - 2 tâches périodiques P1 (C=2, T=5), P2 (C=2, T=10) - 3 tâches apériodiques AP1 (R=4, C=2), AP2(R=10, C=1), AP3(R=11, C=2) P1 (C=2, T=5) P2 (C=2, T=10) Temps creux tâches apériodiques 5 1 15 20 0 AP1 (R=4, C=2) AP3 (R=11, C=2) AP2 (R=10, C=1) Ensa de Marrakech, Ordonnancement temps réel 6 Les serveurs de tâches Minimiser le temps de réponse des tâches apériodiques dans le contexte d’un ordonnancement conduit par priorités. Faire prendre en charge par une tâche particulière qui possède une réelle priorité (statique ou dynamique) sans toutefois compromettre l’exécution des tâches périodiques : t che serveur. Ensa de Marrakech, Ordonnancement temps réel 7 â Les serveurs de tâches Serveur de scrutation (polling server) ⇒ C’est une tâche qui a généralement la plus forte priorité ⇒ A chacune de ses activations, le serveur de scrutation traite les T. APs. en suspens depuis son activation précédente et ce, soit jusqu’à épuisement de sa capacité, soit jusqu’à ce qu’il n’ y a aucune T. AP à servir. ⇒ Le PS sert périodiquement les requêtes apériodiques en attente selon la technique FIFO. ⇒ Si au commencement de son exécution, il n’ y a aucune T. AP en attente, le serveur se suspend jusqu’à sa prochaine occurrence en donnant la main au T. Ps. Ensa de Marrakech, Ordonnancement temps réel 8 Les serveurs de tâches Serveur de scrutation (polling server) ⇒ Condition suffisante de RMA avec un serveur : ⇒ Simple à mettre en oeuvre et test d’ordonnançabilité facilement adaptables ⇒ Le serveur relâche sa capacité C serv si aucun événement déclencheur de tâche apériodique n’est arrivé durant la période de scrutation (temps de réponse aux tâches apériodiques pas très bon). Ensa de Marrakech, Ordonnancement temps réel 9 Les serveurs de tâches Serveur de scrutation (polling server) Exemple (ordonnancement par RM): - 2 tâches périodiques P1 (C=3, T=20), P2 (C=2, T=10) - la tâche serveur Ps (C=2, T=5) (de plus petite période et donc de plus forte priorité) - 3 tâches apériodiques AP1 (R=4, C=2), AP2(R=10, C=1), AP3(R=11, C=2) Ensa de Marrakech, Ordonnancement temps réel 10 Les serveurs de tâches Serveur de scrutation (polling server) Exemple (ordonnance par RM): - 2 tâches périodiques P1 (C=3, T=20), P2 (C=2, T=10) - la tâche serveur Ps (C=2, T=5) (de plus petite période et donc de plus forte priorité) - 3 tâches apériodiques AP1 (R=4, C=2), AP2(R=10, C=1), AP3(R=11, C=2) La condition de faisabilité (RM) est remplie :3/20 + 2/10 + 2/5 =0,75 < 0,77 P1 (C=3, T=20) P2 (C=2, T=10) Ps (c=2, T=5) 5 10 15 20 AP1 (R=4, C=2) AP2 (R=10, C=1) AP3 (R=11, C=2) 2 1 0 5 7 10 12 15 16 Ensa de Marrakech, Ordonnancement temps réel 11 Les serveurs de tâches Serveur de scrutation (polling server) La méthode de scrutation souffre de plusieurs faiblesse dues à la manière dont est gérée sa capacité : ⇒ Lorsque le serveur est prêt, il se peut qu’il n’ait pas de T.APs à traiter et la capacité est alors perdue; ⇒ Lorsque des T. APs. surviennent sur le site, il se peut que le serveur se soit déjà suspendu, contraignant ainsi les T. APs. à attendre sa prochaine occurrence pour être servies. Ensa de Marrakech, Ordonnancement temps réel 12 Les serveurs de tâches Serveur différé (Defferable server DS) ⇒ Cette méthode revient à abaisser le seuil du critère d’ordonnancement des tâches périodiques tout en fournissant un bon temps de réponse aux T. APs. ⇒ Le serveur différé est active quand il y a une T. AP. en attente. Le serveur est suspendu quand il a dépassé son quantum de temps. Son quantum est rempli quand il arrive en début de période. ⇒ En général, on affecte la plus haute priorité à DS (Tds < min (périodes des tâches périodiques)). Elle est définie suivant la méthode RM. Ensa de Marrakech, Ordonnancement temps réel 13 Les serveurs de tâches Serveur différé : exemple - 2 tâches périodiques P1 (C=2, T=6), P2 (C=3, T=8) - la tâche serveur DS (C=1, T=5) (de plus petite période et donc de plus forte priorité) - 3 tâches apériodiques AP1 (R=1, C=0,5), AP2(R=7, C=2), AP3(R=14, C=1) Ensa de Marrakech, Ordonnancement temps réel 14 Les serveurs de tâches Serveur différé : exemple - 2 tâches périodiques P1 (C=2, T=6), P2 (C=3, T=8) - la tâche serveur DS (C=1, T=5) (de plus petite période et donc de plus forte priorité) - 3 tâches apériodiques AP1 (R=1, C=0,5), AP2(R=7, C=2), AP3(R=14, C=1) P1(C=2, T=6) P2 (c=3, T=8) DS (C=1, T=5) 1,5 6 7 10 15 AP1 (R=1, C=0,5) AP2 (R=7, C=2) AP3 (R=14, C=1) 1 0,5 0 5 7 10 12 15 16 Ensa de Marrakech, Ordonnancement temps réel 15 Les serveurs de tâches Serveur différé : comportement indésirable - 1 tâche périodique P1 (C=2, T=7), - la tâche serveur DS (C=3, T=6) - 1 tâche apériodique AP1 (R=21, C=6) P1(C=2, T=7) DS (c=3, T=6) 6 7 12 14 18 21 24 28 AP1 (R=21, C=6) Renouvellement de la capacité de DS Exécution dos a dos Échéance manquée de P1 Ensa de Marrakech, Ordonnancement temps réel 16 Les serveurs de tâches Serveur sporadique (Sporadic server SS) ⇒ Comme le DS, le serveur sporadique est défini par sa priorité d’exécution (fixée par exemple à l’inverse de sa période dans le RM), et sa capacité. ⇒ Contrairement au DS, le SS ne retrouve pas sa capacité originelle à chaque frontière de période mais attend un instant de réapprovisionnement qui se ramène au temps de son dernier démarrage avec une capacité pleine + sa période. IL n’y a plus d’exécution dos à dos possible ⇒ La capacité d’approvisionnement du serveur est égale à celle qu’il a consommé lors de son activation ⇒ La capacité du serveur est consommée au fur et à mesure de l’arrivée des événements à servir dans le système et la capacité restante est conservée. Au lieu de reconsidérer le budget alloué au serveur périodiquement (comme dans DS), on le fait lorsque les requêtes du serveur sont servies. Ensa de Marrakech, Ordonnancement temps réel 17 Les serveurs de tâches Serveur sporadique : exemple - 2 tâches périodiques P1 (C=1, T=5), P2 (C=2, T=6) - la tâche serveur SS (C=1, T=4) - 2 tâches apériodiques AP1 (R=1, C=0,75), AP2(R=3, C=1), P1(C=1, T=5) P2 (c=2, T=6) SS (C=1, T=4) 1 2 3 4 5 6 7 8 9 10 11 AP1 (R=1, C=0,75) AP2 (R=3, C=1) 1 0,25 0 5 7 10 Ensa de Marrakech, Ordonnancement temps réel 18 Les serveurs de tâches Variante du serveur sporadique Une variante consiste transformer le serveur sporadique en serveur en arri re plan (faible priorit ) lorsque sa capacit est puis e afin de r cup rer le temps non-allou - 2 tâches périodiques P1 (C=1, T=5), P2 (C=2, T=6) - la tâche serveur SS (C=1, T=4) - 2 tâches apériodiques AP1 (R=1, C=0,75), AP2(R=3, C=1), Ensa de Marrakech, Ordonnancement temps réel 19 é é è à é é é é é Les serveurs de tâches Serveur périodique et ordonnancement dynamique EDF Les ordonnancements dynamiques permettent, à priori, une meilleure utilisation du processeur. Leur difficulté de mise en oeuvre provient du fait qu'ils ne peuvent pas distinguer les tâches qui ont des échéances temporelles dures, des tâches qui ont moins de contraintes. L'idée est de servir les tâches aux contraintes plus lâches au moyen de serveurs périodiques. On retrouve la même mise en oeuvre de serveur sporadique et serveur différé dans le cas de EDF. Ensa de Marrakech, Ordonnancement temps réel 20 Les serveurs de tâches Serveur périodique et ordonnancement dynamique EDF Exemple EDF/DS Soit un système composé de deux tâches périodiques et d'un serveur d'événements apériodiques, la tâche 1 est définie par T1= 8, C1 = 3, la tâche 2 par T2=6,C2=2, DS par Tds=4, Cds=1. Les tâches 1 et 2 sont prêtes à l'instant 0. Le premier événement apériodique arrive à t = 1.5 et réclame 0.5 unités de traitement. Le deuxième événement arrive à t = 6 et réclame 2 unités de traitement 1. Faire le test de faisabilité de l'ordonnancement EDF 2. Donner le diagramme d’ordonnancement Ensa de Marrakech, Ordonnancement temps réel 21 Les serveurs de tâches Serveur périodique et ordonnancement dynamique EDF Exemple EDF/DS 1. le test de faisabilité : 3/8 + 2/6 + 1/4 = 23/24 < 1 2. le diagramme d’ordonnancement P1(C=3, T=8) P2 (C=2, T=6) DS (C=1, T=4) 2 4 6 8 10 12 14 16 18 20 AP1 (R=1,5 C=0,5) AP2 (R=6, C=2) Ensa de Marrakech, Ordonnancement temps réel 22 Tâches apériodiques à contraintes relatives Algorithme "Slack Stealer" ⇒ Slack Stealer s'appuie sur RMA ⇒ Pas de serveur pour les t ches ap riodiques ⇒ Lorsque une t che ap riodique est activ e, le syst me recule au maximum le d marrage des t ches p riodiques pour autant qu'elles continuent respecter leurs contraintes temporelles. On utilise la laxit des t ches p riodiques pour ordonnancer les t ches ap riodiques au plus t t Ensa de Marrakech, Ordonnancement temps réel 23 é é à â é â ô é é â â é é é è â Tâches apériodiques à contraintes relatives Exemple d’algorithme "Slack Stealer" à t=4 : Ta3 est activée à t=5 Tp1 est réveillée et L(Tp1) = 3 on peut reculer l'exécution deTp1 jusqu'à t=6 pour laisser Ta3 se terminer de même à t=10 et t=11, recul de Tp1 jusqu'à t=13 et Tp2 jusqu'à t=17 pour laisser Ta4 et Ta5 s'exécuter Ensa de Marrakech, Ordonnancement temps réel 24 Tâches apériodiques à contraintes strictes 2 approches ⇒ Les traiter comme des t ches p riodiques avec une pseudo-p riode repr sentant l'intervalle minimal entre 2 occurrences. utilis dans le cas RMA mais difficile d' valuer la pseudo-p riode engendre une sous-utilisation du processeur ⇒ Ordonnancer les t ches en EDF. A chaque nouvelle t che ap riodique, faire tourner une "routine de garantie" pour v rifier que toutes les contraintes temporelles seront respect es. Si non, refuser la t che. 2 politiques d'acceptation dynamique favorise les t ches p riodiques Ensa de Marrakech, Ordonnancement temps réel 25 é é â é â é â é é é é â é â é Tâches apériodiques à contraintes stricte Acceptation dans les temps creux d'une s quence rigide de t ches ⇒ Ordonnancement EDF des t ches p riodiques ⇒ Les t ches ap riodiques accept es sont ordonnanc es dans les temps creux des t ches p riodiques (~ m thode d'arri re-plan) selon l'algorithme EDF ⇒ Routine de garantie (au r veil d'une t che ap riodique): Teste l'existence d'un temps creux suffisant entre le r veil et l' ch ance de la t che ap riodique) V rifie que l'acceptation de la nouvelle t che ne remet pas en cause le respect des contraintes temporelles des autres t ches ap riodiques d j accept es et non encore termin es Si OK, la t che est ajout e la liste des t ches ap riodiques acceptées. Ensa de Marrakech, Ordonnancement temps réel 26 â é é é à é â é â â é â é é é é â à é é é â â é é â é â é è é é é Tâches apériodiques à contraintes stricte Routines de garantie: m thode des temps creux Ensa de Marrakech, Ordonnancement temps réel 27 é Tâches apériodiques à contraintes stricte Routines de garantie: m thode des temps creux Ensa de Marrakech, Ordonnancement temps réel 28 é Tâches apériodiques à contraintes stricte Exemple de l'acceptation dans les temps creux Ensa de Marrakech, Ordonnancement temps réel 29 Les serveurs de tâches Exercices : Soient deux tâches P1 et P2 et un serveur différé S ordonnancés par RMA. On a C1 = 4, T1 = 12, C2 = 6, T2 = 16, Cserv = 2 et Tserv = 10. Soient les événements e1,e2 et e3 arrivant aux instants t=2, t=14 et t=28 et déclenchant des tâches apériodiques de capacités 1, 4 et 2 respectivement. Donner le chronogramme et représenter la capacité de S. Ensa de Marrakech, Ordonnancement temps réel 30

Cours4-SIC-Ordo-TAper (1).pdf

Document Details

Related

Full Transcript

Upgrade to continue