Ecole Polytechnique






Cours : ``Parallélisme''
Travaux dirigés
E. Goubault & M. Martel

TDs 1 et 2

8 et 15 janvier 2002




1  Démarrage de threads simples

Question
Faire un programme JAVA qui démarre deux threads: Pour ce faire, il faut créer deux classes (une par processus) qui chacune sont des sous-classes de Thread, et une autre classe qui contient un main lançant les deux processus. L'entier en mémoire partagée sera en fait une ``classe enveloppante'' pour les entiers, on pourra utiliser par exemple la classe suivante:

public class UnEntier {
    int val;
    
    public UnEntier(int x) {
        val = x;
    }

    public int intValue() {
        return val;
    }

    public void setValue(int x) {
        val = x;
    }
}
Corrigé
public class Proc1 extends Thread {

    UnEntier refI;

    Proc1(UnEntier ent) {
        refI = ent;
    }
    
    public void run() {
        try {
            System.out.print("\nP1 starts...");
            sleep(100);
            refI.setValue(42);
            System.out.print("\nP1 ends...");            
        } catch (InterruptedException e) { return ; }
    }
}
public class Proc2 extends Thread {

    UnEntier refI;

    Proc2(UnEntier ent) {
        refI = ent;
    }

    public void run() {
        try {
            System.out.print("\nP2 starts...");            
            while (refI.intValue()!=42) { 
                System.out.print("\nP2 waits...") ; 
                sleep (5) ; 
            } ;
            System.out.print("\nP2 ends...");            
        } catch (InterruptedException e) { return ; }            
    }
}
public class Exo1 {

    public static void main(String[] args) {
        UnEntier i = new UnEntier(0);
    
        new Proc1(i).start() ;
        new Proc2(i).start() ;
    }
}

2  Threads récursifs: Fibonacci

Question
Ecrire un calcul de la fonction f de Fibonacci, définie par la récurrence, en utilisant des threads JAVA. L'idée est de paralléliser l'algorithme récursif naturel permettant de calculer f (que l'on pourra écrire dans un premier temps si l'on ne se sent plus très à l'aise avec JAVA). Mais pour calculer f(n+2), au lieu de s'appeler soi-même deux fois pour calculer f(n+1) et f(n), on créera un thread pour calculer f(n+1) et un autre pour calculer f(n). Ainsi, on définira une classe,

public class Fibon extends Thread {
...
    public void run() {
    ...
    }
}
dont la méthode run() sera en charge de calculer la fonction f. Pour ce faire il faut que la classe Fibon contienne un champ argument, et un champ résultat, ce dernier pouvant ``survivre'' dans la mémoire partagée au thread qui le calcule. Ainsi nous devons utiliser une ``classe enveloppante'' pour le résultat. On pourra utiliser pour ce faire la classe UnEntier vue précedemment.

On programmera donc,
Corrigé
public class Fibon extends Thread {

    int arg;
    UnEntier res;

    Fibon(int x, UnEntier intref) {
        arg = x;
        res = intref;
    }

    public void run() {
        UnEntier res1 = new UnEntier(0);
        UnEntier res2 = new UnEntier(0);
        System.out.println("Fibo("+arg+")");
        if ((arg == 0) || (arg == 1)) 
            res.setValue(1);
        else {
            Thread x = new Fibon(arg-1,res1);
            Thread y = new Fibon(arg-2,res2);
            x.start();
            y.start();
            try {
                x.join();
                y.join();
            } catch(InterruptedException e) {};
            res.setValue(res1.intValue()+res2.intValue());
        }
    }

    public static void main(String[] args) {
        UnEntier R = new UnEntier(0);
        Thread t = new Fibon(Integer.parseInt(args[0]),R);
        t.start();
        try {
            t.join();
        } catch(InterruptedException e) {};
        System.out.println("Resultat="+R.intValue());
    }
}

3  Crible d'Erathostène

Question
Ecrire un programme JAVA ``par passage de messages'' affichant la suite des nombres premiers en utilisant la méthode du crible : un processus est chargé de générer les entiers naturels, dont on élimine d'abord les multiples de 2, puis 3, 5, etc. au moyen de processus filtrants successifs. On utilisera les deux classes suivantes:

import java.util.*;

public class MsgQueue {
    Vector queue = new Vector();

    public synchronized void send(Object obj) {
        queue.addElement(obj); 
    }

    public synchronized Object recv() {
        if (queue.size() == 0)
            return null;
        Object obj = queue.firstElement();
        queue.removeElementAt(0);
        return obj;
    }
}
Et:

public class Process {
    MsgQueue In;
    MsgQueue Out;

    public Process(MsgQueue i, MsgQueue o) {
        In = i;
        Out = o;
    }

    public void send(int x) {
        Out.send(new Integer(x));
// System.out.println(Thread.currentThread().getName()+": send("+x+")");
    }

    public int recv() {
        Object x = In.recv();
        while (x == null)
            x = In.recv();
        int res = ((Integer) x).intValue();
// System.out.println(Thread.currentThread().getName()+": recv "+res);
        return res;
    }
}
Corrigé
import java.util.*;


class MsgQueue {
    Vector queue = new Vector() ;
    
    public synchronized void send(Object obj) {
        queue.addElement(obj);
    }
    
    public synchronized Object recv() {
        if (queue.size()==0) 
            return null;
        Object obj = queue.firstElement();
        queue.removeElementAt(0);
        return obj;
    }

    public synchronized int size() {
        return queue.size();
    }
}
    
class Process {
    MsgQueue In;
    MsgQueue Out;
    
    public Process(MsgQueue i,MsgQueue o) {
        In=i;
        Out=o;
    }
    
    public void send(int x) {
        Out.send(new Integer(x));
    }
    
    public int recv() {
        Object x = In.recv();
        while (x==null)
            x=In.recv();
        int res = ((Integer) x).intValue();
        return res;
    }
}

class Generateur extends Thread {
    int n;
    Process p;
    
    Generateur(int max,MsgQueue mq) { 
        n=max;
        p=new Process(null,mq);
    }
    
    public void run() {
        for(int i=2;i<=n;i++) {
            p.send(i);
        };
        p.send(-1);
    }
}

class Filtre extends Thread {
    int filtre;
    Process p;

    Filtre(MsgQueue mq) { 
        p=new Process(mq,new MsgQueue()); 
    }     

    public void run() {
        int i;
    
        filtre = p.recv();
        if (filtre != -1) {
            System.out.println(filtre);
            new Filtre(p.Out).start();
            i=p.recv();
            while (i!=-1) {
                if (i % filtre != 0) {
                    p.send(i);
                };
                i=p.recv();
            };
            p.send(-1);
        }
    }
}

class Eratosthene {

    public static void main(String[] args){
        if (args.length<1) {
            System.out.println("Usage : java Eratosthene n");
            return;
        }
        MsgQueue mq = new MsgQueue();
        new Generateur(Integer.parseInt(args[0]),mq).start();
        new Filtre(mq).run();
    }
}

This document was translated from LATEX by HEVEA.