:: Enseignements :: ESIPE :: E4INFO :: 2017-2018 :: Concurrence ::

Volatile, Atomic, Compare and Set

Exercice 1 - A vos chronometres

On cherche à savoir combien d'itérations d'une boucle on peut faire en 100 millisecondes. Un de vos collègues a produit le code suivant:

Sans exécuter le code, que fait ce programme ?
Vérifier, en exécutant le programme (plusieurs fois), si vous avez vu juste.
Comment doit-on corriger le problème ?
Modifier la classe Bogus en conséquence.
On cherche maintenant a accélérer le code de Bogus en utilisant le mot clé volatile au lieu des blocs synchronized.
Créer une classe BogusVolatile qui n'utilise pas de bloc synchronized.
Comment appelle-t-on les implantations qui n'ont ni blocs synchronized, ni lock ?

Exercice 2 - Generateur pseudo-aléatoire lock-free

On souhaite modifier la classe RandomNumberGenerator pour la rendre thread-safe sans utiliser ni section critique ni verrou (lock-free donc).

Expliquer comment fonctionne un générateur pseudo-aléatoire et pourquoi l'implantation ci-dessous n'est pas thread-safe.
Utiliser la classe AtomicLong et la méthode compareAndSet pour obtenir une implantation lock-free du générateur pseudo-aléatoire.
Depuis le jdk 1.8, la classe AtomicLong possède une méthode updateAndGet, comment peut-on l'utiliser ici ? Modifiez votre code en conséquence.
Un des inconvénients des champs "atomiques" est qu'ils alourdissent l'allocation nécessaire pour chaque objet. En effet, pour utiliser un long pour chaque objet générateur, il faut allouer un AtomicLong qui permettra lui-même d'accéder de manière atomique à la valeur d'un long, chaque accès nécessitant lui-même une indirection...
Faites une nouvelle implantation du générateur pseudo-aléatoire qui utilise la classe VarHandle. Un VarHandle ne nécessite qu'une seule instance (static) pour mettre à jour de manière atomique le champ volatile long de n'importe lequel des objets générateur de cette classe.

Exercice 3 - 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 size() permettant respectivement d'ajouter un élément en fin de la liste et de retourner la taille 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écupère 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 assigne 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 qui va implanter une liste thread-safe sans verrou.
Dans un premier temps, implanter la méthode addLast. Pour cela vous utiliserez la classe VarHandle.
Comment doit-on modifier le code de size 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.