Ordonnancement temps réel et dimensionnement pire cas PDF

Ordonnancement temps réel et dimensionnement pire cas Version (très) allégée Pierre Courbin [email protected] D’après des cours de M. Laurent George – avec son accord Contexte Automobile Avionics Sen...

Ordonnancement temps réel et dimensionnement pire cas Version (très) allégée Pierre Courbin [email protected] D’après des cours de M. Laurent George – avec son accord Contexte Automobile Avionics Sensor network Temps-Réel (TR) Military Defence Smart Cities Telecom Multimedia Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Contents 1 Concepts temps réel 2 Algorithmes d’ordonnancement 3 Conditions d’ordonnançabilité 4 Conclusions et perspectives 5 Références Pierre Courbin Temps Réel 3 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Contents 1 Concepts temps réel Introduction Modèle de tâche séquentielle Ordonnanceurs 2 Algorithmes d’ordonnancement 3 Conditions d’ordonnançabilité 4 Conclusions et perspectives 5 Références Pierre Courbin Temps Réel 4 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Concepts temps réel Introduction Pierre Courbin Temps Réel 5 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Sujet du cours Ordonnancement de Tâches Séquentielles Temps-Réel (TR) Dur Préemptives ou non Préemptives sur une plate-forme Uni-Processeur Quésaco ? Pierre Courbin Temps Réel 6 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Ordonnancement de Tâches Séquentielles TR Dur Préemptives ou non Préemptives sur une plate-forme Uni-Processeur Faire la vaisselle Voter Chaque soir, 20 minutes maximum. Tous les 5-6 ans, 15 minutes maximum. ( WCET ) (Prochains : 2026, Municipales) τw (Ow , Cw , Tw , Dw ) = τv (Ov , Cv , Tv , Dv ) = τw (20h, 20min, 24h, 24h) τv (8h, 15min, 5y, 12h) Ow Tw =24h Ov Tv =5years Dw =24h Dw =24h Dv =12h Dv =12h Cw Cw Cv Cv  Wash Wash  Vote Vote 20h 20h 8h 20h 8h 20h I-Deadline C-Deadline TR souple TR dur Pierre Courbin Temps Réel 7 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Ordonnancement de Tâches Séquentielles TR Dur Préemptives ou non Préemptives sur une plate-forme Uni-Processeur Faire la vaisselle Voter Ow Ov Dw =24h Dv =12h Cw Cv  Wash  Vote 20h 8h 20h ⇓ ⇓ Cw Cv  2 1 Wash ε  1 Vote Cw  2 2 Wash ε  2 P-Task S-Task Pierre Courbin Temps Réel 8 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Ordonnancement de Tâches Séquentielles TR Dur Préemptives ou non Préemptives sur une plate-forme Uni-Processeur Éléments d’un Système Temps Réel (STR) Plusieurs tâches, Une ou plusieurs ressources qui peuvent exécuter les tâches (e.g. processeurs si les tâches sont des programmes). Ordonnanceur Un ordonnanceur est un algorithme qui doit choisir, à chaque instant, quelle instance de tâche doit être exécutée. En général, il fonctionne ainsi : Il assigne des priorités aux tâches ou aux instances des tâches, Il choisit l’instance de tâche qui a la plus haute priorité. Pierre Courbin Temps Réel 9 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Ordonnancement de Tâches Séquentielles TR Dur Préemptives ou non Préemptives sur une plate-forme Uni-Processeur Autre analogie Considérons un STR défini par : Tâche ⇐⇒ le besoin, pour un citoyen, d’être écouté Processeur ⇐⇒ un·e politique avec la capacité d’écouter Exemple Un jeu de tâches τ composé de deux citoyens qui ont besoin d’être écoutés : τ1 (O1 , C1 , T1 , D1 ) = τ1 (4h, 6h, 24h, 16h), τ2 (O2 , C2 , T2 , D2 ) = τ2 (8h, 5h, 24h, 14h). Un·e politique π1 peut écouter. (Uni-Processeur) Pierre Courbin Temps Réel 10 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Exemple Un jeu de tâches τ composé de deux citoyens qui ont besoin d’être écoutés : τ1 (O1 , C1 , T1 , D1 ) = τ1 (4h, 6h, 24h, 16h), τ2 (O2 , C2 , T2 , D2 ) = τ2 (8h, 5h, 24h, 14h). Ordonnanceur EDF [BRH90] def O1 + D1 < O2 + D2 ⇒ τ1 ≻ τ2 , Load(τ ) = supt>0 DBFt(τ,t) = 0.58 < 1 π1 τ1 τ2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Ordonnanceur DM [LL73] (Préemption) D2 < D1 ⇒ τ2 ≻ τ1 , W CRT 2 = 5 < D2 = 14, W CRT 1 = 11 < D1 = 16 π1 τ1 τ2 τ1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Pierre Courbin Temps Réel 11 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Principe fondamental Le temps réel n’a pas de lien direct avec la rapidité ! Le Déterminisme Garantir qu’un STR respectera ses spécifications pendant toute sa durée de vie. Pour nous : garantir la ponctualité des tâches exécutées par le STR. Comment garantir le déterminisme ? Exprimer les conditions de faisabilité d’un système Approche pire cas Pierre Courbin Temps Réel 12 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Introduction Méthode classique de résolution d’un STR Approche "pire cas" : Modèle de tâches connus : durée d’exécution pire cas, lois d’activations et contraintes temporelles Identifier la classe du problème d’ordonnancement Pour cette classe de problème Non-concret Déterminer les pires scenarii d’activation des travaux des tâches si ils ne sont pas connus à priori Concret Prendre en compte les dates d’activation des travaux lorsqu’elles sont connues Exprimer les conditions de faisabilité associées Vérifier que ces conditions sont valides pour une architecture donnée Pierre Courbin Temps Réel 13 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Modèle de tâche séquentielle Concepts temps réel Modèle de tâche séquentielle Pierre Courbin Temps Réel 14 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Modèle de tâche séquentielle Modèle de tâche séquentielle (τi ) I Une tâche τi génère des travaux (job) Jij. Durée d’exécution pire cas (Ci ) Chaque tâche τi a une durée d’exécution pire cas Ci aussi appelé Worst Case Execution Time (WCET). Loi d’activation (Ti ) Chaque tâche τi peut avoir une loi d’activation : Périodique – Les demandes d’activation de la tâche sont périodiques, de période Ti Sporadique – Les demandes d’activation de la tâche ont une inter-arrivée ⩾ Ti Pierre Courbin Temps Réel 15 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Modèle de tâche séquentielle Modèle de tâche séquentielle (τi ) II Contrainte temporelle (Di ) Tout job Jij d’une tâche τi qui s’est activé à l’instant tji doit être terminé à l’instant tji + Di. On appelle : Di , l’échéance relative de la tâche tji + Di , l’échéance absolue du job Première activation (Oi ) et gigue (Gi ) On peut aussi spécifier certains paramètres supplémentaires pour la tâche τi : Oi , l’offset de première activation de la tâche dans le cas concret. Gi , la gigue maximale d’activation de la tâche (écart maximum possible entre la date d’activation envisagée et la date d’activation effective) Pierre Courbin Temps Réel 16 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Modèle de tâche séquentielle Modèle de tâche séquentielle (τi ) III Paramètres génériques d’un jeu de tâche τ Finalement, un jeu de tâches τ composé de n tâches est défini comme τ = {τ1 (O1 , C1 , T1 , D1 ),... , τn (On , Cn , Tn , Dn )}. Une tâche τi = τi (Oi , Ci , Ti , Di ) est définie par ce 4-tuple avec : Oi est le premier instant d’arrivée de τi , i.e., l’instant de la première activation depuis le démarrage du système. Ci est le WCET de τi , i.e., le temps maximum d’exécution requis pour chacun de ses jobs. Ti est la période (périodique) ou inter-arrivée (sporadique) de la τi , i.e., l’inter-arrivée exacte (périodique) ou minimum (sporadique) entre deux activations successives de la tâche. Di est la deadline relative de τi , i.e., le temps avant lequel le job courant doit se terminer relativement à sa date d’activation. Pierre Courbin Temps Réel 17 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Modèle de tâche séquentielle Modèle de tâche séquentielle (τi ) IV τ Jeu de tâches τi ième tâche du jeu de tâches τ Jij j ème job/travail/activation de la tâche τi Oi Premier instant d’arrivée de τi Ci Worst Case Execution Time (WCET) de τi Ti Période ou inter-arrivée minimum de τi Di Deadline relative de τi Oi Ti Ti Di Di Di Ci Ci Ci τi Ji0 Ji1 Ji2 0 t0i = Oi t0i + Di t1i t1i + Ti Modèle de tâche séquentielle Pierre Courbin Temps Réel 18 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Modèle de tâche séquentielle Concepts supplémentaires A propos des offsets : Scénario synchrone : Oi = 0, ∀i ∈ [1; n] Scénario asynchrone : Oi , ∀i ∈ [1; n] sont des contraintes du système Offset Free : les offsets peuvent être fixés librement par l’ordonnanceur A propos des instants spécifiques : Instant critique : un instant où toutes les tâches activent un job simultanément Instant critique de niveau de priorité pi : un instant où tous les jobs de priorité ⩾ pi sont activés simultanément Notations : τi ≻ τj si la priorité de τi est supérieure à celle de τj Pierre Courbin Temps Réel 19 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Ordonnanceurs Concepts temps réel Ordonnanceurs Pierre Courbin Temps Réel 20 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Ordonnanceurs Ordonnanceurs Modèles d’ordonnanceurs Event Driven : l’ordonnanceur est invoqué sur événement (réveil/terminaison d’un job) Time Driven : l’ordonnanceur détermine ses instants d’invocation (en général : invocation périodique) Non oisif (work conserving) : L’ordonnanceur ne peut laisser un job en attente s’il n’a rien à faire Coût de préemption Négligé (au mieux intégré dans le WCET) ? La majeure partie des travaux sur le temps réel négligent ce coût, hypothèse prise dans la suite sauf indication Pierre Courbin Temps Réel 21 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Contents 1 Concepts temps réel 2 Algorithmes d’ordonnancement Priorité fixe au niveau des tâches Priorité fixe au niveau des jobs Priorité dynamique au niveau des jobs Notion d’optimalité 3 Conditions d’ordonnançabilité 4 Conclusions et perspectives 5 Références Pierre Courbin Temps Réel 22 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité fixe au niveau des tâches Algorithmes d’ordonnancement Priorité fixe au niveau des tâches Pierre Courbin Temps Réel 23 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité fixe au niveau des tâches Priorité fixe au niveau des tâches Fixed Task Priority (FTP) : une priorité fixe est attribuée au niveau de la tâche, les travaux héritent de cette priorité. RM signifie Rate Monotonic (RM) [LL73]. Fonction de la période de la tâche : Ti < Tj ⇒ τi ≻ τj. Plus la période est petite, plus un job est prioritaire. DM signifie Deadline Monotonic (DM) [Aud+91]. Fonction de l’échéance relative de la tâche : Di < Dj ⇒ τi ≻ τj. Plus l’échéance relative est petite, plus un job est prioritaire. OPA signifie Optimal Priority Assignment (OPA) [Aud01 ; Aud91]. On l’appelle aussi "Procédure d’Audsley". Algorithme permettant d’attribuer des priorités (voir Algorithme 1 slide 25). Pierre Courbin Temps Réel 24 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité fixe au niveau des tâches Procédure d’Audsley pour l’attribution de priorité fixes Algorithme 1 : Audlsey’s Optimal Priority Assignment Input : Task set τ = τ(C,T,D) , with n tasks without priorities 1 τ ′ = τ ; // Copy of task set τ 2 for j=n to 1 do 3 unassigned = TRUE; 4 for τi in τ ′ AND unassigned=TRUE do 5 if τi at priority level j is feasible in τ then 6 τi take the priority j in τ ; 7 Remove τi from τ ′ ; 8 unassigned = FALSE; 9 end if 10 end for 11 if unassigned=TRUE then 12 exitError() ; // No feasible priority assignment exists 13 end if 14 end for Pierre Courbin Temps Réel 25 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité fixe au niveau des jobs Algorithmes d’ordonnancement Priorité fixe au niveau des jobs Pierre Courbin Temps Réel 26 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité fixe au niveau des jobs Priorité fixe au niveau des jobs Fixed Job Priority (FJP) : une priorité fixe est attribuée au niveau de chacun des jobs à chaque activation d’un nouveau job et ne change pas entre les activations. EDF signifie Earliest Deadline First (EDF) [LL73]. Fonction de l’échéance absolue du job : tki + Di < tlj + Dj ⇒ Jik ≻ Jjl. Le job d’échéance absolue la plus petite est le plus prioritaire. FIFO signifie Fisrt In First Out (FIFO). Fonction de la date d’activation du job : tki < tlj ⇒ Jik ≻ Jjl. Plus le job arrive tôt dans le système, plus il est prioritaire. Pierre Courbin Temps Réel 27 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité dynamique au niveau des jobs Algorithmes d’ordonnancement Priorité dynamique au niveau des jobs Pierre Courbin Temps Réel 28 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Priorité dynamique au niveau des jobs Priorité dynamique au niveau des jobs Dynamic Job Priority (DJP) : les priorités des jobs peuvent évoluer à chaque instant. LLF signifie Least Laxity First (LLF) [Mok83 ; Leu89]. Le job avec la plus petite laxité est le plus prioritaire. La laxité d’un job Jik est le temps pendant lequel le job peut ne pas être exécuté sans remettre en cause sa deadline, soit tki + Di − t − Cik (t) avec : tki la date d’activation de Jik Cik (t) la durée d’exécution restante pour Jik Di tki + Di − t Cik (t) Laxity τi Jik,1 Jik,2 tk i t i + Di tk Représentation de la laxité Pierre Courbin Temps Réel 29 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Notion d’optimalité Algorithmes d’ordonnancement Notion d’optimalité Pierre Courbin Temps Réel 30 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Notion d’optimalité Notion d’optimalité Définition (Optimalité d’un algorithme) Un algorithme est optimal si il trouve toujours une solution valide pour tout problème qui admet au moins une solution. Autrement dit : "Si c’est possible, j’y arrive !". Définition (Contraposée de l’optimalité d’un algorithme) Si un algorithme optimal ne trouve pas de solution valide alors il n’existe pas de solution au problème. Autrement dit : "Si je n’y arrive pas, personne ne peut !" L’optimalité est très liée au contexte (modèles de tâches, modèles d’ordonnancement,...) Pierre Courbin Temps Réel 31 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Notion d’optimalité Optimalité pour ordonnanceurs FTP Echéances Non-concret Asynchrone Offset free Préemptif RM I-Deadline Optimal Non Optimal Non Optimal [LL73] [LW82] [GD97] DM C-Deadline Optimal Non Optimal Non Optimal [LM80] [LW82] [GD97] OPA A-Deadline Optimal Optimal Optimal Audsley [Aud91] [Yom09] [Goo03] Non Préemptif RM I-Deadline Non Optimal Non Optimal Non Optimal [GRS96] DM C-Deadline Non Optimal Non Optimal Non Optimal [GRS96] OPA A-Deadline Optimal Audsley [GRS96] ?? ?? Optimalité pour l’attribution de priorité fixe au niveau des tâches Pierre Courbin Temps Réel 32 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Notion d’optimalité Optimalité pour ordonnanceurs FJP et DJP Echéances Non-concret Asynchrone Offset free Préemptif EDF A-Deadline Optimal Optimal Optimal [LL73 ; BRH90] LLF A-Deadline Optimal Optimal Optimal [Mok83 ; Leu89] Non Préemptif EDF A-Deadline Optimal Non Optimal Non Optimal [Der74 ; JSM91] LLF A-Deadline Non Optimal Non Optimal Non Optimal [GRS96] Optimalité pour l’attribution de priorité dynamique au niveau des tâches Pierre Courbin Temps Réel 33 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Contents 1 Concepts temps réel 2 Algorithmes d’ordonnancement 3 Conditions d’ordonnançabilité Intervalle d’étude Tests d’ordonnançabilité 4 Conclusions et perspectives 5 Références Pierre Courbin Temps Réel 34 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Comment garantir le respect de l’échéance d’une tâche ? Définition (Tests d’ordonnançabilité) Un test est dit d’ordonnançabilité si il permet de déterminer si un jeu de tâche donné peut être ordonnancé sans manquer de deadline avec un ordonnanceur donné. Différentes formes de tests existent : basé sur l’étude de l’ordonnancement sur un intervalle donné basé sur un test mathématique d’ordonnançabilité d’après les paramètres du jeu de tâches : basé sur le calcul du Pire Temps de Réponse (WCRT) basé sur la quantité de travail exécutée dans un intervalle de temps Différents types de tests pour vérifier si un jeu de tâches est ordonnançable : Necessary Test (N-Test) – Doit être respecté Sufficient Test (S-Test) – Peut être respecté Necessary and Sufficient Test (NS-Test) – Test exact Pierre Courbin Temps Réel 35 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Intervalle d’étude Conditions d’ordonnançabilité Intervalle d’étude Pierre Courbin Temps Réel 36 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Intervalle d’étude Intervalle d’étude I Dans un contexte préemptif avec des tâches sporadiques, le scénario d’activation pire cas est le scénario synchrone. Intervalle d’étude – Préemptif – Sporadique – Plus Petit Commun Multiple (PPCM) Considérant le pire cas dans un contexte préemptif avec tâches sporadiques, pour vérifier si un jeu de tâches est ordonnançable, il suffit de l’ordonnancer en considérant : Scénario : synchrone Intervalle d’étude : PPCM des périodes des tâches. PPCM des Périodes τ3 τ2 τ1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 τ1 (0, C1 , 4, 4), τ2 (0, C2 , 8, 8), τ3 (0, C3 , 12, 12). P P CM = 24. Pierre Courbin Temps Réel 37 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Intervalle d’étude Intervalle d’étude II Intervalle d’étude – Préemptif – Sporadique – Request Bound Function (RBF) Réduction de l’intervalle en utilisant la RBF [LSD89] pour calculer l’instant où le processeur a un instant libre (idle time). On peut donc considérer : Scénario : synchrone Intervalle d’étude : [0; L] définit par l’équation 1. Soit l’intervalle [0; L] avec L solution de :   P n   L0 = Ci  i=1 L k+1 = RBF (Lk )   P n  jusqu’à Lk+1 = Lk si Ci Ti ⩽1 i=1 n l m def X t avec RBF (τ, t) = × Ci (1) Ti i=1 Pierre Courbin Temps Réel 38 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Intervalle d’étude Intervalle d’étude III Intervalle d’étude – Préemptif – Sporadique – RBF Jeu de tâches : τ = {τ1 (O1 , 2, 5, 3), τ2 (O2 , 4, 7, 6)}. P P CM = 35 Pn RBF (t) y=t L0 = Ci = 2 + 4 = 6 i=0
15 L3 = L2 = L L1 = RBF τ, L0 = RBF (τ, 6) = RBF (L2) 14 6 6 13 ×2+ ×4 = 2×2+1×4 = 8 5 7 RBF (L1) 12
L2 τ, L1 11 = RBF = RBF (τ, 8) = 8 8 10 ×2+ × 4 = 2 × 2 + 2 × 4 = 12 5 7 9
RBF (L0) 8 L3 = RBF τ, L2 = RBF (τ, 12) = 7  12   12  n P Ci 6 ×2+ × 4 = 3 × 2 + 2 × 4 = 14 i=0 5 7 5
L4 3 4 = RBF τ, L = RBF (τ, 14) =  14   14  3 ×2+ × 4 = 3 × 2 + 2 × 4 = 14 5 7 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t L0 L1 L2 L3 =⇒ L4 = L3 = L = 14 Pierre Courbin Temps Réel 39 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Intervalle d’étude Intervalle d’étude – Exemple Intervalle d’étude – Préemptif – Sporadique – Exemple Considérons le jeu de tâches périodique composé des 3 tâches : τ1 , τ2 , τ3 , avec : τ1 = (O1 , C1 , T1 , D1 ) = (0, 2, 7, 5), τ2 = (O2 , C2 , T2 , D2 ) = (0, 3, 11, 7), τ3 = (O3 , C3 , T3 , D3 ) = (0, 5, 13, 10). Nous avons donc : P P CM = 1001 L = 39 Il "suffit" dont de vérifier si le jeux de tâche est ordonnançable entre 0 et 39 pour vérifier son ordonnançabilité générale. ττ11 τ2 Avec DM : τ3 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 ττ11 τ2 Avec EDF : τ3 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 Pierre Courbin Temps Réel 40 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Conditions d’ordonnançabilité Tests d’ordonnançabilité Pierre Courbin Temps Réel 41 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Tests d’ordonnançabilité Définition ( N-Test ) Un test d’ordonnançabilité est dit Necessary Test (N-Test) si un résultat négatif permet de conclure que le jeu de tâche n’est pas ordonnançable. En résumé : Je suis négatif ? Pas ordonnançable ! Je suis positif ? Ce n’est pas perdu, mais il faut creuser plus... Définition ( S-Test ) Un test d’ordonnançabilité est dit Sufficient Test (S-Test) si un résultat positif permet de conclure que le jeu de tâche est ordonnançable. En résumé : Je suis négatif ? Ce n’est pas perdu, mais il faut creuser plus... Je suis positif ? Ordonnançable ! Définition ( NS-Test ) Test Nécessaire Un test d’ordonnançabilité est dit Necessary and Sufficient Test (NS-Test) si le résultat permet de statuer directement sur l’ordonnançabilité du jeu de tâche avec l’ordonnanceur associé. Jeux de tâches ordonnançables En résumé : (Nécessaire et suffisant) Je suis négatif ? Pas ordonnançable ! Je suis positif ? Ordonnançable ! Test Suffisant Pierre Courbin Temps Réel 42 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Tests génériques – Tout ordonnanceurs N-Test – Uτ – Utilisation du jeu de tâches L’utilisation totale du jeu de tâche ne dépasse pas 1 n X def Ci Uτ = ⩽1 (2) i=1 Ti NS-Test – W CRT i – Pire Temps de Réponse (WCRT) Le WCRT de chaque tâche qui correspond à la pire durée entre sa date d’activation sa date de fin d’exécution est inférieur à la deadline relative. [JP86] ∀i ∈ [1; n], W CRT i ⩽ Di (3) Ce WCRT se calcule différemment suivant l’ordonnanceur utilisé. Pierre Courbin Temps Réel 43 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Ordonnanceurs FTP RM – Préemptive – Implicit Deadline (I-Deadline) S-Test – Utilisation – [LL73] def X n C √
i n Uτ = ⩽ n 2−1 (4) Ti i=1 √ n
avec lim n 2−1 = ln(2) ≃ 0.69 n→+∞ S-Test – Borne Hyperbolique – [BBB03] n YC  i +1 ⩽ 2 (5) Ti i=1 FTP – Préemptive – Constrained Deadline (C-Deadline) – Non concret NS-Test – WCRT – [LSD89 ; Aud+93] ∀τi ∈ τ, W CRT i ⩽ Di et W CRT i est solution de ( W CRT 0 = Ci i
= Ci + RBF τ hp(τ,τi ) , W CRT k k+1 W CRT i i k+1 jusqu’à W CRT = W CRT k ou W CRT k > Di i i i hp(τ,τi ) avec τj ∈ τ si τj ∈ τ et τj ≻ τi (6) Pierre Courbin Temps Réel 44 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Ordonnanceurs FJP – EDF I EDF – Préemptive – I-Deadline NS-Test – Utilisation def X n Ci Uτ = ⩽1 (7) Ti i=1 EDF – Préemptive – C-Deadline S-Test – Densité – [Liu00] def X n Ci Λτ = ⩽1 (8) min(Ti , Di ) i=1 Pierre Courbin Temps Réel 45 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Ordonnanceurs FJP – EDF II EDF – Préemptive – Arbitraty Deadline (A-Deadline) – Non concret NS-Test – Demand Bound Function (DBF) – [BRH90] ∀t > 0, DBF (τ, t) ⩽ t X n  j k def t − Di avec DBF (τ, t) = max 0, 1 + × Ci (9) Ti i=1 def DBF (τ, t) Autrement dit : Load(τ ) = supt>0 ⩽1 (10) t NS-Test – DBF amélioration – [FBB06]   def DBF (τ, t) Load(τ ) = max Uτ , supt∈S t n n l m o def [ P − Di avec S = Di + ki × Ti , 0 ⩽ ki ⩽ −1 (11) Ti i=1 et P est le PPCM de toutes les périodes des tâches S est composé de toutes les deadlines absolues des tâches dans l’intervalle [Dmin ; P ] que l’on peut réduire à [Dmin ; L] d’après le calcul de L à l’équation 1. Pierre Courbin Temps Réel 46 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Tests d’ordonnançabilité Ordonnanceurs FJP – EDF III EDF – Préemptive – A-Deadline – Non concret – DBF Jeu de tâches : τ = {τ1 (O1 , 2, 5, 3), τ2 (O2 , 4, 7, 6)}. P P CM = 35 ; L = 14. S = {3, 6, 8, 13}.  3−3 
DBF (τ, t) y=t DBF (τ, 3) = max 0, 1 + ×2+  3−65
15 DBF (τ, t) > t max 0, 1 + ×4 = DBF (τ, 13) 14 7 1×2+0×4 = 2  
13 6−3 DBF (τ, 6) = max 0, 1 + ×2+ 5 12  6−6 
11 max 0, 1 + ×4 = 7 10 1×2+1×4 = 6  
9 8−3 DBF (τ, 8) = max 0, 1 + ×2+ DBF (τ, 8) 8 5  8−6 
7 max 0, 1 + ×4 = 7 DBF (τ, 6) 6 2×2+1×4 = 8  
5 13−3 DBF (τ, 13) = max 0, 1 + ×2+ 5  13−6 
4 3 max 0, 1 + ×4 = 7 DBF (τ, 3) 2 3 × 2 + 2 × 4 = 14 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t D11 D21 D12 D13 = D22 =⇒ DBF (τ, 13) = 14 > 13, τ n’est pas ordonnançable avec EDF Pierre Courbin Temps Réel 47 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Contents 1 Concepts temps réel 2 Algorithmes d’ordonnancement 3 Conditions d’ordonnançabilité 4 Conclusions et perspectives Conclusions Perspectives 5 Références Pierre Courbin Temps Réel 48 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Conclusions Conclusions et perspectives Conclusions Pierre Courbin Temps Réel 49 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Conclusions Conclusions Résumé Vous savez maintenant : Ce qu’est un ordonnanceur Choisir un ordonnanceur en fonction du contexte et des tâches Vérifier l’ordonnançabilité d’un jeu de tâches : par ordonnancement sur le bon intervalle d’étude par calcul du respect de tests d’ordonnançabilités Procédure de vérification d’ordonnançabilité 1 Vérification du N-Test 2 S’il est respecté, vérification du S-Test 3 S’il n’est pas respecté, calcul du PPCM 4 S’il est trop grand, calcul de L 5 Si le PPCM ou L sont assez petit, on dessine l’ordonnancement 6 S’ils sont trop grand, on vérifie le NS-Test Pierre Courbin Temps Réel 50 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Perspectives Conclusions et perspectives Perspectives Pierre Courbin Temps Réel 51 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Perspectives Perspectives – et bien plus encore... Sensibilité multi-critères Prise en compte du cout exact de la préemption Le cas synchrone n’est plus le pire cas [Yom09] : problème ouvert Les propriétés de cyclicité des ordonnancement pourraient être remises en cause Temps réel et énergie (batterie de durée de vie limitée) Approche Dynamic Power Management (DPM) Approche Dynamic Voltage Frequency Scaling (DVFS) Multiprocesseurs ( G-Scheduling , P-Scheduling , SP-Scheduling ) Multi-mode : problématique de changement de mode – comment passer d’un mode d’exécution à un autre Criticité mixte (mixed criticality) : plusieurs tâches de différents niveaux de criticité coexistent [Ves07 ; San+12] Évolution vers des systèmes de systèmes où des tâches de criticité différentes doivent pouvoir échanger des informations Problème : la certification impose le niveau de criticité maximum Évolution vers les architectures post-moore Évolution vers des tailles nanométriques Parallélisme important, problématique de l’interconnect Influences mutuelles des composants (diaphonie, problèmes thermiques) Grande variabilité des composants, besoin de robustesse et d’adaptivité Temps réel probabiliste Pierre Courbin Temps Réel 52 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Contents 1 Concepts temps réel 2 Algorithmes d’ordonnancement 3 Conditions d’ordonnançabilité 4 Conclusions et perspectives 5 Références Bibliographie Acronymes Pierre Courbin Temps Réel 53 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Bibliographie Références Bibliographie Pierre Courbin Temps Réel 54 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Bibliographie Bibliographie I [Aud01] Neil C. Audsley.  On priority asignment in fixed priority scheduling . In : Information Processing Letters 79.1 (mai 2001), pages 39-44. issn : 0020-0190. doi : 10.1016/S0020- 0190(00)00165- 4. [Aud91] Neil C. Audsley. Optimal Priority Assignment And Feasibility Of Static Priority Tasks With Arbitrary Start Times. Rapport technique. University of York, nov. 1991. [Aud+93] Neil C. Audsley, Alan Burns, Mike Richardson, Ken Tindell et Andy Wellings.  Applying new scheduling theory to static priority pre-emptive scheduling . In : Software Engineering Journal 8.5 (sept. 1993), pages 284-292. issn : 0268-6961. [Aud+91] Neil C. Audsley, Alan Burns, Mike Richardson et Andy Wellings.  Hard Real-Time Scheduling : The Deadline-Monotonic Approach . In : Proceedings of the 8th IEEE Workshop on Real-Time Operating Systems. IEEE Workshop on Real-Time Operating Systems (RTOS). Mai 1991, pages 133-137. [BRH90] Sanjoy K. Baruah, Louis E. Rosier et Rodney R. Howell.  Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor . In : Real-Time Systems 2.4 (oct. 1990), pages 301-324. issn : 0922-6443. doi : 10.1007/BF01995675. [BBB03] Enrico Bini, Giorgio C. Buttazzo et Giuseppe M. Buttazzo.  Rate monotonic analysis : the hyperbolic bound . In : IEEE Transactions on Computers 52.7 (juill. 2003), pages 933-942. issn : 0018-9340. doi : 10.1109/TC.2003.1214341. Pierre Courbin Temps Réel 55 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Bibliographie Bibliographie II [Der74] Michael L. Dertouzos.  Control Robotics : The Procedural Control of Physical Processes. . In : Proceedings of the International Federation for Information Processing. International Federation for Information Processing (IFIP). Stockholm, Sweden : American Elservier, août 1974, pages 807-813. isbn : 0-7204-2803-3. [FBB06] Nathan W. Fisher, Theodore P. Baker et Sanjoy K. Baruah.  Algorithms for Determining the Demand-Based Load of a Sporadic Task System . In : Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Embedded and Real-Time Computing Systems and Applications (RTCSA). Sydney, Australia, août 2006, pages 135-146. isbn : 0-7695-2676-4. doi : 10.1109/RTCSA.2006.12. [GRS96] Laurent George, Nicolas Rivierre et Marco Spuri. Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling. Rapport de recherche RR-2966. Projet REFLECS. INRIA, sept. 1996. [Goo03] Joël Goossens.  Scheduling of Offset Free Systems . In : Real-Time Systems 24.2 (2003), pages 239-258. issn : 0922-6443. doi : 10.1023/A:1021782503695. [GD97] Joël Goossens et Raymond Devillers.  The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems . In : Real-Time Systems 13.2 (1997), pages 107-126. issn : 0922-6443. doi : 10.1023/A:1007980022314. [JSM91] Kevin Jeffay, Donald F. Stanat et Charles U. Martel.  On non-preemptive scheduling of period and sporadic tasks . In : Proceedings of the 12th IEEE Real-Time Systems Symposium. IEEE Real-Time Systems Symposium (RTSS). San Antonio, Texas, USA, déc. 1991, pages 129-139. isbn : 0-8186-2450-7. doi : 10.1109/REAL.1991.160366. Pierre Courbin Temps Réel 56 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Bibliographie Bibliographie III [JP86] Mathai Joseph et Paritosh K. Pandya.  Finding Response Times in a Real-Time System . In : The Computer Journal 29 (5 1986), pages 390-395. doi : 10.1093/comjnl/29.5.390. [LSD89] John Lehoczky, Lui Sha et Ye Ding.  The Rate Monotonic scheduling algorithm : exact characterization and average case behavior . In : Proceedings of the 10th IEEE Real-Time Systems Symposium. IEEE Real-Time Systems Symposium (RTSS). Santa Monica, California, USA : IEEE Computer Society, déc. 1989, pages 166-171. isbn : 0-8186-2004-8. doi : 10.1109/REAL.1989.63567. [Leu89] Joseph Y. Leung.  A new algorithm for scheduling periodic real-time tasks . In : Algorithmica 4.1-4 (juin 1989), pages 209-219. issn : 0178-4617. doi : 10.1007/BF01553887. [LM80] Joseph Y. Leung et Maggie L. Merrill.  A Note on Preemptive Scheduling of Periodic, Real-Time Tasks . In : Information Processing Letters 11.3 (nov. 1980), pages 115-118. doi : 10.1016/0020-0190(80)90123- 4. [LW82] Joseph Y. Leung et Jennifer Whitehead.  On the complexity of fixed-priority scheduling of periodic, real-time tasks . In : Performance Evaluation 2 (fév. 1982), pages 237-250. doi : 10.1016/0166- 5316(82)90024- 4. [LL73] Chung Laung Liu et James W. Layland.  Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment . In : Journal of ACM 20.1 (jan. 1973), pages 46-61. issn : 0004-5411. doi : 10.1145/321738.321743. [Liu00] Jane Win Shih Liu. Real-Time Systems. 1st. Upper Saddle River, NJ, USA : Prentice Hall PTR, avr. 2000. isbn : 0130996513. Pierre Courbin Temps Réel 57 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Bibliographie Bibliographie IV [Mok83] Aloysius Ka-Lau Mok.  Fundamental design problems of distributed systems for the hard-real-time environment . Thèse de doctorat. Massachusetts Institute of Technology. Department of Electrical Engineering et Computer Science, mai 1983. [San+12] Franç Santy, Laurent George, Philippe Thierry et Joël Goossens.  Relaxing Mixed-Criticality Scheduling Strictness for Task Sets Scheduled with FP . In : Proceedings of the 24th Euromicro Conference on Real-Time Systems. EuroMicro Conference on Real-Time Systems (ECRTS). Pisa, Italy, juill. 2012, pages 155-165. isbn : 978-1-4673-2032-0. doi : 10.1109/ECRTS.2012.39. [Ves07] Steve Vestal.  Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance . In : Proceedings of the 28th IEEE Real-Time Systems Symposium. IEEE Real-Time Systems Symposium (RTSS). Tucson, Arizona, USA : IEEE Computer Society, déc. 2007, pages 239-243. doi : 10.1109/RTSS.2007.47. [Yom09] Patrick Meumeu Yomsi.  Prise en compte du coùt exact de la préemption dans l’ordonnancement temps réel monoprocesseur avec contraintes multiples (In French) . Thèse de doctorat. Université Paris Sud - Orsay / Paris 11, 2009. url : http://parts.ulb.ac.be/media/articles/THPM.pdf. Pierre Courbin Temps Réel 58 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Acronymes Références Acronymes Pierre Courbin Temps Réel 59 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Acronymes Acronymes I TR Temps-Réel. 2, 6–10 A-Deadline Arbitraty Deadline. 32, 33, 46, 47 C-Deadline Constrained Deadline. 7, 32, 44, 45 DBF Demand Bound Function. 11, 46, 47 DJP Dynamic Job Priority. 29, 33 DM Deadline Monotonic. 11, 24, 32, 40 DPM Dynamic Power Management. 52 DVFS Dynamic Voltage Frequency Scaling. 52 EDF Earliest Deadline First. 11, 27, 33, 40, 45–47 FIFO Fisrt In First Out. 27 FJP Fixed Job Priority. 27, 33, 45–47 Pierre Courbin Temps Réel 60 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Acronymes Acronymes II FTP Fixed Task Priority. 24, 32, 44 G-Scheduling Ordonnancement Global. 52 I-Deadline Implicit Deadline. 7, 32, 44, 45 LLF Least Laxity First. 29, 33 N-Test Necessary Test. 35, 42, 43, 50 NS-Test Necessary and Sufficient Test. 35, 42–46, 50 OPA Optimal Priority Assignment. 24, 32 P-Scheduling Ordonnancement Partitionné. 52 P-Task Tâche Parallèle. 8 PPCM Plus Petit Commun Multiple. 37, 39, 40, 46, 47, 50 Pierre Courbin Temps Réel 61 / 52 Concepts Ordonnancement Ordonnançabilité Conclusion Références Acronymes Acronymes Acronymes III RBF Request Bound Function. 38, 39, 44 RM Rate Monotonic. 24, 32, 44 S-Task Tâche Séquentielle. 8 S-Test Sufficient Test. 35, 42, 44, 45, 50 SP-Scheduling Ordonnancement Semi-Partitionné. 52 STR Système Temps Réel. 9, 10, 12, 13 WCET Worst Case Execution Time. 7, 15, 17, 18, 21 WCRT Pire Temps de Réponse. 11, 35, 43, 44 Pierre Courbin Temps Réel 62 / 52