1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
|
/**
* Tri d'un tableau d'entiers multi-thread.
* Utilisation de wait() et notify() au lieu de join()
*/
public class Trieur extends Thread
{
private int[] t; // tableau à trier
private int debut, fin; // tranche de ce tableau qu'il faut trier
private Trieur parent; // thread Trieur qui a lancé ce (this) Trieur
private int nbNotify = 0; // La Condition est materialisee ainsi: "nombre de notifications de terminaison=2"
// Initialement, la condition est fausse (nbNotify=0)
public Trieur(int[] t)
{
this(null, t, 0, t.length - 1);
}
private Trieur(Trieur parent, int[] t, int debut, int fin)
{
this.parent = parent;
this.t = t;
this.debut = debut;
this.fin = fin;
}
public synchronized void notifier()
{
// Modifier la condition, et signaler le(s) thread(s) potentiellement
// endormi(s) en attente d'une modification de cette condition.
// Code à fournir
(this.nbNotify)++;
if(this.nbNotify == 2)
{
// On débloque le thread qui attend sur l'objet this c'est à dire this.
//this.notify(); // Curieux, ne fonctionne pas, le programme tourne à l'infini...
this.notifyAll(); // ...alors que celui là fonctionne. Pourquoi ?
}
}
public void run()
{
if (fin - debut < 2)
{
if (t[debut] > t[fin])
{
echanger(debut, fin);
}
}
else
{
int milieu = debut + (fin - debut) / 2;
Trieur trieur1 = new Trieur(this, t, debut, milieu);
Trieur trieur2 = new Trieur(this, t, milieu + 1, fin);
trieur1.start();
trieur2.start();
/*
* QUESTION A POSER :
* On crée la cascades des trieurs ==> il est possible que deux trieurs fils fassent notifyAll() sur
* le parent avant que celui-ci n'ait put passer par son if()wait().
* Le parent wait() donc à l'infini après avoir été notify(). ==> BAD, le prog ne termine jamais.
*/
// Attend les 2 threads fils par le biais du test d'une condition
// qui, si non verifiee, entraine l'utilisation de wait() sur
// le moniteur associe implicitement a l'objet courant (càd à this)
// jusqu'à ce qu'elle soit vérifiée
synchronized( this ) // on pose un lock sur this
{
try
{
// Code à fournir <======= AJOUT
if(this.nbNotify < 2)
this.wait(); // <=== le Thread this attend sur lui même
// Utilisation de wait() en dehors d'une boucle : What's the problem ?
}
catch(InterruptedException e) {}
}
triFusion(debut, fin);
}
// indique qu'il a fini au parent (eventuel) qui l'attend
// Code à fournir
if(this.parent != null)
this.parent.notifier();
}
/**
* Echanger t[i] et t[j]
*/
private void echanger(int i, int j)
{
int valeur = t[i];
t[i] = t[j];
t[j] = valeur;
}
/**
* Fusionne 2 tranches déjà triées du tableau t.
* - 1ère tranche : de debut à milieu = (debut + fin) / 2
* - 2ème tranche : de milieu + 1 à fin
* @param debut premier indice de la 1ère tranche
* @param fin dernier indice de la 2ème tranche
*/
private void triFusion(int debut, int fin)
{
// tableau où va aller la fusion
int[] tFusion = new int[fin - debut + 1];
int milieu = (debut + fin) / 2;
// Indices des éléments à comparer
int i1 = debut,
i2 = milieu + 1;
// indice de la prochaine case du tableau tFusion à remplir
int iFusion = 0;
while (i1 <= milieu && i2 <= fin)
{
if (t[i1] < t[i2])
{
tFusion[iFusion++] = t[i1++];
}
else
{
tFusion[iFusion++] = t[i2++];
}
}
if (i1 > milieu)
{
// la 1ère tranche est épuisée
for (int i = i2; i <= fin; )
{
tFusion[iFusion++] = t[i++];
}
}
else
{
// la 2ème tranche est épuisée
for (int i = i1; i <= milieu; )
{
tFusion[iFusion++] = t[i++];
}
}
// Copie tFusion dans t
for (int i = 0, j = debut; i <= fin - debut; )
{
t[j++] = tFusion[i++];
}
}
public static void main(String[] args)
{
int[] t = {5, 8, 3, 2, 7, 10, 1};
Trieur trieur = new Trieur(t);
trieur.start();
try
{ // on continue d'utiliser un join() pour etre sur que le tri
// complet est termine avant d'afficher le resultat du tri
trieur.join();
}
catch(InterruptedException e) {}
for (int i = 0; i <t.length; i++)
{
System.out.print(t[i] + " ; ");
}
System.out.println();
}
} |
