Laboratoire d'Informatique Scientifique et Industrielle - École Nationale Supérieure de Mécanique et d'Aérotechnique 1- 1 Tutorial ordonnancement Emmanuel

Laboratoire d'Informatique Scientifique et Industrielle - École Nationale Supérieure de Mécanique et d'Aérotechnique 1- 1

Tutorial ordonnancement


Emmanuel Grolleau

LISI/ENSMA



1. Introduction aux modèles d’ordonnancement

–Système exemple

–Programmation dirigée par le temps/par les événements

–Tâches concrètes et non concrètes

–Périodicité

–Structure d’une tâche



• Aéronef Miniature Autonome de Détection et d’Observation– Mini drone

– Envergure 55 cm

– Autonomie 20 à 30 minutes en vol de croisière

– Masse ~930 grammes

Centrale inertielle IMU• 3 gyromètres• 3 accéléromètres• Echantillonnage interne > 1kHz

Récepteur GPS 12 canaux 4Hz30g

Récepteur RC

MODEM 860 MHz• 9600 bps• portée max 8km• 100 mW

ServocommandesMPC-555

• 40 MHz• RTOS OSEK/VDX• Coprocesseur FP

Utilisation• 2 UART (GPS, Modem)• 5 entrées PWM RC• 4 sorties PWM,Servos•CAN ( IMU)

CAN 1Mbps, 50Hz

RS232 56kbps, 4Hz

PPM, 50 Hz

PPM, 50 Hz

RS232 115kbps, 10Hz

Modes de vol• Manuel : pilotage par RC• Assisté : roulis/vitesse ascensionnelle• Autonome : assisté + navigation mission• Retour à la base• Montée sur panne GPS/RC/Modem• Crash sur place sur panne grave (IMU+RC)

38g

38+25g

58g

1.1 Exemple de STR : le drone AMADO



• Gestion parallèle de– Réception GPS

» 1 trame toutes les 250 ms, événement initié par un dispositif externe

» chaque trame arrive octet par octet (120 octets/trame), chaque octet doit être stocké avant l’arrivée du prochain octet (1/5600o/s ~ 175 µs après)

• Pénalité : perte de la trame, donc prise en compte de la position retardée de 250 ms

– Réception de données venant du sol

» 1 trame au plus toutes les 100 ms, événement initié par un dispositif externe

» Chaque trame est composée de 10 octets, chaque octet doit être lu et stocké en moins de 1/960o/s ~ 1 ms

• Pénalité : perte d’une commande provenant du sol

– Réception de donnés de la centrale inertielle

» 1 message toutes les 20 ms, événement initié par un dispositif externe

» Chaque message CAN est composé de 3 trames de 8 octets de données, séparés de 80 µs, comme dans le cas des liaisons RS-232, chaque trame doit être lue et stockée avant l’arrivée de la suivante

• Pénalité : instabilité, perte totale ou partielle de contrôle pouvant mener au crash

– Récepteur de consignes manuelles via le récepteur RC

» Assure le pilotage en mode répéteur lorsque le système est en mode manuel, initié par un dispositif externe

» 5 entrées doivent être surveillées (différence temporelle entre front montant et descendant) et les sorties correspondantes (servo-moteurs) doivent être mises à jour toutes les 20 ms

• Pénalité : fonctionnement manuel saccadé des gouvernes pouvant entraîner un crash

– Génération des commandes vers les servo-moteurs

» Initié par l’horloge interne

» 5 sorties doivent être programmées avec une valeur de commande toutes les 20 ms• Pénalité : fonctionnement saccadé pouvant entraîner un crash

1.1 Besoin de parallélisme



– Envoi des données vers le sol de navigation/horizon artificiel

» Initié par l’horloge interne (choix de 50 ms)• Pénalité : retard d’affichage d’informations au pilote

– Navigation

» Calqué sur l’arrivée d’informations GPS (~250 ms)• Pénalité : mauvaise trajectoire

– Détection/gestion de pannes

» Initié par l’horloge interne (choix de 200 ms)• Pénalité : retard de détection de panne, danger de crash moteur allumé

– Algorithme de régulation d’attitude

» Initié 1 fois sur 3 par les informations provenant de la centrale• Pénalité : perte de contrôle

• Récapitulatif :– 4 « tâches périodiques » sont initiées par un dispositif externe, leur période est imposée par ceux-ci, il nous

faut répondre en temps réel à ceux-ci. On ne connaît pas la date de la première réception.

– 3 « tâches périodiques » initiées par l’horloge interne

– 2 tâches initiées par une autre tâche

– Contraintes de temps inhérentes à la dynamique du système et des dispositifs capteurs/actionneurs

– Les pénalités de retard peuvent aller d’un certain inconfort à la destruction du système, voire à exposer les opérateurs à un risque physique

– La plupart des événements se produisent de façon périodique (il arrive cependant que des événements soient apériodiques)

» Exemple : données provenant du sol, au plus toutes les 100ms (mais cela peut être plus)

1.1 Besoin de parallélisme/2



• Pour lire un signal externe, il existe deux façons de procéder

• Scrutation (polling) : il s’agit de scruter une entrée suffisamment fréquemment pour détecter un changement d’état significatif

– Exemple : scrutation de l’entrée série provenant du GPS

1.2 Scrutation ou interruption ?

Arrivée de l’événement scruté

Réveil d’une scrutation

Exécution d’une scrutation

temps

Période de scrutation

Prise en compte de l’événement scruté

Cas favorable

tempsCas défavorable

Événement manqué car arrivé juste après l’avoir testé

Retard dû à l’occupationdu processeur à autre chose

Ecrasement de l’événement précédent Seul le 3ème événement est perçu,après écrasement des 2 autres



• Principe du délai critique Di

– Une tâche i doit se terminer dans un délai ≤ Di après être activée– Comment cela est-il vérifié ? Lors de l’étude d’ordonnançabilité

• Soit Ci la durée maximum que le processeur doit consacrer à l’exécution d’une tâche• Soit Pi la période avec laquelle la tâche est activée

– Le processeur doit consacrer Ci/Pi de la fraction de son temps à l’exécution de la tâche

• Exemple :– Le GPS : il faut un temps de traitement de 54 µs par octet reçu, et la tâche de scrutation doit être capable de

récupérer des événements séparés de 175 µs– Si l’on choisit une période de scrutation de 87 µs, et un délai critique égal à la période, on est sûr de ne pas

manquer d’octet, mais à un coût de 54/87=62 % du processeur !!!– Ceci est d’autant plus regrettable que les arrivées ont lieu pendant 120 octets/5600 octets/second ~ 21 ms

toutes les 250 ms…. Imaginez le temps gaspillé…– Si l’on ajoute les autres traitements, il nous faudra un processeur nettement plus rapide afin de diminuer le

temps de traitement.

1.2 Scrutation

Période + Délai critique ≤ écart événements

temps

Événement manqué car arrivé juste après l’avoir testéPas d’écrasement de l’événement précédent

Délai critique

Cas défavorable

Prise en compte événement



• Exemple :– Dans le pire cas, la tâche traitant les octets provenant du GPS doit être activée toutes les 175 µs, elle utilisera

donc 54/175 = 31 % du processeur lorsqu’un message arrivera, et ceci pendant 21 ms toutes les 250 ms.

• Le déclenchement des traitements sur interruption ne nécessite pas une période aussi courte que la scrutation. La charge Ci/Ti est donc moins élevée.

• Remarques :– Le traitement par interruption nécessite un capteur actif (en opposition au capteur passif)

– On se ramène souvent au cas périodique, même lorsque les événements ne sont pas périodiques (le pire cas est périodique)

– Il est fréquent que les dates réelles d’arrivée des événements ne soient pas connues, il faut essayer de se ramener au pire cas

1.2 Interruptions

tempsCas défavorable

Latence du noyau+activation de la tâche de traitement

Pire période = durée minimale interévénement



• Programmation dirigée par les événements– Les tâches sont déclenchées par les événements (interruptions)

» Exemple: l’arrivée d’une trame CAN déclenche une interruption

– Avantage : réactivité aux événements à moindre coût processeur

– Inconvénient : dates de réveil des tâches (au moins partiellement) inconnues

– On parle de tâches non concrètes

– Exécution : ordonnancement en-ligne du système, généralement dirigé par les priorités

• Programmation dirigée par le temps– Les interruptions mettent à jour un modèle interne (exemple : dernière trame GPS

reçue, dernière trame IMU reçue, etc.)

– Avantage : système parfaitement connu (voire modulable pour augmenter l’ordonnançabilité)

– On parle de tâches concrètes

– Inconvénient : moins réactif aux événements (temps de réponse de bout en bout plus élevé et charge processeur plus élevée)

– Exécution : ordonnancement hors-ligne ou en-ligne

1.2 Programmation dirigée par le temps/les événements



• Contrainte stricte (hard real-time)– Une violation des contraintes temporelles peut être dangereuse pour le système

» Exemple : tâche d’acquisition centrale inertielle du drone

• Contraintes fermes (firm real-time)– Violer une échéance n’est pas catastrophique mais la qualité du résultat diminue

» Exemple : d’après la simulation aérodynamique, pour la tâche d’acquisition GPS, il faut au moins 1 trame sur 2 pour une navigation presque correcte (1,2)-firm

» Au niveau de la centrale inertielle, 1 trame sur 2 serait suffisante pour assurer une stabilité suffisante du vol

• Contraintes molles (soft real-time)– Respecter les échéances augmente la qualité du résultat

» Exemple : système météo envisageable sur le système AMADO, applications multimédia

1.3 Contraintes de temps



• Tâches périodiques– Tâches réveillées périodiquement

» soit par l’horloge interne (exemple : génération de commandes toutes les 20 ms)

» soit par un événement externe périodique (exemple : navigation toutes les 250 ms à réception d’une trame GPS complète) ou possédant un délai minimal entre 2 déclenchements successifs (réception des données station sol)

» soit par une tâche elle-même périodique (exemple : régulation d’attitude réveillée toutes les 60 ms par la tâche de réception d’information de la centrale inertielle)

• Tâches sporadiques (terminologie J.W.S. Liu)– Tâches à contraintes strictes réveillées par un événement externe non caractérisé par un délai minimal inter-

arrivée. But : test d’acceptance.

• Tâches apériodiques– Tâches à contraintes molles réveillées par un événement externe non caractérisé par un délai minimal inter-

arrivée.

– Ordonnancement de type meilleur effort

1.4 Périodicité des tâches



• Tâches réveillées par l’horloge interneDate_réveil date_couranteFaire toujours

…

Date_réveil Date_réveil + Période_tâcheDormir jusqu’à Date_réveil

Fait

• Tâches réveillées par événement extérieur– Utilisent une ISR (Interrupt Service Routine) exécutée dès que l’interruption a lieu qui déclenche la tâche

Faire toujours

Attendre événement déclencheur

…

Fait

• Tâches logicielles (héritent de la périodicité de la tâche qui les réveille)Faire toujours

Attendre événement ou message ou événement ou …

…

Fait

1.4 Structures typiques des tâches



2. Ordonnancement à priorités fixes

–Notations–Problématiques–Exemple d’algorithme: RM–Validation

»Simulation»Période d’activité»Tests polynomiaux

–Autres algorithmes: DM, Audsley



2.1 Notations

Temps

i

ri,1 ri,2 ri,3 ri,40

Di

di,1 di,2 di,3

Ti

Ci

• Système de tâches S={1, 2, …, n}• Tâche i caractérisée par

– Ci : sa pire durée d’exécution ou WCET (worst-case execution time)– ri = ri,1 sa première date d’activation lorsqu’elle est connue. Dans ce cas on parle de tâche

concrète. Parfois réglable au gré du concepteur (offset free). Lorsqu’elle est inconnue on parle de tâche non concrète. Dans le cas des tâches concrètes, on parle de tâches synchrones au démarrage (ou simultanées) si tous les ri sont nuls, asynchrones au démarrage (ou non simultanées) sinon

– Ti : sa période d’activation; à partir de sa première activation, créant une instance (job) ji,1 (ou i,1) à exécuter, une tâche est activée toutes les Ti unités de temps, donnant à chaque fois naissance à une instance ji,j (ou i,j). Les instances sont non réentrantes les unes par rapport aux autres.

– Di : son délai critique (relative deadline)» Une instance ji,j de la tâche i doit être exécutée avant son échéance (deadline) di,j = ri,j+Di

» Les instances ji,1 et ji,2 respectent leur échéance alors que ji,3 viole son échéance» Si Di=Ti on parle d’échéance sur requête. Si Di>Ti on parle d’échéances arbitraires

(l’exécution d’une instance peut « déborder » sur la période suivante)

Remarque : souvent une lettre majusculesymbolise une durée et une minuscule une date



2.1 Différents modèles de tâches

• Périodicité– Tâches périodiques

– Tâches sporadiques

– Tâches apériodiques (algorithme de type meilleur-effort, pas de validation possible)

• Échéance– Échéance sur requête : Ti = Di

– Échéance : Di ≤ Ti

– Échéance arbitraire (ou non reliées au périodes) : Ti et Di non ordonnés

• Réveil– Tâches concrètes : toutes les dates de réveil sont connues

» Tâches simultanées i, ri = 0

» Tâches différées i / ri 0

» Tâches offset free : on peut choisir les ri comme cela nous arrange

– Tâches non concrètes : les dates de réveil sont inconnues

» Modèle RMA (Rate Monotonic Analysis)

» Tâches non concrètes dans lesquels seuls les décalages entre certaines tâches sont connus• Transactions et tâches à offset

• Modèle multiframe généralisé

• Interdépendance des tâches– Tâches indépendantes : toutes les tâches peuvent être préemptées par toute tâche n’importe quand

– Tâches non préemtibles : une tâche ne peut être préemptée

– Tâches partageant des ressources : l’ordonnancement doit respecter l’exclusion mutuelle

– Tâches à contraintes de précédence : certaines tâches doivent attendre des messages ou synchronisations provenant d’autres tâches



2.1 Différents modèles de tâches

• Facteurs pratiques– Tâches à suspension : après son lancement, une tâche se suspend pendant une entrée/sortie par exemple

– Energy aware scheduling : prise en compte de la gestion d’énergie

– Contraintes fermes, QoS…

– Etc.



2.2 Problématiques de l’ordonnancement

• Problème de décision : un système est-il ordonnançable?– Existe-t-il un algorithme d’ordonnancement qui ordonnance fiablement une configuration donnée ? Le système est-il ordonnançable? Réponse : oui ou non

» Exemple : S = {i::=<Ci,Di,Ti>}={1::=<2,3,5>, 2::=<3,10,10>}

» Exemple : S2 = {i::=<Ci,Di,Ti>}={1::=<4,5,5>, 2::=<3,10,10>} n’est pas ordonnançable sur un seul processeur

• Problème de recherche d’algorithme ou de séquence pour un système de tâches– Trouver un algorithme d’ordonnancement qui ordonnance fiablement un système (méthode en-ligne)

– Exhiber une séquence d’ordonnancement répétable infiniment qui ordonnance fiablement un système (méthode hors-ligne)

• Problème d’ordonnançabilité (c’est un problème de décision)– L’algorithme d’ordonnancement X ordonnance-t-il fiablement le système S?

Un algorithme ordonnance fiablement un système de tâches si tout schéma d’arrivée conforme à la définition dusystème voit le système respecter les contraintes de toutes les instances des tâches

1

2

S est ordonnançable car il existe au moins un algorithme l’ordonnançant fiablement



2. 2 La complexité et l’ordonnancement

• La problématique principale de l’ordonnancement est qu’un bon nombre de problèmes (par exemple, lorsque les tâches partagent des ressources critiques) est NP-difficile ou Co-NP-difficile

– Par conjecture, il n’existe donc pas d’algorithme donnant en tant raisonnable une réponse exacte

– Donner une réponse exacte résulte en une explosion combinatoire

• Problématiques principales de l’ordonnancement en-ligne– Evaluer des algorithmes d’ordonnancement (les contraintes temporelles sont-elles respectées ? Tel critère

est-il minimisé ?) en utilisant des tests approchés (heuristiques) polynomiaux ou pseudo-polynomiaux permettant d’approximer de façon la moins pessimiste possible le comportement d’un algorithme

» Par exemple, calculer une borne supérieure du temps de réponse des tâches qui soit la moins pessimiste possible, mais qui ne puisse en aucun cas être optimiste

– Evaluer et comparer des algorithmes

» Conditions d’optimalité des algorithmes dans des classes d’algorithmes

» Par exemple trouver un ratio qui caractérise l’écart maximal donné par une heuristique par rapport à la réponse que donnerait un algorithme NP-difficile optimal

• Problématiques principales de l’ordonnancement hors-ligne– Limiter au maximum l’explosion combinatoire en réduisant au maximum l’espace des états, en trouvant des

classes d’équivalence entre états lors d’une construction/exploration de l’espace des solutions.



2.3 Classes d’algorithmes d’ordonnancement

Priorités fixesRM,DM,Audsley…

Priorités dynamiquesEDF,EDL,ML,Pfair…

Algorithmes conservatifs(le processeur ne peut êtreinactif que si aucune tâchen’est active)

Ordonnancements non conservatifs

Algorithmes en-ligne(ordonnancement dirigépar les priorités)Connaissance desinstances activesuniquement

Algorithmes hors-ligne(ordonnancement dirigés par le temps)Connaissance du passé et du futur



2.4 Ordonnancement à priorités fixes

• Utilisé par la quasi-totalité des applications embarquées actuelles

• Problèmes– Problème de décision : étant donné un système de tâches, existe-t-il une affectation de priorités ordonnançant

fiablement le système ?

» Réponse liée aux 2 problèmes suivants

– Problème de recherche : trouver une affectation de priorités ordonnançant fiablement le système

» Réponse sous forme d’algorithme de recherche d’affectation nécessitant la résolution du problème suivant

– Problème de décision : l’affectation de priorité donnée ordonnance-t-elle fiablement le système ?

» Réponse sous forme de tests d’ordonnançabilité



2.4.1 Rate Monotonic

• Article de référence :– C.L. Liu and J.W. Layland,"Scheduling algorithms for multiprogramming in real-time environment", Journal of

the ACM, vol. 20(1), pp. 46-61, 1973

• Contexte– Tâches indépendantes, périodiques, à échéance sur requête, non concrètes : une tâche est définie par <C i, Ti>

avec implicitement Di = Ti

• Algorithme– Affecter une priorité en fonction de la période : plus la période est petite, plus la priorité est élevée

• Résultats– Rate Monotonic est optimal dans la classe des algorithmes à priorités fixes

» Cela signifie que si un algorithme à priorités fixes ordonnance fiablement un système de tâches S, alors RM ordonnance fiablement S

» De façon équivalente, tout système ordonnançable par un algorithme à priorités fixes est ordonnançable par RM

– Théorème de l’instant critique: pour des tâches indépendantes, le pire temps de réponse pour une tâche de priorité i advient lorsque toutes les tâches de priorité supérieure à i sont activées simultanément avec la tâche étudiée.

» Conséquence : pour des tâches non concrètes, le cas concret simultané est un pire cas. Si un algorithme ordonnance fiablement un système de tâches simultanées S={<Ci,Ti>} i=1..n, alors il ordonnance fiablement tout système de tâches S={<r i,Ci,Ti>}i=1..n

• Tests d’ordonnançabilité possibles– Simulation => nous aurons à déterminer sur quelle durée (durée d’étude) (CNS)

– Calcul du pire temps de réponse (CNS)

– Calcul de la charge processeur (CS)



2.4.1 Instant critique : illustration

1

2

Supposons que r1-r2 = 4

Temps de réponse 2,1 = 12 Temps de réponse 2,2 = 13

temps

1

2

Temps de réponse 2,1 = 14 Temps de réponse 2,2=13

temps

Supposons les tâches simultanées

• Soit un système de tâches non concrètes S = {1::=<1,4>, 2::=<10,14>} donné sous la forme <Ci,Ti>. Une affectation de priorités RM donnerait Prio(1)=2, Prio(2)=1

• Remarque : le temps de réponse d’une tâche ne dépend que des tâches de priorité supérieure (ou égale) : 1 n’est pas influencée par 2

• Ou doit-on arrêter la simulation pour conclure que le système est fiablement ordonnancé ?



2.4.2 Durée d’étude : cyclicité des ordonnancements

• Contexte– Leung et Merrill l’ont appliqué à des tâches indépendantes à échéance avec l’algorithme à priorités

dynamiques Earliest Deadline

– Geniet et Grolleau ont généralisé le résultat à (presque) tout algorithme d’ordonnancement déterministe pour tâches dépendantes ou indépendantes à échéance

• Résultats– Pour un algorithme d’ordonnancement déterministe A (face à la même configuration, l’algorithme prend la

même décision) d’un système de tâches concrètes simultanées à échéance, et une séquence d’ordonnancement valide A donnée par A sur l’intervalle de temps [0..PPCM(T i)[. Le système est fiablement ordonnancé par A. La séquence infinie obtenue est A*.

– Dans le même contexte, mais pour un système de tâches différées, soit une séquence valide A créée par A sur [0..max(ri)+2PPCM(Ti)[. Notons A,montée la séquence sur [0..max(ri)+PPCM(Ti)[ et A,c la séquence sur [max(ri)+PPCM(Ti).. max(ri)+2PPCM(Ti)[. Le système est alors fiablement ordonnancé par A. La séquence infinie obtenue est A,montée A,c*

• Conséquences– Pour les systèmes de tâches indépendantes non concrètes, le système peut être validé par simulation du

système de tâches concrétisé en simultané

– Les systèmes de tâches indépendantes concrètes peuvent être validées par simulation

– Une séquence d’ordonnancement hors-ligne peut être construite

– Une simulation doit être menée sur une durée PPCM(T i) pour des tâches simultanées

– Et sur une durée au pire de max(ri)+2PPCM(Ti) pour des tâches différées

– Est-ce que c’est grand un PPCM ?

» Non polynomial, une borne supérieure de PPCM(1,2,3,4..,m) est 3m.

» La simulation est une technique non polynomiale• En général, proscrite des techniques de validation (sauf dans le cas concret différé), mais utilisée pour comprendre un

fonctionnement ou en ordonnancement hors-ligne



2.4.3 Demande processeur

1

2

temps

• Remarque 1 : le système se retrouve dans le même état à l’instant 28 qu’à l’instant 0– Par même état nous entendons même motif d’arrivées des tâches, et comme à l’instant initial, le processeur

n’a plus rien à traiter

• Observons cela sur un diagramme de charge de niveau de priorité 1

temps

Chargeà traiter



2.4.3 Autre vue de la demande processeur

temps1

2

1 1 1 2 1 1 1 11

2

Période d’activité

Point creux

Demande processeur

Traitement



2.4.3 Période d’activité

• Intuitivement– La terminaison d’une tâche est retardée (de façon équivalente, son temps de réponse est augmenté) par les requêtes des

tâches de priorité supérieure ou égale

– Plus la première instance des tâches de priorité supérieure (ou égale) est proche de la première instance d’une tâche, et plus elle mettra de temps à descendre à 0 unités de temps de charge restante (c’est quand la charge restant à traiter d’une tâche tombe à 0 que celle-ci est terminée)

– Remarque : la couleur n’a pas d’importance, puisque le diagramme fait apparaître les périodes d’activité du niveau de priorité du diagramme, ici celle de la tâche 2

– En comparaison, voici le diagramme des charges de niveau de priorité 2. Les périodes d’activité de niveau de priorité 2 ne durent qu’une unité de temps

temps

Chargeà traiter

Ceci est un temps creuxCeci est une période d’activitéde niveau de priorité 1

Ceci aussi

temps

Chargeà traiter

Instant critique

On peut voir sur ce diagramme de charge que l’algorithme RM est conservatif

Ceci est un instant creux



2.4.3 Calcul du pire temps de réponse (RTA)

• Articles de référence :– M. Joseph and P. Pandya,"Finding response times in real-time system", The Computer Journal, vol. 29(5), pp.

390-395, 1986

• Contexte– Tâches indépendantes à échéance inférieure ou égale à la période pour [JP 86]

• Résultats– Soit hp(i) l’ensemble des indices de tâches de priorité supérieure (ou égale) à la priorité de i, en excluant i

» Par exemple, soient {1, 2, 3, 4} de priorité croissante, hp(2)={3,4}

– Le temps de réponse de i est donné par la charge à traiter plus l’interférence des tâches de priorité supérieure, en démarrant à l’instant critique, car le pire temps de réponse de i intervient dans la plus longue période d’activité de niveau de priorité prio(i), et celle-ci démarre (y compris pour les tâches à échéances arbitraires) à l’instant critique

• Application au cas Di≤Ti

– Si i respecte ses échéances, son pire temps de réponse est le plus petit point fixe de la suite

)(

)()1(

)0(

ihpj

jj

ni

ini

ii

CT

RCR

CRLa suite converge si et seulement si U≤1

Complexité pseudo-polynomiale

RTA



2.4.3 Calcul du pire temps de réponse échéances arbitraires

• La formule de calcul de [JP 86] ne peut pas s’appliquer telle qu’elle est définie, car elle ne prend pas en compte la possibilité pour une instance i,j de la tâche i d’interférer avec les instances suivantes. Cependant le résultat suivant reste valide

– Le temps de réponse de i est donné par la charge à traiter plus l’interférence des tâches de priorité supérieure, en démarrant à l’instant critique, car le pire temps de réponse de i intervient dans la plus longue période d’activité de niveau de priorité prio(i), et celle-ci démarre (y compris pour les tâches à échéances arbitraires) à l’instant critique

– Il faut donc aller jusqu’à la fin de la période d’activité initiée par l’instant critique et regarder dans cette période d’activité quelle est l’instance de tâche avec le plus long temps de réponse

• C’est l’idée exploitée par [Leh 90]. L’idée est qu’il faut tester toutes les échéances des instances situées dans la première période d’activité

• Ri(*)(k) donne la date de fin la plus tardive de i,k (i.e. kième instance de i) d’où

• On applique cette formule de la façon suivante : on commence à k=1 (on a alors le même fonctionnement que [JP 86]).

– Si Ri(*)(1)>Di, il y a violation d’échéance (on peut tout de même continuer si l’on souhaite obtenir le pire temps de

réponse)

– Si Ri(*)(1)>Ti, la deuxième instance fait partie de la première période d’activité, on termine donc pour k=1, mais on

sait qu’il faudra tester aussi k=2. De même si Ri(*)(2)>2Ti, il faudra tester k=3, etc. tant que Ri

(*)(k)>kTi on teste k+1. Le processus converge si et seulement si U<1. Chaque date de fin d’instance i,k est comparée à di,k

)(

)()1(

)0(

)(

)(

ihpj

jj

ni

ini

ii

CT

RkCkR

kCkR

iii TkkRkTR )1()()( (*)



2.4.4 Test polynomiaux

• Ils se basent sur l’utilisation processeur– Ui=Ci/Ti

– U=Ui

• Condition nécessaire triviale d’ordonnançabilité U1

• Liu & Layland ont proposé une condition suffisante d’ordonnançabilité (la plus connue mais pas la meilleure)– CS signifie que

» si la réponse au test est OUI, le système est fiablement ordonnancé par RM

» Si la réponse au test est NON, on ne peut conclure

• Condition suffisante de Liu & Layland 73– Soit S une configuration de n tâches indépendantes à échéance sur requête. Le système S est ordonnancé

fiablement par RM si U≤ n (21/n – 1)

69.0)2ln()12(lim /1 n

n n

charge100%69%0%

incertitude

n

1

0.690.780.82



2.4.4 Test polynomiaux plus récents

• Borne de Sjödin et Hansson 98

• Borne hyperbolique (Bini et al. 03)

• Borne de Bini et Baruah 07– Tient en échéances arbitraires

• Tests polynomiaux réglables basés sur la RTA -HET ( Hyperbolic Exact Test) de Bini et Buttazzo 04

– Schémas d’approximation

)(

)(

1ihpj j

iihpj j

iU

CTR

ni iU..12)1(

)(

)(

1

)1(

ihpj j

ihpj jji

iU

UCCTR



2.4.5 Récapitulatif

• RM est optimal dans la classe des algorithmes à priorités fixes pour les systèmes de tâches indépendantes préemptibles à échéance sur requête, concrètes simultanées ou non concrètes

• Différents CS polynomiales basées sur la charge ou bien sur la RTA

• Une CN triviale est que U<1 pour qu’un système de tâches soit ordonnançable sur 1 processeur

Tout algo

• La simulation permet, à un coût exponentielle, de valider un système de tâches indépendantes et préemptibles

– Une séquence d’ordonnancement est périodique sur une période de PPCM(T i) à partir du début pour des tâches simultanées, ou au pire de max(r i)+PPCM(Ti) pour des tâches différées

Tout algodéterministe

• Le pire temps de réponse d’une tâche intervient dans la première période d’activité, qui démarre à l’instant critique (tâches indépendantes, préemptibles, concrètes simultanées ou non concrètes)

– Dans le cas Di≤Ti, il suffit de tester la 1ère instance de chaque tâche (pseudo-polynomial)

– Dans le cas Di>Ti il faut tester toutes les instances de la 1ère période d’activité (exponentiel)

Tout algoà priorités fixes

Spécifiqueou tout algo à priorités fixes



2.4.6 Deadline Monotonic

• Contexte– Tâches indépendantes, périodiques, à échéance D i≤Ti, simultanées (donc concrètes) : une tâche est définie

par <Ci,Di,Ti>

• Algorithme– Deadline Monotonic : Affecter une priorité en fonction du délai critique : plus le délai critique est petit, plus la

priorité est élevée

• Résultats– Deadline Monotonic est optimal dans la classe des algorithmes à priorités fixes

• Tests d’ordonnançabilité possibles– Simulation (CNS) mais coût exponentiel (de l’ordre de PPCM(T i))

– RTA (CNS) à coût pseudo-polynomial : aucun changement par rapport à RM

– Conditions suffisantes polynomiales



2.4.7 L’affectation d’Audsley <ri,Ci,Di,Ti>

• Contexte– Tâches indépendantes, périodiques, à échéance arbitraires, concrètes non simultanées : une tâche est définie

par <ri,Ci,Di,Ti>

• Algorithme– Idée : le temps de réponse d’une tâche ne dépend que des tâches de priorité supérieure. Donc soit k la tâche

de priorité la plus faible. Son temps de réponse est indépendant de l’ordre des priorités des tâches de priorité supérieure (rappelons-nous que le calcul du temps de réponse se base sur la période d’activité de niveau Prio(k), qui n’est dépendante que de la charge des tâches, et non pas de leur priorité relative)

– Principe : trouver une tâche ordonnançable avec la priorité la plus faible (appliquer un test d’ordonnançabilité dérivé de [Leh 90]) ou une simulation

– Trouver dans les tâches restantes une tâche ordonnançable avec le niveau de priorité supérieur, procéder ainsi jusqu’à ce que toutes les tâches aient une priorité

• Résultats– L’affectation d’Audsley est optimale pour les tâches indépendantes préemptibles concrètes non simultanées

• Tests d’ordonnançabilité possibles– Le système est ordonnançable par construction

• Complexité– Il y a au plus n(n-1)/2 affectation à tester, le problème étant que le test d’ordonnançabilité effectué à chaque

pas est exponentiel

– La complexité vient principalement du fait qu’il est Co-NP-difficile de déterminer l’endroit où débute la plus longue période d’activité pour chaque niveau de priorité une simulation (ou quasi équivalent en complexité) est requise



2.4.7 Audsley : exemple

• Soit S = {<0,1,4,4>,<1,3,8,6>,<3,1,4,4>} un système de tâches indépendantes, préemptibles, concrètes données sous la forme <ri,Ci,Di,Ti>

– Essayons d’affecter la priorité 1 (la plus faible) à 1

– Cela ne fonctionne pas, 1 ne peut donc se voir assigner la priorité la plus faible

– Essayons d’affecter la priorité 1 à 2

– Dans ce cas, le pire temps de réponse de 2est 7, on peut donc lui affecter cette priorité

Charge de prio1

1 2 2 2 2 2 21 1 1 1 1 1 13 3

3 3 3

3 3

3

Fin de période d’activité

Violation d’échéance

temps

Réveils

Échéance de 1

Charge de prio1

1 2 2 2 2 2 21 1 1 1 1 1 13 3

3 3 3

3 3

3

temps

Réveils



2.4.7 Audsley : exemple /suite

– Essayons maintenant d’affecter la priorité 2 à 1

– Le pire temps de réponse est 1

– On donne alors la plus forte priorité à 3. La CNS d’ordonnançabilité pour 3 est C3≤D3 puisque c’est la seule tâche prise en considération.

Charge de prio2

1 1 13 3 3

temps

Réveils



3. Facteurs pratiques

–Ressources critiques

–Tâches non préemptibles

–Contraintes de précédence



3.1 Ordonnancement en présence de ressources critiques

• Lorsque des ressources critiques sont en jeu, il faut prendre en compte le problème de l’exclusion mutuelle

– Problèmes possibles

» Interblocage (dîner des philosophes)

» Inversion de priorité (voir plus loin)

» Anomalies d’ordonnancement

1

2

temps

3

Utilisation de la ressource R

1

2

temps

3

C3=5 => violation d’échéance, c’est une anomalie d’ordonnancement

C3=6 => cela fonctionne sur la simulation

La tâche est bloquée lors de l’accès à la ressource, c’est normal, cela s’appelle un blocage (direct)



3.1.1 Inversion de priorité

• Une inversion de priorité a lieu lorsqu’une tâche se voit retarder par une tâche de priorité inférieure, alors qu’elle ne partage pas de ressource directement avec cette tâche

1

2

temps

3

Utilisation de la ressource R

Inversions de priorité : 2 s’exécute alors que 1 est bloquée, pourtant ce n’est pas 2 qui détient la ressource bloquant 1

1

2

temps

3

blocage

héritage

Libération R => retour au niveau de priorité initiale



3.1.2 Protocole à Priorité Héritée

• Article de référence :– L. Sha, R. Rajkumar and J.P. Lehoczky,"Priority inheritance protocols : an approach to real-time

synchronization", IEEE Transactions on Computers, vol. 39n. 9, 1990, pp. 1175-1185

• Contexte– Algorithmes à priorités fixes

• Nom– Protocole à priorité héritée (PPH) ou Priority Inheritance Protocol (PIP)

• Principe– Lorsqu’une tâche i est bloquée pour accéder à une ressource R, la tâche j détenant R hérite de la priorité de i pendant la durée de sa section critique sur R

• Résultats– Supprime toute inversion de priorité

• Effets de bord– Même une tâche n’utilisant pas de ressource peut subir un blocage indirect de la part d’une tâche de priorité

inférieure

1

2

temps

3



3.1.2 Etude du Protocole à Priorité Héritée

• Inconvénients– Ne supprime pas l’interblocage

– Si une tâche utilise plusieurs ressources, elle peut être bloquée à chaque entrée en section critique

– Complexe à implémenter

• Implémentation– Lorsqu’une tâche est en section critique, son niveau de priorité peut être augmenté lorsqu’elle est en attente

du processeur ou bloquée par une instruction de type prendre(ressource) sur une ressource qu’elle détient. Pendant son exécution, plusieurs tâches peuvent augmenter sa priorité

i

Utilisation de R1

Utilisation de R2

Utilisation de R1 et R2

Héritage de prio(j) à cause de R1

Héritage de prio(k) à cause de R2

Héritage de prio(m) à cause de R2

La priorité retombe à prio(j)




1

2

temps

3

Utilisation de R1

Utilisation de R2


Héritage de priorité

• Une tâche peut être bloquée par une section critique pour chaque ressource

– Blocage direct ou indirect

• La durée de blocage Bi d’une tâche due aux sections critiques du système est la durée pendant laquelle une tâche peut être bloquée (de façon directe ou indirecte) par une tâche de priorité inférieure

• Pour PIP

– lp(i) ensemble des indices de plus petite priorité que i

– Durée SCi(R) : durée maximale de section critique de i sur R

• Dans l’exemple, B1 = 5, B2=3, B3 = 0

Rressource

jilpji RSCduréeB ))((max )(




• S’il y avait une tâche de priorité intermédiaire située entre 1 et 2, même si elle n’utilisait pas de ressource, son Bi serait de 5 (durée SC3(R1)+durée SC2(R2)) car elle peut subir un blocage indirect dû à 1

• Si il y avait une tâche de priorité supérieure à celle de 1, en appliquant la formule proposée, son Bi serait de max{durée SC3(R1),durée SC1(R1)}+max{durée SC2(R2),durée SC1(R2)}=5

– Cependant, il est évident que la formule donnée est pessimiste dans ce cas, car cette tâche ne pourrait en aucun cas subir un blocage indirect, pourquoi ?

• La formule devrait prendre en compte le fait qu’on ne prend en compte que les ressources utilisées par au moins une tâche de priorité supérieure à la tâche dont on calcule le Bi

• En fait, les formules de calcul du pire temps de réponse sont

)(

)( ))((maxihpdetâcheuneparutiliséeRressource

jilpji RSCduréeB

)(

)()1(

)0(

)(

)(

ihpj

jj

ni

iini

iii

CT

RkCBkR

kCBkR

)(

)()1(

)0(

ihpj

jj

ni

iini

iii

CT

RCBR

CBR

Pour Di≤Ti Pour des échéances arbitraires)1()((*), kTkRTR iiki



3.1.3 Protocole à Priorité Plafond

• Article de référence :– L. Sha, R. Rajkumar and J.P. Lehoczky,"Priority inheritance protocols : an approach to real-time

synchronization", IEEE Transactions on Computers, vol. 39n. 9, 1990, pp. 1175-1185


• Nom– Protocole à priorité plafond (PPP) ou Priority Ceiling Protocol (PCP)

• Principe– Chaque ressource est munie d’une priorité plafond égale à la plus grande priorité des tâches susceptibles de

l’utiliser

– Une variable, nommée plafond système, est la priorité plafond maximale des ressources en cours d’utilisation

– Une tâche ne peut entrer en section critique (opération Prendre(R)) que si sa priorité est strictement supérieure au plafond système ou si elle détient elle-même le plafond système

– Lorsqu’une tâche i est bloquée pour accéder à une ressource R, la tâche j détenant R hérite de la priorité de i pendant la durée de sa section critique sur R

• Résultats– Supprime toute inversion de priorité

– Une tâche ne peut être bloquée au maximum que par une seule section critique de priorité inférieure par période d’activité

– Absence d’interblocage

• Effets de bord– Même une tâche n’utilisant pas de ressource peut subir un blocage indirect de la part d’une tâche de priorité

inférieure

– Une tâche, même si elle est la plus prioritaire des tâches active, peut être bloquée en accédant à un sémaphore même libre : c’est un blocage d’évitement



3.1.3 Comparaison PPP - PPH

1

2

temps

3

Utilisation de R1

Utilisation de R2



PPH

1

2

temps

3

PPP = > 1 blocage max

Blocage d’évitement



3.1.3 Etude du Protocole à Priorité Plafond

• Sur l’exemple précédent : B1=max(2,3) ; B2 = max(3) ; B3 = 0

• Les formules de calcul du pire temps de réponse sont les mêmes, sauf que Bi est plus faible qu’avec le PPH

• Problème : implémentation aussi complexe que PPH

))((max)(),(

RSCduréeB jihpdetâcheuneparutiliséeRressource

iilpj

)(

)()1(

)0(

)(

)(

ihpj

jj

ni

iini

iii

CT

RkCBkR

kCBkR

)(

)()1(

)0(

ihpj

jj

ni

iini

iii

CT

RCBR

CBR

Pour Di≤Ti Pour des échéances arbitraires



3.1.4 Protocole à Super Priorité ou Priorité Plafond Immédiat

• Article de référence :– C. Kaiser,"Exclusion mutuelle et ordonnancement par priorité", Technique et Science Informatiques, vol. 1(1),

pp. 59-68, 1982


• Nom– Protocole à priorité plafond immédiat (PPPI) ou Protocole à Super Priorité ou Stak Based Priority Ceiling

Protocol

• Principe– Chaque ressource est munie d’une priorité plafond égale à la plus grande priorité des tâches susceptibles de

l’utiliser (comme pour PPP)

– Une variable, nommée plafond système, est la priorité plafond maximale des ressources en cours d’utilisation (comme pour PPP)

– Une tâche ne peut entrer en section critique (opération Prendre(R)) que si sa priorité est strictement supérieure au plafond système ou si elle détient elle-même le plafond système (comme pour PPP)

– Lorsqu’une tâche i entre en section critique, elle hérite pendant toute la section critique de la priorité plafond de la ressource

• Résultats– Mêmes propriétés que le protocole à priorité plafond, en effet même si le comportement peut être différent, le

calcul du facteur de blocage est identique

– Implémentation très simple

» Il en résulte que ce protocole est implémenté sur la plupart des exécutifs (norme POSIX, norme OSEK/VDX) et en Ada

» Etrangement, il n’est pas proposé par VxWorks



Utilisation de R1

Utilisation de R2



1

2

temps

3

PPP = > 1 blocage max

3.1.4 Protocole à Super Priorité ou Priorité Plafond Immédiat




3.1.5 Complexité et optimalité en présence de ressources

• Article de référence :– A.K. Mok, "Fundamental design problems of distributed systems for the hard real-time environment", Thesis,

Massachussets Institute of Technologie, 1983

• Contexte– Tout algorithme d’ordonnancement, tâches avec ressources critiques

• Résultats– Le problème de décider si un système de tâches avec contraintes de ressources est ordonnançable est un

problème NP-difficile

– Aucun algorithme en-ligne (non clairvoyant) n’est optimal pour ordonnancer des tâches avec contraintes de ressources

1

2

Question : ce système peut-il être validé pour DM-PPP ?



• Preuve du résultat :– Le problème de décider si un système de tâches avec contraintes de ressources est ordonnançable est un

problème NP-difficile

» Réduction de 3-Partition :

• soit un ensemble {n1, n2, …, n3m} de 3m entiers tels que ni=mB et B/4<ni <B/2 (remarque, il y a une petite erreur dans la définition utilisée dans [Mok 83] : il utilise ≤, ce qui rendrait la preuve fausse)

• 3-Partition : est-il possible de partitionner l’ensemble en ensembles disjoints de 3 entiers tels que leur somme vaut B ?

» NP-complet au sens fort [Garey&Johnson]

– Montrer que tout instance de 3-Partition peut s’exprimer comme une instance d’un problème d’ordonnancement avec ressources, et ceci avec une transformation polynomiale des données d’entrée

» Prendre une tâche 3m+1 définie par <C3m+1=1, D3m+1=1,T3m+1=B+1> partageant la ressource critique R (le système de tâches défini est tel que aucune tâche ne peut être préemptée=>le même résultat tiendrait en non préemptible)

» Pour chaque nombre ni construire une tâche périodique i définie par <Ci,Di,Ti> avec Ci=ni, et Di=Ti=mB+m (échéance sur requête) utilisant une ressource critique R pendant son exécution (i.e. les tâches ne peuvent pas se préempter mutuellement)

» U=100%. Le système est ordonnançable si et seulement si on peut placer dans chaque intervalle de taille B 3 tâches dont la somme des Ci vaut B. Cela signifie que si on répond à la question « le système est-il ordonnançable? » on répond par la même occasion à la question 3-Partition

– Ceci s’appelle une réduction polynomiale : Ordonnancer en présence de ressources est au moins aussi dur que 3-Partition => Ordonnancer en présence de ressources est NP-difficile au sens fort (il serait NP-complet si l’équivalence était montrée, ou un algorithme NP exhibé)

3.1.5 Ordonnancer avec ressource est NP-difficile

3m+1

B B B B



3.1.6 Conclusion sur les protocoles de gestion de ressources

• Problèmes rencontrés– Le problème de l’ordonnançabilité est NP-difficile au sens fort

– Un algorithme non clairvoyant ne peut pas être optimal

– En l’absence de protocole, on a des problèmes d’inversion de priorité et d’anomalies d’ordonnancement

– La simulation ne valide en aucun cas le système

• Protocoles principaux définis dans le cas des techniques d’ordonnancements à priorité fixe

– Protocole à priorité héritée

» Durée de blocage relativement longue

» Interblocage possible

» Implémentation coûteuse en temps

– Protocole à priorité plafond

» Durée de blocage courte

» Absence d’interblocage

» Implémentation coûteuse en temps

– Protocole à priorité plafond immédiate

» Durée de blocage courte

» Absence d’interblocage

» Implémentation simple et peu coûteuse

» Un peu anti-intuitif



3.2 Ordonnancement non-préemptif

• Complexité du problème d’ordonnançabilité– NP-difficile (la preuve de Mok tient dans ce contexte)

• A partir de ce que nous savons, nous pouvons déduire les propriétés suivantes– L’instant critique pour une tâche a lieu lorsqu’elle se réveille en même temps que toutes les tâches plus

prioritaires qu’elle

– Dans le cas du protocole à priorité plafond, une tâche peut être retardée une seule fois par une tâche de priorité plus faible pendant sa période d’activité



3.3 Contraintes de précédence et synchronisations

• Contraintes de précédence (représentent les messages/synchronisations)– Contraintes de précédence normale : les tâches ont la même période

• Découpage en forme normale– Chaque attente de message/synchronisation se trouve en début de tâche

– Chaque envoi de message/synchronisation se trouve en fin de tâche

– La priorité d’une tâche et sa date de réveil doivent être cohérentes avec les précédences

• Exemple 1 = <0,4,8,8>, 2 = <0,4,8,8>, 3 = <1,1,4,8>, 4 = <0,1,7,8>

– Algorithme DM

– Découpage 1,1 = <0,1,8,8>, 1,2 = <0,2,8,8>, 1,3 = <0,1,8,8>, 2,1 = <0,1,8,8>, 2,2 = <0,2,8,8>, 2,3 = <0,1,8,8>, 3 = <1,1,4,8>, 4 =

<0,1,7,8>

– Mise en conformité des dates de réveil et priorités: si i j alors ri ≤rj et avec DM Di≤Dj (les ex-æquo sont traités de sorte que les priorités soient cohérentes avec les précédences)

1 2

3

4

m1

m2

m4

m3

1,1 2,1

3

4

m1

m2

m4

m3

1,2

1,3

2,2

2,3




– Ajustement des ri (et des Di pour conserver les mêmes délais critiques par rapport aux dates de réveil initialement données)

» r2,1=1r3, et D2,1=D2-(r2,1-r2)=8-1=7

» r2,2=1 max(r1,1,r2,1), et D2,2=D2-(r2,2-r2)=8-1=7

» r2,3=1 r2,2, et D2,3=D2-(r2,3-r2)=8-1=7

» r1,3=1 max(r1,2,r2,1) et D1,3=D1-(r1,3-r1)=7

» r’4=1 r2,3 et D’4=D4-(r’4-r4)=6

– Ajustement des délais critiques

» Toutes les tâches précédant 4 doivent avoir un délai critique ≤6

» D2,1=6, D1,1=6, D2,2=6, D2,3=6

» Toutes les tâches précédent 1,3 doivent avoir un délai critique ≤7 => D1,2=7

1,1 2,1

3

4

m1

m2

m4

m3

1,2

1,3

2,2

2,3

<1,1,4,8>

<1,1,6,8>

<1,2,6,8>

<1,1,6,8>

<1,1,6,8>

<0,1,6,8>

<0,2,7,8>

<1,1,7,8>




• Simuler le fonctionnement du système– Vérifier que les contraintes de précédence sont respectées naturellement par l’ordonnancement

• Attention, il faut avoir conscience du fait que le découpage est un artifice de validation, les tâches ne sont pas découpées en réalité

• Attention, si les priorités ne sont pas cohérentes avec les précédences, simuler n’est pas valider

– Illustration: une anomalie d’ordonnancement

– Rappel : Ci est une durée au pire, donc à l’exécution il est possible que C1<2 (par exemple Ci=1)

1

2

temps

3Prio

rité

cro

issa

nte

1

2

temps

3Prio

rité

cro

issa

nte



3.4 Modèle à gigue d’activation

• Article de référence– K. Tindell, “Adding Time-Offsets to Schedulability Analysis”, Technical Report YCS 221, Dept of Computer

Science, University of York, England, January 1994

• Justification– Lorsque les tâches attendent un message provenant d’un autre processeur, ordonnancé séparément du

processeur analysé, une tâche attendant un message périodique sur le réseau peut se réveiller plus ou moins tard par rapport à sa date de réveil prévue. En effet, la tâche émettrice peut être plus ou moins retardée sur l’autre processeur (voir analyse holistique dans le cas réparti).

– Une instance i,k d’une tâche à gigue d’activation (jitter ou release jitter) est activée entre les dates ri,k et ri,k+Ji. Une telle tâche concrète avec gigue d’activation est définie par <r i, Ci, Di, Ji, Ti>, et une non concrète par <Ci, Di, Ji, Ti>.

• Résultat de base connu [Tin 94]– La plus longue période d’activité d’une tâche coïncide avec le réveil d’au moins une tâche de plus haut niveau

de priorité dont le réveil a été retardé d’une valeur correspondante à sa gigue maximale

1

J1



3.4 Instant critique avec gigue de démarrage

1

2

J2

3

J1

Instant critique pour une tâche de plus faible priorité

J3

– Interférence sur une période d’activité de niveau j de longueur t :

– La longueur de la plus longue période d’activité de niveau de priorité i est donc le point fixe de

– Le temps de réponse de chaque instance i,k faisant partie de cette période d’activité est donné par

(noter la présence du jitter maximal)

jihpj j

j CT

tJ

)(

)(

)()1(

)0(

)(

)(

ihpj

jj

nij

iini

iii

CT

RJkCBkR

kCBkR

iii TkJR )1((*)



3.5 Autres facteurs pratiques

• Groupes de tâches liés par des relations d’offset– Modèle multiframe

– Modèle multiframe généralisé

– Transactions

• Tâches qui se suspendent



4. Ordonnancement à priorités dynamiques

–Optimalité

–Concept de demande processeur

–Comparaison avec l’ordonnancement à priorités fixes



4.1 EDF

• Proposé à l’heure actuelle dans quelques noyaux universitaires expérimentaux

• L’algorithme le plus utilisé est Earliest Deadline First (EDF)– La priorité d’une tâche est d’autant plus importante que son échéance est proche

• Raison– Règle de Jackson [Jac 55]: Etant donné un système de tâches sporadiques simultanées indépendantes à

échéance, n’importe quel algorithme qui exécute les tâches dans l’ordre des échéances non décroissantes est optimal en vue de minimiser le retard maximal

– Retardi (Lateness): TRi – di ; retard maximal Lmax= maxi{Retardi}

– J.R. Jackson, « Scheduling a production line to minimize maximum tardiness », Management Science Research Project 43, University of California, Los Angeles, 1955

– Preuve : réalisée par échange

» Soit un algorithme A minimisant le retard maximal, tel qu’il existe deux tâches a et b avec da≤db et b termine juste avant a. Nous nommons la séquence ainsi produite. Notons que A ne respecte pas la règle de Jackson. Le retard maximal entre ces deux tâches dans , Lmax(a,b) est donné par le retard de a. Prenons maintenant la séquence ’ identique à sauf que a s’exécute juste avant b. Le retard maximal est donné soit par le retard de a (qui est inférieur à celui obtenu dans ) soit par le retard de b, qui ne peut lui non plus être supérieur à celui de a dans . Donc on peut toujours échanger l’ordre d’exécution 2 à 2 sans augmenter le retard maximum en partant d’une séquence, pour arriver à une séquence respectant la règle de Jackson qui minimise donc le retard maximal.

b a

ba’

da db

da db

L’a L’b

LaLb



4.2 Optimalité

• Articles de référence– W. Horn, « Some simple scheduling algorithms », Naval Research Logistic Quarterly, 21, 1974

– M.L. Dertouzos,"Control robotics: the procedural control of physical processes", proc. IFIP Congress 1974, pp. 807-813

• Contexte : tâches indépendantes

• Résultats– Jackson a étudié l’ancêtre d’EDF (nommé Earliest Due Date) et a montré son optimalité pour minimiser le

retard maximal lorsque toutes les tâches sont simultanées et sporadiques (noter qu’EDD n’a pas à être préemptif).

– [Horn74] reprend cet algorithme sous le nom d’EDF et montre son optimalité quant à la minimisation du retard maximal même dans le cas où les tâches ne sont pas simultanées

– [Der74] démontre l’optimalité d’EDF pour le respect d’échéances pour des tâches sporadiques réveillées à n’importe quel moment. Cela signifie que dans ce cas, si le système est ordonnançable, alors EDF l’ordonnance fiablement.

– [LL73] un système de tâches périodiques, indépendantes, à échéance sur requête, simultanées ou non, est ordonnançable par EDF si et seulement si U≤1.

» On voit que dans ce cas, même avec une charge de 100%, EDF respecte toujours les échéances

– Dans un contexte où la préemption est toujours autorisée (pas de ressources critiques, tâches préemptibles), un système est ordonnançable si et seulement si il est ordonnancé fiablement par EDF (résultat très fort d’optimalité !)

– EDF perd son optimalité lorsque la préemption n’est pas autorisée (tâches non préemptibles, ou bien exclusions mutuelles)



4.3 validation EDF : cas Di≤Ti

• Article de référence– K. Jeffay and D.L. Stone,"Accounting for Interrupt Handling Costs in Dynamic Priority Task Systems", proc.

IEEE Real-Time Systems Symposium, Raleigh-Durham, NC, USA, 1993

– S.K. Baruah, L.E. Rosier and R.R. Howell,"Algorithms and complexity concernig the preemptive scheduling of periodic, real-time tasks on one processor", Real-Time Systems, vol. 2, pp. 301-324, 1990

• Contexte : tâches indépendantes, concrètes simultanées

• Concepts– Demande processeur et période d’activité : une période d’activité pour EDF est une période [t,t+L] pendant

laquelle la demande processeur (charge restante à traiter) d’échéance ≤t+L est non nulle.

• Résultats– En tâches simultanées, le temps de réponse le plus long arrive dans la première période d’activité

– [JS93] Un système de tâches simultanées avec Di=Ti est ordonnançable par EDF si et seulement si

– Avec Bp (busy period) longueur de la période d’activité, obtenue par point fixe de l’équation

– Remarque : en synchrone et à échéance sur requête, bien entendu la CNS U≤1 est à utiliser à la place de cette CNS. Cependant, cette CNS sert de base à la CNS de [BRH90] fonctionnant pour D i≤Ti:

i

n

i ipi C

T

LLBTPPCML

1

),),(min( Charge à traiter avant L (Di=Ti)

n

ii

i

CT

LLW

1

)(

i

n

i i

i

pikiiikiki

CT

DLLDL

BTPPCMdDkTddD

1

,,,

1,

)),(min(, Ensemble d’échéances de la périoded’activité

Nombre de périodes entièrement terminées+ la période en cours



4.3 Validation EDF : cas non concret

• Article de référence– M. Spuri, "Analysis of deadline scheduled real-time systems", INRIA, 2772, Jan, 1996

• La plupart des applications dirigées par les priorités sont composées de tâches non concrètes.

• Résultat– Le pire temps de réponse d’une tâche se trouve dans une période d’activité initiée par un instant où toutes les

autres tâches sont réveillées en même temps.

• Interprétation– Lorsque l’on veut évaluer le temps de réponse d’une tâche non concrète, il faut considérer que toutes les

autres tâches sont réveillées en même temps mais faire varier la date de réveil de la tâche dont on étudie le temps de réponses.

– La gigue d’activation, lorsqu’il y en a une, est appliquée comme en priorités fixes : on considère un instant critique où toutes les autres tâches sont réveillées avec une gigue de démarrage maximale à l’instant critique. Pour la tâche étudiée, on fait varier sa date de réveil entre les instants 0 et r tels que la période d’activité ait une longueur Bp. Dès lors que la période d’activité diminue, on peut arrêter l’étude.

– La validation d’un tel système est longue puisqu’il faudra faire varier la date de réveil, au pire sur la longueur de la période d’activité qui peut être PPCM(Ti). Pour chaque date de réveil, il faut alors faire un calcul (recherche de point fixe) de temps de réponse.




• Articles de référence– M. Chen and K. Lin,"Dynamic priority ceilings : a concurrency control protocol for real-time systems", Real-

Time Systems, vol. 2(4), pp. 325-346, 1990

• Nom : Protocole à Priorité Plafond Dynamique (PPPD)

• Principe : le plafond système est recalculé à chaque fin de tâche afin de s’adapter à la variation des priorités

• Exemple : 1::=<0,1,4,6>, 2::=<-0.33,2,8,8>, 3::=<-0.66,3,12,12>. Caractérisons la priorité d’une tâche par sa prochaine date d’échéance. Plus le nombre est petit, plus la priorité est élevée. A l’instant -0.66, prio(1,-0.66)=4, prio(2,-0.66)=8 , prio(3,-0.66)=12. Le plafond de R1 est donc p1(-0.66) =min{4,12}=4, et le plafond de R2 est p2(-0.66)=min{8,12}=8. Le plafond système est alors défini comme dans le protocole original, et les règles et propriétés sont les mêmes

Utilisation de R1Utilisation de R2



1

2

temps

3


p1=4p2=4c=4 p1=4

p2=4c=4

p1=10p2=7.66

p1=10p2=10c=

p1=16p2=15.66c=

c=10

c=7.66 c=15.66

p1=16p2=16c=

p1=16p2=16c=16

p1=22p2=22c=

c=22 c=

c= 22




• Inconvénients– Implémentation complexe et coûteuse (gestion de l’héritage et mise à jour des plafonds)

– Le protocole Preemption Ceiling a été proposé : celui-ci se base sur une table prévisionnelle. Il a été proposé dans : T.P. Baker,"Stack-based scheduling of real-time processes", The Journal of Real-Time Systems, vol. 3, pp. 67-99, 1991

• Pire durée de blocage– Pour une tâche donnée, la pire durée de blocage est la longueur maximale d’une section critique des autres

tâches

• Absence d’interblocage

• [CL90] proposent la condition suffisante suivante pour les systèmes de tâches simultanées à échéance sur requête :

• Pour l’exemple traité précédemment : on ne peut donc pas conclure sur l’ordonnançabilité avec cette condition suffisante.

n

i i

ii

T

BC

1

1



4.4 Comparaison avec les FPP

• Avantages des algorithmes à priorités dynamiques– Puissance d’ordonnancement strictement supérieure

– Bon comportement face au traitement des sporadiques (minimise le retard maximal)

• Inconvénients– Effet domino

– Comportement complexe dans le cas non concret

Documents

Laboratoire d'Informatique Scientifique et Industrielle - École Nationale Supérieure de Mécanique et d'Aérotechnique 1- 1 Tutorial ordonnancement Emmanuel