Aller au contenu

L'objectif de ce chapitre est de considérer des programmes qui s'exécutent au même moment, soit chacun leur tour, soit simultanément.

On va ainsi observer deux phénomènes majeurs :

  • la concurrence quand plusieurs programmes veulent accéder à une même ressource
  • le parallélisme quand deux programmes s'exécutent au même moment sur des unités de calcul différentes (des processeurs ou des cœurs)

Il faut donc, pour que les interactions se passent bien, qu'on soit capable de gérer la synchronisation entre les programmes.

Remarque

La caractérisation de la concurrence et du parallélisme faite ici est assez naïve mais convient pour une première exposition.

Processus, threads

Processus

Un processus est un programme s'exécutant dans un environnement. Il dispose du code binaire du programme, et des bibliothèques qu'il utilise, ainsi qu'un espace mémoire dont on a vu l'organisation dans un précédent chapitre.

Quand un programme s'exécute, il a plein accès à une unité de calcul du processeur. Il peut ainsi modifier les registres du processeur.

Remarque

Suite à la limite d'évolution des fréquences d'horloge de processeur, il y a eu un développement des processeurs multi-cœurs (cores en anglais) permettant de proposer des unités de calculs indépendantes mais reliées. Mettant ainsi à profit des mécanismes partagés entre les différents cœurs.

C'est pour correspondre à cette réalité qu'on a fait le choix ici de parler d'unité de calcul d'un processeur.

Pour autant, un programme ne s'exécute pas d'une traite à chaque lancement. Si c'était le cas, une boucle while pourrait ainsi bloquer le processeur. En fait, le système d'exploitation définit des interruptions qui permettent dans certains cas au processeur d'interrompre l'exécution du programme en cours pour basculer dans le système d'exploitation.

C'est ainsi que le système d'exploitation va pouvoir distribuer l'accès au processeur à différents programmes. Chaque fois qu'il faut passer d'un programme à un autre, il est nécessaire de restaurer tout son environnement d'exécution : on parle de contexte d'exécution, il contient l'organisation de la mémoire mais aussi des copies des valeurs des registres avant la bascule. Ce procédé est assez coûteux en temps et s'appelle la bascule de contexte, ou context switching.

Pour qu'un processus en lance un autre, par exemple pour réaliser une autre tâche en parallèle, il est nécessaire qu'il se duplique complètement. Un appel système est disponible pour cela fork(). Toute mémoire partagée entre les deux processus doit alors avoir été créée explicitement avec des appels systèmes. Ce modèle d'exécution n'est pas au programme en MPI.

Threads

Le point de départ des threads, ou fils d'exécution en français, est qu'une séparation complète d'un processus en deux copies est inutilement lourde :

  • elle demande de copier toutes les données d'un processus, bien qu'on puisse imaginer que la copie est superficielle
  • elle limite les possibilités de partage immédiat de mémoire

Un thread est juste une exécution d'un processus, c'est-à-dire où on est dans l'exécution et quel est le contexte, i.e. la pile d'exécution. Il est toujours nécessaire de sauvegarder le contexte des registres pour passer d'un thread à un autre, mais deux threads lancés par un même processus partageront tout le reste de la mémoire.

Ainsi, les threads d'un même processus partagent :

  • les variables globales
  • le tas

mais ont un accès exclusif et personnel

  • au processeur et à ses registres
  • à leur pile d'exécution

Pour passer d'un thread à un autre, il est encore nécessaire de faire une bascule de contexte. Cependant, on peut imaginer que la bascule de contexte entre deux threads d'un même processus peut être réalisée plus rapidement qu'entre deux processus.

Le fait que la mémoire soit partagée permet de communiquer entre les threads de manière directe.

Les différents threads vont pouvoir être interrompus par le système comme les processus. C'est le système d'exploitation qui va ainsi être responsable du choix du thread à exécuter. Quand on dispose de plusieurs unités de calcul, les threads peuvent s'exécuter en parallèle.

C'est le cadre choisi pour ce chapitre en MPI.

Threads coopératifs

Comme pour les processus, les threads sont gérés au niveau du système d'exploitation. Cela n'est donc pas forcément portable d'un système à un autre.

Il est possible de permettre la concurrence qu'offrent les threads sans qu'ils correspondent à de vrais threads systèmes. On parle de threads coopératifs car, en l'absence d'intervention du système d'exploitation, ce sont ces threads eux-mêmes qui vont laisser la main, soit manuellement avec une opération de yield, soit en redéfinissant les appels systèmes.

Des bibliothèques comme lwt (en OCaml) permettent de gérer cela.

Quelle utilité pratique ?

Si l'essentiel du cours de MP2I/MPI a été traité dans le cadre d'une exécution séquentielle d'un unique programme, il serait peu avisé d'en déduire qu'il s'agit du cadre standard. La plupart des programmes peuvent tirer parti de la concurrence et/ou du parallélisme.

Les programmes devant effectuer de lourdes tâches de calcul ont intérêt à exploiter le matériel au maximum, et sur un processeur à huit cœurs, il semble peu efficace d'en utiliser un seul. Au premier abord, on pourrait penser obtenir un facteur x8 dans l'efficacité dans ce cas. Cependant, pour que les calculs se déroulent bien, le parallélisme a un coût et utiliser à 100% le processeur pour un calcul est un objectif inaccessible sauf dans des cas très spécifiques où on effectue des calculs sans liens, comme pour du lancer de rayon sommaire.

Les programmes interactifs vont bénéficier de la concurrence pour ne pas bloquer l'interface. Afin d'avoir une interface réactive, il ne faut pas qu'un calcul ou un appel système prenne du temps et empêche d'interagir avec elle.

Lancer des threads en C

Pour créer des threads, on utilise la bibliothèque pthread dont l'en-tête est pthread.h.

Remarque

Si vous avez un problème à l'édition de lien, il faut rajouter -lpthread.

Pour créer un thread :

  • on définit une valeur pthread_t t qui va contenir les données du thread
  • on appelle pthread_create(&t, NULL, f, arg); où f est une fonction de prototype void *f(void *arg); et arg est une valeur de type void *

Remarque

En C, le type void * joue un rôle particulier :

  • toute valeur de type T *a peut être convertie en un void *
  • toute valeur de type void *v peut être convertie en un T *

Ces conversions sont implicites en C, il n'y a rien à écrire.

Ainsi, le code suivant est correct :

#include <stdio.h>

void incremente(void *a)
{
    int *t = a;
    *t = *t + 1;
}

int main(void)
{
    int n = 3;
    incremente(&n);
    printf("n = %d\n", n);
}

Ainsi, il est possible de faire des fonctions génériques en utilisant le type void * comme une sorte de 'a en OCaml.

Comme le type int est, sur les architectures usuelles, plus petit que le type void * en termes de taille, il est possible de faire des conversions explicites pour ne pas avoir à définir une variable comme n ici.

Par exemple, on définit la fonction incremente qui va prendre un entier en argument par pointeur et l'incrémenter.

void *incremente(void *arg)
{
    int *n = arg;
    *n = *n + 1;

    return NULL; // pas de retour
}

On peut alors lancer cette fonction dans un thread :

pthread_t t;
int v = 3;
pthread_create(&t, NULL, incremente, &v);

Pour attendre qu'un thread t termine on appelle pthread_join(t, NULL) :

pthread_join(t, NULL);
printf("%d\n", v);

Remarque

Il est également possible d'avoir une valeur de retour mais c'est hors programme.

Pour lancer plusieurs threads, il suffit de faire plusieurs appels à pthread_create.

Remarque

Lancer deux threads

Si on écrit :

pthread_t t1, t2;
pthread_create(&t1, NULL, f, NULL);
pthread_join(t1, NULL);
pthread_create(&t2, NULL, f, NULL);
pthread_join(t2, NULL);

Les deux threads ne vont pas s'exécuter en même temps car on attend avec le join que le premier thread termine pour lancer le second.

Il faut donc créer les threads puis les attendre :

pthread_t t1, t2;
pthread_create(&t1, NULL, f, NULL);
pthread_create(&t2, NULL, f, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);

Ici, on privilégie l'attente sur le premier, mais on pourrait le faire sur le second.

Il arrive qu'on ait besoin de passer un identificateur pour chaque thread, son indice dans le tableau convient alors simplement. Avec les limites du programme, il faut alors écrire :

pthread_t t1, t2;
int i1 = 0, i2 = 1;
pthread_create(&t1, NULL, f, &i1);
pthread_create(&t2, NULL, f, &i2);
pthread_join(t1, NULL);
pthread_join(t2, NULL);

Remarque

Lancer n threads au démarrage

Pour lancer un grand nombre de threads, il va être nécessaire de stocker les pthread_t pour pouvoir appeler join. Le plus simple est alors de passer par un pthread_t[].

Si le nombre est connu à l'avance, on peut réaliser un tableau statique :

pthread_t t[10];
for(int i = 0; i < 10; i++) // on les lance
    pthread_create(&t[i], NULL, f, NULL);
// ensuite quand on veut les attendre, il faut refaire une boucle
for(int i = 0; i < 10; i++)
    pthread_join(t[i], NULL);

Si le nombre n'est pas connu, on peut effectuer un tableau avec malloc, mais il ne faut pas oublier de libérer après les join.

Si on a besoin d'avoir les identificateurs pour les threads, dans les limites du programme, c'est un peu maladroit, il faut réaliser un tableau d'entiers pour les indices :

pthread_t t[10];
int t_idx[10];
for(int i = 0; i < 10; i++) { // on les lance
    t_idx[i] = i;
    pthread_create(&t[i], NULL, f, &t_idx[i]);
}

Remarque

Avancé : Lancer des threads avec un pool

Il n'est pas rare d'avoir besoin d'effectuer des tâches à la volée et avoir des tableaux de pthread_t n'est pas le plus souple. On utilise plutôt un sac de pthread_t :

  • quand on lance un nouveau thread, on l'ajoute dans le sac
  • en sortie de programme, on réalise des join(retire(sac)) tant que le sac est non vide.

Section critique et exclusion mutuelle

Définition

Définition

On appelle section critique une suite d'instructions qui ne peut pas être exécutée par deux threads en même temps. Cette propriété est appelée l'exclusion mutuelle.

Remarque

Cela suppose une symétrie entre les threads qui n'est pas toujours souhaitable. Parfois, deux threads doivent exécuter deux suites d'instructions différentes mais il faut tout de même s'assurer qu'il y a exclusion mutuelle, on parlera alors encore abusivement de section critique.

Exemple de section critique : compteur partagé

On considère ici deux threads \(t_0\) et \(t_1\) qui vont chacun incrémenter \(n\) fois un compteur entier global initialement à 0.

Le pseudo-code de chaque thread est donc :

Répéter n fois
    compteur = compteur + 1

On s'attendrait ainsi au fait qu'au bout de \(2n\) incréments, la valeur du compteur soit à \(2n\). Cependant, en exécutant ce programme en présence de parallélisme, on constate que la valeur du compteur n'est pas déterministe et qu'elle est inférieure à \(2n\).

Notons \(lit_i\) et \(ecrit_i\) les événements indiquant que le thread \(t_i\) va lire ou écrire dans le compteur. Ces événements ont un temps de début et un temps de complétion, si le temps de complétion de \(e\) est inférieur au temps de départ de \(e'\), on notera \(e \rightarrow e'\).

Remarque

La relation \(\rightarrow\) est une relation d'ordre stricte partielle. Deux événements sont incomparables quand il existe un instant pendant lequel les deux événements se produisent.

On a donc deux suites d'événements : \(lit_i \rightarrow ecrit_i\) qui vont s'entrelacer.

Si on observe

\[ lit_0 \rightarrow ecrit_0 \rightarrow lit_1 \rightarrow ecrit_1 \]

tout se passe bien, si la valeur du compteur était \(x\) au départ, le thread 0 va lire \(x\), écrire \(x+1\), le thread 1 va lire \(x+1\) et écrire \(x+2\).

Mais, si on observe

\[ lit_1 \rightarrow ecrit_0 \text{ et } lit_0 \rightarrow ecrit_1 \]

alors les deux threads vont lire \(x\) et écrire \(x+1\), ce qui ne va pas réaliser les deux incrémentations.

Ces incrémentations perdues sont celles qui induisent une valeur plus faible du compteur.

Remarque

Même si ça a peu de chances de se produire en pratique, car cela signifierait qu'on a interrompu un thread entre l'évaluation et l'affectation, il peut être intéressant de considérer que le problème se pose même en l'absence de vrai parallélisme.

Modèle mémoire

Afin de raisonner, on va adopter un modèle mémoire simple, même s'il n'est pas forcément réaliste.

On fait ainsi plusieurs hypothèses :

  • Écritures simultanées : si deux écritures en mémoire ont lieu en même temps à la même adresse, on suppose que la dernière écriture est complète. Si les deux finissent en même temps, celle qui est effectivement complétée est non déterministe.
  • Séquentialité des accès : si deux accès ont lieu à la suite, ils sont effectivement réalisés dans cet ordre en mémoire.
  • Pas d'optimisation : toutes les instructions d'écriture ou de lecture sont effectuées dans le code final.

Remarque

Ces hypothèses peuvent sembler très naturelles mais elles sont peu réalistes dans un contexte moderne. On cite ici ce qui pourrait se passer en pratique :

  • Écritures simultanées : rien ne dit qu'il y a atomicité des écritures de données pour certaines tailles de valeurs. Ainsi, un entier sur 64 bits pourrait être décomposé en deux entiers sur 32 bits, et l'écriture des deux parties qui en résulte pourrait ne pas être cohérente. Pour faire un exemple plus visuel, imaginons qu'un thread écrive AA pendant qu'un autre écrit BB, on pourrait se retrouver avec AB ou BA ce qui ne correspond à aucune écriture réelle.
  • Séquentialité des accès : chaque écriture mémoire n'est pas faite directement, elle peut passer par un cache propre au thread et n'être réalisée qu'à la fin d'une suite d'opérations. Pour ne pas avoir ce problème, on peut utiliser des barrières mémoires.
  • Pas d'optimisation : vu du point de vue d'un seul thread, certaines instructions que l'on va écrire semblent être inutiles, elles ne sont là que pour gérer l'interaction entre plusieurs threads. Si on ne fait pas attention, le compilateur risque de les optimiser.

Instructions atomiques

Afin de faciliter la synchronisation, le processeur dispose d'instructions atomiques : elles effectuent une lecture suivie d'une écriture en mémoire sans qu'aucun autre accès à cette case ne puisse s'intercaler, comme si elles étaient exécutées en section critique.

On a notamment les deux instructions :

  • fetch and add pour incrémenter une valeur en mémoire sans problème entre la lecture des données et l'écriture
  • test and set pour écrire true dans une case mémoire tout en renvoyant l'ancienne valeur de cette case (ce qui permet de tester et de modifier un drapeau en une seule opération).

Verrou, mutex

Définition

Définition

Un verrou (en anglais lock) est une primitive qui permet d'assurer l'exclusion mutuelle entre deux ou plusieurs threads.

Il s'agit d'un type verrou et de quatre opérations :

  • void verrou_init(verrou *) alloue et initialise le verrou
  • void verrou_detruit(verrou *) détruit le verrou
  • void verrou_verrouille(verrou *) attend que le verrou soit déverrouillé et le verrouille
  • void verrou_deverrouille(verrou *) déverrouille le verrou

En anglais, on utilise les termes lock et unlock pour les deux opérations. Un verrou est plus souvent appelé un mutex, car sa raison d'être est de garantir l'exclusion mutuelle (mutual exclusion).

Le cas usuel d'utilisation du verrou est :

verrou_verrouille(&v);
// SECTION CRITIQUE
verrou_deverrouille(&v);

Quand on parlera des propriétés d'un verrou, on supposera qu'il est toujours utilisé dans ce cadre-là.

Remarque

L'attente du verrou peut être réalisée :

  • par une boucle active, un while, on parle alors d'attente active
  • en utilisant un mécanisme du système d'exploitation pour qu'il réveille le thread quand le verrou est disponible.

Propriétés d'un verrou

On peut demander plusieurs propriétés pour un verrou :

  • l'exclusion mutuelle, un seul thread peut exécuter la section critique à un moment donné
  • l'absence d'interblocage : si un thread effectue un appel à verrouille alors au moins un thread, peut-être un autre, va rentrer en section critique ensuite, on parle aussi de vivacité
  • l'absence de famine : si un thread effectue un appel à verrouille, il ne va pas attendre indéfiniment
  • premier arrivé, premier servi : si un thread demande à verrouiller avant un autre, il prendra le verrou avant lui

Pour les deux propriétés de vivacité, on suppose naturellement que chaque thread en section critique finit par en sortir (et donc par appeler deverrouille) et que chaque thread finit toujours par être exécuté par l'ordonnanceur.

Remarque

Pour donner un sens précis à demander avant, on découpe verrouille en une première partie, appelée porte d'entrée, qui s'exécute en un nombre borné d'étapes (sans attente), suivie de la partie d'attente. Un thread \(A\) demande le verrou avant un thread \(B\) quand \(A\) a terminé sa porte d'entrée avant que \(B\) ne commence la sienne.

On a alors le théorème suivant :

Théorème

  • Si un verrou vérifie premier arrivé, premier servi et l'absence d'interblocage, alors il y a absence de famine.
  • S'il y a absence de famine, alors il y a absence d'interblocage.
Preuve
  • On considère \(n\) threads et un thread \(A\) qui termine sa porte d'entrée. Chaque thread n'ayant qu'une demande en cours à la fois, au plus \(n-1\) threads ont commencé leur porte d'entrée avant que \(A\) n'ait fini la sienne sans être encore entrés en section critique. Tout autre thread qui demande le verrou commence sa porte d'entrée après la fin de celle de \(A\), donc passe après \(A\) par la propriété premier arrivé, premier servi. Par absence d'interblocage, tant que \(A\) attend, des threads entrent en section critique : ce ne peuvent être que les au plus \(n-1\) threads précédents, chacun au plus une fois avant \(A\). Donc \(A\) finit par entrer en section critique.
  • Si un thread appelle verrouille, par absence de famine, ce thread lui-même finit par entrer en section critique, ce qui est plus fort que l'absence d'interblocage.

Remarque

L'hypothèse d'absence d'interblocage est nécessaire dans le premier point : un verrou qui ne laisse jamais entrer personne vérifie trivialement premier arrivé, premier servi.

Le verrou de Peterson

On considère un problème de section critique à deux threads, on suppose que chaque thread a un identifiant 0 ou 1 qu'il connaît. On peut reprendre l'exemple du compteur partagé et on va chercher à remplir la partie en commentaire avec les variables définissant le verrou et le code des fonctions associées. Ici, on passe l'identificateur du thread au verrou.

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

int compteur = 0;
int N = 100000;

/*
 * les variables globales permettant de gérer le verrou
 * Le code de verrouille et de deverrouille
 */

void *incremente(void *arg)
{
    int *i_arg = arg;
    int id = *i_arg; // le numéro du thread

    for(int i = 0; i < N; i++) {
        verrouille(id);
        compteur = compteur + 1;
        deverrouille(id);
    }
    return NULL;
}

int main(void)
{
    pthread_t t0, t1;
    int i0 = 0, i1 = 1;
    pthread_create(&t0, NULL, incremente, &i0);
    pthread_create(&t1, NULL, incremente, &i1);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);
    printf("compteur = %d (attendu %d)\n", compteur, 2 * N);
}

Première idée : des drapeaux spécifiques

On considère deux drapeaux indiquant si un thread veut verrouiller ainsi qu'un système de politesse : tant qu'un autre thread veut verrouiller, on attend.

bool flags[2] = {}; // initialise deux flags à false

void verrouille(int id)
{
    int autre = 1 - id;

    flags[id] = true;
    while(flags[autre]) { // attente active
    }
}

void deverrouille(int id)
{
    flags[id] = false;
}

Théorème

Ce verrou satisfait l'exclusion mutuelle.

Preuve

Par l'absurde, supposons que les deux threads sont simultanément dans la section critique. On va raisonner sur le dernier appel à verrouille ayant été effectué par chaque thread.

Comme le thread 0 a réussi à obtenir le verrou, il a réalisé la suite d'événements : \(ecrit_0\)(flags[0] = true) \(\rightarrow\) \(lit_0\)(flags[1] == false) \(\rightarrow SC_0\) où \(SC_0\) est la section critique pour le thread 0.

De même, le thread 1 a réalisé : \(ecrit_1\)(flags[1] = true) \(\rightarrow\) \(lit_1\)(flags[0] == false) \(\rightarrow SC_1\).

Comme le thread 0 a lu flags[1] == false alors que le thread 1 ne remet flags[1] à false qu'en sortant de sa section critique, c'est forcément que l'écriture flags[1] = true a été réalisée ensuite : \(lit_0\)(flags[1] == false) \(\rightarrow\) \(ecrit_1\)(flags[1] = true).

Par transitivité, on a donc \(ecrit_0\)(flags[0] = true) \(\rightarrow\) \(ecrit_1\)(flags[1] = true).

Or, par symétrie, on peut faire le même raisonnement en échangeant les threads 0 et 1, donc on a également \(ecrit_1\)(flags[1] = true) \(\rightarrow\) \(ecrit_0\)(flags[0] = true).

Comme la relation \(\rightarrow\) est un ordre strict, c'est impossible.

Contradiction.

Si jamais deux threads appellent verrouille au même moment (plus précisément, si chacun écrit son drapeau avant que l'autre ne lise le sien), chacun va attendre dans la boucle while sans espoir que la valeur flags qu'ils observent ne puisse changer vu que l'autre thread responsable sera également bloqué.

Ainsi, il y a interblocage.

Deuxième idée : un drapeau partagé

On peut se dire que le mécanisme utilisant deux drapeaux échoue en raison de l'indépendance des écritures. On va maintenant utiliser un drapeau partagé victim qui indique quel thread doit attendre. Comme il y a une unique valeur, on est certain que le second thread à verrouiller va changer la valeur.

int victim = 0;

void verrouille(int id)
{
    victim = id;

    while(victim == id) { // attente active
    }
}

void deverrouille(int id)
{
}

Théorème

Ce verrou satisfait l'exclusion mutuelle.

Preuve

Par l'absurde, supposons que les deux threads sont simultanément dans la section critique et considérons le dernier appel à verrouille de chaque thread.

Le thread 0 a réalisé \(ecrit_0\)(victim = 0) \(\rightarrow\) \(lit_0\)(victim == 1) \(\rightarrow SC_0\). Comme il a lu la valeur 1 après avoir écrit 0, le thread 1 a écrit victim = 1 entre les deux. Or le thread 1 n'écrit dans victim qu'une fois par appel à verrouille et il est en section critique : il s'agit donc de l'écriture de son dernier appel et \(ecrit_0\)(victim = 0) \(\rightarrow\) \(ecrit_1\)(victim = 1).

Par symétrie, on a également \(ecrit_1\)(victim = 1) \(\rightarrow\) \(ecrit_0\)(victim = 0), ce qui est impossible car \(\rightarrow\) est un ordre strict.

Contradiction.

Cependant, on remarque que pour être débloqué, un thread doit attendre qu'un autre thread verrouille. Il y a donc interblocage quand un thread est seul à verrouiller, ce qui est toujours le cas quand un des deux threads termine avant.

Algorithme de Peterson

Le verrou de Peterson consiste à fusionner les deux comportements.

bool flags[2] = {}; // initialise deux flags à false
int victim = 0;

void verrouille(int id)
{
    int autre = 1 - id;

    flags[id] = true;
    victim = id;
    while(flags[autre] && victim == id) { // attente active
    }
}

void deverrouille(int id)
{
    flags[id] = false;
}

Remarque

L'ordre des deux écritures flags[id] = true; puis victim = id; est essentiel. Si on les inverse, l'exécution suivante viole l'exclusion mutuelle : le thread 0 écrit victim = 0, puis le thread 1 écrit victim = 1 et flags[1] = true, lit flags[0] == false et entre en section critique ; le thread 0 écrit alors flags[0] = true, lit victim == 1 et entre aussi en section critique.

Théorème

Ce verrou satisfait l'exclusion mutuelle.

Preuve

Par l'absurde, supposons que les deux threads sont simultanément dans la section critique et considérons le dernier appel à verrouille de chaque thread. Sans perte de généralité, on suppose que le thread 0 est le dernier à avoir écrit dans victim : \(ecrit_1\)(victim = 1) \(\rightarrow\) \(ecrit_0\)(victim = 0).

Le thread 0 est sorti de la boucle après \(ecrit_0\)(victim = 0), en lisant soit flags[1] == false, soit victim == 1. Comme personne n'écrit dans victim après \(ecrit_0\) (le thread 1 est en section critique), il a nécessairement lu flags[1] == false.

Mais on a \(ecrit_1\)(flags[1] = true) \(\rightarrow\) \(ecrit_1\)(victim = 1) \(\rightarrow\) \(ecrit_0\)(victim = 0) \(\rightarrow\) \(lit_0\)(flags[1]) et le thread 1 ne remet flags[1] à false qu'en sortant de sa section critique : le thread 0 a donc lu flags[1] == true.

Contradiction.

Théorème

Ce verrou satisfait l'absence de famine.

Preuve

Par l'absurde, supposons qu'il y ait famine. Sans perte de généralité, on peut supposer que le thread 0 reste indéfiniment bloqué dans la boucle de verrouille. Il lit donc indéfiniment flags[1] == true et victim == 0.

  • Si le thread 1 ne demande plus le verrou, flags[1] vaut false à partir d'un certain moment et le thread 0 sort de la boucle.
  • Le thread 1 ne peut pas rester en section critique indéfiniment (hypothèse) ni être bloqué dans sa boucle, car victim vaut 0 et la condition victim == 1 est fausse.
  • Il reste le cas où le thread 1 sort de sa section critique puis rappelle verrouille. Il écrit alors victim = 1, et comme seul le thread 1 pourrait remettre victim à 0, le thread 0 lit ensuite victim == 1 et sort de sa boucle.

Contradiction.

Remarque

En lançant le programme précédent d'incrémentation avec ce verrou, il est probable de ne pas observer 200000 dans le compteur bien que les deux threads fassent chacun cent mille incréments dans une section critique.

En effet, les hypothèses sur la gestion de la mémoire ne sont pas satisfaites sur des ordinateurs récents. De plus, en langage C, ces accès concurrents non protégés à flags et victim constituent des data races dont le comportement n'est pas défini : avec des optimisations (-O2), le compilateur peut par exemple ne lire victim qu'une seule fois avant la boucle d'attente. On peut réparer ce verrou en forçant le processeur à gérer la mémoire comme on l'attend en plaçant des barrières mémoire à l'aide de l'instruction :

asm volatile ("mfence" ::: "memory");

En pratique, il semble que placer une barrière avant d'entrer dans l'attente active suffit. Cependant, on devrait la placer avant chaque accès mémoire, ce qui ralentirait fortement le programme. En effet, ces instructions ont un coût qui peut parfois dépasser le bénéfice obtenu par l'exécution parallèle.

L'algorithme de la boulangerie de Lamport

L'algorithme de la boulangerie de Lamport est une généralisation du verrou de Peterson pour n threads. L'idée est d'associer à chaque thread un numéro de ticket et de débloquer à chaque fois le thread de plus petit numéro de ticket, comme lorsqu'on fait la queue dans un commerce.

Ici, on n'aura aucune garantie que les numéros de tickets soient uniques, mais en considérant un couple (ticket, identificateur) on peut toujours déterminer le thread prioritaire.

On va conserver les drapeaux comme avec le verrou de Peterson, les numéros de tickets vont eux permettre de généraliser le rôle qu'avait victim précédemment.

Ici, les numéros de tickets sont stockés dans le tableau labels et, comme pour Peterson, on a un tableau flags de booléens.

bool flags[10] = {};
int labels[10] = {};

Pour verrouiller, on passe le drapeau du thread à true et on choisit pour numéro de ticket \(1 + \max_k\) labels[k] qui est calculé dans une boucle. Ces deux étapes constituent la porte d'entrée.

Ensuite, on attend tant qu'il existe un thread \(k\) tel que flags[k] == true et dont le couple (labels[k], k) < (labels[i], i) dans l'ordre lexicographique.

void lock(int i)
{
    flags[i] = true;
    int m = labels[0];
    for(int k = 1; k < 10; k++)
        if(m < labels[k])
            m = labels[k];
    labels[i] = 1 + m;

    while(true) {
        bool cango = true;
        for(int k = 0; k < 10; k++) {
            if (k != i && flags[k]
                && (labels[k] < labels[i]
                || (labels[k] == labels[i] && k < i)))
                cango = false;
        }
        if (cango)
            break;
    }
}

Comme annoncé, les labels généralisant victim, il y a la même fonction que précédemment pour déverrouiller.

void unlock(int i)
{
    flags[i] = false;
}

Théorème

Ce verrou satisfait l'exclusion mutuelle, l'absence d'interblocage et la propriété premier arrivé, premier servi. Il satisfait donc l'absence de famine.

Preuve

On remarque d'abord que les valeurs successives de labels[i] sont strictement croissantes, car le maximum calculé par le thread \(i\) prend en compte son propre ancien ticket.

  • Absence d'interblocage : supposons que des threads attendent indéfiniment sans qu'aucun thread n'entre en section critique. Comme les portes d'entrée sont de longueur bornée, à partir d'un certain moment plus aucun drapeau ni ticket ne change. Le thread en attente \(A\) dont le couple (labels[A], A) est minimal parmi les threads ayant leur drapeau levé effectue alors une itération complète de la boucle sans trouver de thread prioritaire : il sort de la boucle. Contradiction.
  • Premier arrivé, premier servi : si \(A\) termine sa porte d'entrée avant que \(B\) ne commence la sienne, alors \(B\) lit labels[A] après son écriture par \(A\), donc labels[B] \(>\) labels[A]. Tant que \(A\) n'est pas sorti de section critique, flags[A] vaut true et (labels[A], A) < (labels[B], B) : \(B\) attend.
  • Exclusion mutuelle : supposons \(A\) et \(B\) simultanément en section critique, avec (labels[A], A) < (labels[B], B) pour les tickets de leurs derniers appels. Lors de sa dernière vérification de \(A\), \(B\) a lu flags[A] == false ou un ticket de \(A\) tel que le couple correspondant soit plus grand que (labels[B], B). Les tickets de \(A\) étant croissants, un ancien ticket de \(A\) donne un couple encore plus petit : \(B\) a donc lu flags[A] == false, avant que \(A\) ne lève son drapeau lors de son dernier appel. On a ainsi : \(ecrit_B\)(labels[B]) \(\rightarrow\) \(lit_B\)(flags[A]) \(\rightarrow\) \(ecrit_A\)(flags[A] = true) \(\rightarrow\) \(lit_A\)(labels[B]) \(\rightarrow\) \(ecrit_A\)(labels[A]). Le thread \(A\) a donc lu le ticket de \(B\) et choisi labels[A] \(>\) labels[B], ce qui contredit (labels[A], A) < (labels[B], B).

L'absence de famine découle alors du théorème sur les propriétés des verrous.

Utiliser les mutex de pthread

Les deux mécanismes de verrou que l'on vient de voir ont plusieurs défauts :

  • ils sont basés sur des attentes actives
  • ils supposent des hypothèses fortes sur la gestion de la mémoire

Comme souvent, il vaut mieux reposer sur des primitives déjà programmées et qui ont souvent été adaptées pour coller au mieux aux architectures sur lesquelles on développe.

Remarque

Une des premières versions sous Linux de la bibliothèque pthread que l'on va utiliser a été écrite par Xavier Leroy, qui n'est autre que l'architecte principal derrière Caml Light puis OCaml.

Cela prouve qu'on peut à la fois écrire l'histoire en C et en OCaml !

Pour avoir accès à ces fonctions, il faut également inclure pthread.h.

Le type des verrous est pthread_mutex_t.

Initialisation

On peut initialiser un verrou déjà alloué de deux manières :

  • si c'est un verrou statique, il suffit de lui donner la valeur initiale PTHREAD_MUTEX_INITIALIZER :

    pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

  • dans tous les cas, si on a un pointeur pthread_mutex_t *m, on va appeler pthread_mutex_init(m, NULL). Ce pointeur peut être obtenu depuis une allocation statique :

    pthread_mutex_t m;
pthread_mutex_init(&m, NULL);

    et dans ce cas c'est équivalent à l'initialisation précédente, ou alors dynamiquement :

    pthread_mutex_t *m = malloc(sizeof(pthread_mutex_t));
pthread_mutex_init(m, NULL);

Verrouiller et déverrouiller un mutex

On utilise les deux fonctions suivantes pour un mutex m :

pthread_mutex_lock(&m); // verrouille
pthread_mutex_unlock(&m); // déverrouille

Destruction

Quand on a fini d'utiliser un mutex, on le détruit avec l'appel suivant :

pthread_mutex_destroy(&m);

Exemple d'utilisation

On reprend le code précédent de l'incrémentation d'un compteur partagé :

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

int compteur = 0;
int N = 100000;

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;

void *incremente(void *arg)
{
    for(int i = 0; i < N; i++) {
        pthread_mutex_lock(&m);
        compteur = compteur + 1;
        pthread_mutex_unlock(&m);
    }
    return NULL;
}

int main(void)
{
    pthread_t t0, t1;
    pthread_create(&t0, NULL, incremente, NULL);
    pthread_create(&t1, NULL, incremente, NULL);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);

    printf("compteur = %d (attendu %d)\n",
        compteur, 2 * N);
    pthread_mutex_destroy(&m);
}

Sémaphores

Principe

Les sémaphores généralisent les verrous. Il s'agit de compteurs partagés de ressources avec deux opérations :

  • rendre une ressource en incrémentant un compteur
  • attendre qu'une ressource soit disponible et décrémenter le compteur

Une manière intuitive de voir cela est de considérer une pièce dans laquelle seulement n personnes peuvent être présentes à la fois :

  • on considère devant un réceptacle avec \(n\) jetons
  • pour entrer on attend que le réceptacle ne soit pas vide, on prend un jeton et on entre
  • en sortant, on repose son jeton dans le réceptacle.

Cas initial n = 1 : mutex

Quand le sémaphore dispose initialement d'un seul jeton, une seule personne peut rentrer dans la pièce à la fois : on retrouve l'exclusion mutuelle :

Un sémaphore de valeur initiale 1 permet de réaliser un mutex.

Cas initial n = 0 : signal

Si le sémaphore a une valeur initiale de 0, personne ne peut prendre de ressource initialement. Cela peut sembler inutile, mais rien n'impose que la valeur initiale d'un sémaphore soit sa valeur maximale. Ainsi, on peut incrémenter le sémaphore ce qui va permettre de débloquer un thread attendant pour la décrémenter.

Ce mécanisme permet ainsi de réaliser un signal. Si le thread 1 veut attendre que le thread 2 ait fini de faire une action pour continuer :

  • on crée un sémaphore de valeur 0
  • le thread 1 attend le sémaphore et bloque
  • quand il le souhaite, le thread 2 peut incrémenter le sémaphore
  • cela débloque alors le thread 1

On parle de signal, c'est très pratique de raisonner en termes de signaux pour réaliser des synchronisations complexes.

Utiliser les sémaphores avec pthread

Pour utiliser les sémaphores, on va inclure l'en-tête semaphore.h qui définit le type sem_t des sémaphores.

Initialiser un sémaphore

On initialise un sémaphore s avec la valeur initiale n ainsi :

sem_init(&s, 0, n);

Le second paramètre sera toujours à 0 pour nous.

Libérer un sémaphore

Une fois qu'on a fini de l'utiliser, on le libère avec

sem_destroy(&s);

Attendre une ressource

Pour attendre un sémaphore, et donc décrémenter ensuite sa valeur, on utilise

sem_wait(&s);

Rendre une ressource

L'opération inverse de l'attente, appelée post en anglais, qui va incrémenter la valeur est :

sem_post(&s);

Réalisation d'un mutex

On reprend l'exemple précédent pour montrer la richesse des sémaphores en réalisant un mutex :

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

int compteur = 0;
int N = 100000;

sem_t s;

void *incremente(void *arg)
{
    for(int i = 0; i < N; i++) {
        sem_wait(&s);
        compteur = compteur + 1;
        sem_post(&s);
    }
    return NULL;
}

int main(void)
{
    pthread_t t0, t1;
    sem_init(&s, 0, 1);
    pthread_create(&t0, NULL, incremente, NULL);
    pthread_create(&t1, NULL, incremente, NULL);
    pthread_join(t0, NULL);
    pthread_join(t1, NULL);

    printf("compteur = %d (attendu %d)\n",
        compteur, 2 * N);
    sem_destroy(&s);
}

Utilisation d'un signal

On va considérer deux threads très simples : le thread 1 affiche A puis B, le thread 2 affiche C puis D. Contrainte : on demande que le B ne soit pas affiché avant que le thread 2 ait affiché C. Ainsi la trace, ce qui va être affiché sur la sortie, peut être par exemple ACDB ou CADB mais pas ABCD.

Pour cela, on va faire en sorte que le thread 2 signale qu'il a fini au thread 1 avec un sémaphore à 0.

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

sem_t s;

void *threadAB(void *arg)
{
    putchar('A');
    sem_wait(&s);
    putchar('B');

    return NULL;
}

void *threadCD(void *arg)
{
    putchar('C');
    sem_post(&s);
    putchar('D');

    return NULL;
}

int main(void)
{
    pthread_t t1, t2;
    sem_init(&s, 0, 0); // à 0 car c'est un signal

    pthread_create(&t1, NULL, threadAB, NULL);
    pthread_create(&t2, NULL, threadCD, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    sem_destroy(&s);
}

On a fait l'hypothèse en parlant des signaux qu'ils seraient attendus avant d'être produits, mais ce n'est pas nécessaire.

Que se passe-t-il si le thread 2 poste le sémaphore avant que le thread 1 ne l'attende ? Il va s'incrémenter et passer à 1, ainsi le thread 1 pourra l'acquérir sans attente.

Problèmes classiques

Rendez-vous à deux threads

On considère un problème proche du problème du paragraphe précédent : deux threads veulent écrire AB mais tous les threads doivent avoir écrit A avant qu'un thread écrive B. Ainsi, la trace doit forcément être AABB.

Il est ainsi nécessaire que les deux threads s'attendent mutuellement. On va donc définir un signal thread 0 a fini et un signal thread 1 a fini.

Bien entendu, pour ne pas bloquer, il faut poster ces signaux avant d'attendre l'autre signal. On obtient donc le code suivant :

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

sem_t s[2];

void *threadAB(void *arg)
{
    int *i_arg = arg;
    int id = *i_arg;

    putchar('A');
    sem_post(&s[id]);
    sem_wait(&s[1 - id]);
    putchar('B');

    return NULL;
}

int main(void)
{
    pthread_t t[2];
    int ids[] = { 0, 1 };

    sem_init(&s[0], 0, 0); // à 0 car c'est un signal
    sem_init(&s[1], 0, 0); // à 0 car c'est un signal

    pthread_create(&t[0], NULL, threadAB, &ids[0]);
    pthread_create(&t[1], NULL, threadAB, &ids[1]);
    pthread_join(t[0], NULL);
    pthread_join(t[1], NULL);

    sem_destroy(&s[0]);
    sem_destroy(&s[1]);
}

Rendez-vous à n threads : barrière

On souhaite généraliser le mécanisme précédent à \(n\) threads mais sans que la solution ne dépende du nombre de threads.

Avec \(n\) threads, on doit donc avoir chaque thread qui affiche A puis attend tous les autres threads pour ensuite afficher B. Ainsi, la trace sera forcément A..AB..B.

Comme on dispose d'un nombre constant de primitives de synchronisation, les threads doivent partager un signal. La solution classique consiste, à la manière d'une chute de dominos, à faire en sorte que chaque thread réveillé libère le suivant.

Celui qui lance la réaction en chaîne est le dernier thread ayant écrit un A. Pour le connaître, on va rajouter une incrémentation de compteur avec une section critique.

Remarque

Cela implique que les threads connaissent le nombre de threads dans la barrière.

On va considérer un sémaphore barrier et chaque thread va donc exécuter :

sem_wait(&barrier);
sem_post(&barrier);

Le dernier thread à finir va également réaliser un post de la barrière, la barrière est donc rendue \(n+1\) fois et acquise \(n\) fois, chaque fois dans l'ordre :

rendue → acquise → rendue → … → rendue

On obtient ainsi le programme suivant :

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

int count = 0;

pthread_mutex_t count_lock = PTHREAD_MUTEX_INITIALIZER;
sem_t barrier;

void *f(void *arg)
{
    putchar('A');

    pthread_mutex_lock(&count_lock);
    count = count + 1;
    pthread_mutex_unlock(&count_lock);

    if (count == 10)
        sem_post(&barrier);

    sem_wait(&barrier);
    sem_post(&barrier);

    putchar('B');

    return NULL;
}

int main(void)
{
    pthread_t t[10];

    sem_init(&barrier, 0, 0);

    for(int i = 0; i < 10; i++)
        pthread_create(&t[i], NULL, f, NULL);

    for(int i = 0; i < 10; i++)
        pthread_join(t[i], NULL);

    sem_destroy(&barrier);
}

Note

Faire le dessin de la réaction en chaîne.

Remarque

On peut s'étonner que la solution proposée accède à la valeur du compteur en dehors d'une section critique. En effet, il n'est pas inenvisageable d'avoir le comportement suivant :

  • l'avant-dernier thread à prendre la section critique incrémente le compteur à n-1
  • le dernier thread en section critique le passe à n
  • les deux threads lisent en même temps la nouvelle valeur du compteur à n
  • les deux threads postent le sémaphore

Cependant, on est assuré qu'on ne poste jamais le sémaphore avant qu'il y ait eu effectivement n exécutions de la section critique. Ainsi, le seul risque est de trop incrémenter le sémaphore, ce qui n'a aucune influence sur notre algorithme.

Notons toutefois qu'en C, cette lecture non protégée d'une variable modifiée par d'autres threads est une data race, dont le comportement n'est formellement pas défini. Il est plus sûr de lire count dans la section critique, par exemple en y mémorisant la valeur count == 10 dans une variable locale testée ensuite.

Barrière réutilisable

On cherche maintenant à faire en sorte que la barrière soit réutilisable après une synchronisation complète. Le problème est lié à la remarque précédente : en l'absence d'accès au compteur en section critique, on ne connaît pas sa valeur à la fin et on ne peut pas le réinitialiser.

Pour bien comprendre le problème, on va modifier le code précédent :

void *f(void *arg)
{
    for(int i = 0; i < N; i++)
    {
        putchar('A');

        // ATTENTE D'ARRIVÉE

        putchar('B');

        // ATTENTE DE DÉPART
    }

    return NULL;
}

Ici, on veut donc effectuer plusieurs boucles AAABBBAAABBB... il y a donc deux barrières implicites avant et après l'affichage de B. On va ainsi considérer deux sémaphores et deux réactions en chaînes : inbarrier initialement à 0 et outbarrier initialement à 1.

Le code va devenir :

void *f(void *arg)
{
    for(int i = 0; i < N; i++) {
        putchar('A');

        pthread_mutex_lock(&count_lock);
        count = count + 1;
        if (count == 10) {
            sem_wait(&outbarrier);
            sem_post(&inbarrier);
        }
        pthread_mutex_unlock(&count_lock);

        // réaction en chaîne 1
        sem_wait(&inbarrier);
        sem_post(&inbarrier);

        putchar('B');

        pthread_mutex_lock(&count_lock);
        count = count - 1;
        if (count == 0) {
            sem_wait(&inbarrier);
            sem_post(&outbarrier);
        }
        pthread_mutex_unlock(&count_lock);

        // réaction en chaîne 2
        sem_wait(&outbarrier);
        sem_post(&outbarrier);
    }

    return NULL;
}

Note

Faire un beau dessin ici.

Remarque

On a fait le choix ici de placer le putchar('B'); entre les deux phases de la barrière. Cela a pour conséquence que tous les B seront affichés avant la nouvelle itération d'un thread.

Cependant, ce comportement qui est un bonus de notre implémentation peut être ignoré si on place putchar('B'); après la seconde réaction en chaîne.

En faisant cela, on aura AAA-BBABAA-BABBAA... c'est-à-dire des séries de trois B et de trois A des itérations suivantes mélangés.

Encapsuler la barrière

On va définir un type barrier_t en C pour les barrières réutilisables. L'interface sera :

void barrier_init(barrier_t *b, int n);
void barrier_destroy(barrier_t *b);
void barrier_sync_in(barrier_t *b);
void barrier_sync_out(barrier_t *b);
void barrier_sync(barrier_t *b);

Les deux fonctions d'attente sync_in et sync_out permettent la granularité de la partie précédente pour séparer les deux phases de la synchronisation.

struct barrier {
    int n;
    int count;
    pthread_mutex_t count_lock;
    sem_t inbarrier;
    sem_t outbarrier;
};
typedef struct barrier barrier_t;

void barrier_init(barrier_t *b, int n)
{
    b->n = n;
    b->count = 0;
    pthread_mutex_init(&b->count_lock, NULL);
    sem_init(&b->inbarrier, 0, 0);
    sem_init(&b->outbarrier, 0, 1);
}

void barrier_destroy(barrier_t *b)
{
    pthread_mutex_destroy(&b->count_lock);
    sem_destroy(&b->inbarrier);
    sem_destroy(&b->outbarrier);
}

void barrier_sync_in(barrier_t *b)
{
    pthread_mutex_lock(&b->count_lock);
    b->count = b->count + 1;
    if (b->count == b->n) {
        sem_wait(&b->outbarrier);
        sem_post(&b->inbarrier);
    }
    pthread_mutex_unlock(&b->count_lock);

    sem_wait(&b->inbarrier);
    sem_post(&b->inbarrier);
}

void barrier_sync_out(barrier_t *b)
{
    pthread_mutex_lock(&b->count_lock);
    b->count = b->count - 1;
    if (b->count == 0) {
        sem_wait(&b->inbarrier);
        sem_post(&b->outbarrier);
    }
    pthread_mutex_unlock(&b->count_lock);

    sem_wait(&b->outbarrier);
    sem_post(&b->outbarrier);
}

void barrier_sync(barrier_t *b)
{
    barrier_sync_in(b);
    barrier_sync_out(b);
}

Producteurs-consommateurs

On considère maintenant le problème suivant :

  • \(p\) threads producteurs vont produire des tâches à traiter
  • \(c\) threads consommateurs vont traiter des tâches non traitées
  • les tâches à traiter sont stockées dans un tableau de capacité \(N\) sous la forme d'une file de tâches
  • si un producteur veut produire une tâche mais que la file est pleine, il doit attendre
  • si un consommateur veut consommer une tâche mais que la file est vide, il doit attendre

La manière dont on a réalisé une file dans un tableau peut être simplifiée à l'aide de sémaphores : en effet, si on utilise des sémaphores pour gérer le nombre de places libres et le nombre de places occupées, il sera impossible de réaliser un ajout ou une suppression illicite.

Afin de mesurer des performances, les tâches seront des empreintes de temps telles qu'on peut en prendre avec la fonction gettimeofday de sys/time.h. En effet, cette fonction permet de remplir une struct timeval avec le temps actuel et une très bonne précision (à la microseconde).

struct timeval buffer[N];
int buffer_capacity = N;
int buffer_start = 0;
int buffer_end = 0;

void add_task(struct timeval task)
{
    buffer[buffer_end] = task;
    buffer_end = (buffer_end + 1) % N;
}

struct timeval take_task()
{
    struct timeval d = buffer[buffer_start];
    buffer_start = (buffer_start + 1) % N;
    return d;
}

Les fonctions qu'on aimerait protéger sont celles-ci :

void *produce(void *arg)
{
    while(true) {
        struct timeval tm;
        gettimeofday(&tm, NULL);
        add_task(tm);
    }

    return NULL;
}

void *consume(void *arg)
{
    while(true) {
        struct timeval tm1 = take_task();
        struct timeval tm2;
        gettimeofday(&tm2, NULL);
        unsigned long long t = 1000000 * (tm2.tv_sec - tm1.tv_sec) 
                + (tm2.tv_usec - tm1.tv_usec);

        printf("Task waited %llu us\n", t);
    }
}

Comme annoncé précédemment, on suppose que la file n'est jamais pleine (pour add_task) ou vide (pour take_task) dans ces fonctions, on pourra s'en assurer de manière indirecte par la synchronisation.

On va ainsi considérer deux sémaphores et un verrou :

  • un sémaphore items indiquant le nombre d'éléments de la file, initialement à 0
  • un sémaphore spaces indiquant le nombre de places libres dans la file, initialement à N
  • un verrou m permettant d'assurer l'exclusion mutuelle dans l'accès à la file

Un producteur va ainsi :

  • attendre une place libre avec une acquisition de spaces
  • ajouter la tâche dans une section critique protégée par m
  • incrémenter le nombre d'objets en signalant le sémaphore items

Cela correspond au code :

void *produce(void *arg)
{
    while(true) {
        struct timeval tm;
        gettimeofday(&tm, NULL);

        sem_wait(&spaces);
        pthread_mutex_lock(&m);
            add_task(tm);
        pthread_mutex_unlock(&m);
        sem_post(&items);
    }

    return NULL;
}

Un consommateur va faire l'opération inverse :

  • attendre un objet avec une acquisition de items
  • retirer la tâche dans une section critique protégée par m
  • incrémenter le nombre de places libres en signalant le sémaphore spaces
void *consume(void *arg)
{
    while(true) {
        sem_wait(&items);
        pthread_mutex_lock(&m);
            struct timeval tm1 = take_task();
        pthread_mutex_unlock(&m);
        sem_post(&spaces);

        struct timeval tm2;
        gettimeofday(&tm2, NULL);

        unsigned long long t = 1000000 * (tm2.tv_sec - tm1.tv_sec)
            + (tm2.tv_usec - tm1.tv_usec);

        printf("Task waited %llu us\n", t);
    }
}

Le dîner des philosophes

On considère \(n\) philosophes assis autour d'une table ronde, chacun a une baguette à sa gauche et une baguette à sa droite. Les philosophes alternent entre penser et manger. Pour manger un philosophe a besoin de deux baguettes.

Le code d'un philosophe est donc :

while(true) {
    penser();
    attraper_baguettes();
    manger();
    reposer_baguettes();
}

On demande de trouver une solution pour la synchronisation de la prise des baguettes afin d'assurer :

  • qu'au plus un philosophe tienne une baguette donnée
  • qu'il n'y ait pas de famine
  • que si \(n \ge 4\), au moins deux philosophes puissent manger simultanément.

On va numéroter les philosophes de 0 à \(n-1\), et on numérote les baguettes par le numéro du philosophe à leur droite.

Le philosophe \(i\) doit donc attraper les baguettes \(i\) et \((i+1) \mod n\) pour manger.

Il va de soi qu'on ne peut pas mettre un verrou sur la table elle-même, car cela aurait pour effet de ne permettre qu'à un seul philosophe de manger. Il faut donc rajouter plus de granularité.

Ce problème est bien plus difficile qu'il n'en a l'air. On va voir différentes propositions mais aucune ne sera satisfaisante.

Premier essai

On va considérer ici un sémaphore par baguette qu'on notera baguettes[i]. On suppose que chaque sémaphore est initialisé à 1. On propose les programmes suivants :

void attraper_baguettes(int i)
{
    sem_wait(&baguettes[i]);
    sem_wait(&baguettes[(i+1)%n]);
}

void reposer_baguettes(int i)
{
    sem_post(&baguettes[i]);
    sem_post(&baguettes[(i+1)%n]);
}

Ce code est simple mais va provoquer un interblocage si tous les philosophes attrapent leur première baguette (la baguette i) en même temps : chacun attend alors indéfiniment la baguette tenue par son voisin.

États des philosophes

On considère maintenant que les philosophes ont trois états : en train de penser, en train de manger, ayant faim. On a ainsi rajouté un état intermédiaire qui est un état d'attente.

Initialement, chaque philosophe est en train de penser.

On considère également \(n\) sémaphores signalant que le ième philosophe mange, ils sont initialisés à 0, car aucun ne mange au départ.

Pour manipuler les états, on rajoute un verrou m.

int PENSER = 0;
int MANGER = 1;
int FAIM = 2;

int etats[n] = {};
sem_t mange[n];
pthread_mutex_t m;

On va définir une fonction permettant de laisser le philosophe \(i\) manger s'il le désire. Cette fonction permettra à la fois d'être utilisée par le philosophe désirant manger et par un philosophe ayant fini de manger et voulant le signaler aux philosophes à sa gauche et à sa droite.

void test(int i)
{
    if(etats[i] == FAIM && etats[gauche(i)] != MANGER
        && etats[droite(i)] != MANGER) {
        etats[i] = MANGER;
        sem_post(&mange[i]);
    }
}

Pour attraper les baguettes, un philosophe va changer son état en section critique en déclarant avoir faim, prendre les baguettes avec le test si c'est possible et attendre d'être effectivement en train de manger avec son sémaphore :

void attraper_baguettes(int i)
{
    pthread_mutex_lock(&m);
    etats[i] = FAIM;
    test(i);
    pthread_mutex_unlock(&m);
    sem_wait(&mange[i]);
}

Pour reposer les baguettes, on modifie l'état du philosophe en section critique et on débloque les philosophes à gauche et à droite.

void reposer_baguettes(int i)
{
    pthread_mutex_lock(&m);
    etats[i] = PENSER;
    test(gauche(i));
    test(droite(i));
    pthread_mutex_unlock(&m);
}

Ainsi, pour manger, un philosophe va

  • soit directement prendre les baguettes et s'auto-signaler, s'il a faim et que personne ne mange à sa gauche et à sa droite
  • soit attendre son sémaphore, ce qui implique qu'un philosophe à gauche ou à droite mange, attendre qu'il finisse de manger et qu'on lui signale qu'il peut manger.

Ici, on considère qu'un philosophe tient ses deux baguettes exactement quand son état est MANGER.

Théorème

À tout moment, au plus un philosophe tient une baguette donnée et il n'y a pas de situation d'interblocage.

Preuve

Les états ne sont modifiés que lorsque le verrou m est pris, on peut donc raisonner sur des invariants vérifiés à chaque libération du verrou.

  • Invariant 1 : deux philosophes voisins ne sont jamais tous les deux dans l'état MANGER. C'est vrai initialement, et un philosophe ne passe dans l'état MANGER que dans test, après avoir vérifié que ses deux voisins ne sont pas dans cet état. Comme une baguette n'est partagée que par deux voisins, au plus un philosophe la tient.
  • Invariant 2 : si un philosophe est dans l'état FAIM, un de ses voisins est dans l'état MANGER. En effet, quand un philosophe passe dans l'état FAIM, il appelle immédiatement test : il ne reste dans l'état FAIM que si un voisin mange. Et quand un philosophe cesse de manger, il appelle test sur ses deux voisins : un voisin affamé passe alors dans l'état MANGER sauf si son autre voisin mange.
  • Supposons qu'il y ait interblocage. L'attente du verrou ne peut pas durer indéfiniment car les sections critiques sont courtes et le verrou ne présente pas d'interblocage. Un philosophe bloqué indéfiniment l'est donc sur sem_wait(&mange[i]) ; il n'est pas dans l'état MANGER, sinon son sémaphore aurait été incrémenté, donc il est dans l'état FAIM. Par l'invariant 2, un de ses voisins mange, et comme les philosophes ne mangent pas indéfiniment, celui-ci finit par appeler reposer_baguettes : le système n'est donc pas bloqué.

Malheureusement, cette solution n'est pas parfaite car il y a bien une possibilité de famine.

On considère 5 philosophes et on va affamer le philosophe 0.

  • au départ les philosophes 2 et 4 commencent à manger, puis le philosophe 0 a faim
  • puis les philosophes 1 et 3 ont faim
  • le philosophe 2 finit de manger, ce qui libère 1, puis le philosophe 4 finit de manger, ce qui libère 3
  • puis les philosophes 2 et 4 ont faim
  • le philosophe 3 finit de manger, ce qui libère 4, puis le philosophe 1 finit de manger, ce qui libère 2
  • et on répète indéfiniment

Avec cet ordre, à tout instant l'un des voisins 1 ou 4 du philosophe 0 est en train de manger : chaque appel à test(0) échoue et on affame le philosophe 0 qui ne pourra jamais manger.