Parallélisme

Concurrence et ordonnancement

Tâches

Au chapitre 6, on a fait travailler plusieurs processus en même temps. Chacun avait sa propre mémoire : c'est sûr, mais pour échanger des données, il faut passer par un tube ou un fichier.

Ce chapitre étudie l'autre façon de faire : plusieurs tâches qui s'exécutent en même temps dans la même mémoire. On parle de programmation concurrente. Les tâches peuvent s'exécuter vraiment en même temps, sur plusieurs processeurs (on parle alors de parallélisme), ou à tour de rôle sur un seul processeur, assez vite pour donner l'illusion de la simultanéité. Les problèmes, on va le voir, sont les mêmes dans les deux cas.

Dans un processus, ces tâches s'appellent des fils d'exécution, en anglais threads. On les présente en détail à la fin du chapitre ; il suffit pour l'instant de savoir qu'un fil d'exécution est une fonction qui s'exécute en même temps que le reste du programme, avec sa propre pile, mais en partageant tout le reste : variables globales, tas, fichiers ouverts.

Ordonnancement

C'est le système qui décide, à chaque instant, quelle tâche s'exécute sur quel processeur : c'est l'ordonnancement. Il peut interrompre une tâche n'importe quand, entre deux instructions machine, pour en faire tourner une autre, puis la reprendre plus tard là où elle en était. Le programme ne sait pas quand cela arrive, et ne peut pas le prévoir.

Déterminisme

Un programme séquentiel est déterministe : avec les mêmes entrées, il fait toujours la même chose. Un programme concurrent ne l'est plus. L'ordre dans lequel les instructions des différentes tâches s'entrelacent change d'une exécution à l'autre, et avec lui, parfois, le résultat.

C'est ce qui rend les erreurs de concurrence si difficiles : un programme faux peut marcher mille fois, puis échouer une fois, chez le client. Et l'erreur disparaît souvent dès qu'on ajoute un printf pour l'observer, parce que l'affichage change le minutage.

Atomicité et section critique

Très peu de choses sont atomiques. compteur = compteur + 1, qui tient sur une ligne de C, se traduit en trois instructions machine :

1. Lire : charger compteur depuis la mémoire dans un registre.
2. Calculer : ajouter 1 au registre.
3. Écrire : ranger le registre dans compteur.

Si deux tâches exécutent cette ligne en même temps, et que l'ordonnanceur les entrelace mal, il peut arriver ceci (le compteur vaut 5 au départ) :

Deux incrémentations, et le compteur n'a augmenté que de 1 : une mise à jour a été perdue. C'est une situation de compétition (race condition) : le résultat dépend de l'ordre d'exécution.

Une solution au problème de la section critique doit garantir trois choses :

• l'exclusion mutuelle : jamais deux tâches à la fois dans la section critique ;
• le progrès : si la section critique est libre et qu'une tâche veut y entrer, elle finit par y entrer (les tâches qui ne sont pas intéressées ne peuvent pas l'en empêcher) ;
• l'attente bornée : une tâche qui veut entrer ne peut pas être doublée indéfiniment par les autres.

Un exemple simple : les gardiens compteurs

Le problème

Un musée a deux entrées, avec un gardien à chacune. À chaque visiteur qui entre, le gardien ajoute 1 à un compteur commun, affiché à l'accueil. On simule chaque gardien par un fil d'exécution qui compte un million de visiteurs :

#include <pthread.h>
#include <stdio.h>

#define VISITEURS 1000000

static long compteur = 0;           /* partagé par les deux gardiens */

static void *gardien(void *arg)
{
    (void)arg;
    for (int i = 0; i < VISITEURS; i++)
        compteur = compteur + 1;    /* un visiteur de plus */
    return NULL;
}

int main(void)
{
    pthread_t g1, g2;
    pthread_create(&g1, NULL, gardien, NULL);
    pthread_create(&g2, NULL, gardien, NULL);
    pthread_join(g1, NULL);
    pthread_join(g2, NULL);
    printf("visiteurs : %ld (attendu : %d)\n", compteur, 2 * VISITEURS);
    return 0;
}

pthread_create lance la fonction gardien dans un nouveau fil d'exécution ; pthread_join attend qu'il ait fini (on y revient en fin de chapitre). Les programmes de ce chapitre se compilent avec gcc -std=c11 -Wall -Wextra -Werror -D_POSIX_C_SOURCE=200809L -pthread. Sans optimisation, trois exécutions de suite sur une machine à huit cœurs :

$ ./compteur
visiteurs : 1336530 (attendu : 2000000)
$ ./compteur
visiteurs : 1271531 (attendu : 2000000)
$ ./compteur
visiteurs : 1463361 (attendu : 2000000)

Un tiers des visiteurs perdus, et jamais le même nombre. Compilé avec -O2, le même programme affiche 2 000 000 à chaque fois : le compilateur a remplacé la boucle par une seule addition, et la fenêtre où les gardiens se gênent est devenue si petite qu'on ne la voit plus. Le programme est toujours faux ; l'erreur est seulement cachée, et reviendra le jour où la boucle fera autre chose.

Il faut faire de compteur = compteur + 1 une section critique. Essayons, avec des moyens simples.

Première tentative : des drapeaux

Chaque gardien a un drapeau, qu'il lève quand il est en train de compter. Avant de compter, il attend que le drapeau de l'autre soit baissé :

while (veut[autre])
    ;                               /* on attend que l'autre ait fini */
veut[moi] = 1;
compteur = compteur + 1;            /* section critique */
veut[moi] = 0;

Cela ne marche pas. Les deux gardiens peuvent regarder le drapeau de l'autre en même temps, le trouver baissé tous les deux, lever chacun le leur, et entrer ensemble. Entre le moment où l'on regarde et celui où l'on lève son drapeau, l'autre a le temps de faire de même. Le test et la prise ne forment pas une opération atomique. Le programme complet (avec des variables atomiques pour les drapeaux, voir plus bas) perd toujours des visiteurs :

$ ./tentative1
visiteurs : 1697394 (attendu : 2000000)

Lever son drapeau avant de regarder celui de l'autre ne vaut pas mieux : les deux gardiens peuvent lever le leur en même temps, et attendre chacun que l'autre baisse le sien, pour toujours. C'est un interblocage (deadlock).

Deuxième tentative : chacun son tour

Une variable partagée tour dit quel gardien a le droit de compter. Quand il a fini, il donne le tour à l'autre :

while (tour != moi)
    ;                               /* on attend son tour */
compteur = compteur + 1;            /* section critique */
tour = autre;                       /* on passe la main */

L'exclusion mutuelle est assurée : tour ne désigne qu'un gardien à la fois. Mais les gardiens doivent désormais alterner strictement. Si l'entrée ouest voit passer un million de visiteurs et l'entrée est dix seulement, le gardien ouest, après son onzième visiteur, attend que le gardien est lui rende la main… ce qui n'arrivera jamais. La condition de progrès n'est pas respectée : une tâche qui ne veut pas entrer empêche l'autre d'entrer. Le programme complet ne se termine pas (on l'arrête au bout de cinq secondes) :

$ timeout 5 ./tentative2; echo "code $?"
code 124

La solution : l'algorithme de Peterson

Gary Peterson a publié en 1981 une solution pour deux tâches, qui combine les deux idées : les drapeaux disent qui veut entrer, et le tour départage les deux gardiens quand ils veulent entrer en même temps.

static void entrer(int moi)
{
    int autre = 1 - moi;
    veut[moi] = 1;                  /* je veux entrer */
    tour = autre;                   /* mais je laisse la priorité à l'autre */
    while (veut[autre] && tour == autre)
        ;                           /* j'attends s'il veut entrer et que c'est son tour */
}

static void sortir(int moi)
{
    veut[moi] = 0;
}

Pourquoi ça marche :

• Exclusion mutuelle. Si les deux gardiens sont dans la section critique, chacun a franchi sa boucle d'attente. Le gardien A l'a franchie parce que veut[B] était faux ou que tour valait A. Comme B avait levé son drapeau avant d'écrire tour, c'est que tour valait A. Et symétriquement, tour valait B pour B. Or tour n'a qu'une valeur : celui qui l'a écrit en dernier s'est donné la priorité à l'autre, et c'est lui qui attend.
• Progrès. Si l'autre ne veut pas entrer, son drapeau est baissé, et on entre tout de suite : plus d'alternance forcée.
• Attente bornée. Si l'autre sort puis veut rentrer aussitôt, il écrit tour = moi en rentrant : il ne peut pas passer devant une deuxième fois.

La version correcte :

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

#define VISITEURS 1000000

static long compteur = 0;
static atomic_int veut[2];
static atomic_int tour;

static void entrer(int moi)
{
    int autre = 1 - moi;
    atomic_store(&veut[moi], 1);    /* je veux entrer */
    atomic_store(&tour, autre);     /* mais je laisse la priorité à l'autre */
    while (atomic_load(&veut[autre]) && atomic_load(&tour) == autre)
        ;                           /* j'attends s'il veut entrer et que c'est son tour */
}

static void sortir(int moi)
{
    atomic_store(&veut[moi], 0);
}

static void *gardien(void *arg)
{
    int moi = *(int *)arg;
    for (int i = 0; i < VISITEURS; i++) {
        entrer(moi);
        compteur = compteur + 1;    /* section critique */
        sortir(moi);
    }
    return NULL;
}

int main(void)
{
    pthread_t g[2];
    int id[2] = { 0, 1 };
    for (int i = 0; i < 2; i++)
        pthread_create(&g[i], NULL, gardien, &id[i]);
    for (int i = 0; i < 2; i++)
        pthread_join(g[i], NULL);
    printf("visiteurs : %ld (attendu : %d)\n", compteur, 2 * VISITEURS);
    return 0;
}

$ ./peterson
visiteurs : 2000000 (attendu : 2000000)

Juste à chaque exécution. Peterson a surtout un intérêt historique et pédagogique : il montre qu'on peut assurer l'exclusion mutuelle avec de simples lectures et écritures. En pratique, on utilise les outils du système, présentés plus bas.

Les problèmes de l'attente active

Toutes ces solutions font attendre activement : la tâche qui attend tourne en boucle, en relisant sans cesse une variable. Elle occupe un processeur pour ne rien faire, et le temps passé à attendre est pris à la tâche qui, elle, a du travail utile.

L'inversion de priorité

Pire : l'attente active peut bloquer tout le système. Supposons un ordonnanceur à priorités, qui fait toujours tourner la tâche prête la plus prioritaire. Une tâche B, de basse priorité, entre dans une section critique. Une tâche H, de haute priorité, veut y entrer à son tour, et attend activement. H est prête (elle tourne !), elle est plus prioritaire que B : l'ordonnanceur ne donne plus jamais la main à B, qui ne peut donc jamais sortir de la section critique. H attend B, qui attend le processeur que H occupe.

Même sans attente active, la priorité peut s'inverser : si H dort en attendant B, une tâche M de priorité moyenne, qui n'a rien à voir avec la section critique, peut occuper le processeur à la place de B, et retarder H indéfiniment. C'est ce qui est arrivé en 1997 au robot Mars Pathfinder, sur Mars : une tâche de météo, de basse priorité, tenait un verrou dont avait besoin une tâche de haute priorité, et des tâches de communication, de priorité moyenne, l'empêchaient de le relâcher. Un chien de garde, voyant la tâche prioritaire en retard, redémarrait le robot, encore et encore. On l'a corrigé à distance en activant l'héritage de priorité : une tâche qui tient un verrou attendu par une tâche plus prioritaire hérite temporairement de sa priorité.

La solution est de ne pas attendre activement : une tâche qui ne peut pas entrer doit s'endormir, et être réveillée quand la section critique se libère. Seul le système peut le faire : c'est ce que fournissent les outils suivants.

Les outils de synchronisation

Les verrous (mutex)

Un verrou d'exclusion mutuelle, mutex en anglais (mutual exclusion), a deux opérations :

• verrouiller (pthread_mutex_lock) : si le verrou est libre, on le prend ; sinon, on s'endort jusqu'à ce qu'il se libère, puis on le prend ;
• déverrouiller (pthread_mutex_unlock) : on le rend, et l'une des tâches qui attendaient est réveillée.

Une section critique se place entre les deux :

#include <pthread.h>
#include <stdio.h>

#define VISITEURS 1000000

static long compteur = 0;
static pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;

static void *gardien(void *arg)
{
    (void)arg;
    for (int i = 0; i < VISITEURS; i++) {
        pthread_mutex_lock(&verrou);
        compteur = compteur + 1;
        pthread_mutex_unlock(&verrou);
    }
    return NULL;
}

int main(void)
{
    pthread_t g1, g2;
    pthread_create(&g1, NULL, gardien, NULL);
    pthread_create(&g2, NULL, gardien, NULL);
    pthread_join(g1, NULL);
    pthread_join(g2, NULL);
    printf("visiteurs : %ld (attendu : %d)\n", compteur, 2 * VISITEURS);
    return 0;
}

$ ./mutex
visiteurs : 2000000 (attendu : 2000000)

Seule la tâche qui a verrouillé peut déverrouiller. Et un verrou ne protège une donnée que si tous les accès à cette donnée le prennent : c'est une convention, que le compilateur ne vérifie pas.

Les conditions

Un verrou protège une donnée. Mais souvent, une tâche doit aussi attendre que la donnée soit dans un certain état : qu'une file ne soit plus vide, qu'un travail soit prêt. Tester l'état en boucle, c'est revenir à l'attente active. Une variable de condition permet de s'endormir jusqu'à ce qu'une autre tâche signale que l'état a changé :

• pthread_cond_wait(&cond, &verrou) : libère le verrou et s'endort, d'un seul coup (atomiquement) ; au réveil, reprend le verrou avant de rendre la main ;
• pthread_cond_signal(&cond) : réveille une des tâches qui attendent sur cond ;
• pthread_cond_broadcast(&cond) : les réveille toutes.

Une condition s'utilise toujours avec un verrou, et toujours dans ce schéma :

pthread_mutex_lock(&verrou);
while (!condition_voulue)
    pthread_cond_wait(&cond, &verrou);
/* ici, la condition est vraie, et on tient le verrou */
...
pthread_mutex_unlock(&verrou);

Il faut libérer le verrou en s'endormant, sinon celui qui doit changer l'état ne pourrait jamais le prendre ; et le faire atomiquement, sinon le signal pourrait arriver entre le déverrouillage et l'endormissement, et être perdu. C'est pourquoi pthread_cond_wait fait les deux à la fois.

Les barrières

Une barrière fait attendre un groupe de tâches jusqu'à ce que toutes y soient arrivées. C'est utile quand un calcul se fait par étapes, et que l'étape 2 de chaque tâche a besoin des résultats de l'étape 1 de toutes les autres.

#include <pthread.h>
#include <stdio.h>

#define N 3

static pthread_barrier_t barriere;

static void *travail(void *arg)
{
    int num = *(int *)arg;
    printf("fil %d : étape 1\n", num);
    pthread_barrier_wait(&barriere);    /* personne ne passe avant les autres */
    printf("fil %d : étape 2\n", num);
    return NULL;
}

int main(void)
{
    pthread_t fil[N];
    int id[N];
    pthread_barrier_init(&barriere, NULL, N);
    for (int i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&fil[i], NULL, travail, &id[i]);
    }
    for (int i = 0; i < N; i++)
        pthread_join(fil[i], NULL);
    pthread_barrier_destroy(&barriere);
    return 0;
}

$ ./barriere
fil 0 : étape 1
fil 1 : étape 1
fil 2 : étape 1
fil 2 : étape 2
fil 0 : étape 2
fil 1 : étape 2

L'ordre des lignes change d'une exécution à l'autre, mais les trois « étape 1 » viennent toujours avant les « étape 2 ».

Le problème des lecteurs et des rédacteurs

Une donnée partagée, un annuaire par exemple, est lue très souvent et modifiée rarement. Un verrou ordinaire ne laisse passer qu'une tâche à la fois, même si elles ne font toutes que lire. Or plusieurs lectures simultanées ne posent aucun problème : seules les écritures doivent être seules.

Un verrou lecteurs-rédacteurs a deux façons d'être pris : en lecture (plusieurs tâches à la fois) ou en écriture (une seule, et aucun lecteur) :

static pthread_rwlock_t verrou = PTHREAD_RWLOCK_INITIALIZER;
static int annuaire[100];           /* la donnée partagée */

static int lire(int i)
{
    pthread_rwlock_rdlock(&verrou); /* plusieurs lecteurs à la fois */
    int x = annuaire[i];
    pthread_rwlock_unlock(&verrou);
    return x;
}

static void ecrire(int i, int x)
{
    pthread_rwlock_wrlock(&verrou); /* un rédacteur, seul */
    annuaire[i] = x;
    pthread_rwlock_unlock(&verrou);
}

Reste une question de politique : si des lecteurs arrivent sans cesse, un rédacteur peut attendre indéfiniment qu'il n'y en ait plus aucun. C'est la famine. Les implémentations choisissent de favoriser les lecteurs ou les rédacteurs ; sous Linux, le choix par défaut favorise les lecteurs.

Un problème plus évolué : producteurs et consommateurs

Le problème

Des tâches produisent des données (des requêtes qui arrivent, des images décodées), d'autres les consomment (les traitent, les affichent). Entre les deux, une file : les producteurs y déposent, les consommateurs y retirent, dans l'ordre d'arrivée. C'est le schéma de tous les serveurs, et c'est aussi celui d'un tube entre deux processus (chapitre 5).

Trois contraintes :

1. Exclusion mutuelle : la file est partagée, un seul à la fois la modifie.
2. Un consommateur qui trouve la file vide attend qu'un producteur y dépose quelque chose.
3. La file a une capacité bornée : un producteur qui la trouve pleine attend qu'un consommateur y fasse de la place.

Avec un verrou et deux conditions

On range la file dans un tableau circulaire. Le verrou assure la contrainte 1 ; la condition non_vide fait attendre les consommateurs, la condition non_pleine les producteurs.

#include <pthread.h>
#include <stdio.h>

#define CAPACITE 4
#define PRODUITS 20

/* Une file circulaire bornée, protégée par un verrou et deux conditions. */
static int file[CAPACITE];
static int tete = 0, nb = 0;
static pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;
static pthread_cond_t non_vide = PTHREAD_COND_INITIALIZER;
static pthread_cond_t non_pleine = PTHREAD_COND_INITIALIZER;

static void deposer(int x)
{
    pthread_mutex_lock(&verrou);
    while (nb == CAPACITE)
        pthread_cond_wait(&non_pleine, &verrou);
    file[(tete + nb) % CAPACITE] = x;
    nb++;
    pthread_cond_signal(&non_vide);
    pthread_mutex_unlock(&verrou);
}

static int retirer(void)
{
    pthread_mutex_lock(&verrou);
    while (nb == 0)
        pthread_cond_wait(&non_vide, &verrou);
    int x = file[tete];
    tete = (tete + 1) % CAPACITE;
    nb--;
    pthread_cond_signal(&non_pleine);
    pthread_mutex_unlock(&verrou);
    return x;
}

static void *producteur(void *arg)
{
    (void)arg;
    for (int i = 1; i <= PRODUITS; i++)
        deposer(i);
    deposer(-1);                    /* marque de fin */
    return NULL;
}

static void *consommateur(void *arg)
{
    (void)arg;
    long total = 0;
    int x;
    while ((x = retirer()) != -1)
        total += x;
    printf("consommateur : total = %ld\n", total);
    return NULL;
}

int main(void)
{
    pthread_t p, c;
    pthread_create(&c, NULL, consommateur, NULL);
    pthread_create(&p, NULL, producteur, NULL);
    pthread_join(p, NULL);
    pthread_join(c, NULL);
    return 0;
}

$ ./file_bornee
consommateur : total = 210

La file ne contient jamais plus de quatre éléments : le producteur est freiné par le consommateur. Le producteur signale la fin par une valeur spéciale, -1, que le consommateur reconnaît.

Les sémaphores

Définition

Le sémaphore a été inventé par Edsger Dijkstra en 1965. C'est un compteur entier, jamais négatif, avec deux opérations atomiques :

• P (du néerlandais proberen, essayer ; en POSIX sem_wait) : si le compteur est positif, le décrémenter ; sinon, s'endormir jusqu'à ce qu'il le devienne, puis le décrémenter ;
• V (verhogen, augmenter ; en POSIX sem_post) : incrémenter le compteur, et réveiller une tâche qui attendait.

On peut voir le compteur comme un nombre de jetons : P en prend un (en attendant s'il n'y en a plus), V en rend un. Un sémaphore initialisé à 1 est un verrou. Initialisé à $n$, il laisse passer $n$ tâches à la fois. Initialisé à 0, il sert à attendre un événement : P bloque jusqu'à ce qu'une autre tâche fasse V.

#include <semaphore.h>

int sem_init(sem_t *s, int partage, unsigned valeur);   /* partage = 0 : entre fils d'un même processus */
int sem_wait(sem_t *s);                                 /* P */
int sem_post(sem_t *s);                                 /* V */

Contrairement à un verrou, un sémaphore n'a pas de propriétaire : une tâche peut faire V sur un sémaphore sur lequel une autre a fait P. C'est ce qui permet de les utiliser pour faire signe d'une tâche à l'autre.

Producteurs et consommateurs avec des sémaphores

Trois sémaphores suffisent : places compte les cases libres (initialisé à la capacité), elements compte les cases pleines (initialisé à 0), exclusion protège la file (initialisé à 1). Plus besoin de tester si la file est pleine ou vide : les compteurs le font.

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>

#define CAPACITE 4
#define PRODUITS 1000
#define NPROD 3

static int file[CAPACITE];
static int entree = 0, sortie = 0;
static sem_t places;                /* nombre de cases libres */
static sem_t elements;              /* nombre de cases pleines */
static sem_t exclusion;             /* un seul à la fois dans la file */

static void deposer(int x)
{
    sem_wait(&places);              /* P(places) */
    sem_wait(&exclusion);
    file[entree] = x;
    entree = (entree + 1) % CAPACITE;
    sem_post(&exclusion);
    sem_post(&elements);            /* V(elements) */
}

static int retirer(void)
{
    sem_wait(&elements);
    sem_wait(&exclusion);
    int x = file[sortie];
    sortie = (sortie + 1) % CAPACITE;
    sem_post(&exclusion);
    sem_post(&places);
    return x;
}

static void *producteur(void *arg)
{
    (void)arg;
    for (int i = 1; i <= PRODUITS; i++)
        deposer(i);
    return NULL;
}

int main(void)
{
    sem_init(&places, 0, CAPACITE);
    sem_init(&elements, 0, 0);
    sem_init(&exclusion, 0, 1);

    pthread_t p[NPROD];
    for (int k = 0; k < NPROD; k++)
        pthread_create(&p[k], NULL, producteur, NULL);

    long total = 0;                 /* main est le consommateur */
    for (int i = 0; i < NPROD * PRODUITS; i++)
        total += retirer();
    for (int k = 0; k < NPROD; k++)
        pthread_join(p[k], NULL);
    printf("total = %ld (attendu : %d)\n", total, NPROD * PRODUITS * (PRODUITS + 1) / 2);
    return 0;
}

$ ./file_semaphores
total = 1501500 (attendu : 1501500)

La notion de threads

Définition générale

Là où fork copie toute la mémoire, créer un fil d'exécution ne demande qu'une nouvelle pile. Et là où deux processus doivent passer par un tube pour échanger, deux fils d'exécution n'ont qu'à écrire dans une variable globale… ce qui est à la fois leur force et, on l'a vu tout au long du chapitre, leur danger.

Types de threads

Qui gère les fils d'exécution : le noyau du système, ou une bibliothèque dans le processus ?

• Les fils utilisateur sont gérés par une bibliothèque, sans que le noyau le sache : il ne voit qu'un processus. Créer un fil et passer de l'un à l'autre est très rapide (aucun appel système). Mais le noyau n'accorde au processus qu'un seul processeur, et si un fil fait un appel système bloquant (un read sur le clavier), c'est tout le processus qui s'endort.
• Les fils noyau sont gérés par le système, qui les ordonnance comme des processus. Ils peuvent tourner sur plusieurs processeurs, et un fil bloqué ne bloque que lui ; en échange, chaque création et chaque changement de fil passe par le noyau.

On décrit les implémentations par la façon dont elles associent les fils du programme aux fils du noyau :

Avantages et inconvénients

Par rapport à plusieurs processus, les fils d'exécution :

• se créent et se changent plus vite ;
• communiquent sans effort, par la mémoire partagée ;
• mais ne sont pas isolés : un fil qui écrit au mauvais endroit corrompt la mémoire de tous les autres, et une erreur de segmentation dans l'un tue tout le processus ;
• et leur mémoire partagée impose de synchroniser chaque accès, avec tous les pièges de ce chapitre.

Un navigateur web utilise les deux : un processus par onglet, pour qu'un onglet qui plante n'emporte pas les autres, et plusieurs fils d'exécution dans chaque processus.

Programmer avec les threads POSIX

La norme POSIX définit une bibliothèque de fils d'exécution, les pthreads (<pthread.h>). On compile avec l'option -pthread.

Créer et attendre

int pthread_create(pthread_t *fil, const pthread_attr_t *attributs,
                   void *(*fonction)(void *), void *argument);
int pthread_join(pthread_t fil, void **resultat);

• pthread_create lance fonction(argument) dans un nouveau fil d'exécution, et range son identifiant dans *fil. attributs peut valoir NULL (réglages par défaut). Elle rend 0 en cas de succès, un code d'erreur sinon.
• La fonction prend un void * et rend un void * : c'est la façon générique, en C, de passer « n'importe quoi » (chapitre 2). On lui passe l'adresse d'une donnée, qu'elle reconvertit dans le bon type.
• pthread_join attend la fin du fil, et récupère ce que sa fonction a rendu. C'est l'équivalent de wait pour les processus : un fil terminé qu'on n'attend pas garde ses ressources.
• Quand main se termine, le processus entier se termine, avec tous ses fils. Il faut donc les attendre avant.

Pour passer plusieurs données, et récupérer un résultat, on passe l'adresse d'une structure. Voici la somme d'un grand tableau, coupée en quatre tranches, une par fil :

#include <pthread.h>
#include <stdio.h>

#define N 4
#define TAILLE 1000000

static int tab[TAILLE];

struct tranche {
    int debut, fin;                 /* on somme tab[debut .. fin-1] */
    long somme;                     /* le résultat, rempli par le fil */
};

static void *sommer(void *arg)
{
    struct tranche *t = arg;
    t->somme = 0;
    for (int i = t->debut; i < t->fin; i++)
        t->somme += tab[i];
    return NULL;
}

int main(void)
{
    for (int i = 0; i < TAILLE; i++)
        tab[i] = i % 10;

    pthread_t fil[N];
    struct tranche tr[N];           /* une structure par fil : rien de partagé */
    for (int k = 0; k < N; k++) {
        tr[k].debut = k * TAILLE / N;
        tr[k].fin = (k + 1) * TAILLE / N;
        pthread_create(&fil[k], NULL, sommer, &tr[k]);
    }

    long total = 0;
    for (int k = 0; k < N; k++) {
        pthread_join(fil[k], NULL);
        total += tr[k].somme;
    }
    printf("somme = %ld\n", total);
    return 0;
}

$ ./somme
somme = 4500000

Aucun verrou ici : chaque fil écrit dans sa propre structure, et main ne lit les résultats qu'après pthread_join. La meilleure synchronisation est celle dont on n'a pas besoin : on découpe le travail pour que les fils partagent le moins possible.

Le piège de la variable de boucle

#include <pthread.h>
#include <stdio.h>

#define N 4

static void *travail(void *arg)
{
    int num = *(int *)arg;
    printf("je suis le fil %d\n", num);
    return NULL;
}

int main(void)
{
    pthread_t fil[N];
    for (int i = 0; i < N; i++)
        pthread_create(&fil[i], NULL, travail, &i);   /* FAUX */
    for (int i = 0; i < N; i++)
        pthread_join(fil[i], NULL);
    return 0;
}

$ ./boucle
je suis le fil 2
je suis le fil 3
je suis le fil 4
je suis le fil 4

Les quatre fils reçoivent la même adresse, celle de i. Chacun lit i quand il démarre, c'est-à-dire n'importe quand : la boucle a pu avancer entre-temps, ou même être finie (d'où le 4). Pire, une fois la boucle terminée, i n'existe plus, et son adresse peut être réutilisée pour autre chose. Le résultat change à chaque exécution.

Conclusion

Dès que plusieurs tâches partagent une donnée et que l'une au moins la modifie, il faut synchroniser. Retenons :

• une ligne de C n'est pas atomique ; sans protection, les mises à jour se perdent, et d'une exécution à l'autre, pas toujours ;
• on protège une section critique par un verrou ; on attend un état par une condition, toujours dans une boucle while ; les sémaphores comptent des ressources ;
• on évite l'interblocage en prenant toujours les verrous dans le même ordre ;
• et surtout, on partage le moins possible : chaque fil travaille sur ses propres données, et on ne met en commun que les résultats.

Ce qui rend la concurrence difficile, ce n'est pas le code, qui reste court : c'est qu'on ne peut pas la tester. Un programme concurrent juste se démontre, en raisonnant sur tous les entrelacements possibles, comme on l'a fait pour Peterson.