Ordonnancement
de t ches dans un
milieu h t rog ne
Dr. Yosr SLAMA
2020-2021
Introduction
2
u Contexte : L'ordonnancement de t ches ind pendantes
en milieu h t rog ne (OTIMHTR) est applicable pour un
ordonnancement par niveau sans chevauchement dans le
cas d'un graphe de t ches.
u Hypoth ses : on dispose dun ensemble de n t ches
ind pendantes tj de co ts respectifs cj (j=1..n)
ordonnancer sur p processeurs de vitesses respectives
v1, v2, & vp
u Objectif : Equilibrage de charge Minimiser le
makespan
M triques
3
u La charge pond r e dun processeur Pi (not e CHPi) est
d finie par la somme des co ts des t ches allou es Pi
divis e par sa vitesse vi
CHPi= Somme cj (cj : co t des t ches tj affect es i) / vi
u Lorsque toutes les t ches seront allou es aux processeurs,
le makespan M(p) sera alors le maximum des charges
pond r es des diff rents processeurs
M(p)= max(CHPi) (i=1..p)
4
Principes
On pr sente diff rentes m thodes dordonnancement
bas es principalement sur les deux principes suivants :
u Principe 1 : On affecte la t che courante au processeur
dont la charge pond r e (CHP) est la plus faible.
Remarque : Si deux processeurs ont la m me CHP, on
choisira le plus rapide
u Principe 2 : On affecte la t che courante au processeur
qui la terminera le plus vite (on comparera les CHP des
processeurs si on leur affecte la t che courante)
5
Algorithmes :
On pr sente 3 algorithmes it ratifs (1 tape = allocation dune t che sur
un processeur quon choisira):
u LS List Scheduling (t ches prises dans l'ordre 1...n),
u SPT Shortest Precessing Time (t ches tri es par co t croissant)
u LPT Longest Precessing Time (t ches tri es par co t d croissant)
u Chacun de ces 3 algorithmes a une version1 et une version 2 selon le
principe appliqu .
u On aura donc 6 versions dalgorithmes :
LS-1
LS-2
SPT-1
SPT-2
LPT-1
LPT-2
LS-1, SPT-1 et LPT-1
u n=8 de co ts 4, 6, 3,10, 7, 3, 8, 3. p=2 v1=1 et v2 =1/2
u LS-1 4, 6, 3,10, 7, 3, 8, 3
Publicité
M(2)=32
u SPT-1 3, 3, 3, 4, 6, 7, 8, 10
M(2)=38
P1
CHP1
P2
4
4
6
3
7
7
CHP2
12
26
u Pour placer la t che de co t 4,
P1
on a le m me CHP=6 donc on choisit
CHP1
le processeur le plus rapide : P1
P2
CHP2
3
3
3
6
3
6
6
18
10
17
3
32
4
10
10
38
6
3
20
8
28
7
17
8
25
u LPT-1 10, 8, 7, 6, 4, 3, 3, 3
M(2)=30
LPT-1 est le meilleur
4
21
3
24
3
27
3
Publicité
30
P1
10
CHP1 10
P2
8
CHP2 16
7
17
6
28
Heuristique dam lioration
7
u Il existe une heuristique dam lioration bas e sur le transfert dune t che dun
processeur un autre.
u Exemple pour SPT-1
On peut transf rer la t che
de co t 3 de P2 vers P1
u M(2) qui tait gal 38
devient : M(2)=38-6=32
P1
CHP1
P2
CHP2
3
3
3
6
3
6
6
18
4
10
10
38
7
17
8
25
P1
CHP1
P2
CHP2
3
3
X
X
3
6
6
12
4
10
10
32
7
Publicité
17
8
25
3
28
u On calcule d=max CHP- min CHP (ici 38-25 =13) et on choisit une t che ti
transf rer du processeur le plus charg au processeur le moins charg permettant
de minimiser d
LS-2, SPT-2 et LPT-2
u n=8 de co ts 4, 6, 3,10, 7, 3, 8, 3. p=2 v1=1 et v2 =1/2
8
u LS-2 4, 6, 3,10, 7, 3, 8, 3
M(2)=31
LS-2 Meilleur que LS-1
u SPT-2 3, 3, 3, 4, 6, 7, 8, 10
M(2)=34
SPT-2 Meilleur que SPT-1
P1
CHP1
P2
CHP2
4
4
3
6
6
10
7
20
10
20
3
26
3
23
8
31
4
10
6
16
8
24
10
34
P1
CHP1
P2
CHP2
3
3
3
6
3
6
7
20
Publicité
u LPT-2 10, 8, 7, 6, 4, 3, 3, 3
M(2)=30
LPT-2 aussi performant que LPT-1
(meilleur quilibrage de charge)
P1
10
CHP1 10
P2
8
CHP2 16
7
17
4
24
6
23
3
30
3
26
3
29
9
Comparaison
u LS-2 Meilleur que LS-1
u SPT-2 Meilleur que SPT-1
u M me makespan pour LPT-2 et LPT-1 mais LPT-2 offre un meilleur
quilibrage de charge
Donc le principe 2 est plus pertinent que le principe 1 pour le cas des
ordonnancements h t rog nes
car il permet quand il faut d liminer le processeur le plus faible ou les
processeurs les plus faibles au d but ou au milieu de lordonnancement
Exemple : p=2 P1 v1=1 et P2 v2=1/5 ; n=2 c1=10 c2=5
u Si on affecte la t che c1 P1 et c2 P2,
M(2)=max(CHP1,CHP2)=max(c1/v1,c2/v2)=max(10,25)=25
u Si on affecte les 2 t ches P1, M(1)=CHP2=(c1+c2)/v1=15
u M(2)>M(1) donc ici le processeur P2 sera limin des le d but car son
utilisation ralentit lex cution
G n ralisation
u Cas p=2 : 2 processeur P1 et P2 tels que v1>v2 et de n t ches de co ts
c1,& cn
u Si on affecte la t che tq de co t cq=min(ci) P2 et le reste des t ches
P1, M(2)= max ((somme (ci)-cq)/v1 , cq/v2)
u Si on affecte toutes les t che P1 : M(1)= somme (ci)/v1
u Si M(2)>M(1) alors P2 sera limin d s le d but
u Cas p=3 : 3 proceurs v1>v2>=v3 et n t ches co ts tri s c1>=c2&>=cn
u Si on affecte la t che de co t cn P3 et de co t c(n-1) P2 et le reste des
t ches P1,
M(3)= max ((somme (ci)-cn-c(n-1))/v1 , c(n-1)/v2,cn/v3)
u Si on affecte toutes les t che P1 : M(1)= somme (ci)/v1
u Si M(3)>M(1) alors P1 etP2 seront limin s d s le d but
10