TP 3 - Algorithmique non-bloquante

Ce TP est à rendre. Envoyez une archive contenant votre compte-rendu et vos fichiers source avant mardi prochain à 13h30, par e-mail à Jean-Pierre Lozi (vous trouverez l'adresse sur le site de l'UE).

Exercice : une pile sans verrous

Le but de cet exercice est d'implémenter une pile sans verrou et de comparer les performances de cette pile à celle d'une pile avec verrou. Pour cela, nous allons implémenter la pile sans verrou proposée par Mellor-Crummey et Scott (Synchronization Without Contention, publié à ASPLOS en 1991).

Question 1. Dans un premier temps, vous allez créer un environnement dans lequel nous pourrons tester nos piles. Dans ce premier exercice, vous devez créer N threads, N étant un paramètre du programme. Chaque thread doit afficher le message "Thread <N> starting..." puis se terminer. Ne fixez pas les threads sur des cœurs.

Question 2. Implémentez les fonctions push_lock_free(int value) et int pop_lock_free() permettant d'ajouter et de retirer un entier dans la pile stack_lock_free. Pour cela, utilisez l'algorithme sans verrou vu en cours, à ceci près que votre fonction pop doit bloquer (attente active) tant qu'il n'y a pas d'élément dans la pile. Remarque : Lorsque vous ajoutez un noeud, vous devez préalablement allouer sa mémoire. On vous demande, dans cette question, de le pas libérer la mémoire d'un noeud dans pop.

Vous testerez votre code en ajoutant et retirant 10⁶ éléments dans votre pile à partir de chaque thread (tous les ajouts avant tous les retraits). Testez votre programme avec 10 threads.

Question 3. On vous demande maintenant de libérer la mémoire des structures allouées dans la fonction pop. Pour quelle raison votre programme plante-t-il? Expliquez clairement le problème dans votre rapport.

Nous n'allons pas résoudre le problème pour l'instant, donc retirez votre free().

Question 4. Nous allons maintenant créer la version avec verrou de la pile. Implémentez les fonctions push_mutex(int value) et int pop_mutex() permettant d'ajouter et de retirer des éléments à votre pile stack_mutex. Pour cela, utilisez un algorithme avec verrouillage (pthread_mutex_lock()). Ajoutez un paramètre à votre programme qui permettra de choisir l'une ou l'autre des implémentations.

Testez votre fonction dans le thread en ajoutant et retirant 10³ éléments dans votre file à partir de chaque thread.

Question 5. En utilisant la fonction gettimeofday(), faîtes quelques mesures. Quel algorithme est le plus efficace?

Question 6. Utilisez maintenant l'algorithme CLH que vous avez implémenté au dernier TP pour produire la troisième version de la pile. Comparez vos trois implémentations avec un nombre variable de threads (ajustez le nombre d'opérations pour obtenir des temps de mesure raisonnables). Bonus : vous pouvez également utiliser des usleep(250) dans vos boucles d'attente active pour voir comment cela affecte vos résultats.

Question 7. Expliquez comment vous pourriez régler le problème de la question 1.3. On ne vous demande pas d'implémenter votre solution.

Question 8. Un compare-and-swap permet seulement de vérifier que la valeur d'un pointeur est la même que précédemment, et non pas qu'elle n'a pas été modifiée entre temps. Cela pose-t-il un problème pour votre pile non-bloquante ? Si oui, comment le résoudre ?