Understanding the performance of mutual exclusion algorithms on modern multicore machines

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 multicœurs 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.A plethora of optimized mutual exclusion lock algorithms have been designed over the past 25 years to mitigate performance bottlenecks related to critical sections and synchronization.Unfortunately, there is currently no broad study of the behavior of these optimized lock algorithms on realistic applications that consider different performance metrics, such as energy efficiency and tail latency.In this thesis, we perform a thorough and practical analysis, with the goal of providing software developers with enough information to achieve fast, scalable and energy-efficient synchronization in their systems.First, we provide a performance study of 28 state-of-the-art mutex lock algorithms, on 40 applications, and four different multicore machines.We not only consider throughput (traditionally the main performance metric), but also energy efficiency and tail latency, which are becoming increasingly important.Second, we present an in-depth analysis in which we summarize our findings for all the studied applications.In particular, we describe nine different lock-related performance bottlenecks, and propose six guidelines helping software developers with their choice of a lock algorithm according to the different lock properties and the application characteristics.From our detailed analysis, we make a number of observations regarding locking algorithms and application behaviors, several of which have not been previously discovered:(i) applications not only stress the lock/unlock interface, but also the full locking API (e.g., trylocks, condition variables),(ii) the memory footprint of a lock can directly affect the application performance,(iii) for many applications, the interaction between locks and scheduling is an important application performance factor,(iv) lock tail latencies may or may not affect application tail latency,(v) no single lock is systematically the best,(vi) choosing the best lock is difficult (as it depends on many factors such as the workload and the machine), and(vii) energy efficiency and throughput go hand in hand in the context of lock algorithms.These findings highlight that locking involves more considerations than the simple "lock - unlock" interface and call for further research on designing low-memory footprint adaptive locks that fully and efficiently support the full lock interface, and consider all performance metrics