Concurrence et synchronisation

22.1 Plusieurs fils dans un même programme

Jusqu'ici, un programme faisait une chose à la fois. Les processeurs modernes ont plusieurs cœurs, et un programme peut les employer tous — en lançant plusieurs fils d'exécution qui partagent la même mémoire.

Le programme borne strictement le périmètre : « l'apprentissage des notions liées au parallélisme d'exécution se limite au cas de fils d'exécution (threads) internes à un processus, sur une machine. Les problèmes d'algorithmes répartis et les notions liées aux réseaux et à la communication asynchrone sont hors programme. » Et pour les fils eux-mêmes : « on s'en tient aux notions de base : création, attente de terminaison ».

#include <pthread.h>

void* travail(void* arg) { /* ... */ return NULL; }

int main(void) {
    pthread_t fil;
    pthread_create(&fil, NULL, travail, NULL);   /* attributs par défaut */
    /* le fil principal continue PENDANT ce temps */
    pthread_join(fil, NULL);                     /* on attend sa terminaison */
    return 0;
}

let fil = Thread.create travail () in
Thread.join fil

22.2 Le non-déterminisme

Exemple 22.2Le compteur partagé, ou pourquoi $x=x+1$ n'est pas une opération

int compteur = 0;      /* PARTAGÉ par les deux fils */

void* incrementer(void* arg) {
    for (int i = 0; i < 100000; i = i + 1) { compteur = compteur + 1; }
    return NULL;
}
/* deux fils lancés : on attend 200000. On obtient un nombre INFÉRIEUR,
   et différent à chaque exécution. */

La raison tient à ce que fait vraiment la machine. compteur = compteur + 1 n'est pas une instruction mais trois :

Les deux fils ont lu $0$, ajouté $1$, écrit $1$. Un incrément a été perdu. C'est une course critique (race condition).

22.3 Résoudre l'exclusion mutuelle par le logiciel

Le programme demande deux algorithmes : « algorithme de Peterson pour deux fils d'exécution, algorithme de la boulangerie de Lamport pour plusieurs fils d'exécution ». Ils sont présentés « en privilégiant le pseudo-code ».

22.3.1 L'algorithme de Peterson

bool veut[2] = {false, false};   /* veut[i] : le fil i demande à entrer */
int  tour = 0;                   /* à qui la priorité, en cas de conflit */

/* Protocole du fil i (l'autre est j = 1 - i). */
void entrer(int i) {
    int j = 1 - i;
    veut[i] = true;              /* 1. j'annonce mon intention */
    tour = j;                    /* 2. je CÈDE le tour à l'autre */
    while (veut[j] && tour == j) { /* attente active */ }
}

void sortir(int i) {
    veut[i] = false;             /* je libère */
}