Sans futex, cela n’a aucun sens

• Il est regrettable que le manuel The Art of Multiprocessor Programming n’aborde pas la notion de futex
• Le futex est un composant clé de la synchronisation efficace en programmation parallèle moderne, avec de meilleures performances que les verrous traditionnels basés sur System V
• Les futex adoptent une structure qui sépare l’acquisition du verrou des opérations d’attente/réveil, ce qui réduit les appels système inutiles et l’overhead
• L’article inclut des exemples et des techniques pour implémenter directement, à partir des futex, diverses primitives de concurrence comme les spinlocks, mutex et verrous récursifs
• L’auteur critique le fait que l’ouvrage ne traite pas des méthodes de synchronisation modernes indispensables en pratique d’ingénierie, soulignant l’écart entre le monde académique et l’industrie

---

Introduction

• Phil Eaton a lancé un club de lecture autour de The Art of Multiprocessor Programming, 2nd Edition
• Ce livre est considéré comme un manuel de référence en programmation parallèle, mais l’auteur lui reproche son manque de portée pratique
• Il critique en particulier le fait que, bien que destiné aux étudiants de fin de licence et de master, il n’aborde pas le futex, une technique de synchronisation essentielle

Qu’est-ce qu’un futex, et pourquoi est-ce important ?

• Le futex, abréviation de “fast user space mutex”, n’est pas vraiment un mutex à proprement parler, mais plutôt une primitive de synchronisation fournie par l’OS pour implémenter les verrous modernes
• Par le passé, la plupart des verrous reposaient sur les sémaphores de System V IPC, avec des limites en efficacité et en scalabilité
• Avec l’introduction des futex dans Linux en 2002, les performances ont été 20 à 120 fois supérieures à celles des verrous System V dans des environnements avec 1000 tâches concurrentes
• D’autres OS comme Windows (2012) et macOS (2016) ont aussi adopté des mécanismes similaires
• Les verrous des bibliothèques système largement utilisées aujourd’hui, comme pthreads, s’appuient sur les futex

Principe de fonctionnement du futex et ce qui le distingue

• Les sémaphores traditionnels combinaient verrouillage et attente, tandis que le futex sépare l’acquisition du verrou des opérations d’attente/réveil
• Cela permet de réduire les délais inutiles et les appels système ; lors de la libération d’un verrou, s’il est certain qu’aucun thread n’attend, il n’est pas nécessaire d’entrer dans le noyau
• L’appel d’attente (wait) du futex ne met en attente que si « la valeur à une adresse mémoire donnée correspond à l’état attendu », avec prise en charge des timeouts
• L’appel de réveil (wake) du futex réveille le nombre souhaité de threads dans la liste d’attente interne associée à une adresse mémoire donnée
• Le mécanisme vérifie explicitement la valeur réelle en mémoire, afin d’éviter une attente inutile si l’état a déjà changé

Utilisation concrète des futex : implémentation directe

• Le futex étant une primitive de bas niveau, on utilise des types atomic en tenant compte des questions d’ordre des opérations mémoire côté compilateur et matériel
• Sous Linux, il faut appeler directement le syscall futex via syscall ; sur macOS, on utilise l’interface __ulock (des API plus simples ont été ajoutées récemment)
• En pratique, l’attente sur futex renvoie 0 en cas de succès, et un code d’erreur en cas d’échec (timeout, etc.)
• Opérations centrales basées sur futex :
  • h4x0r_futex_wait_timespec() : attend si la valeur attendue correspond, avec possibilité de timeout
  • h4x0r_futex_wake() : réveille un seul ou tous les threads en attente

Exemples concrets d’implémentation de mutex/spinlock/verrou récursif

Spinlock

• La forme de verrou la plus simple, fonctionnant avec un seul bit (atomic_fetch_or)
• Il boucle indéfiniment (« spin ») jusqu’à obtenir le verrou, mais en cas de forte contention, il gaspille du CPU et présente des problèmes structurels comme une mauvaise libération du verrou ou des risques de deadlock en cas d’appel récursif

Mutex hybride (« unsafe » mutex)

• En général, on essaie d’abord avec un spinlock, puis après un certain nombre d’échecs on bascule vers un futex pour un blocage plus efficace
• S’il n’y a pas de thread en attente, on peut éviter des appels système inutiles ; pour les threads en attente, on peut aussi minimiser les syscalls de réveil
• Comme la vérification stricte de propriété ou la gestion de la récursivité sont incomplètes, l’appellation « unsafe » est utilisée

Mutex avec compteur de waiters

• Un bit représente l’état du verrou, les autres servent à compter le nombre de threads en attente, afin de réduire les syscalls de réveil inutiles
• Il n’y a toujours ni gestion de propriété ni gestion de récursivité

Mutex avec gestion de propriété

• La valeur pthread_t permet de suivre clairement le propriétaire du verrou et son état, afin de détecter des unlock incorrects ou des usages récursifs problématiques
• L’acquisition, la libération et la gestion des waiters sont toutes contrôlées strictement par des opérations atomiques

Verrou récursif

• Il ajoute un compteur de profondeur (depth) par thread, permettant au même thread d’acquérir plusieurs fois le verrou
• Lors du unlock, la profondeur diminue ; quand elle atteint 0, le déverrouillage réel et le réveil ont lieu
• Chaque opération est implémentée avec des opérations atomiques et une vérification stricte de propriété

Défis restants et réalité de l’ingénierie

• Si le thread propriétaire du verrou se termine de manière anormale, la gestion du verrou exige des mécanismes supplémentaires comme une liste d’administration dédiée ou des callbacks de fin
• L’usage de mutex partagés entre processus demande également des précautions supplémentaires pour gérer les changements d’état
• Les verrous POSIX RW ne définissent pas le comportement en cas de récursivité imbriquée et les implémentations diffèrent, ce qui rend la sûreté difficile à garantir en pratique
• L’auteur critique le fait que les enjeux de concurrence vraiment importants en pratique (futex, verrous récursifs, runtimes asynchrones, etc.) ne soient pas intégrés aux cursus

Conclusion

• The Art of Multiprocessor Programming est trop centré sur l’histoire ou la théorie et ne transmet pas correctement des savoirs pratiques essentiels de la programmation parallèle moderne
• Ne pas traiter correctement des composants clés de synchronisation comme les futex, tels qu’ils fonctionnent réellement dans les systèmes, peut nuire concrètement à la formation des générations suivantes
• L’auteur insiste sur la nécessité d’intégrer les concepts récents et de renforcer le contenu pratique

Référence

• L’ensemble des exemples de code est disponible sur codeberg