Le compteur perdu, mesuré

Loin du compte, et jamais deux fois la même. Dix exécutions de chaque, mesurées :

Ce ne sont pas quelques incréments perdus : c'est la moitié, puis les trois quarts. Avec quatre fils, on obtient à peine plus qu'avec deux — ajouter des fils n'ajoute presque rien, car ils s'écrasent mutuellement.

Le mécanisme, tel que le cours le décrit. La ligne compteur = compteur + 1 se décompose en trois opérations machine : lire, ajouter, écrire. Si deux fils lisent la même valeur $v$, tous deux écriront $v+1$ : un incrément a disparu. Sur des dizaines de milliers de tours, cela se produit constamment.

Pourquoi le résultat est-il si stable autour de $100000$ ? Parce que le nombre obtenu est, en gros, le nombre d'incréments du dernier fil à écrire, plus ce que les autres ont eu le temps de faire pendant leurs tranches d'ordonnancement. Le résultat n'est ni « $200000$ moins quelques-uns » ni aléatoire : il est structurellement voisin de $100000$. Un résultat faux peut être régulier, et cette régularité est trompeuse : elle ressemble à un résultat.

pthread_mutex_t verrou = PTHREAD_MUTEX_INITIALIZER;

void* incrementer(void* arg) {
    for (int i = 0; i < 100000; i = i + 1) {
        pthread_mutex_lock(&verrou);
        compteur = compteur + 1;          /* SECTION CRITIQUE */
        pthread_mutex_unlock(&verrou);
    }
    return NULL;
}