Contribution à l’élaboration d’ordonnanceurs de processus légers performants et portables pour architectures multiprocesseurs

Les ordonnanceurs

L’ordonnanceur est le cœur de toute bibliothèque de processus légers. Il est responsable des décisions d’ordonnancement, c’est-à-dire du choix du processus léger applicatif à exécuter dans chacun des LWP disponibles. L’interface de l’ordonnanceur possède peu de primitives : le processus léger peut changer son état (prêt/bloqué/mort), passer la main ou encore réveiller un processus léger endormi. L’interface est suffisamment souple pour ne pas imposer un type précis d’ordonnanceur. Notre expérience des versions précédentes de MARCEL (ordonnanceur en O(1) mono- ou multifile) ainsi que l’étude approfondie des ordonnanceurs du noyau LINUX (file unique comme pour les anciens noyaux LINUX, multifile en O(1) des noyaux 2.6, avec gestion de domaines[Cor04] en cours de développement, etc.) nous a convaincus que cette interface est adaptée à de nombreux types d’ordonnanceurs.

L’ordonnanceur par défaut

La bibliothèque MARCEL est fournie avec un ordonnanceur générique qui possède une file globale, des files spécifiques aux LWP et deux niveaux de priorités. Par défaut, les processus légers ont la priorité standard et sont rangés dans la file globale. L’application peut modifier ce comportement via une primitive de changement de priorité ou par l’utilisation d’attributs spéciaux à la création des processus légers. Aucun équilibrage de charge automatique n’est fait entre les files spécifiques aux LWP. Il est assez simple de rajouter des niveaux de priorité et/ou des files supplémentaires attachées, par exemple, à un sous-groupe de processeurs. La distinction entre file unique et file spécifique à un (ou quelques) LWP prend toute son importance dès que la machine possède plusieurs processeurs. En cas de file unique, on pourra observer une forte contention au niveau du verrou de protection de la file ; cette contention est en particulier observable sous le noyau LINUX jusque dans ses versions 2.4.x. En revanche, si chaque LWP a sa propre file, les possibilités de contention se limitent aux insertions (resp. retraits) des processus légers réveillés (resp. endormis), mais il devient alors nécessaire d’assurer l’équilibrage de la charge sur les différentes files.

D’autres ordonnanceurs

L’interface entre l’ordonnanceur et le reste de notre bibliothèque est assez réduite et permet donc son remplacement relativement facilement. Il est malgré tout très important de remarquer que l’ordonnanceur n’est pas lui-même une entité indépendante vis-à-vis de l’exécution du reste du programme. Les décisions d’ordonnancement sont prises individuellement par chaque LWP. En particulier, il n’y a rien, a priori, qui permette à un LWP donné d’ordonnancer à cet instant un ensemble de processus légers sur un ensemble de LWP. Les décisions d’ordonnancement sont prises de manière décentralisée. Les LWP peuvent juste choisir le processus léger à ordonnancer en leur sein et éventuellement positionner des variables que les autres LWP consulteront et prendront en compte lorsqu’ils se rendront, eux aussi, à un point d’ordonnancement. Bien que facilitées par la présence d’une interface concise, la création et la mise au point d’un nouvel ordonnanceur restent complexes. En effet, les mécanismes de protection et de synchronisation sont délicats à mettre en œuvre correctement, en particulier si l’on désire éviter une importante contention comme celle provoquée par un verrou global protégeant l’ensemble des données d’un ordonnanceur. Une piste de recherche intéressante paraît être de développer des ordonnanceurs directement paramétrables par l’application. On demande alors directement à l’application ses critères d’élection du processus à ordonnancer. Ou encore, on développe des interfaces plus abstraites, afin que l’application transmette à 60 

UNE BIBLIOTHÈQUE DE PROCESSUS LÉGERS UNIVERSELLE

Ici, les processus légers sont structurés par l’application au moyen de bulles, éventuellement imbriquées. De plus, ces bulles possèdent des propriétés d’ordonnancement relatives à la façon d’ordonnancer ou de répartir les entités (sous-bulles ou processus légers) qui les composent, par exemple : – les entités ont peu de dépendances entre elles, donc elles s’exécutent parfaitement en parallèle ; – les entités travaillent sur des données communes, donc il faudrait les placer sur des processeurs assez proches vis-à-vis de la hiérarchie mémoire. Parallèlement à ces bulles, l’ordonnanceur fournit un ensemble de files d’ordonnancement correspondant à chaque hiérarchie de processeur. Ainsi, pour une machine biprocesseur hyperthreadée, l’ordonnanceur définit 1 + 2 + 4 = 7 files : – une pour les travaux pouvant s’exécuter sur n’importe quelle unité de calcul ; – deux pour chacun des deux processeurs. Un travail dans une telle file s’exécutera nécessairement sur le processeur correspondant ; – quatre pour chacune des quatre unités de calcul (deux threads par processeur). Là encore, un travail placé dans une telle file s’exécutera uniquement dans l’unité de calcul correspondante. Le programme peut alors diriger l’ordonnancement en exprimant comment l’ordonnanceur doit essayer de répartir les entités d’une bulle lorsqu’il ordonnance celle-ci. On peut descendre ou non dans la hiérarchie des files, ce qui localise ou non les travaux. On peut également rassembler les travaux sur une même file ou, au contraire, les disperser sur des files différentes, ce qui permet de favoriser le parallélisme ou bien la localité lors de l’exécution des travaux. Les personnalités Chacun reconnaît le rôle fondamental de l’interface d’une bibliothèque. Toutefois, cette notion recouvre différents aspects. Il convient, de fait, de distinguer deux sortes d’interfaces : l’interface binaire, également nommée ABI pour Application Binary Interface. Il s’agit de l’interface entre bibliothèques et programmes déjà compilés. Cette interface définit les conventions d’appels de fonction (au niveau du code machine), la liste des symboles (fonctions et variables) disponibles dans une bibliothèque, la composition des objets manipulés (taille et placement des champs des structures de données partagées), etc. ; l’interface de programmation, également nommée API pour Application Programming Interface. Il s’agit de l’interface au niveau du langage de programmation. Elle définit les noms des objets9 que le programmeur peut utiliser dans son code sans avoir à se soucier de l’implémentation interne de ces objets : il peut être amené à manipuler une structure de données sans connaître l’organisation interne de cette structure ni même sa taille. Nous verrons ci-dessous que notre bibliothèque sera amenée à proposer plusieurs interfaces différentes aux programmes. Pour pouvoir les distinguer facilement, nous avons nommé personnalité toute interface de notre bibliothèque permettant de manipuler les processus légers. Voyons maintenant pourquoi plusieurs personnalités se sont révélées nécessaires. 4.2.4.1 Fonctionnalités L’interface de programmation proposée par le standard POSIX est incontournable car utilisée de nos jours par la majorité des applications et bibliothèques manipulant des proces8http://www.emn.fr/x-info/bossa/ 9 Il s’agit ici des objets au sens large (fonction, variable, macro, type, structure, etc.) et non pas des objets des « langages objets ».  sus légers. Toutefois, notre bibliothèque utilise dans certaines configurations la bibliothèque de processus légers du système pour gérer ses LWP. Employant les symboles définis par le standard POSIX, elle ne peut pas les offrir elle-même aux applications. C’est pourquoi MARCEL propose une première personnalité, nommée POSIX source qui est identique à celle définie par la norme POSIX au préfixe près : le préfixe pmarcel_ remplace le préfixe pthread_ des fonctions, types, etc. Cela permet ainsi un portage rapide des programmes et bibliothèques sur MARCEL. Cependant, l’interface POSIX n’est pas suffisamment riche. Aussi, pour profiter des fonctionnalités supplémentaires offertes par la bibliothèque MARCEL, un programme ou une bibliothèque devra utiliser une interface étendue. Ces fonctions sont préfixées par marcel_. Outre les nouvelles fonctionnalités, elles reprennent également les fonctions de la norme POSIX, mais en les optimisant. Cette optimisation, lorsqu’elle est possible, peut prendre plusieurs formes dont l’utilisation de code en ligne (inline) qui évite un appel de fonction, ou encore l’abandon de spécificités de la norme POSIX rarement employées. Par exemple, pour les verrous (mutex), seul le type standard est implémenté pour la version marcel_ alors que la version pmarcel_ supporte aussi les verrous récursifs ou ceux avec vérification d’erreur. L’ensemble de ces fonctions définit la personnalité Marcel ; celle-ci est la personnalité la plus écartée de la norme mais, en contrepartie, elle offre des optimisations et des fonctionnalités supplémentaires. 

Compatibilité et réentrance

L’utilisation de bibliothèques externes peut provoquer des problèmes de réentrance vis-à-vis des processus légers. Plusieurs cas peuvent se présenter : 1. la bibliothèque n’utilise aucune donnée de classe de stockage globale, elle fonctionne très bien en environnement multithreadé sans aucune modification ; 2. la bibliothèque utilise des données globales mais rien n’a été prévu pour son utilisation en environnement multithreadé ; 3. la bibliothèque utilise des données globales mais protège ses structures grâce aux primitives de synchronisation de processus légers de la norme POSIX. De nos jours, la plupart des bibliothèques correspondent aux cas 1 ou 3. Mais quelques unes n’ont pas été modifiées pour supporter le multithreading. C’est le cas de la bibliothèque de communication bas niveau GM pour les réseaux MYRINET. Le cas 1 ne pose pas de problème. Pour utiliser une bibliothèque non protégée (cas 2), un programme multithreadé utilisant MARCEL ou la bibliothèque du système devra protéger lui-même ses accès à la bibliothèque en question en s’interdisant, par exemple grâce à un verrou, de lui faire deux appels simultanés. Le cas 3 est plus problématique : puisque MARCEL gère lui-même les processus légers utilisateur, le système ne les connaît pas. Et lorsque la bibliothèque demande au système de protéger les accès à ses variables globales, le système n’est d’aucune aide puisque, de son point de vue, il n’y a qu’un seul flot d’exécution. Trois approches sont alors possibles pour gérer cette situation : recompiler la bibliothèque en lui faisant utiliser les primitives MARCEL plutôt que celles du système. Cela résout les problèmes ; la bibliothèque peut même utiliser les primitives optimisées de MARCEL. Par contre, cela nécessite le code source de la bibliothèque..