Ce qui est partagé, et ce qui ne l'est pas

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 22 — Concurrence et synchronisation

Énoncé

Trois fils exécutent la fonction suivante. Que valent locale, globale et tas[0] à la fin ?


int  globale = 0;
int* tas;                      /* alloué par malloc dans main */

void* travail(void* arg) {
    int locale = 0;
    for (int i = 0; i < 5; i = i + 1) {
        locale  = locale  + 1;
        globale = globale + 1;
        tas[0]  = tas[0]  + 1;
    }
    printf("locale = %d\n", locale);
    return NULL;
}

Corrigé

Mesuré : chaque fil affiche locale = 5, et l'on lit globale = 15, tas[0] = 15.

La variable locale est déclarée dans la fonction : elle vit sur la pile du fil, et chaque fil a la sienne. Trois fils, trois variables distinctes, aucune interaction. C'est la portée du chapitre chap:memoire, appliquée à trois piles au lieu d'une.

globale et tas[0] sont partagées : la première est dans le segment des données, la seconde sur le tas, et les deux zones sont communes à tout le processus. Les trois fils écrivent au même endroit.

Mais voici l'observation qui compte, et elle est mesurée. Sur vingt exécutions consécutives, globale a valu $15$ vingt fois. Le programme est pourtant faux : globale = globale + 1 n'est pas atomique, et rien ne garantit ce $15$ .

AttentionUn programme concurrent faux se comporte correctement, jusqu'à ce qu'il ne le fasse plus

Quinze incréments s'exécutent en quelques microsecondes : la probabilité que l'ordonnanceur interrompe un fil entre la lecture et l'écriture est infime. Le défaut est là, il ne se manifeste pas.

C'est exactement ce que dit le cours : « il se manifeste une fois sur mille, en production, jamais pendant les tests ». Ici on le tient : la même faute, portée à $100000$ tours, fait perdre la moitié des incréments (exercice 22.2). Le nombre de tours ne change pas la correction du programme — il change seulement la probabilité qu'on s'en aperçoive.

Corollaire de méthode : en concurrence, un test qui passe ne prouve rien. La correction se raisonne, ou se vérifie exhaustivement (problème 22.2). Elle ne s'observe pas.

Un signe visible du non-déterminisme subsiste malgré tout : l'ordre des trois lignes affichées change d'une exécution à l'autre — 0, 2, 1 puis 0, 1, 2. Les fils progressent dans un ordre que personne ne contrôle.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.