TP 2 - Algorithmes de verrouillage

Encore une fois, pour ce TP, il est fortement recommandé d'utiliser les machines de la salle de TP, mais vous pouvez utiliser votre propre machine si celle-ci a au moins quatre cœurs. Vous pourrez cependant avoir à modifier quelques définitions dans le code qui vous est fourni pour pouvoir l'utiliser sur votre machine.

Exercice : une pile à verrous

Téléchargez l'archive suivante. Elle contient les fichiers source de ce TP. Si vous utilisez votre propre machine, modifiez USE_CPUS et CACHE_LINE_SIZE dans definitions.h. Le fichier stack_mutex.c implémente un programme dont les threads manipulent une pile protégée avec des mutexes POSIX. Chaque thread effecture de très nombreuses opérations push() et pop(). Lisez le code et assurez-vous que vous le comprenez.

Question 1. Lancez le code avec quatre threads sur quatre cœurs en utilisant bench.sh. Quelles performances obtenez-vous ?

Question 2. Copiez le fichier stack_mutex.c vers stack_spinlock.c. Dans ce fichier, remplacez le mutex POSIX par un spinlock basique que vous implémenterez vous-même. Avec quatre threads sur quatre cœurs, quelles performances obtenez-vous ?

Question 3. Essayez maintenant avec mille threads sur un seul cœur, avec le mutex POSIX et le spinlock. Pouvez-vous expliquer les performances que vous observez?

Question 4. Créez maintenant stack_clh.c, dans lequel vous implémenterez l'algorithme CLH. Quelles performances obtenez vous pour quatre threads sur quatre cœurs ?

Question 5. Comparez les algorithmes MCS et CLH. En quoi sont-ils similaires ? Quelle est la différence principale entre les deux algorithmes ?

Jetez maintenant un œil à la page wikipedia du Ticket Lock. À votre avis, cet algorithme est-il plus rapide ou plus lent que CLH ?

Question 6. Créez finalement stack_ticket.c, qui utilisera votre implémentation du Ticket Lock. Les performances sont elles-meilleures, pires, ou similaires à celles de CLH ?

Question 7. Essayez de remplacer _mm_pause() par sched_yield() dans chacune des boucles à attente active de vos verrous. Lorsque vous lancez vos algorithmes avec 1000 threads sur un cœur, quelle différence observez-vous en termes de performances ?

Pour aller plus loin...

Pour aller plus vite que CLH ou le Ticket Lock, il va falloir utiliser un algorithme dans lequel un thread exécute, en plus de sa section critique, de nombreuses autres sections critiques en attente provenant d'autres threads. Chaque chaîne de sections critiques est exécutée sans aucune synchronisation, ce qui est très efficace... Attention cependant, avec un tel algorithme, on n'a plus de fonctions lock() et unlock() : si on ne peut pas acquérir le verrou directement, il faut stocker un pointeur vers une fonction qui encapsule la section critique quelque part, et de la même manière, il faut stocker un objet de contexte qui contiendra les arguments et la valeur de retour de la fonction !

Jetez un œil à l'article suivant, et implémentez l'algorithme 1 (page 4). Quelles performances obtenez-vous ? Pour améliorer encore les performances, vous pouvez essayer de faire en sorte que le combinateur évite les paires de push() et de pop() qui s'annulent, comme décrit dans l'article...