Probleme – Une barrière réutilisable pour $n$ fils

1. La version naïve. Le dernier arrivé libère tout le monde.

int compteur = 0;
pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;
sem_t tourniquet;                 /* initialisé à 0 */

void barriere_naive(void) {
    pthread_mutex_lock(&verrou);
    compteur = compteur + 1;
    if (compteur == N) {
        for (int k = 0; k < N; k = k + 1) { sem_post(&tourniquet); }
        compteur = 0;             /* on réarme pour le tour suivant */
    }
    pthread_mutex_unlock(&verrou);
    sem_wait(&tourniquet);
}

Elle est correcte au premier tour : les $N-1$ premiers fils s'endorment, le dernier poste $N$ jetons, tout le monde repart.

2. Elle est fausse au deuxième, et la faute est nette : rien n'empêche un fil rapide de refaire un tour complet et de revenir à la barrière avant qu'un fil lent n'ait consommé son jeton. Il en consomme alors deux — le sien et celui du retardataire — et repart avec un tour d'avance. Le retardataire attend un jeton qui a été pris.

Mesuré, sur $4$ fils et $2000$ tours, la barrière naïve encadrant chaque tour :

Une « désynchronisation » est comptée quand deux fils diffèrent de plus d'un tour au moment où ils devraient tous être au même. Les tours atteints à l'arrêt le montrent : $2000$, $1990$, $1993$, $1984$ — seize tours d'écart, là où la barrière promet zéro.

3. La correction : deux tourniquets. L'idée est de forcer tout le monde à franchir une première porte, puis une seconde, de sorte qu'aucun fil ne puisse revenir avant que le dernier n'ait franchi la première.

int compteur = 0;
pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;
sem_t t1;                          /* initialisé à 0 : ferme  */
sem_t t2;                          /* initialisé à 1 : ouvert */

void barriere(void) {
    /* --- premier tourniquet : on entre tous --- */
    pthread_mutex_lock(&verrou);
    compteur = compteur + 1;
    if (compteur == N) { sem_wait(&t2); sem_post(&t1); }   /* ferme t2, ouvre t1 */
    pthread_mutex_unlock(&verrou);
    sem_wait(&t1); sem_post(&t1);          /* on passe, et on laisse passer */

    /* --- second tourniquet : on sort tous --- */
    pthread_mutex_lock(&verrou);
    compteur = compteur - 1;
    if (compteur == 0) { sem_wait(&t1); sem_post(&t2); }   /* ferme t1, ouvre t2 */
    pthread_mutex_unlock(&verrou);
    sem_wait(&t2); sem_post(&t2);
}

Le motif sem_wait suivi immédiatement de sem_post est le tourniquet : chaque fil prend le jeton et le repose aussitôt, de sorte que tous passent l'un après l'autre — mais aucun avant que le jeton n'ait été posé.

La preuve en deux invariants.

Invariant 1 — exactement un tourniquet est ouvert à la fois. Au départ, $t_2$ vaut $1$ et $t_1$ vaut $0$. La bascule sem_wait(&t2); sem_post(&t1); est faite sous le verrou, donc atomiquement, et ne se produit que lorsque compteur == N ; la bascule inverse ne se produit que lorsque compteur == 0. Il ne peut donc jamais y avoir deux portes ouvertes.

Invariant 2 — aucun fil ne franchit $t_1$ avant que les $N$ ne soient arrivés. Le sémaphore $t_1$ vaut $0$ tant que le $N$-ième fil n'a pas incrémenté compteur. Tout fil arrivé plus tôt est bloqué dans sem_wait(&t1).

Conclusion. Un fil rapide qui refait un tour se présente au premier tourniquet, incrémente compteur — mais $t_1$ a été refermé par le dernier sortant de la phase précédente. Il attend. L'avance d'un tour est devenue impossible, et c'est exactement ce que mesurent les zéro désynchronisations.