Programmation Multicoeur - TP 2

Récupérez l’archive utile pour ce TP.

Commençons par introduire les threads en Java.

Compteur concurrent en Java

Exercice Dans exo1_compteur/ vous trouverez le code d’un compteur concurrent. Lisez-le pour apprendre comment on lance un thread en Java, soit en implémentant l’interface Runnable, soit via une fonction anonyme. Vous vous souvenez de ce qu’est un accès concurrent (data race)? Exécutez le programme pour vous rafraichir la mémoire. Votre mission: explorer différentes approches pour éliminer ces data races. A chaque fois, définissez une nouvelle classe qui concrétise Compteur.

1. CompteurMutex: utilisez un mutex (cf cours de la semaine dernière). La documentation de l’interface Lock de Java est votre amie.
2. ComteurAtomic: utilisez un entier atomique
3. CompteurCAS: utilisez la méthode compareAndSet de l’entier atomique.
4. CompteurSynchronized: faites précéder la déclaration de la méthode incr du mot-clé synchronized.

Notion de moniteur

Un moniteur est une structure de programme inventée par Per Brinch Hansen et Tony Hoare qui est apparue pour la première fois dans le langage Concurrent Pascal. Bien que l’idée n’ait donc pas été originellement formulée en paradigme objet, elle peut se décrire simplement comme un objet dans lequel les méthodes (déclarées synchronized en Java) s’exécutent en section critique. Il y a donc un mutex implicite associé à l’objet. Un moniteur dispose aussi d’une variable de condition associée à ce mutex. Il s’agit d’une nouvelle primitive de synchronisation dont nous devons maintenant parler.

Avant d’en expliquer le fonctionnement, essayons de donner une implémentation d’un sémaphore sans variable de condition. Un sémaphore est un compteur atomique positif et bloquant: on peut d’une part l’incrémenter de manière atomique (release), d’autre part le décrémenter de manière atomique (acquire), mais bloquante: la valeur après décrément doit rester positive ou nulle. On peut notamment utiliser un sémaphore comme un verrou: avec une valeur 1, le verrou est libre, et avec une valeur 0, le verrou est pris. Il s’agit d’une autre primitive de synchronisation très classique et disponible dans la libraire standard de Java, cf java.util.concurrent.Semaphore, et comme souvent on va la redéfinir simplement pour l’intérêt pédagogique.

interface Semaphore {
    void set(int initValue);
    void acquire(); // <- bloquant!
    void release();
}

class LockSemaphore<S extends Semaphore> implements Lock {
    private final S s;
    LockSemaphore(S s){ 
        this.s = s;
        s.set(1);
    }
    public void lock() { s.acquire(); }
    public void unlock() { s.release(); }
    // on triche un peu, avec l'interface Lock de Java
    // il resterait des méthodes à implémenter...
}

Exercice: Complétez le code dans exo2_semaphore/SemaphoreAtomicInteger.java et donnez une implémentation d’un sémaphore avec un AtomicInteger. Exécutez et vérifiez que votre implémentation est correcte.

Si l’on avait voulu implémenter un sémaphore à l’aide d’un moniteur, sans connaitre les variables de condition, on aurait pu naïvement écrire ceci

class SemaphoreNaif implements Semaphore {
    private int val;
    SemaphoreNaif(int initValue){ val = initValue;}
    synchronized void release(){ val++; }
    synchronized void acquire(){
        while( val < 1 );
        val--;
    }
}

Question Est-ce que vous voyez pourquoi c’est une très mauvaise idée?

Revenons maintenant aux variables de condition. Une variable de condition permet à un thread, au milieu d’une section critique, de se mettre en attente (wait). Le thread relâche alors le verrou pour permettre à un autre thread de le prendre, et s’endort. Un autre thread, au milieu de la section critique, peut signaler la variable de condition. Ce thread signaleur réveille alors un (notify) ou tous (notifyAll) les threads en attente, et le signaleur conserve le verrou. Le ou les threads réveillés sont remis dans la file d’attente du verrou, et quand il acquerront le verrou, ils reprendront la section critique juste après le wait où ils s’étaient endormis. Si aucun thread n’était endormi au moment du signal, le signal est perdu. Pour implémenter un sémaphore, on peut donc définir le moniteur comme suit.

class SemaphoreMonitor implements Semaphore {

    private int val;
    private final int init;

    SemaphoreMonitor(int initValue){ init = val = initValue; }

    synchronized void release(){
        val++;
        if ( val == 1 ) notifyAll();
    }

    synchronized void acquire(){
        while ( val < 1 ) wait();
        val--;
    }

    int getInit() { return init; }
}

Questions :

• pourquoi n’est-il pas nécessaire de déclarer getInit synchronisée?

• pourquoi n’a-t-on pas juste écrit if ( val < 1 ) wait();?

• pourquoi n’a-t-on pas utilisé simplement notify()?

Parallélisation de boucle

L’un des intérêts des threads est qu’ils permettent d’améliorer les performances d’un programme lorsqu’il est exécuté sur une machine multicoeur (autrement dit à peu près n’importe quelle machine aujourd’hui). Il existe plusieurs “patrons” de parallélisation de code qu’il faut connaitre, nous allons nous intéresser pour le moment au plus simple d’entre eux, la parallélisation de boucle, et nous allons le faire sur un problème très simple, le comptage du nombre d’occurrences d’une valeur donnée dans un tableau.

Exercice

1. Exécutez et lisez le code dans le répertoire exo3_nbOccurs/.

2. Implémentez la méthode nbOccursParallel2 qui calcule le nombre d’occurences en utilisant deux threads qui se partagent la première et la deuxième moitié du tableau. Exécutez et vérifiez que le résultat est correct et le speedup raisonnable.

3. Implémentez la méthode nbOccursParallelN qui calcule le nombre d’occurrences en utilisant N threads. Exécutez et vérifiez que le résultat est correct et le speedup raisonnable (attention, la création de thread coûte cher, vous serez loin d’un speedup de N).

4. Ré-implémentez la méthode nbOccursParallelN en utilisant un ExecutorService et un ArrayList de Future.