<html><head><META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>2. Linux sur SMP</title><link href="style.css" rel="stylesheet" type="text/css"><meta content="DocBook XSL Stylesheets V1.68.1" name="generator"><link rel="start" href="index.html" title="Le traitement en parallèle sous Linux"><link rel="up" href="index.html" title="Le traitement en parallèle sous Linux"><link rel="prev" href="ar01s01.html" title="1. Introduction"><link rel="next" href="ar01s03.html" title="3. Clusters de systèmes Linux"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table summary="Navigation header" width="100%"><tr><th align="center" colspan="3">2. Linux sur SMP</th></tr><tr><td align="left" width="20%"><a accesskey="p" href="ar01s01.html">Précédent</a> </td><th align="center" width="60%"> </th><td align="right" width="20%"> <a accesskey="n" href="ar01s03.html">Suivant</a></td></tr></table><hr></div><div class="sect1" lang="fr"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="N102AE"></a>2. Linux sur SMP</h2></div></div></div><p>
Ce document donne un bref aperçu de la manière dont on utilise <a href="http://www.linux.org.uk/SMP/title.html" target="_top">le SMP sous Linux</a>
pour le traitement en parallèle. L'information la plus à jour concernant
le SMP sous Linux est fort probablement disponible via la liste de
diffusion du SMP Linux Project (N.D.T. : en anglais). Envoyez un
courrier électronique à
<code class="email"><<a href="mailto:majordomo CHEZ vger POINT rutgers POINT edu">majordomo CHEZ vger POINT rutgers POINT edu</a>></code>
avec le texte <code class="literal">subscribe linux-smp</code> pour rejoindre la
liste.
</p><p>
Le SMP sous Linux fonctionne-t-il vraiment ? En juin 1996, j'ai
fait l'achat d'un bi-Pentium 100MHz flambant neuf. Le système complet et
assemblé, comprenant les deux processeurs, la carte-mère Asus, 256
kilo-octets de mémoire cache, 32 méga-octets de RAM, le disque dur d'1.6
giga-octet, le lecteur de CD-ROM 6X, une carte Stealth 64 et un moniteur
15'' Acer m'a coûté 1800 dollars. Cela ne fait que quelques centaines de
dollars de plus qu'un système monoprocesseur. Pour faire fonctionner le
SMP sous Linux, il a suffi d'installer le Linux monoprocesseur
d'origine, de recompiler le noyau en décommentant la ligne
<code class="literal">SMP=1</code> dans le <span class="emphasis"><em>Makefile</em></span> (bien que
je trouve le fait de mettre <code class="literal">SMP</code> à
<code class="literal">1</code> un peu ironique ! ;-) ), et d'informer
<code class="literal">lilo</code> de l'existence du nouveau noyau. Ce système
présente une stabilité et des performances suffisamment bonnes pour
qu'il me serve depuis de station de travail principale. Pour résumer, le
SMP sous Linux, ça fonctionne !
</p><p>
La question qui se présente alors est : existe-t-il suffisamment
d'API de haut niveau permettant d'écrire et d'exécuter des programmes en
parallèle et utilisant la mémoire partagée sous Linux SMP ? Courant
1996, il n'y en avait pas beaucoup. Les choses ont changé. Par exemple,
il existe désormais une bibliothèque POSIX de gestion des
<span class="foreignphrase"><em class="foreignphrase">threads</em></span><sup>[<a href="#ftn.N102D7" name="N102D7">2</a>]</sup> très complète.
</p><p>
Bien que les performances soient moins élevées que celles des mécanismes
de mémoire partagée natifs, un système Linux sur SMP peut aussi utiliser
la plupart des logiciels de traitement en parallèle initialement
développés pour des <span class="foreignphrase"><em class="foreignphrase">clusters</em></span> de stations
de travail en utilisant la communication par
<span class="foreignphrase"><em class="foreignphrase">socket</em></span>. Les <span class="emphasis"><em>sockets</em></span>
(voir section 3.3) fonctionnent à l'intérieur d'une machine en SMP, et
même dans un <span class="foreignphrase"><em class="foreignphrase">cluster</em></span> de machines SMP
reliées en réseau. Cependant, les <span class="foreignphrase"><em class="foreignphrase">sockets</em></span>
engendrent beaucoup de pertes en temps inutiles pour du SMP. Cela
complique le problème car Linux SMP n'autorise en général qu'un seul
processeur à la fois à se trouver dans le noyau et le contrôleur
d'interruption est réglé de façon à ce que seul le processeur de
<span class="foreignphrase"><em class="foreignphrase">boot</em></span><sup>[<a href="#ftn.N102EE" name="N102EE">3</a>]</sup> puisse traiter les interruptions. En dépit de cela,
l'électronique de communication typique des systèmes SMP est tellement
meilleure que la plupart des <span class="foreignphrase"><em class="foreignphrase">clusters</em></span> en
réseau que les logiciels pour <span class="foreignphrase"><em class="foreignphrase">cluster</em></span>
fonctionneront souvent mieux sur du SMP que sur le
<span class="foreignphrase"><em class="foreignphrase">cluster</em></span> pour lequel ils ont été conçus.
</p><p>
Le reste de cette section traite de l'électronique contrôlant le SMP,
passe en revue les mécanismes Linux de base partageant de la mémoire
à travers les différents processus d'un programme en parallèle, fait
quelques remarques concernant l'atomicité, la volatilité, les verrous
et les lignes de cache, et donne enfin des références vers d'autres
ressources de traitement en parallèle à mémoire partagée.
</p><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N102FD"></a>2.1. L'électronique SMP</h3></div></div></div><p>
Bien que les systèmes SMP soit répandus depuis de nombreuses années,
jusque très récemment, chaque machine tendait à implémenter les
fonctions de base d'une manière suffisamment différente des autres pour
que leur gestion par le système d'exploitation ne soit pas portable. Les
choses ont changé avec la <span class="foreignphrase"><em class="foreignphrase">Intel's MultiProcessor
Specification</em></span> (Spécification MultiProcesseurs d'Intel)
souvent désignée par <span class="emphasis"><em>MPS</em></span>. La spécification MPS 1.4
est actuellement disponible sous forme de document PDF sur <a href="http://www.intel.com/design/intarch/MANUALS/242016.htm" target="_top">http://www.intel.com/design/intarch/MANUALS/242016.htm</a><sup>[<a href="#ftn.N1030A" name="N1030A">4</a>]</sup>,
mais gardez à l'esprit qu'Intel réorganise souvent son site web. Un large
panel de constructeurs fabrique des systèmes conformes à MPS pouvant
recevoir jusqu'à quatre processeurs, mais en théorie, MPS admet bien
plus de processeurs.
</p><p>
Les seuls systèmes non MPS et non IA32 reconnus par Linux SMP sont les
machines SPARC multiprocesseurs de Sun4m. Linux SMP prend aussi en
charge la plupart des machines Intel conformes à MPS 1.1 ou 1.4,
comptant jusqu'à 16 processeurs 486DX, Pentium, Pentium MMX, Pentium Pro
ou Pentium II. Parmi les processeurs IA32 non pris en charge (N.D.T. :
par le SMP), on trouve les Intel 386 et 486SX/SLC (l'absence de
coprocesseur mathématique interfère sur les mécanismes du SMP) et les
processeurs AMD et Cyrix (qui nécessitent des circuits de gestion du SMP
différents et qui ne semblent pas être disponibles à l'heure où ce
document est écrit).
</p><p>
Il est important de bien comprendre que les performances de différents
systèmes conformes à MPS peuvent fortement varier. Comme l'on peut s'y
attendre, une des causes de différence de performance est la vitesse
du processeur : Une horloge plus rapide tend à rendre les systèmes plus
rapides, et un processeur Pentium Pro est plus rapide qu'un Pentium.
En revanche, MPS ne spécifie pas vraiment comment le matériel doit
mettre en œuvre la mémoire partagée, mais seulement comment cette
implémentation doit fonctionner d'un point de vue logiciel. Cela
signifie que les performances dépendent aussi de la façon dont
l'implémentation de la mémoire partagée interagit avec les caractéristiques
de Linux SMP et de vos applications en particulier.
</p><p>
La principale différence entre les systèmes conformes à MPS réside
dans la manière dont ils implémentent l'accès à la mémoire physiquement
partagée.
</p><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N10317"></a>2.1.1. Chaque processeur possède-t-il sa propre mémoire cache de niveau 2 (L2) ?</h4></div></div></div><p>
Certains systèmes MPS à base de Pentium, et tous les systèmes MPS
Pentium Pro et Pentium II ont des mémoires cache L2 indépendantes
(le cache L2 est embarqué dans le module des Pentium Pro et Pentium II).
Les mémoires caches L2 dissociées sont généralement réputées augmenter
les performances de l'ordinateur, mais les choses ne sont pas si évidentes
sous Linux. La principale complication provient du fait que l'ordonnanceur
de Linux SMP n'essaie pas de maintenir chaque processus sur
le même processeur, concept connu sous le nom d'<span class="emphasis"><em>affinité processeur</em></span>.
Cela pourrait bientôt changer. Un débat a récemment eu lieu sur ce sujet dans la
communauté des développeurs Linux SMP, sous le titre « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">processor
bindings</em></span></span> » (« <span class="quote">associations de processeurs</span> »). Sans affinité processeur,
des caches L2 séparés peuvent introduire des délais non négligeables
lorsqu'un processus se voit allouer une tranche de temps d'exécution
sur un processeur qui n'est pas le même que celui sur lequel il
s'exécutait juste avant.
</p><p>
Plusieurs systèmes relativement bon marché sont organisés de manière
à ce que deux processeurs Pentium puissent partager la même mémoire
cache L2. La mauvaise nouvelle, c'est que cela crée des conflits à
l'utilisation de ce cache, qui dégradent sérieusement les performances
lorsque plusieurs programmes séquentiels indépendants s'exécutent
simultanément. La bonne nouvelle, c'est que bon nombre de programmes
parallèles pourraient tirer profit de la mémoire cache partagée, car
si les deux processeurs veulent accéder à la même ligne de mémoire
partagée, seul un processeur doit aller la rapatrier dans le cache,
et l'on évite des conflits de bus. Le manque d'affinité processeur
peut aussi s'avérer moins désastreux avec un cache L2 partagé. Ainsi,
pour les programmes parallèles, il n'est pas vraiment certain que
partager la mémoire cache L2 soit si préjudiciable que l'on pourrait
le penser.
</p><p>
À l'usage, notre bi-Pentium à mémoire cache partagée
de 256Ko présente une vaste échelle de performances, dépendantes du
niveau d'activité noyau requis. Au pire, le gain en vitesse
n'atteint qu'un facteur de 1,2. En revanche, nous avons aussi
constaté une accélération de 2,1 fois la vitesse d'origine, ce qui
suggère que les calculs intensifs à base de SPMD tirent vraiment
profit de l'effet d'« <span class="quote">acquisition partagée</span> » (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">shared fetch</em></span></span> »).
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N10331"></a>2.1.2. Configuration du bus ?</h4></div></div></div><p>
La première chose à dire est que la plupart des systèmes modernes
relient le processeur à un ou plusieurs bus PCI qui à leur tour
sont « <span class="quote">pontés</span> » vers un ou plusieurs bus ISA ou EISA. Ces ponts
engendrent des temps de latence, et l'ISA comme l'EISA offrent
généralement des bandes passantes plus réduites que le PCI
(ISA étant le plus lent). C'est pourquoi les disques, cartes vidéos et
autres périphériques de haute performance devraient en principe
être connectés sur un bus PCI.
</p><p>
Bien qu'un système MPS puisse apporter un gain en vitesse honorable
à plusieurs programmes parallèles de calcul intensif même avec un
seul bus PCI, les opérations d'entrées/sorties, elles, ne sont pas
meilleures que sur un système monoprocesseur. Elles sont peut-être même
un peu moins bonnes à cause des conflits de bus entre les processeurs.
Ainsi, si votre objectif est d'accélérer les entrées/sorties, prenez
soin de choisir un système MPS comportant plusieurs bus PCI indépendants
et plusieurs contrôleurs d'entrées/sorties (par exemple : plusieurs
chaînes SCSI). Il vous faudra être prudent, et sûr que Linux
reconnaît tout votre matériel. Gardez aussi à l'esprit le fait que
Linux n'autorise qu'un seul processeur à la fois à entrer en mode
noyau, aussi devrez-vous choisir des contrôleurs qui réduisent au
minimum le temps noyau nécessaire à leurs opérations. Pour atteindre
des performances vraiment très élevées, il se pourrait même qu'il
vous faille envisager d'effectuer vous-même les opérations d'entrée/sortie
de bas niveau directement depuis les processus utilisateurs,
sans appel système… ce n'est pas forcément aussi difficile que
cela en a l'air, et cela permet d'éviter de compromettre la sécurité du
système (voir la section 3.3 pour une description des techniques de
base).
</p><p>
Il est important de remarquer que la relation entre vitesse du bus
et vitesse du processeur est devenue très floue ces dernières années.
Bien que la plupart des systèmes utilisent maintenant la même fréquence
de bus PCI, il n'est pas rare de trouver un processeur rapide apparié
avec un bus lent. L'exemple classique est celui du Pentium 133 qui
utilise en général un bus plus rapide que celui du Pentium 150, produisant
des résultats étranges sur les logiciels bancs de tests (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">benchmarks</em></span></span> »).
Ces effets sont amplifiés sur les systèmes SMP, où il est encore plus
important d'utiliser un bus rapide.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N10341"></a>2.1.3. Interfoliage de la mémoire et technologie DRAM</h4></div></div></div><p>
L'interfoliage de la mémoire n'a en fait absolument rien à voir
avec le MPS, mais vous verrez souvent cette mention accompagner
les systèmes MPS car ceux-ci sont typiquement gourmands en
bande passante mémoire. Concrètement, l'interfoliage en deux ou
en quatre voies organise la RAM de façon à ce que l'accès à un
bloc de mémoire se fasse au travers de plusieurs bancs de RAM
plutôt qu'un seul. Ceci accélère grandement les accès à la
mémoire, particulièrement en ce qui concerne le chargement et
l'enregistrement du contenu des lignes de cache.
</p><p>
Il faut toutefois souligner que ce fait n'est pas aussi évident
qu'il y parait, car la DRAM EDO et les différentes technologies
mémoire tendent à optimiser ce genre d'opérations. Un excellent
aperçu des différentes technologies DRAM est disponible sur
<a href="http://www.pcguide.com/ref/ram/tech.htm" target="_top">http://www.pcguide.com/ref/ram/tech.htm</a>.
</p><p>
Ainsi, par exemple, mieux vaut-il avoir de la mémoire DRAM EDO
interfoliée à 2 voies, ou de la mémoire SDRAM non interfoliée ?
C'est une très bonne question et la réponse n'est pas simple,
car la mémoire interfoliée comme les technologies DRAM exotiques
ont tendance à être coûteuses. Le même investissement en mémoire
plus ordinaire vous apporte en général une mémoire centrale bien
plus vaste. Même la plus lente des mémoire DRAM reste autrement
plus rapide que la mémoire virtuelle par fichier d'échange…
</p></div></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1034E"></a>2.2. Introduction à la programmation en mémoire partagée</h3></div></div></div><p>
<span class="foreignphrase"><em class="foreignphrase">Okay</em></span>, donc vous avez décidé que le traitement
en parallèle sur SMP, c'est génial… Par quoi allez-vous commencer ? Eh bien,
la première étape consiste à en apprendre un peu plus sur le fonctionnement réel
de la communication par mémoire partagée.
</p><p>
A première vue, il suffit qu'un processeur range une valeur en mémoire
et qu'un autre la lise. Malheureusement, ce n'est pas aussi simple.
Par exemple, les relations entre processus et processeurs sont très
floues. En revanche, si nous n'avons pas plus de processus actifs que
de processeurs, les termes sont à peu près interchangeables. Le reste
de cette section résume brièvement les cas de figure typiques qui
peuvent poser de sérieux problèmes, si vous ne les connaissiez pas
déjà : les deux différents modèles utilisés pour déterminer ce qui
est partagé, les problèmes d'atomicité, le concept de volatilité,
les instructions de verrouillage matériel, les effets de la ligne
de cache, et les problèmes posés par l'ordonnanceur de
Linux.
</p><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N10358"></a>2.2.1. Partage Intégral contre Partage Partiel</h4></div></div></div><p>
Il existe deux modèles fondamentaux couramment utilisés en programmation
en mémoire partagée : le <span class="emphasis"><em>partage intégral</em></span>
et le <span class="emphasis"><em>partage partiel</em></span>. Ces modèles
permettent tous deux aux processeurs de communiquer en chargeant et
rangeant des données depuis et dans la mémoire. La différence réside
dans le fait que le partage intégral place toutes les structures en
mémoire partagée, quand le partage partiel, lui, distingue les structures
qui sont potentiellement partageables et celles qui sont
<span class="emphasis"><em>privées</em></span>, propres à un seul processeur
(et oblige l'utilisateur à classer explicitement ses structures dans l'une
de ces catégories).
</p><p>
Alors quel modèle de partage mémoire faut-il utiliser ? C'est surtout
une affaire de chapelle. Beaucoup de gens aiment le partage intégral
car ils n'ont pas spécialement besoin d'identifier les structures qui
doivent être partagées au moment de leur déclaration. On place simplement
des verrous sur les objets auxquels l'accès peut créer des conflits, pour
s'assurer qu'un seul processeur (ou processus) y accède à un moment donné.
Mais là encore, ce n'est pas aussi simple… aussi beaucoup d'autres
gens préfèrent, eux, le modèle relativement sûr du partage partiel.
</p><div class="sect4" lang="fr"><div class="titlepage"><div><div><h5 class="title"><a name="N10368"></a>2.2.1.1. Partage intégral</h5></div></div></div><p>
Le bon coté du partage intégral est que l'on peut aisément reprendre
un programme séquentiel existant et le convertir progressivement en
programme parallèle en partage intégral. Vous n'avez pas à déterminer
au préalable les données qui doivent être accessibles aux autres
processeurs.
</p><p>
Posé simplement, le principal problème avec le partage intégral vient
du fait qu'une action effectuée par un processeur peut affecter les
autres processeurs. Ce problème ressurgit de deux manières :
</p><p>
<div class="itemizedlist"><ul type="disc"><li><p>
Plusieurs bibliothèques utilisent des structures de données qui
ne sont tout simplement pas partageables. Par exemple, la convention
UNIX stipule que la plupart des fonctions peuvent renvoyer un code
d'erreur dans une variable appelée <code class="literal">errno</code>.
Si deux processus en partage intégral font des appels divers, ils vont
interférer l'un sur l'autre car ils partagent la même variable
<code class="literal">errno</code>. Bien qu'il existe désormais une
bibliothèque qui règle le problème de cette variable, ce problème se présente toujours
dans la plupart des bibliothèques comme par exemple X-Window qui, à moins de prendre
des précautions très spéciales, ne fonctionnera pas si différents appels sont
passés depuis différents processus en partage intégral.
</p></li><li><p>
En temps normal, un programme qui utilise un pointeur ou un index
défaillant provoque au pire l'arrêt du processus qui contient le code corrompu.
Il peut même générer un fichier <code class="literal">core</code> vous renseignant sur les conditions
dans lesquelles se sont déroulés les événements. En programmation parallèle
à partage intégral, il est fort probable que les accès illégaux provoquent
la <span class="emphasis"><em>fin d'un processus qui n'est pas le fautif</em></span>, rendant
la localisation et la correction de l'erreur quasiment impossibles.
</p></li></ul></div>
</p><p>
Aucun de ces deux problèmes n'est courant dans le cas du partage
partiel, car seules sont partagées les structures explicitement marquées
comme telles. De plus, il est trivial que le partage intégral ne peut
fonctionner que si les processeurs exécutent exactement la même image
en mémoire. On ne peut pas utiliser le partage intégral entre des images
de code différentes (c'est-à-dire que vous pourrez travailler en SPMD,
mais pas d'une manière générale en MIMD).
</p><p>
Les supports de programmation en partage intégral existent le plus
couramment sous la forme de <span class="emphasis"><em>bibliothèques de
<span class="foreignphrase"><em class="foreignphrase">threads</em></span></em></span>. Les <a href="http://liinwww.ira.uka.de/bibliography/Os/threads.html" target="_top"><span class="foreignphrase"><em class="foreignphrase">threads</em></span></a>
sont essentiellement des processus « <span class="quote">allégés</span> » dont
l'exécution peut ne pas être planifiée comme celle des processus UNIX
normaux et qui, c'est le plus important, partagent tous la même page
mémoire. L'adaptation des <a href="http://www.mit.edu:8001/people/proven/IAP_2000/index.html" target="_top">Pthreads</a>
POSIX a fait l'objet de nombreux efforts. La grande question est :
ces adaptations parallélisent-elles les
<span class="foreignphrase"><em class="foreignphrase">threads</em></span> d'un programme en environnement
Linux SMP (idéalement, en attribuant un processeur à chaque
<span class="foreignphrase"><em class="foreignphrase">thread</em></span>) ?. L'API POSIX ne l'impose
pas, et certaines versions comme <span class="emphasis"><em>PCthreads</em></span> semblent
ne pas implémenter une exécution en parallèle des
<span class="foreignphrase"><em class="foreignphrase">threads</em></span> : tous les
<span class="foreignphrase"><em class="foreignphrase">threads</em></span> d'un programme sont conservés à
l'intérieur d'un seul processus Linux.
</p><p>
La première bibliothèque de <span class="foreignphrase"><em class="foreignphrase">threads</em></span> à avoir pris en charge le parallélisme
sous Linux SMP fut la désormais quelque peu obsolète bibliothèque
<span class="emphasis"><em>bb_thread</em></span>, une toute petite bibliothèque qui utilisait l'appel Linux
<code class="literal">clone()</code> pour donner naissance à de nouveaux
processus Linux, planifiés indépendamment les uns des autres, tous partageant
un même espace d'adressage. Les machines Linux SMP peuvent lancer plusieurs
de ces « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">threads</em></span></span> » car chaque « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">thread</em></span></span> » est un processus Linux à part entière.
L'inconvénient, c'est que l'on ne peut obtenir l'ordonnancement « <span class="quote">poids-plume</span> »
apportée par les bibliothèques de <span class="foreignphrase"><em class="foreignphrase">threads</em></span> d'autres systèmes
d'exploitation. La bibliothèque utilisait un peu de code assembleur intégré
dans un code source en langage C pour mettre en place un bloc de mémoire pour la
pile de chaque <span class="foreignphrase"><em class="foreignphrase">thread</em></span> et fournir des fonctions d'accès atomiques à un tableau
de verrous (les <span class="emphasis"><em>mutex</em></span>). Sa documentation se résumait à un fichier
<code class="literal">LISEZMOI</code> et à un court programme d'exemple.
</p><p>
Plus récemment, une version de <span class="foreignphrase"><em class="foreignphrase">threads</em></span> POSIX utilisant <code class="literal">clone()</code>
a été développée. Cette bibliothèque,
<a href="http://pauillac.inria.fr/~xleroy/linuxthreads/" target="_top">LinuxThreads</a>,
est clairement la bibliothèque en partage intégral favorite pour l'utilisation
sous Linux SMP. Les <span class="foreignphrase"><em class="foreignphrase">threads</em></span> POSIX sont bien documentés, et les documents
<a href="http://pauillac.inria.fr/~xleroy/linuxthreads/README" target="_top">LinuxThreads README</a>
et <a href="http://pauillac.inria.fr/~xleroy/linuxthreads/faq.html" target="_top">LinuxThreads FAQ</a>
sont vraiment très bien réalisés. A présent, le principal problème est
que les <span class="foreignphrase"><em class="foreignphrase">threads</em></span> POSIX ont encore beaucoup de détails à régler, et que
LinuxThread est toujours un projet en cours d'évolution. D'autre part,
les <span class="foreignphrase"><em class="foreignphrase">threads</em></span> POSIX ont évolué pendant dans leur phase de standardisation,
aussi devrez-vous être prudent pour ne pas développer en suivant une version obsolète du standard.
</p></div><div class="sect4" lang="fr"><div class="titlepage"><div><div><h5 class="title"><a name="N103EE"></a>2.2.1.2. Partage Partiel</h5></div></div></div><p>
Le Partage Partiel consiste réellement à « <span class="quote">ne partager que ce qui
doit être partagé</span> ». Cette approche est valable pour le MIMD en
général (et pas simplement le SPMD) à condition de prendre soin
d'allouer les objets partagés aux mêmes endroits dans le plan mémoire de
chaque processeur. Plus important encore, le partage partiel facilite
l'estimation et l'ajustage des performances, le débogage des sources, et
cætera. Les seuls problèmes sont :
</p><p>
<div class="itemizedlist"><ul type="disc"><li><p>
Déterminer à l'avance ce qui doit être partagé peut s'avérer difficile.
</p></li><li><p>
L'allocation d'objets dans la mémoire partagée peut en fait se révéler
malaisé, spécialement en ce qui concerne tout ce qui aurait du être déclaré
dans la pile. Par exemple, il peut être nécessaire d'allouer explicitement
des objets partagés dans des segments de mémoire séparés, nécessitant des
routines d'allocation mémoire séparées, et impliquant l'ajout de pointeurs
et d'indirections supplémentaires à chaque référence.
</p></li></ul></div>
</p><p>
Actuellement, il existe deux mécanismes similaires permettant aux
groupes de processus sous Linux de posséder des espaces mémoire
indépendants, mais de tous partager un unique et relativement étroit
segment de mémoire. En supposant que vous n'ayez pas bêtement exclu
l'option « <span class="quote">System V IPC</span> » lorsque que vous avez configuré
votre système Linux (N.D.T. : ici à la recompilation du noyau), Linux
gère un mécanisme très portable devenu célèbre sous le nom de
« <span class="quote">mémoire partagée System V</span> ». L'autre alternative est une
fonction de projection en mémoire dont l'implémentation varie grandement
selon le système UNIX utilisé : L'appel système
<code class="literal">mmap</code>. Vous pouvez — et devriez —
apprendre le fonctionnement de ces primitives au travers des pages du
manuel (<span class="foreignphrase"><em class="foreignphrase">man pages</em></span>)… mais vous
trouverez quand même un rapide aperçu de chacune d'elles dans les
sections 2.5 et 2.6 pour vous aider à démarrer.
</p></div></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N1040F"></a>2.2.2. Atomicité et ordonnancement</h4></div></div></div><p>
Que vous utilisiez l'un ou l'autre des modèles cités ci-dessus, le
résultat est à peu près le même : vous obtenez un pointeur sur un bloc de
mémoire en lecture/écriture accessible par tous les processus de votre
programme en parallèle. Cela signifie-t-il que je peux laisser mes
programmes accéder aux objets partagés comme s'ils se trouvaient en
mémoire locale ordinaire ? Pas tout à fait…
</p><p>
L'<span class="emphasis"><em>atomicité</em></span> désigne une opération sur
un objet effectuée en une séquence indivisible et ininterruptible.
Malheureusement, les accès à la mémoire partagée n'impliquent pas que
les toutes les opérations sur les données de cette mémoire se fassent
de manière atomique. A moins de prendre des précautions spéciales, seules les
opérations de lecture ou d'écriture s'accomplissant en une seule transaction
sur le bus (c'est-à-dire alignées sur une adresse multiple de 8, 16 ou 32
bits, à l'exclusion des opérations 64 bits ou mal alignées) sont atomiques. Pire encore,
les compilateurs « <span class="quote">intelligents</span> » comme GCC font souvent des optimisations qui
peuvent éliminer les opérations mémoire nécessaires pour s'assurer que les autres processeurs
puissent voir ce que le processeur concerné a fait. Heureusement, ces problèmes ont tous
deux une solution… en acceptant seulement de ne pas se soucier de la
relation entre l'efficacité des accès mémoire et la taille de la ligne de
cache.
</p><p>
En revanche, avant de traiter de ces différents cas de figure, il est
utile de préciser que tout ceci part du principe que les références à
la mémoire pour chaque processeur se produisent dans l'ordre où elles
ont été programmées. Le Pentium fonctionne de cette manière, mais les
futurs processeurs d'Intel pourraient ne pas le faire. Aussi, quand
vous développerez sur les processeurs à venir, gardez à l'esprit qu'il
pourrait être nécessaire d'encadrer les accès à la mémoire avec des
instructions provoquant l'achèvement de toutes les accès à la mémoire
en suspens, provoquant ainsi leur mise en ordre.
L'instruction <code class="literal">CPUID</code> semble provoquer
cet effet.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N10422"></a>2.2.3. Volatilité</h4></div></div></div><p>
Pour éviter que l'optimiseur du GCC ne conserve les valeurs de la
mémoire partagée dans les registres de processeur, tous les objets
en mémoire partagée doivent être déclarés avec l'attribut
<code class="literal">volatile</code>. Tous les accès en lecture ou écriture
ne nécessitant l'accès qu'à un seul mot se feront alors de manière
atomique. Par exemple, en supposant que <span class="emphasis"><em>p</em></span> est un pointeur
sur un entier, et que ce pointeur comme l'entier qu'il pointe se trouvent en
mémoire partagée, la déclaration en C ANSI ressemblera à :
</p><p>
<pre class="programlisting">
volatile int * volatile p;
</pre>
</p><p>
Dans ce code, le premier <code class="literal">volatile</code> concerne
l'<code class="literal">int</code> que <code class="literal">p</code> pointe
éventuellement, quand le second <code class="literal">volatile</code> s'applique
au pointeur lui-même. Oui, c'est ennuyeux, mais c'est le prix à payer
pour que GCC puisse faire des optimisations vraiment puissantes. En
théorie, l'option <code class="literal">-traditional</code> devrait suffire à
produire du code correct au prix de quelques optimisations, car le
standard C K&R (N.D.T. : Kernigan & Ritchie) pré norme ANSI
établit que toutes les variables sont volatiles si elles ne sont pas
explicitement déclarées comme <code class="literal">register</code>. Ceci étant
dit, si vos compilations GCC ressemblent à <code class="literal">cc -O6
…</code>, vous n'aurez réellement besoin de déclarer les
choses comme étant volatiles qu'aux endroits où c'est nécessaire.
</p><p>
Un rumeur a circulé à propos du fait que les verrous écrits en assembleur
signalés comme modifiant tous les registres du processeur provoquaient de
la part du compilateur GCC l'enregistrement adéquat de toutes les variables en
suspens, évitant ainsi le code compilé « <span class="quote">inutile</span> » associé aux objets déclarés
<code class="literal">volatile</code>. Cette astuce semble fonctionner pour
les variables globales statiques avec la version 2.7.0 de GCC… En revanche,
ce comportement n'est <span class="emphasis"><em>pas</em></span> une recommandation du standard
C ANSI. Pire encore, d'autres processus n'effectuant que des accès en lecture
pourraient conserver éternellement les valeurs dans des registres, et ainsi
ne <span class="emphasis"><em>jamais</em></span> s'apercevoir que la vraie valeur stockée en
mémoire partagée a en fait changé. En résumé, développez comme vous l'entendez,
mais seules les variables déclarées <code class="literal">volatile</code>
offrent un fonctionnement normal <span class="emphasis"><em>garanti</em></span>.
</p><p>
Notez qu'il est possible de provoquer un accès volatile à une variable
ordinaire en utilisant un transtypage (« <span class="quote"><span class="emphasis"><em>casting</em></span></span> ») imposant l'attribut
<code class="literal">volatile</code>. Par exemple, un
<code class="literal">int i;</code> ordinaire peut être référencé en tant
que volatile par <code class="literal">*((volatile int *) &i);</code> .
Ainsi, vous pouvez forcer la volatilité et les coûts supplémentaires qu'elle engendre
seulement aux endroits où elle est critique.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N1047A"></a>2.2.4. Verrous (<span class="foreignphrase"><em class="foreignphrase">Locks</em></span>)</h4></div></div></div><p>
Si vous pensiez que <code class="literal">++i;</code> aurait toujours incrémenté
une variable <code class="literal">i</code> sans problème, vous allez avoir une
mauvaise surprise : même codées en une seule instruction, le
chargement et l'enregistrement du résultat sont deux transactions
mémoire séparées, et d'autres processeurs peuvent accéder à
<code class="literal">i</code> entre ces deux transactions. Par exemple, deux
processus effectuant chacun l'instruction <code class="literal">++i;</code>
pourraient n'incrémenter la variable <code class="literal">i</code> que d'une
unité et non deux. Selon le « <span class="quote">Manuel de l'Architecture et de la
Programmation</span> » du Pentium d'Intel, le préfixe
<code class="literal">LOCK</code> peut être employé pour s'assurer que chacune des
instructions suivantes soit atomique par rapport à l'adresse mémoire à
laquelle elles accèdent :
</p><p>
<pre class="programlisting">
BTS, BTR, BTC mem, reg/imm
XCHG reg, mem
XCHG mem, reg
ADD, OR, ADC, SBB, AND, SUB, XOR mem, reg/imm
NOT, NEG, INC, DEC mem
CMPXCHG, XADD
</pre>
</p><p>
En revanche, il n'est pas conseillé d'utiliser toutes ces opérations.
Par exemple, <code class="literal">XADD</code> n'existait même pas sur 386,
aussi l'employer en programmation peut poser des problèmes de portabilité.
</p><p>
L'instruction <code class="literal">XCHG</code> engendre <span class="emphasis"><em>toujours</em></span>
un verrou, même sans le préfixe <code class="literal">LOCK</code>, et est ainsi
et indiscutablement l'opération atomique favorite pour construire d'autres opérations
atomiques de plus haut niveau comme les sémaphores et les files d'attente partagées.
Bien sûr, on ne peut pas demander à GCC de générer cette instruction en écrivant
simplement du code C. Il vous faudra à la place écrire un peu de code assembleur en
ligne<sup>[<a href="#ftn.N104B6" name="N104B6">5</a>]</sup>. En prenant un objet volatile
<span class="emphasis"><em>obj</em></span> et un registre du processeur
<span class="emphasis"><em>reg</em></span>, tous deux de type <code class="literal">word</code>
(longs de 16 bits), le code assembleur GCC sera :
</p><pre class="programlisting">
__asm__ __volatile__ ("xchgl %1,%0"
:"=r" (reg), "=m" (obj)
:"r" (reg), "m" (obj));
</pre><p>
Quelques exemples de programmes assembleur en ligne utilisant des
opérations bit-à-bit pour réaliser des verrous sont disponibles dans le
code source de la bibliothèque bb_threads.
</p><p>
Il est toutefois important de se souvenir que faire des transactions
mémoire atomiques a un coût. Une opération de verrouillage engendre des
délais supplémentaires assez importants et peut retarder l'activité
mémoire d'autres processeurs, quand des références ordinaires auraient
utilisé le cache local. Les meilleures performances s'obtiennent en
utilisant les opérations atomiques aussi <span class="emphasis"><em>peu</em></span>
souvent que possible. De plus, ces instructions atomiques IA32 ne sont
évidement pas portables vers d'autres systèmes.
</p><p>
Il existe plusieurs alternatives permettant aux instructions ordinaires
d'être utilisées pour mettre en œuvre différents types de
synchronisation, y compris l'<span class="emphasis"><em>exclusion mutuelle</em></span>,
qui garantit qu'au plus un seul processeur met à jour un objet partagé
donné à un moment précis. La plupart des manuels des différents systèmes
d'exploitation traitent d'au moins une de ces techniques. On trouve un
très bon exposé sur le sujet dans la quatrième édition des
<span class="foreignphrase"><em class="foreignphrase">Operating System Concepts</em></span> (Principes des
Systèmes d'Exploitation), par Abraham Silberschatz et Peter B. Galvin,
ISBN 0-201-50480-4.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N104D6"></a>2.2.5. Taille de la ligne de cache</h4></div></div></div><p>
Encore une chose fondamentale concernant l'atomicité et qui peut avoir
des conséquence dramatiques sur les performances d'un SMP : la
taille de la ligne de cache. Même si le standard MPS impose que les
références soient cohérentes quelque soit le cache utilisé, il n'en
reste pas moins que lorsque qu'un processeur écrit sur une ligne
particulière de la mémoire, chaque copie en cache de l'ancienne ligne
doit être invalidée ou mise à jour. Ceci implique que si au moins deux
processeurs écrivent chacun sur des portions différentes de la ligne de
cache, cela peut provoquer un trafic important sur le bus et le cache,
pour au final transférer la ligne depuis le cache vers le cache. Ce
problème est connu sous le nom de <span class="emphasis"><em>faux partage</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">false sharing</em></span></span> »). La
solution consiste uniquement à <span class="emphasis"><em>organiser les données de telle
manière que ce que les objets auxquels on accède en parallèle
proviennent globalement de différentes lignes de cache pour chaque
processus</em></span>.
</p><p>
Vous pourriez penser que le faux partage n'est pas un problème quand on
utilise un cache de niveau 2 partagé, mais souvenez-vous qu'il existe
toujours des caches de niveau 1 séparés. L'organisation du cache et le
nombre de niveaux séparés peut varier, mais la ligne de cache de premier
niveau d'un Pentium est longue de 32 octets, et le cache externe typique
tourne autour de 256 octets. Supposons que les adresses (physiques ou
logiques) de deux objets soient <span class="emphasis"><em>a</em></span> et
<span class="emphasis"><em>b</em></span>, et que la taille de la ligne de cache soit
<span class="emphasis"><em>c</em></span>, que nous admettrons être une puissance de 2.
Pour être très précis, si
<code class="literal">((int) a) & ˜(c-1)</code> est égal à
<code class="literal">((int) b) & ˜(c-1)</code>,
alors les deux références se trouvent dans la même ligne de cache. Une
règle plus simple consiste à dire que si deux objets référencés en
parallèle sont éloignés d'au moins <span class="emphasis"><em>c</em></span> octets, ils
devraient se trouver dans des lignes de cache différentes.
</p></div><div class="sect3" lang="fr"><div class="titlepage"><div><div><h4 class="title"><a name="N104FB"></a>2.2.6. Les problèmes de l'ordonnanceur de Linux</h4></div></div></div><p>
Bien que tout l'intérêt d'utiliser de la mémoire partagée pour les
traitements en parallèle consiste à éviter les délais dus au système
d'exploitation, ces délais peuvent parfois provenir d'autres choses que
les communications en elles-mêmes. Nous avons déjà remarqué que le
nombre de processus que l'on devrait créer doit être inférieur ou égal
au nombre de processeurs de la machine. Mais comment décide-t-on
exactement du nombre de processus à créer ?
</p><p>
Pour obtenir les meilleures performances, <span class="emphasis"><em>le nombre de
processus de votre programme en parallèle doit être égal au nombre de
processus qui peuvent être exécutés simultanément, chacun sur son
processeur</em></span>. Par exemple, si un système SMP à quatre
processeurs héberge un processus très actif pour un autre usage (par
exemple un serveur <span class="foreignphrase"><em class="foreignphrase">web</em></span>), alors votre
programme en parallèle ne devra utiliser que trois processus. Vous
pouvez vous faire une idée générale du nombre de processus actifs
exécutés sur votre système en consultant la « <span class="quote">charge
système moyenne</span> » (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">load
average</em></span></span> ») mise en évidence par la commande
<code class="literal">uptime</code>.
</p><p>
Vous pouvez en outre « <span class="quote">pousser</span> » la priorité de vos processus
de votre programme parallèle en utilisant, par exemple, la commande
<code class="literal">renice</code> ou l'appel système <code class="literal">nice()</code>.
Vous devez être privilégié<sup>[<a href="#ftn.N10520" name="N10520">6</a>]</sup> pour augmenter la priorité d'un processus. L'idée
consiste simplement à éjecter les autres programmes des autres
processeurs pour que votre programme puisse être exécuté sur tous les
processeurs simultanément. Ceci peut être effectué de manière un peu
plus explicite en utilisant la version prototype de Linux SMP disponible
sur <a href="http://www.fsmlabs.com/products/openrtlinux/" target="_top">http://www.fsmlabs.com/products/openrtlinux/</a> et qui
propose un ordonnanceur en temps réel (N.D.T. : il existe désormais un
guide consacré à RTLinux, accessible en ligne : <a href="http://www.traduc.org/docs/howto/lecture/RTLinux-HOWTO.html" target="_top">RTLinux
HOWTO</a>).
</p><p>
Si vous n'êtes pas le seul utilisateur employant votre système SMP comme
une machine en parallèle, il se peut que vous entriez en conflit avec
les autres programmes en parallèle essayant de s'exécuter simultanément.
La solution standard est l'<span class="emphasis"><em>ordonnancement de groupe</em></span>
(« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">gang scheduling</em></span></span> »),
c'est-à-dire la manipulation de la priorité d'ordonnancement de façon à
ce que seuls les processus d'un seul programme en parallèle s'exécutent
à un moment donné. Il est bon de rappeler, en revanche, que multiplier
les parallélismes tend à réduire les retours et que l'activité de
l'ordonnanceur introduit des délais supplémentaires. Ainsi, par exemple,
il sera sûrement préférable, pour une machine à quatre processeurs,
d'exécuter deux programmes contenant chacun deux processus, plutôt que
d'ordonnancer en groupe deux programmes de quatre processus chacun.
</p><p>
Il y a encore une chose dont il faut tenir compte. Supposons que vous
développiez un programme sur une machine très sollicitée le jour, mais
disponible à cent pour cent pendant la nuit pour le traitement en
parallèle. Il vous faudra écrire et tester votre code dans les
conditions réelles, donc avec tous ses processus lancés, même en sachant
que des tests de jour risquent d'être lents. Ils seront en fait
<span class="emphasis"><em>très</em></span> lents si certains de vos processus sont en
état d'<span class="emphasis"><em>attente active</em></span> (« <span class="quote"><span class="foreignphrase"><em class="foreignphrase">busy
waiting</em></span></span> »)<sup>[<a href="#ftn.N10544" name="N10544">7</a>]</sup>, guettant le changement de certaines valeurs en
mémoire partagée, changement censé être provoqué par d'autres processus
qui ne sont pas exécutés (sur d'autres processeurs) au même moment. Ce
même problème apparaît lorsque l'on développe et que l'on teste un
programme sur un système monoprocesseur.
</p><p>
La solution consiste à intégrer des appels système à votre code là où il
peut se mettre en boucle en attendant une action d'un autre processeur,
pour que Linux puisse donner une chance de s'exécuter à un autre
processus. J'utilise pour cela une macro en langage C, appelons-la
<code class="literal">IDLE_ME</code> (N.D.T. :
<code class="literal">MetsMoiEnAttente</code>) : pour faire un simple test,
compilez votre programme par
« <span class="quote"><code class="literal">cc -DIDLE_ME=usleep(1);…</code></span> ».
Pour produire un exécutable définitif, utilisez
« <span class="quote"><code class="literal">cc -DIDLE_ME={}…</code></span> ».
L'appel <code class="literal">usleep(1)</code> réclame une pause d'une
microseconde, qui a pour effet de permettre à l'ordonnanceur de Linux de
choisir un nouveau processus à exécuter sur ce processeur. Si le nombre
de processus dépasse le nombre de processeurs disponibles, il n'est pas
rare de voir des programmes s'exécuter dix fois plus rapidement avec
<code class="literal">usleep(1)</code> que sans.
</p></div></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N10564"></a>2.3. bb_threads</h3></div></div></div><p>
La bibliothèque bb_threads (<span class="foreignphrase"><em class="foreignphrase">"Bare Bones"
threads</em></span>) est une bibliothèque remarquablement simple qui
fait la démonstration de l'utilisation de l'appel système Linux
<code class="literal">clone()</code>. Le fichier <code class="literal">tar.gz</code>
n'occupe que 7 ko ! Bien que cette bibliothèque ait été rendue
pour l'essentiel obsolète par la bibliothèque LinuxThreads, traitée dans
la section 2.4, bb_threads reste utilisable, et est suffisamment simple
et peu encombrante pour former une bonne introduction à la gestion des
<span class="foreignphrase"><em class="foreignphrase">threads</em></span> sous Linux. Il est beaucoup moins
effrayant de se lancer dans la lecture de ce code source que dans celui
de LinuxThreads. En résumé, la bibliothèque bb_threads forme un bon
point de départ, mais n'est pas vraiment adaptée à la réalisation de
grands projets.
</p><p>
La structure de base des programmes utilisant la bibliothèque bb_threads
est la suivante :
</p><div class="orderedlist"><ol type="1"><li><p>
Lancez le programme en tant que processus unique.
</p></li><li><p>
Il vous faudra estimer l'espace maximum dans la pile qui sera nécessaire
à chaque <span class="foreignphrase"><em class="foreignphrase">thread</em></span>. Prévoir large est
relativement sage (c'est à çà que sert la mémoire virtuelle ;-), mais
souvenez-vous que <span class="emphasis"><em>toutes</em></span> les piles proviennent d'un
seul espace d'adressage virtuel, aussi voir trop grand n'est pas une
idée formidable. La démo suggère 64Ko. Cette taille est fixée à
<span class="emphasis"><em>b</em></span> octets par
<code class="literal">bb_threads_stacksize(b)</code>.
</p></li><li><p>
L'étape suivante consiste à initialiser tous les verrous dont vous aurez
besoin. Le mécanisme de verrouillage intégré à cette bibliothèque
numérote les verrous de 0 à <code class="literal">MAX_MUTEXES</code>, et
initialise un verrou <span class="emphasis"><em>i</em></span> par
<code class="literal">bb_threads_mutexcreate(i)</code>.
</p></li><li><p>
La création d'un nouveau <span class="foreignphrase"><em class="foreignphrase">thread</em></span>
s'effectue en appelant une routine de la bibliothèque recevant en
arguments la fonction que le nouveau
<span class="foreignphrase"><em class="foreignphrase">thread</em></span> doit exécuter, et les arguments
qui doivent lui être transmis. Pour démarrer un nouveau
<span class="foreignphrase"><em class="foreignphrase">thread</em></span> exécutant la fonction
<span class="emphasis"><em>f</em></span> de type <code class="literal">void</code> et attendant un
argument <span class="emphasis"><em>arg</em></span>, l'appel ressemblera à
<code class="literal">bb_threads_newthread (f, &arg)</code>, où
<span class="emphasis"><em>f</em></span> devra être déclaré comme suit :
</p><pre class="programlisting">
void f (void *arg, size_t dummy)
</pre><p>
Si vous avez besoin de passer plus d'un argument à votre fonction,
utilisez un pointeur sur une structure contenant les valeurs à
transmettre.
</p></li><li><p>
Lancement du code en parallèle, en prenant soin d'utiliser
<code class="literal">bb_threads_lock(n)</code> et
<code class="literal">bb_threads_unlock(n)</code> où <span class="emphasis"><em>n</em></span> est un
entier indiquant le verrou à utiliser. Notez que les opérations de
verrouillage et déverrouillage sont des opérations de blocage<sup>[<a href="#ftn.N105CD" name="N105CD">8</a>]</sup> très primaires et utilisant des instructions
atomiques de verrouillage du bus, lesquelles peuvent causer des
interférences d'accès à la mémoire, et qui n'essaient en aucun cas
d'agir « <span class="quote">proprement</span> ».
Le programme de démonstration fourni avec bb_threads n'utilisait pas
correctement les verrous pour empêcher <code class="literal">printf()</code>
d'être exécuté depuis les fonctions <code class="literal">fnn</code> et
<code class="literal">main</code>, et à cause de cela, la démo ne fonctionne pas
toujours. Je ne dis pas cela pour démolir la démo, mais plutôt pour bien
mettre en évidence le fait que ce travail comporte <span class="emphasis"><em>beaucoup de
pièges</em></span>. Ceci dit, utiliser LinuxThreads ne se révèle que
légèrement plus facile.
</p></li><li><p>
Lorsqu'un <span class="foreignphrase"><em class="foreignphrase">thread</em></span> exécute
<code class="literal">return</code>, il détruit le processus… mais la pile
locale n'est pas automatiquement désallouée. Pour être plus précis,
Linux ne gère pas la désallocation, et l'espace mémoire n'est pas
automatiquement rendu à la liste d'espace libre de
<code class="literal">malloc()</code>. Aussi, le processus parent doit-il
récupérer l'espace mémoire de chaque processus fils mort par
<code class="literal">bb_threads_cleanup(wait(NULL))</code>.
</p></li></ol></div><p>
Le programme suivant, écrit en langage C, utilise l'algorithme traité
dans la section 1.3 pour calculer la valeur de Pi en utilisant deux
<span class="foreignphrase"><em class="foreignphrase">threads</em></span> bb_threads.
</p><pre class="programlisting">
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include "bb_threads.h"
volatile double pi = 0.0;
volatile int intervalles;
volatile int pids[2]; /* Numéros de processus Unix des threads */
void
do_pi(void *data, size_t len)
{
register double largeur, sommelocale;
register int i;
register int iproc = (getpid() != pids[0]);
/* Fixe la largeur des intervalles */
largeur = 1.0 / intervalles;
/* Effectue les calculs locaux */
sommelocale = 0;
for (i=iproc; i<intervalles; i+=2) {
register double x = (i + 0.5) * largeur;
sommelocale += 4.0 / (1.0 + x * x);
}
sommelocale *= largeur;
/* Obtention des permissions, mise à jour de Pi, et déverrouillage */
bb_threads_lock(0);
pi += sommelocale;
bb_threads_unlock(0);
}
int
main(int argc, char **argv)
{
/* Récupère le nombre d'intervalles */
intervalles = atoi(argv[1]);
/* Fixe la taille de la pile, et crée le verrou */
bb_threads_stacksize(65536);
bb_threads_mutexcreate(0);
/* crée deux threads ... */
pids[0] = bb_threads_newthread(do_pi, NULL);
pids[1] = bb_threads_newthread(do_pi, NULL);
/* nettoie derrière les deux threads */
/* (forme ainsi une barrière de synchro) */
bb_threads_cleanup(wait(NULL));
bb_threads_cleanup(wait(NULL));
/* Affiche le résultat */
printf("Estimation de la valeur de Pi: %f\n", pi);
/* Sortie avec code de SUCCES */
exit(0);
}
</pre></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N10601"></a>2.4. LinuxThreads</h3></div></div></div><p>
LinuxThreads (<a href="http://pauillac.inria.fr/~xleroy/linuxthreads/" target="_top">http://pauillac.inria.fr/~xleroy/linuxthreads/</a>) est une
implémentation assez complète et bien construite en accord avec le
standard de <span class="foreignphrase"><em class="foreignphrase">threads</em></span> POSIX 1003.1c.
Contrairement aux autres adaptations d'implémentations de
<span class="foreignphrase"><em class="foreignphrase">threads</em></span> POSIX, LinuxThreads utilise
également l'appel <code class="literal">clone()</code> du noyau Linux, déjà
employé par bb_threads. La compatibilité POSIX implique qu'il est
relativement aisé de faire l'adaptation de certaines applications
provenant d'autres systèmes, et différents tutoriels et leur support
sont disponibles. Bref, c'est incontestablement la bibliothèque à
utiliser pour développer des applications
<span class="foreignphrase"><em class="foreignphrase">multi-threads</em></span> à grande échelle sous
Linux.
</p><p>
La structure de base d'un programme utilisant LinuxThreads suit ce
modèle :
</p><div class="orderedlist"><ol type="1"><li><p>
Lancement du programme en tant que processus unique.
</p></li><li><p>
Initialisation de tous les verrous dont vous aurez besoin.
Contrairement aux verrous de bb_threads qui sont identifiés par
des numéros, les verrous POSIX sont déclarés comme des variables de
type <code class="literal">pthread_mutex_t lock</code>.
Utilisez <code class="literal">pthread_mutex_init(&lock,val)</code>
pour initialiser chacun des verrous que vous utiliserez.
</p></li><li><p>
Comme avec bb_threads, la création d'un nouveau
<span class="foreignphrase"><em class="foreignphrase">thread</em></span> se fait par l'appel d'une fonction
de la bibliothèque admettant des arguments spécifiant à leur tour la
fonction que le nouveau <span class="foreignphrase"><em class="foreignphrase">thread</em></span> doit
exécuter et les arguments que celle-ci reçoit. Cependant, POSIX impose à
l'utilisateur la déclaration d'une variable de type
<code class="literal">pthread_t</code> pour identifier chaque
<span class="foreignphrase"><em class="foreignphrase">thread</em></span>. Pour créer un
<span class="foreignphrase"><em class="foreignphrase">thread</em></span> <code class="literal">pthread_t
thread</code> exécutant la fonction <code class="literal">f()</code>, on
appelle <code class="literal">pthread_create(&thread,NULL,f,&arg)</code>.
</p></li><li><p>
Lancement de la partie parallèle du programme, en prenant soin d'utiliser
<code class="literal">pthread_mutex_lock(&lock)</code> et
<code class="literal">pthread_mutex_unlock(&lock)</code>
comme il se doit.
</p></li><li><p>
Utilisation de <code class="literal">pthread_join(thread,&retval)</code>
après chaque <span class="foreignphrase"><em class="foreignphrase">thread</em></span> pour tout nettoyer.
</p></li><li><p>
Utilisation de <code class="literal">-D_REENTRANT</code> à la compilation de votre
programme en C.
</p></li></ol></div><p>
Voici l'exemple du calcul de Pi en parallèle, s'appuyant sur
LinuxThreads. L'algorithme de la section 1.3 est utilisé et, comme pour
l'exemple de bb_threads, deux <span class="foreignphrase"><em class="foreignphrase">threads</em></span>
s'exécutent en parallèle.
</p><pre class="programlisting">
#include <stdio.h>
#include <stdlib.h>
#include "pthread.h"
volatile double pi = 0.0; /* Approximation de pi (partagée) */
pthread_mutex_t pi_lock; /* Verrou de la variable ci-dessous */
volatile double intervalles; /* Combien d'intervalles ? */
void *
process(void *arg)
{
register double largeur, sommelocale;
register int i;
register int iproc = (*((char *) arg) - '0');
/* Fixe la largeur */
largeur = 1.0 / intervalles;
/* Fais les calculs locaux */
sommelocale = 0;
for (i=iproc; i<intervalles; i+=2) {
register double x = (i + 0.5) * largeur;
sommelocale += 4.0 / (1.0 + x * x);
}
sommelocale *= largeur;
/* Verrouille la variable pi en vue d'une mise à jour,
effectue la mise à jour, puis déverrouille Pi. */
pthread_mutex_lock(&pi_lock);
pi += sommelocale;
pthread_mutex_unlock(&pi_lock);
return(NULL);
}
int
main(int argc, char **argv)
{
pthread_t thread0, thread1;
void * retval;
/* Récupère le nombre d'intervalles */
intervalles = atoi(argv[1]);
/* Initialise un verrou sur pi */
pthread_mutex_init(&pi_lock, NULL);
/* Crée les deux threads */
if (pthread_create(&thread0, NULL, process, "0") ||
pthread_create(&thread1, NULL, process, "1")) {
fprintf(stderr, "%s: Création des threads impossible\n", argv[0]);
exit(1);
}
/* « Joint » (détruit) les deux threads */
if (pthread_join(thread0, &retval) ||
pthread_join(thread1, &retval)) {
fprintf(stderr, "%s: Erreur à la fusion des threads\n", argv[0]);
exit(1);
}
/* Affiche le résultat */
printf("Estimation de la valeur de Pi: %f\n", pi);
/* Sortie */
exit(0);
}
</pre></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N1066C"></a>2.5. La mémoire partagée de System V</h3></div></div></div><p>
La gestion des IPC (<span class="foreignphrase"><em class="foreignphrase">Inter-Process
Communication</em></span>) System V s'effectue au travers d'un
certain nombre d'appels système fournissant les mécanismes des files de
message, des sémaphores et de la mémoire partagée. Bien sûr, ces
mécanismes ont été initialement conçus pour permettre à plusieurs
processus de communiquer au sein d'un système monoprocesseur. Cela
signifie néanmoins que ces mécanismes devraient aussi fonctionner dans
un système Linux SMP, quelque soit le nombre de processeurs.
</p><p>
Avant d'aller plus loin dans l'utilisation de ces appels, il est
important de comprendre que même s'il existe des appels IPC System V
pour des choses comme les sémaphores et la transmission de messages,
vous ne les utiliserez probablement pas. Pourquoi ? Parce ces
fonctions sont généralement lentes et sérialisées sous Linux SMP.
Inutile de s'étendre.
</p><p>
La marche à suivre standard pour créer un groupe de processus partageant
l'accès à un segment de mémoire partagée est la suivante.
</p><div class="orderedlist"><ol type="1"><li><p>
Lancement du programme en tant que processus unique.
</p></li><li><p>
En temps normal, chaque instance de votre programme en parallèle devra
avoir son propre segment de mémoire partagée, aussi vous faudra-t-il
appeler <code class="literal">shmget()</code> pour créer un nouveau segment de la
taille souhaitée. Mais d'autre part, cet appel peut être utilisé pour
récupérer l'identifiant d'un segment de mémoire partagée déjà existant.
Dans les deux cas, la valeur de retour est soit l'identifiant du segment
de mémoire partagée, soit -1 en cas d'erreur. Par exemple, pour créer un
segment de mémoire partagée long de <span class="emphasis"><em>b</em></span> octets, on
passe un appel ressemblant à
<code class="literal">shmid = shmget(IPC_PRIVATE, b, (IPC_CREAT | 0666))</code>.
</p></li><li><p>
L'étape suivante consiste à attacher ce segment de mémoire partagée au
processus, c'est-à-dire l'ajouter à son plan mémoire. Même si l'appel
<code class="literal">shmat()</code> permet au programmeur de spécifier l'adresse
virtuelle à laquelle le segment doit apparaître, cette adresse doit être
alignée sur une page (plus précisément être un multiple de la taille
d'une page renvoyée par <code class="literal">getpagesize()</code>, correspondant
à 4096 octets), et recouvrera (prendra le pas sur) tout segment de
mémoire s'y trouvant déjà. Ainsi est-il plus sage de laisser le système
choisir une adresse. Dans les deux cas, la valeur de retour est un
pointeur sur l'adresse virtuelle de base du segment fraîchement installé
dans le plan mémoire. L'instruction correspondante est la
suivante :
<code class="literal">shmptr = shmat(shmid, 0, 0)</code>.
Remarquez que vous pouvez allouer toutes vos variables statiques dans ce
segment de mémoire partagée en déclarant simplement vos variables
partagées comme étant les membres d'une structure de type
<code class="literal">struct</code>, et en déclarant <span class="emphasis"><em>shmptr</em></span>
comme étant un pointeur vers ce type de données. Avec cette technique,
une variable partagée <span class="emphasis"><em>x</em></span> serait accessible par
<span class="emphasis"><em>shmptr</em></span><code class="literal">-></code><span class="emphasis"><em>x</em></span>.
</p></li><li><p>
Comme ce segment de mémoire partagée doit être détruit quand le
dernier processus à y accéder prend fin ou s'en détache, il nous
faut appeler <code class="literal">shmctl()</code> pour configurer
cette action par défaut. Le code correspondant ressemble à
<code class="literal">shmctl(shmid, IPC_RMID, 0)</code>.
</p></li><li><p>
Utiliser l'appel Linux <code class="literal">fork()</code><sup>[<a href="#ftn.N106BE" name="N106BE">9</a>]</sup> pour créer le nombre désiré de processus.
Chacun d'eux héritera du segment de mémoire partagée.
</p></li><li><p>
Lorsqu'un processus a fini d'utiliser un segment de mémoire
partagée, il doit s'en détacher. On accomplit cela par un
<code class="literal">shmdt(shmptr)</code>.
</p></li></ol></div><p>
Même avec si peu d'appels système, une fois le segment de mémoire
partagée établi, tout changement effectué par un processeur sur une
valeur se trouvant dans cet espace sera automatiquement visible par les
autres processus. Plus important, chaque opération de communication sera
exonérée du coût d'un appel système.
</p><p>
Ci-après, un exemple de programme en langage C utilisant les segments de
mémoire partagée System V. Il calcule Pi, en utilisant les algorithmes
de la section 1.3.
</p><pre class="programlisting">
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <sys/ipc.h>
#include <sys/shm.h>
volatile struct shared { double pi; int lock; } * partage;
inline extern int xchg(register int reg,
volatile int * volatile obj)
{
/* Instruction atomique d'échange */
__asm__ __volatile__ ("xchgl %1,%0"
:"=r" (reg), "=m" (*obj)
:"r" (reg), "m" (*obj));
return(reg);
}
main(int argc, char **argv)
{
register double largeur, sommelocale;
register int intervalles, i;
register int shmid;
register int iproc = 0;;
/* Alloue de la mémoire partagée */
shmid = shmget(IPC_PRIVATE,
sizeof(struct shared),
(IPC_CREAT | 0600));
partage = ((volatile struct shared *) shmat(shmid, 0, 0));
shmctl(shmid, IPC_RMID, 0);
/* Fais les inits ... */
partage->pi = 0.0;
partage->lock = 0;
/* Crée un fils */
if (!fork()) ++iproc;
/* Récupère le nombre d'intervalles */
intervalles = atoi(argv[1]);
largeur = 1.0 / intervalles;
/* Fais les calculs locaux */
sommelocale = 0;
for (i=iproc; i<intervalles; i+=2) {
register double x = (i + 0.5) * largeur;
sommelocale += 4.0 / (1.0 + x * x);
}
sommelocale *= largeur;
/* Verrou d'attente atomique, ajout, et déverrouillage ... */
while (xchg((iproc + 1), &(shared->lock))) ;
shared->pi += sommelocale;
shared->lock = 0;
/* Fin du processus fils (barrière de synchro) */
if (iproc == 0) {
wait(NULL);
printf("Estimation de pi: %f\n", partage->pi);
}
/* Sortie en bonne et due forme */
return(0);
}
</pre><p>
Dans cet exemple, j'ai utilisé l'instruction atomique d'échange
pour mettre le verrouillage en œuvre. Pour de meilleures performances,
préférez-lui une technique de synchronisation évitant les intructions
verrouillant le bus.
</p><p>
Pendant les phases de débogage, il est utile de se souvenir que la
commande <code class="literal">ipcs</code> renvoie la liste des
facilités des IPC System V en cours d'utilisation.
</p></div><div class="sect2" lang="fr"><div class="titlepage"><div><div><h3 class="title"><a name="N106D8"></a>2.6. Projection mémoire (<span class="foreignphrase"><em class="foreignphrase">Memory Map Call</em></span>)</h3></div></div></div><p>
L'utilisation des appels système pour accéder aux fichiers (les
entrées/sorties) peut revenir cher. En fait, c'est la raison pour
laquelle il existe une bibliothèque de gestion des entrées/sorties
gérant un tampon dans l'espace utilisateur
(<code class="literal">getchar()</code>, <code class="literal">fwrite()</code>, et cætera).
Mais les tampons utilisateur ne remplissent pas leur fonction si
plusieurs processus accèdent au même fichier ouvert en écriture. La
solution Unix BSD à ce problème fut l'ajout d'un appel système
permettant à une portion d'un fichier d'être projetée en mémoire
utilisateur, en utilisant principalement les mécanismes de la mémoire
virtuelle pour provoquer les mises à jour. Le même mécanisme a été
utilisé pendant plusieurs années dans les systèmes de Sequent comme base
de leur gestion du traitement parallèle en mémoire partagée. En dépit de
commentaires très négatifs dans la page de manuel (assez ancienne),
Linux semble correctement effectuer au moins quelques unes des fonctions
de base, et sait prendre en charge l'usage dérivé de cet appel pour
projeter un segment anonyme de mémoire pouvant être partagé par
plusieurs processus.
</p><p>
L'implémentation Linux de l'appel <code class="literal">mmap()</code> est en
elle-même une solution intégrée de remplacement des étapes 2, 3 et 4 du
schéma classique de mémoire partagée System V, mis en évidence dans la
section 2.5. Pour créer un segment de mémoire partagée anonyme :
</p><pre class="programlisting">
shmptr =
mmap(0, /* Le système choisit l'adresse */
b, /* Taille du segment de mémoire partagée */
(PROT_READ | PROT_WRITE), /* droits d'accès, peuvent être rwx */
(MAP_ANON | MAP_SHARED), /* anonyme, partagé */
0, /* descripteur de fichier (inutilisé) */
0); /* offset fichier (inutilisé) */
</pre><p>
L'équivalent de l'appel de mémoire partagée System V
<code class="literal">shmdt()</code> est <code class="literal">munmap()</code> :
</p><pre class="programlisting">
munmap(shmptr, b);
</pre><p>
À mon avis, on ne gagne pas grand chose à utiliser
<code class="literal">mmap()</code> plutôt que les mécanismes de gestion de la
mémoire partagée de System V.
</p></div><div class="footnotes"><br><hr align="left" width="100"><div class="footnote"><p><sup>[<a href="#N102D7" name="ftn.N102D7">2</a>] </sup>
N.D.T. : décomposition d'un programme en plusieurs processus
distincts, mais travaillant simultanément et de concert.
</p></div><div class="footnote"><p><sup>[<a href="#N102EE" name="ftn.N102EE">3</a>] </sup>
N.D.T. : qui a démarré la machine avant de passer en mode SMP.
</p></div><div class="footnote"><p><sup>[<a href="#N1030A" name="ftn.N1030A">4</a>] </sup>
N.D.T. : le lien vers l'ancienne version 1.1, lui, n'existe plus. La
documentation la plus récente se trouve à ce jour sur <a href="http://www.intel.com/design/Pentium4/documentation.htm" target="_top">http://www.intel.com/design/Pentium4/documentation.htm</a>.
</p></div><div class="footnote"><p><sup>[<a href="#N104B6" name="ftn.N104B6">5</a>] </sup>
N.D.T. : inséré au sein du code source, ici en C.
</p></div><div class="footnote"><p><sup>[<a href="#N10520" name="ftn.N10520">6</a>] </sup>
N.D.T. : soit, sous Unix, être sous le compte <code class="literal">root</code>.
</p></div><div class="footnote"><p><sup>[<a href="#N10544" name="ftn.N10544">7</a>] </sup>
N.D.T. : temporisations introduites au sein d'un programme en
utilisant par exemple des boucles et en consommant ainsi tout le temps
machine alloué au processus plutôt qu'en rendant la main au système.
</p></div><div class="footnote"><p><sup>[<a href="#N105CD" name="ftn.N105CD">8</a>] </sup>
N.D.T. : « <span class="quote"><span class="foreignphrase"><em class="foreignphrase">spin
locks</em></span></span> » : mise en état d'attente jusqu'à ce
qu'une condition soit remplie.
</p></div><div class="footnote"><p><sup>[<a href="#N106BE" name="ftn.N106BE">9</a>] </sup>
N.D.T. : Il s'agit en fait d'un appel Unix standard.
</p></div></div></div><div class="navfooter"><hr><table summary="Navigation footer" width="100%"><tr><td align="left" width="40%"><a accesskey="p" href="ar01s01.html">Précédent</a> </td><td align="center" width="20%"> </td><td align="right" width="40%"> <a accesskey="n" href="ar01s03.html">Suivant</a></td></tr><tr><td valign="top" align="left" width="40%">1. Introduction </td><td align="center" width="20%"><a accesskey="h" href="index.html">Sommaire</a></td><td valign="top" align="right" width="40%"> 3. <span class="foreignphrase"><em class="foreignphrase">Clusters</em></span> de systèmes Linux</td></tr></table></div></body></html>
