Probleme – Le tampon borné, et ce que chaque outil protège

1. Le code.

#define N 4
int tampon[N];
int tete = 0, queue = 0;
sem_t vides, pleines;
pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;

/* Précondition : appelé après sem_wait(&vides) ET sous le verrou. */
void deposer(int x) { tampon[queue] = x; queue = (queue + 1) % N; }
/* Précondition : appelé après sem_wait(&pleines) ET sous le verrou. */
int  retirer(void)  { int x = tampon[tete]; tete = (tete + 1) % N; return x; }

void* producteur(void* arg) {
    for (int i = 0; i < ARTICLES; i = i + 1) {
        sem_wait(&vides);                    /* une place se libère */
        pthread_mutex_lock(&verrou);
        deposer(numero_unique(arg, i));
        pthread_mutex_unlock(&verrou);
        sem_post(&pleines);                  /* un article de plus */
    }
    return NULL;
}

void* consommateur(void* arg) {
    for (;;) {
        sem_wait(&pleines);
        pthread_mutex_lock(&verrou);
        int x = retirer();
        pthread_mutex_unlock(&verrou);
        sem_post(&vides);
        if (x < 0) { break; }                /* le jeton d'arrêt */
        traiter(x);
    }
    return NULL;
}

L'arrêt propre est un point de méthode. Les consommateurs bouclent sans fin : il faut leur dire de s'arrêter, et un simple drapeau fini = true ne suffit pas — un consommateur endormi dans sem_wait(&pleines) ne le lira jamais. On dépose donc un jeton d'arrêt par consommateur, une valeur qui ne peut pas être un article. Le réveil vient du sémaphore, comme pour un article ordinaire.

2. Les trois invariants, et il faut les attribuer précisément.

Les deux sémaphores comptent, le verrou sérialise. C'est la distinction du cours entre mutex et sémaphore, ici rendue concrète : vides et pleines n'ont pas de propriétaire — le producteur incrémente pleines que le consommateur décrémente. Un mutex ne pourrait pas jouer ce rôle : il se rend par celui qui l'a pris.

Noter la somme invariante : à tout instant, $\mathtt{vides}+\mathtt{pleines}+(\text{fils en section critique})=N$. Les deux compteurs se partagent les $N$ cases.

3. Les mesures, avec et sans mutex, six exécutions de chaque. Chaque article porte un numéro unique, et l'on compte combien sont perdus et combien sont reçus plusieurs fois.

4. Pourquoi un blocage, et pas seulement des données fausses. C'est la question intéressante.

Sans le verrou, deux consommateurs peuvent lire tete en même temps : ils retirent le même article, puis incrémentent tete deux fois — ou une seule, si l'incrément lui-même se perd. La conséquence immédiate est celle des $24$ doublons et des $24$ pertes.

Mais tete et queue ne sont pas des données ordinaires : ce sont les indices dont dépend la correspondance entre les sémaphores et le tampon. Si tete avance de deux au lieu d'un, le tampon contient un article que plus personne ne retirera jamais, alors que pleines a bien été décrémenté. Le compte des sémaphores et le contenu réel divergent définitivement.

Le blocage arrive alors par les jetons d'arrêt : l'un d'eux est lu deux fois par le même consommateur, ou perdu. Un consommateur ne reçoit jamais le sien et s'endort pour toujours ; le fil principal l'attend dans son pthread_join. Les compteurs mesurés le montrent : $10001$ ou $10002$ articles consommés pour $10000$ produits — on a consommé plus qu'on n'a produit, ce qui n'a aucun sens et prouve qu'un article a été retiré deux fois.