On suppose que l'on dispose d'un réseau linéaire de p processeurs P1,...,Pp, c'est à dire que les processeurs sont organisés sur une ligne, et que chacun peut communiquer avec son voisin de gauche et son voisin de droite s'il en a un. On veut trier n entiers, avec p qui divise n. Chaque processeur a au départ n/p entiers, et on veut trouver un algorithme parallèle qui permette de faire en sorte que la sous-suite sur Pi soit ordonnée et inférieure à la sous-suite ordonnée Pj, pour tout i<j. C'est à dire tout simplement que l'on veut trier en parallèle les données réparties sur les processeurs Pi.
En s'inspirant du réseau de tri pair-impair vu en cours, écrire un tel algorithme en JAVA. Pour ce faire, on utilisera la classe Buffer suivante, pour coder les échanges de données entre chaque processus, chacun implémentant un comparateur du réseau de tri.
class Buffer {
int val;
Buffer() { val = -1; }
synchronized void write(int v) {
while (val!=-1) {
try { wait(); } catch (InterruptedException e) {};
};
val = v;
notifyAll();
}
synchronized int read() {
while (val==-1) {
try { wait(); } catch (InterruptedException e) {};
};
int n = val;
val = -1;
notifyAll();
return n;
}
}
class Comparateur extends Thread {
int proc; // numero de processeur
int val; // valeur courante
int nMax; // nb de valeurs a trier
int[] tab; // pour stocker les resultats finaux
Buffer lg,ld,eg,ed; // lecture-ecriture, droite-gauche
Comparateur(int p,int v,int n,int[] tt,Buffer llg,Buffer eeg,Buffer lld,Buffer eed) {
proc = p; val = v; nMax = n; tab = tt;
lg = llg; ld = lld; eg = eeg; ed = eed;
}
public void run() {
int dv,gv; // valeurs lues a gauche et a droite
for (int etape=0;etape<nMax;etape++) {
if ((etape%2)==0) {
if ((proc%2)==0) {
if (ed!=null) ed.write(val);
if (ld!=null) dv = ld.read(); else dv = val;
if (dv<val) { val = dv; }
} else {
if (eg!=null) eg.write(val);
if (lg!=null) gv = lg.read(); else gv = val;
if (gv>val) { val = gv; }
}
} else {
if ((proc%2)==0) {
if (eg!=null) eg.write(val);
if (lg!=null) gv = lg.read(); else gv = val;
if (gv>val) { val = gv; }
} else {
if (ed!=null) ed.write(val);
if (ld!=null) dv = ld.read(); else dv = val;
if (dv<val) { val = dv; }
}
}
}
tab[proc] = val;
}
}
class Tri {
static final int nMax = 10;
static int[] tab = { 62,49,22,67,11,6,51,17,29,37 };
static int[] tabTrie = new int[nMax];
public static void main(String[] args) {
Comparateur[] cmp = new Comparateur[nMax];
Buffer lg,eg,ld,ed;
lg = null; eg = null ;
for (int i=0;i<nMax-1;i++) { // creation des threads
ld = new Buffer();
ed = new Buffer();
cmp[i]= new Comparateur(i,tab[i],nMax,tabTrie,lg,eg,ld,ed);
lg = ed; eg = ld;
};
ld = null; ed = null; // creation du dernier thread
cmp[nMax-1] = new Comparateur(nMax-1,tab[nMax-1],nMax,tabTrie,lg,eg,ld,ed);
for (int i=0;i<nMax;i++) { // execution des threads
cmp[i].start();
};
for (int i=0;i<nMax;i++) { // attente des resultats
try { cmp[i].join(); } catch (InterruptedException e) {} ;
};
for (int i=0;i<nMax;i++) { // affichage resultats
System.out.println(tabTrie[i]);
};
}
}
Programmes: Tri.java.
On cherche à implémenter un ordonnanceur à tourniquet pour les threads JAVA en JAVA. L'idée est que l'on doit définir un thread ordonnanceur qui gère une file d'attente de threads utilisateurs JAVA et les ordonnancer un à un pour un quantum de temps élémentaire donné (une constante de votre programme). Cet ordonnanceur ne gèrera pas de notion de priorité.
Chaque thread utilisateur devra s'enregistrer auprès de l'ordonnanceur en appelant la méthode addThread() (à écrire). On pourra aussi écrire une méthode removeThread qui désinscrit un thread auprès de cet ordonnanceur. On utilisera la classe CircularList, qui fournit une implémentation de liste circulaire, avec les méthodes:
Avant de commencer, on répondra aux questions suivantes: quelle doit être la priorité du thread ordonnanceur? du thread utilisateur actif? des threads non encore actifs?
La priorité du thread ordonnanceur doit être maximale, du thread actif: médiane, des threads
non encore actifs: minimale.
L'ordonnanceur:
public class CPUScheduler extends Thread {
private int timeslice;
private CircularList threads;
public boolean shouldRun = false;
public CPUScheduler(int t) {
threads = new CircularList();
timeslice = t;
}
public void addThread(Thread t) {
threads.insert(t);
t.setPriority(2);
}
public void removeThread(Thread t) {
t.setPriority(5);
threads.delete(t);
}
public void run() {
Thread current;
setPriority(6);
while (shouldRun) {
current = (Thread) threads.getNext();
if (current == null)
return;
current.setPriority(4);
try {
Thread.sleep(timeslice);
} catch (InterruptedException ie) {};
current.setPriority(2);
}
}
}
Et un programme de test:
class TestThread extends Thread {
String id;
public TestThread(String s) {
id = s;
}
public float doCalc(int i) {
float x;
for (int j=0; j<100000; j++)
x = j*j-j;
return x;
}
public void run() {
int i;
float y;
for (i = 0; i < 100; i++) {
y = doCalc(i);
System.out.println(id);
}
}
}
public class Test {
public static void main(String args[]) {
CPUScheduler c = new CPUScheduler(100);
TestThread t1, t2, t3;
t1 = new TestThread("Thread 1");
t2 = new TestThread("Thread 2");
t3 = new TestThread("Thread 3");
c.addThread(t1);
c.addThread(t2);
c.addThread(t3);
c.start();
t1.start();
t2.start();
t3.start();
}
}
Les programmes: CPUScheduler.java, Test.java.