Hugo Guiroux - Comprendre la performance des algorithmes d'exclusion mutuelle sur les machines multicoeurs modernes

Une multitude d’algorithmes d’exclusion mutuelle ont été conçus au cours des vingt-cinq dernières années, dans le but d’améliorer les performances liées à l’exécution de sections critiques et aux verrous. Malheureusement, il n’existe actuellement pas d’étude générale et complète au sujet du comportement de ces algorithmes d’exclusion mutuelle sur des applications réalistes (par opposition à des applications synthétiques) qui considère plusieurs métriques de performances, telles que l’efficacité énergétique ou la latence. Dans cette thèse, nous effectuons une analyse pragmatique des mécanismes d’exclusion mutuelle, dans le but de proposer aux développeurs logiciels assez d’informations pour leur permettre de concevoir et/ou d’utiliser des mécanismes rapides, qui passent à l’échelle et efficaces énergétiquement.
Premièrement, nous effectuons une étude de performances de 28 algorithmes d’exclusion mutuelle faisant partie de l’état de l’art, en considérant 40 applications et quatre machines multicoeurs différentes. Nous considérons non seulement le débit (la métrique de performance traditionnellement considérée), mais aussi l’efficacité énergétique et la latence, deux facteurs qui deviennent de plus en plus importants. Deuxièmement, nous présentons une analyse en profondeur de nos résultats. Plus particulièrement, nous décrivons neufs problèmes de performance liés aux verrous et proposons
six recommandations aidant les développeurs logiciels dans le choix d’un algorithme d’exclusion mutuelle, se basant sur les caractéristiques de leur application ainsi que les propriétés des différents algorithmes.

A partir de notre analyse détaillée, nous faisons plusieurs observations relatives à l’interaction des verrous et des applications, dont plusieurs d’entre elles sont à notre connaissance originales : (i) les applications sollicitent fortement les primitives lock/unlock mais aussi l’ensemble des primitives de synchronisation liées à l’exclusion mutuelle (ex. trylocks, variables de conditions), (ii) l’empreinte mémoire d’un verrou peut directement impacter les performances de l’application, (iii) pour beaucoup d’applications, l’interaction entre les verrous et l’ordonnanceur du système d’exploitation est un facteur primordial de performance, (iv) la latence d’acquisition d’un verrou a un impact très variable sur la latence d’une application, (v) aucun verrou n’est systématiquement le meilleur, (vi) choisir le meilleur verrou est difficile, et (vii) l’efficacité énergétique et le débit vont de pair dans le contexte des algorithmes d’exclusion mutuelle.
Ces découvertes mettent en avant le fait que la synchronisation à base de verrou ne se résume pas seulement à la simple interface “lock – unlock”. En conséquence, ces résultats appellent à plus de recherche dans le but de concevoir des algorithmes d’exclusion mutuelle avec une empreinte mémoire faible, adaptatifs et qui implémentent l’ensemble des primitives de synchronisation liées à l’exclusion mutuelle. De plus, ces algorithmes ne doivent pas seulement avoir de bonnes performances d’un point de vue du débit, mais aussi considérer la latence ainsi que l’efficacité énergétique.