:: Enseignements :: ESIPE :: E4INFO :: 2014-2015 :: Java Réseau I - Concurrence et E/S ::

Volatile, operations atomiques, Compare and Set

Exercice 1 - Liste concurrente et atomicité

On souhaite écrire une implantation de liste chaînée de chaînes de caractères avec insertion à la fin, concurrente et n'utilisant ni section critique, ni verrou.
La liste devra possèder deux méthodes addLast(E e) et forEach() permettant respectivement d'ajouter un élement en fin de la liste et d'appeler un java.util.function.Consumer sur l'ensemble des élements de la liste.
Le code ci-dessous est une implantation non-thread safe de la liste

Détail d'implantation, pour éviter de gérer différemment le cas de la liste vide, une liste est crée initialement avec un maillon contenant la valeur null.

L'idée de l'algorithme concurrent est la suivante: pour éviter toute synchronisation lors de l'ajout, on récupere le maillon à la fin de la liste puis on teste en utilisant une opération atomique si le maillon est toujours la fin de la liste; si oui, on lui assigner le nouveau maillon créé. Si ce n'est pas le dernier maillon, on récupère de nouveau le maillon à la fin de la liste et on recommence la même opération...

Recopier le code de la classe StringList dans une classe LockFreeStringList et remplacer le champ Entry next par AtomicReference<Entry> next.
Implanter la méthode addLast comme décrit précédemment.
Comment doit-on modifier le code de forEach pour que la méthode soit thread-safe ?
On souhaite améliorer la complexité de la méthode addLast en maintenant, en plus d'une référence sur la tête de la liste (head), une référence sur la queue de la liste (tail).
Modifier l'implantation de addLast pour utiliser le champ tail et le mettre à jour.
Le problème de cette solution est que dans chaque maillon, on stocke un objet AtomicReference qui contient une référence vers un objet Entry. Cela fait une redirection de trop. Utilisez AtomicReferenceFieldUpdater pour éviter cette redirection inutile.

Exercice 2 - Travail en parallèle

On souhaite écrire un programme calculant combien il existe de nombre premiers dans un tableau de 1 000 000 entiers long donné.
Pour savoir si un nombre est premier on utilisera la méthode suivante

     public static boolean isPrime(long n) {
        return IntStream.rangeClosed(2, (int) Math.sqrt(n)).noneMatch(divisor -> n % divisor == 0);
     }

On souhaite paralléliser le programme en permettant d'exécuter en même temps plusieurs calculs sur différents CPUs. On va donc découper le tableau (virtuellement, juste avec des index) pour que chaque CPUs calcule le nombre de nombre premiers sur une partie du tableau.
Pour les tests, on initialisera les cases du tableau avec des valeurs aléatoires entre 1 et 1 000 000.

Dans une méthode primeInParallelWithExecutors qui prend le tableau en paramètre, créer un ExecutorService en utilisant la classe Executors permettant de distribuer le calcul sur 5 threads différents.
Dans un premier temps, on ne s'intéresse qu'aux sommes intermédiaires que l'on va afficher. Écrire le programme qui effectue le calcul en parallèle en utilisant des Callable qui effectuent le calcul.
Penser à utiliser la méthode shutdown pour indiquer qu'il n'y a plus de calculs à effectuer.
Effectuer un affichage des sommes intermédiaires.
Que remarque t-on ?
Utiliser le mécanisme de Future pour calculer la somme totale.
Ecrire une méthode primeInParallelWithStream qui fait le même calcul avec un Stream parallèle.
Pour avoir un Stream parallèle, il suffit d'appeler parallel() sur l'interface Stream.
Vérifier que vous obtenez le même résultat qu'avec le pool de threads.