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();
}
} |
Partager