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 e Pi) sont ordonnan ables sur un seul processeur par RM si et
seulement si lutilisation totale du syst me U est inf rieure ou gale 1 (Ud1).
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 quun 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
Publicité
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) lensemble 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 nest pas ordonnan able par RM. Soit Ti la t che qui va rater la premi re son
deadline linstant 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 jhp(i), ni,j un entier positif / Pi = ni,j Pj
Do t=n. ni,j Pj jhp(i) (t est aussi un multiple entier de toute t che plus prioritaire que i)
Dautre part, dire queTi va manquer son deadline linstant t veut dire qu partir de linstant 0 (o
toutes les t ches sont released pour la premi re fois -toutes les t ches sont en phases-), et jusqu
linstant t, la demande en temps de notre syst me pour ex cuter toutes les t ches released pendant
Publicité
cet intervalle est sup rieure t : le temps requis pour ex cuter lensemble des t ches arriv es entre
linstant 0 et linstant t est sup rieur cet intervalle de temps ( gal t).
Cest- -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 lintervalle de temps [0..t] est
tout simplement gal au nombre darriv es t/Pj multipli par le temps dex cution ej)
2
Or, lutilisation totale du syst me est gale :
(cid:22) =
(cid:13)/(cid:25)(cid:13)(cid:26)
(cid:20)(cid:6)
(cid:5)(cid:6)
e
(cid:6)(cid:10)(cid:11)(cid:12)(cid:13)(cid:14)*{(cid:13)} > 1
(cid:20)(cid:6)
Publicité
(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 nest pas ordonnan able par RM)
Alors (U>1)
(A (cid:1) B) (cid:2) ( B (cid:1) A)
Si (Ud1) 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)
Lautre sens est imm diat ; do l quivalence.
3