Optimalité de EDF :
1
Optimalité de RM :
Un système de tâches simplement périodiques, indépendantes et préemptables ; dont les délais sont supérieurs ou égaux aux périodes (Di ≥ Pi) sont ordonnançables sur un seul processeur par RM si et seulement si l’utilisation totale du système U est inférieure ou égale à 1 (U≤1).
Preuve:
Nous allons considérer le cas où toutes les tâches de notre système sont en phases et que les Di=Pi. Notons que ceci représente un pire cas pour notre système. Autrement dit, si cette affirmation est vraie pour un tel système, elle sera dans le cas de tâches déphasées et des deadlines supérieurs eux périodes.
Rappelons qu’un système composé de tâches périodiques est dit simplement périodique si la période de chaque tâche est un multiple entier de la période des autres tâches de périodes inférieures (plus prioritaires au sens de RM):
∀ Ti et Tk, avec pi < pk, ∃ nk,i un entier positif / pk = nk,i ⋅pi
Nous notons par hp(i) l’ensemble des indices de toutes les tâches qui sont plus prioritaires que la tâche Ti au sens de RM. Considérons ainsi un système simplement périodique S, que nous allons ordonnancer selon RM. Et supposons que S n’est pas ordonnançable par RM. Soit Ti la tâche qui va rater la première son deadline à l’instant t. Comme les Di=Pi, t va donc être un multiple entier de Pi : t=n.Pi De plus, puisque S est simplement périodique, alors ∀ j∈hp(i), ∃ ni,j un entier positif / Pi = ni,j ⋅Pj D’où t=n. ni,j ⋅Pj ∀ j∈hp(i) (t est aussi un multiple entier de toute tâche plus prioritaire que i)
Publicité
D’autre part, dire queTi va manquer son deadline à l’instant t veut dire qu’à partir de l’instant 0 (où toutes les tâches sont released pour la première fois -toutes les tâches sont en phases-), et jusqu’à l’instant t, la demande en temps de notre système pour exécuter toutes les tâches released pendant cet intervalle est supérieure à t : le temps requis pour exécuter l’ensemble des tâches arrivées entre l’instant 0 et l’instant t est supérieur à cet intervalle de temps (égal à t).
C’est-à-dire : ∑
(cid:6)∈(cid:10)(cid:11)(cid:12)(cid:13)(cid:14)∪{(cid:13)}
(cid:4) (cid:5)(cid:6)
(cid:7)(cid:8)
> (cid:19)
(cid:1) (cid:19) ∑
(cid:20)(cid:6) (cid:6)∈(cid:10)(cid:11)(cid:12)(cid:13)(cid:14)∪{(cid:13)} > (cid:19) (cid:1) ∑ (cid:5)(cid:6)
(cid:6)∈(cid:10)(cid:11)(cid:12)(cid:13)(cid:14)∪{(cid:13)} > 1
Publicité
(cid:20)(cid:6) (cid:5)(cid:6)
(Note : le temps requis par les processus de type Tj arrivées pendant l’intervalle de temps [0..t] est tout simplement égal au nombre d’arrivées t/Pj multiplié par le temps d’exécution ej)
2
Or, l’utilisation totale du système est égale à :
(cid:22) = ∑
(cid:13)/(cid:25)(cid:13)∈(cid:26)
(cid:20)(cid:6) (cid:5)(cid:6)
≥ ∑
(cid:6)∈(cid:10)(cid:11)(cid:12)(cid:13)(cid:14)∪{(cid:13)} > 1
Publicité
(cid:20)(cid:6) (cid:5)(cid:6)
Ainsi, nous venons de monter que :
Si (S est un système de tâches simplement périodiques, en phases, indépendantes et préemptables ; avec Di = Pi ; qui n’est pas ordonnançable par RM)
Alors (U>1)
(A (cid:1) B) (cid:2) (¬B (cid:1) ¬A)
Si (U≤1) alors (tout système S de tâches simplement périodiques, en phases, indépendantes et préemptables ; avec Di = Pi ; est ordonnançable par RM)
L’autre sens est immédiat ; d’où l’équivalence.
3