TD Ordonnancement
Exercice 1
Soit les trois tâches indépendantes et préemptibles, toutes prêtes à la date t=0 :
T1 (C=1, D=P=3),
T2 (C=1, D=P=4),
T3 (C=2, D=P=6).
Pour chacune des politiques d'ordonnancement RM, EDF et LLF :
1. Calculer U, le facteur d'utilisation du processeur, que peut-on en conclure ?
2. Donner un schéma du séquencement des tâches.
Indication : n(2(1/n)-1) = 0,78 pour n = 3 ;
Exercice 2
Un système d'arrosage automatique doit arroser trois types de plantes :
les plus fragiles qui doivent être arrosées pendant 10 minutes, toutes les 40 minutes,
une deuxième catégorie qui doit recevoir de l'eau pendant 20 minutes, toutes les heures,
enfin, des plantes d'un troisième type qu'il faut arroser toutes les 80 minutes, pendant 20 minutes.
L'arrosage peut se faire de façon fractionnée, c'est-à-dire s'interrompre et reprendre.
Question 1
On cherche une solution pour le partage de l'eau entre ces différentes variétés de plantes :
1. Définir la liste des tâches à accomplir,
2. Puis, pour les stratégies RM et EDF :
Calculer l'ordonnançabilité de ces tâches,
Donner un schéma d'utilisation du système d'arrosage à partir du temps 0.
Question 2
On veut maintenant se servir du système d'arrosage pour nettoyer les allées qui desservent les plantations. On décide de
faire cet entretien pendant 10 minutes toutes les heures.
Cet entretien est-il possible pendant les arrosages :
avec RMS, pourquoi ?
avec EDF, pourquoi ?
Question.3
Pour nettoyer toutes les allées, il faut 20 minutes. Si l'entretien commence 1h30 après le début de l'arrosage des plantes,
pourra-t-on avoir complétement nettoyé les allées :
1. au bout d'une heure ?
2. après 100 minutes ?
Exercice 3
Considérant l’ordonnancement basé sur RMA :
a) Expliquez ce qu’on entend, lorsqu’on dit que la condition d’ordonnancement de
Liu et Layland (eq. 1) est une condition suffisante, mais pas nécessaire.
b) En utilisant la condition de Liu et Layland et l’ordonnancement graphique, que peut-on dire des tâches du tableau
suivant ?
Tâches Temps d’exécution Période
T1 10 50
T2 10 40
T3 15 30
Exercice 4
Soit le tableau suivant :
Tâches Temps d’exécution Deadline Période
T1 1 10 10
T2 18 100 100
T3 2 20 20
T4 5 50 50
T5 x 25 25
Calculez le temps d’exécution maximal x de T5 afin d’avoir un ordonnancement faisable (pour T1 à T5), en considérant
l’ordonnancement RMA (Rate Monotonic Assignement).
Exercice 5
Ordonnançabilité d’un ensemble de tâches paramétrées.
Etant donné un entier naturel strictement positif c, nous considérons le système de tâches {T1, T2, T3}, avec T1 = (2,
9), T2 = (c, 6) et T3 = (1, 9).
1. Déterminez sous quelle condition (sur c) ce système passe-t-il le test d’ordonnançabilité de EDF, puis celui de RM.
2. Nous souhaitons à présent introduire plusieurs copies de la tâche T3. Notons n ce nombre.
a) Déterminez la condition obtenue sur c, en fonction de n, pour que ce nouveau système passe le test EDF.
b) Calculez les valeurs numériques obtenues pour n variant de 1 à 5.
Corrigé
Exercice N° 1
1- Calcul de U
U = 1/3 +1/4 + 2/6 = 0,33 + 0,25 + 0,33 = 0, 91.
Le coefficient U est inférieur à 1: l’ensemble des tâches est ordonnançable par EDF.
Il est supérieur à 0,78 : on ne peut rien dire pour RMS.
2- La période d’étude est égale à 12
Ordonnancement RMS
Ordonnancement EDF
Odonnancement LLF
Exercice N°2
1- T1 (C1 = 10, P = 40)
T2 (C2 = 20, P = 60)
T3 (C3 = 20, P = 80)
2- Calcul de l’ordonnançabilité
U = 0,83
RM
EDF
Question2
T4 (C4 = 10, P = 60)
U=
RMS : Non ordonnancable
EDF
Question3
U = 0,916. D’après le schéma suivant, le nettoyage se termine au bout de 70mn.
Exercice N°3
a) La condition Liu et Layland est suffisante, mais pas nécessaire : si elle est satisfaite, les tâches
peuvent être ordonnancées, sinon, on ne peut rien conclure.
b) La condition de Liu et Layland n’est pas satisfaite : U = 10/50 + 10/40 + 15/30 = 0,95>0,78
,alors il faut vérifier sur le graphe d’exécution si les tâches peuvent être ordonnancées:
La tâche T1 dépasse son deadline lors de sa première période, donc les tâches ne peuvent pas être
ordonnancées RMA.
Exercice N°4
C P 0,743 , on déduit que
i
i
X 6,575
Exercice N°5
1- Ordonnançabilité RM
2/9 + c/6 + 1/9 0,78 c 2,68
Ordonnançabilité EDF
2/9 + c/6 + 1/9 1 c 4
2- Pour n tâche T3
2 c n 14 2n
a) 1 c
9 9 9 3
b) Pour n = 1 c 4
Pour n = 2 c 10/3=3,33
Pour n = 3 c 8/3=2,66
Pour n = 4 c 2
Pour n = 5 c 4/3=1,33
