Examen de contrôle « Systèmes d’exploitation temps réel »

Exercice 1

Question 1 - Condition de Liu et Layland

La condition d’ordonnancement de Liu et Layland établit que si le taux d’utilisation du processeur U est inférieur ou égal à n(2^(1/n) - 1), où n est le nombre de tâches, alors le système est garanti d'être ordonnançable selon Rate Monotonic (RM). On dit qu'elle est suffisante car tout système respectant cette inégalité respectera ses échéances. Cependant, elle n'est pas nécessaire car un système dont le taux d'utilisation dépasse ce seuil théorique (tout en restant inférieur ou égal à 1) peut tout de même s'avérer ordonnançable. Dans ce cas, on doit utiliser un test exact (comme le calcul du temps de réponse) pour statuer.

Question 2.a - Taux d'utilisation et ordonnançabilité

Les priorités attribuées par RM sont inversement proportionnelles aux périodes. Ainsi : Priorité(τ2) > Priorité(τ3) > Priorité(τ1).

Le taux d'utilisation du processeur U se calcule par la somme des Ci/Ti : U = C1/T1 + C2/T2 + C3/T3 U = 7/29 + 1/5 + 2/10 U = 0.2413 + 0.2 + 0.2 = 0.6413

Le plafond de Liu et Layland pour n = 3 tâches est : U_limite = 3 × (2^(1/3) - 1) ≈ 3 × (1.2599 - 1) ≈ 0.7797

Puisque U (0.6413) ≤ U_limite (0.7797), la condition suffisante est respectée. Nous pouvons conclure de façon certaine que le système de tâches est ordonnançable.

Question 2.b - Intervalle de temps minimum (Période d'étude)

La période d'étude minimale pour vérifier l'ordonnançabilité de façon déterministe est l'hyperpériode du système, c'est-à-dire le Plus Petit Commun Multiple (PPCM) des périodes des tâches, puisque les tâches sont toutes réveillées à t=0. PPCM(29, 5, 10) = 29 × 10 = 290. L'intervalle d'étude est donc [0, 290].

Question 2.c - Nombre d'unités de temps libres

Sur l'hyperpériode de 290 unités, le processeur est occupé à hauteur de son taux d'utilisation U = 0.6413, ou plus exactement la fraction exacte : Charge totale = 290 × (7/29 + 1/5 + 2/10) = 290 × (186/290) = 186 unités de temps.

Le nombre d'unités de temps libres est : 290 - 186 = 104 unités.

Question 2.d - Séquences générées par RM sur les 40 premières unités

Ordonnanceur non-préemptif : Dans un système non-préemptif, une tâche qui commence son exécution ne peut pas être interrompue, même si une tâche de plus forte priorité devient prête.

• [0 - 1] : exécution de τ2
• [1 - 3] : exécution de τ3
• [3 - 10] : exécution de τ1 (Malgré l'arrivée de τ2 à t=5, τ1 ne relâche pas le processeur)
• Note de correction : À t=10, τ2 (qui devait s'exécuter avant son échéance à t=10) rate son échéance. Cela démontre que Rate Monotonic requiert la préemption pour fonctionner de façon fiable.
• [10 - 11] : exécution de τ2 (instance de t=5)
• [11 - 12] : exécution de τ2 (instance de t=10)
• [12 - 14] : exécution de τ3 (instance de t=10)
• [14 - 15] : Inactif
• [15 - 16] : exécution de τ2
• [16 - 20] : Inactif
• [20 - 21] : exécution de τ2
• [21 - 23] : exécution de τ3
• [23 - 25] : Inactif
• [25 - 26] : exécution de τ2
• [26 - 29] : Inactif
• [29 - 30] : exécution de τ1 (nouvelle instance)
• [30 - 36] : exécution de τ1 (se poursuit en non-préemptif)
• [36 - 37] : exécution de τ2 (instance de t=30)
• [37 - 38] : exécution de τ2 (instance de t=35)
• [38 - 40] : exécution de τ3 (instance de t=30)

Ordonnanceur préemptif : Ici, τ2 préemptera τ3 et τ1, et τ3 préemptera τ1.

• [0 - 1] : exécution de τ2
• [1 - 3] : exécution de τ3
• [3 - 5] : exécution de τ1 (2 unités complétées sur 7)
• [5 - 6] : exécution de τ2 (préemption)
• [6 - 10] : exécution de τ1 (4 unités complétées, total : 6/7)
• [10 - 11] : exécution de τ2 (préemption)
• [11 - 13] : exécution de τ3
• [13 - 14] : exécution de τ1 (dernière unité, fin de τ1)
• [14 - 15] : Inactif
• [15 - 16] : exécution de τ2
• [16 - 20] : Inactif
• [20 - 21] : exécution de τ2
• [21 - 23] : exécution de τ3
• [23 - 25] : Inactif
• [25 - 26] : exécution de τ2
• [26 - 29] : Inactif
• [29 - 30] : exécution de τ1 (nouvelle instance, 1 unité sur 7)
• [30 - 31] : exécution de τ2
• [31 - 33] : exécution de τ3
• [33 - 35] : exécution de τ1 (2 unités complétées, total : 3/7)
• [35 - 36] : exécution de τ2
• [36 - 39] : exécution de τ1 (3 unités complétées, total : 6/7)
• [39 - 40] : exécution de τ1 (dernière unité, fin de l'instance de τ1)

Question 3.a - Nouveau système et séquence

Nouveaux paramètres : τ1 (T1=30, C1=6), τ2 (T2=5, C2=3), τ3 reste (T3=10, C3=2). U = 6/30 + 3/5 + 2/10 = 0.2 + 0.6 + 0.2 = 1.0. U étant égal à 1.0, il est supérieur au seuil suffisant de Liu & Layland (0.7797). Le test est donc non concluant. L'hyperpériode (PPCM de 30, 5, 10) est de 30 unités. Traçons la séquence préemptive sur la période d'étude [0, 30] :

• [0 - 3] : τ2
• [3 - 5] : τ3
• [5 - 8] : τ2
• [8 - 10] : τ1 (2 unités complétées)
• [10 - 13] : τ2
• [13 - 15] : τ3
• [15 - 18] : τ2
• [18 - 20] : τ1 (2 unités complétées, total : 4/6)
• [20 - 23] : τ2
• [23 - 25] : τ3
• [25 - 28] : τ2
• [28 - 30] : τ1 (2 unités complétées, total : 6/6)

À t=30, toutes les instances sont terminées exactement à leurs échéances. Le système est ordonnançable.

Question 3.b - Test de terminaison (Temps de réponse)

L'équation 2 correspond à l'Analyse de la Demande en Temps (calcul de la récurrence du pire temps de réponse) pour la tâche de plus faible priorité, τ1. La formule est : R1(k+1) = C1 + Σ(j de plus haute priorité) [ ⌈R1(k) ÷ Tj⌉ × Cj ]

• R1(0) = C1 = 6
• R1(1) = 6 + ⌈6 ÷ 5⌉×3 + ⌈6 ÷ 10⌉×2 = 6 + (2×3) + (1×2) = 6 + 6 + 2 = 14
• R1(2) = 6 + ⌈14 ÷ 5⌉×3 + ⌈14 ÷ 10⌉×2 = 6 + (3×3) + (2×2) = 6 + 9 + 4 = 19
• R1(3) = 6 + ⌈19 ÷ 5⌉×3 + ⌈19 ÷ 10⌉×2 = 6 + (4×3) + (2×2) = 6 + 12 + 4 = 22
• R1(4) = 6 + ⌈22 ÷ 5⌉×3 + ⌈22 ÷ 10⌉×2 = 6 + (5×3) + (3×2) = 6 + 15 + 6 = 27
• R1(5) = 6 + ⌈27 ÷ 5⌉×3 + ⌈27 ÷ 10⌉×2 = 6 + (6×3) + (3×2) = 6 + 18 + 6 = 30
• R1(6) = 6 + ⌈30 ÷ 5⌉×3 + ⌈30 ÷ 10⌉×2 = 6 + (6×3) + (3×2) = 6 + 18 + 6 = 30

La suite converge vers 30. Le pire temps de réponse de τ1 est de 30 unités de temps. Comme R1 ≤ T1 (30 ≤ 30), τ1 respecte son échéance. Cela confirme mathématiquement que le système est ordonnançable.

Exercice 2

Question 1 - Identification des tâches

Le système est composé de 4 tâches périodiques. Les durées sont ramenées à la même unité (la minute).

• τ1 (Zone 1) : Période P1 = 30 min, Temps d'exécution e1 = 9 min.
• τ2 (Zone 2) : Période P2 = 40 min, Temps d'exécution e2 = 12 min.
• τ3 (Zone 3) : Période P3 = 60 min, Temps d'exécution e3 = 15 min.
• τ4 (Rapport) : Période P4 = 120 min (2 heures), Temps d'exécution e4 = 5 min.

Priorités RM : τ1 > τ2 > τ3 > τ4 (car 30 < 40 < 60 < 120).

Question 2 - Étude de l'ordonnançabilité

Par l'utilisation ordonnançable : U = 9/30 + 12/40 + 15/60 + 5/120 = 0.3 + 0.3 + 0.25 + 0.0416... = 107/120 ≈ 0.8916. Pour n = 4, le plafond de Liu et Layland est U_limite = 4 × (2^(1/4) - 1) ≈ 0.7568. Puisque U (0.8916) > U_limite (0.7568), le test de la condition suffisante échoue. Nous ne pouvons pas conclure avec cette méthode.

Par l'analyse de la demande en temps : Appliquons l'équation de récurrence (Eq. 2) pour chaque tâche (R_i = Temps de réponse) :

• Pour τ1 : R1 = e1 = 9. 9 ≤ 30 (Respecté).
• Pour τ2 : R2(0) = 12 R2(1) = 12 + ⌈12 ÷ 30⌉×9 = 12 + 9 = 21 R2(2) = 12 + ⌈21 ÷ 30⌉×9 = 21 (Converge). 21 ≤ 40 (Respecté).
• Pour τ3 : R3(0) = 15 R3(1) = 15 + ⌈15 ÷ 30⌉×9 + ⌈15 ÷ 40⌉×12 = 15 + 9 + 12 = 36 R3(2) = 15 + ⌈36 ÷ 30⌉×9 + ⌈36 ÷ 40⌉×12 = 15 + 18 + 12 = 45 R3(3) = 15 + ⌈45 ÷ 30⌉×9 + ⌈45 ÷ 40⌉×12 = 15 + 18 + 24 = 57 R3(4) = 15 + ⌈57 ÷ 30⌉×9 + ⌈57 ÷ 40⌉×12 = 15 + 18 + 24 = 57 (Converge). 57 ≤ 60 (Respecté).
• Pour τ4 : R4(0) = 5 R4(1) = 5 + ⌈5/30⌉×9 + ⌈5/40⌉×12 + ⌈5/60⌉×15 = 5 + 9 + 12 + 15 = 41 R4(2) = 5 + ⌈41/30⌉×9 + ⌈41/40⌉×12 + ⌈41/60⌉×15 = 5 + 18 + 24 + 15 = 62 R4(3) = 5 + 18 + 24 + 30 = 77 (Attendez, ⌈62/30⌉=3, donc 3×9=27. Reprenons :) R4(3) = 5 + ⌈62/30⌉×9 + ⌈62/40⌉×12 + ⌈62/60⌉×15 = 5 + 27 + 24 + 30 = 86 R4(4) = 5 + ⌈86/30⌉×9 + ⌈86/40⌉×12 + ⌈86/60⌉×15 = 5 + 27 + 36 + 30 = 98 R4(5) = 5 + ⌈98/30⌉×9 + ⌈98/40⌉×12 + ⌈98/60⌉×15 = 5 + 36 + 36 + 30 = 107 R4(6) = 5 + ⌈107/30⌉×9 + ⌈107/40⌉×12 + ⌈107/60⌉×15 = 5 + 36 + 36 + 30 = 107 (Converge). 107 ≤ 120 (Respecté).

Toutes les tâches respectent leurs échéances. Le système est ordonnançable.

Question 3 - Simulation sur l'hyperpériode [0, 120]

Avec préemption :

• [0 - 9] : exécution de τ1
• [9 - 21] : exécution de τ2
• [21 - 30] : exécution de τ3 (9 min, reste 6)
• [30 - 39] : exécution de τ1 (nouvelle instance)
• [39 - 40] : exécution de τ3 (1 min de plus, reste 5)
• [40 - 52] : exécution de τ2 (nouvelle instance)
• [52 - 57] : exécution de τ3 (fin de la première instance)
• [57 - 60] : exécution de τ4 (3 min, reste 2)
• [60 - 69] : exécution de τ1 (nouvelle instance)
• [69 - 71] : exécution de τ4 (fin de τ4)
• [71 - 80] : exécution de τ3 (nouvelle instance, 9 min sur 15)
• [80 - 90] : exécution de τ2 (10 min sur 12)
• [90 - 99] : exécution de τ1 (nouvelle instance)
• [99 - 101] : exécution de τ2 (fin de τ2)
• [101 - 107] : exécution de τ3 (fin de τ3)
• [107 - 120] : Inactif

Sans préemption : Dans ce mode, une tâche entamée n'est jamais interrompue.

• [0 - 9] : exécution de τ1
• [9 - 21] : exécution de τ2
• [21 - 36] : exécution de τ3
• Note : à t=30, τ1 arrive mais doit patienter.
• [36 - 45] : exécution de τ1
• Note : à t=40, τ2 arrive mais doit patienter.
• [45 - 57] : exécution de τ2
• [57 - 62] : exécution de τ4 (qui patientait depuis t=0 !)
• Note : à t=60, τ1 et τ3 arrivent.
• [62 - 71] : exécution de τ1
• [71 - 86] : exécution de τ3
• Note : à t=80, τ2 arrive.
• [86 - 98] : exécution de τ2
• Note : à t=90, τ1 arrive.
• [98 - 107] : exécution de τ1
• [107 - 120] : Inactif

(Vérification des échéances : τ4 finit à 62 ≤ 120 ; toutes les tâches respectent leurs limites même en non-préemptif sur cette configuration spécifique).

Question 4 - Nouvelles tâches et leurs natures

L'ajout d'événements modifie la nature du système. Voici les nouvelles tâches identifiées :

1. Répondre au téléphone : Tâche apériodique (ou sporadique) avec contrainte temps réel stricte (Hard Real-Time). L'agent doit impérativement décrocher avant une limite de temps stricte (la fin des sonneries).
2. Nettoyage manuel des caméras : Tâche apériodique avec contrainte temps réel souple (Soft Real-Time). Le nettoyage est nécessaire mais un retard n'est pas catastrophique et n'a pas d'échéance fatale stricte imposée.
3. Vérification de comportement suspect : Tâche sporadique avec contrainte temps réel stricte (Hard Real-Time). La pertinence doit être validée dans un délai maximal imposé et critique de 2 minutes.
4. Notification des autorités : Tâche sporadique (déclenchée en conséquence de la tâche 3) avec contrainte temps réel stricte (Hard Real-Time). Elle requiert une exécution "tout de suite" (latence minimale exigée).

Méthode

Pour aborder un exercice d’ordonnancement temps réel (type RM ou EDF) :

1. Vérification rapide : Commencez toujours par calculer l’utilisation du processeur $U = \Sigma(C_i/T_i)$ et comparez-la au plafond théorique (ici, Liu & Layland). C'est un calcul qui rapporte facilement des points.
2. Gestion de l'incertitude : Si le test rapide échoue (c.-à-d. si U dépasse le seuil suffisant mais reste ≤ 1), ne concluez jamais que le système n'est pas ordonnançable. Vous devez dérouler la méthode de la "demande en temps" (temps de réponse, itératif) ou tracer le diagramme de Gantt complet sur l'hyperpériode.
3. Tracé des diagrammes : Pour simuler la séquence, listez d'abord les instants d'arrivée de toutes les tâches sur l'intervalle. Lisez bien les consignes concernant la préemption : en préemptif, réévaluez la priorité à chaque arrivée d'une tâche ; en non-préemptif, laissez la tâche en cours d'exécution se terminer complètement avant de consulter la file des tâches prêtes.