Deux verrous, deux ordres

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

Énoncé

Deux fils prennent deux mutex, l'un dans l'ordre $(a, b)$ , l'autre dans l'ordre $(b, a)$ , cent mille fois. Que se passe-t-il ? Combien de temps cela met-il ?

Corrigé

Interblocage, cinq fois sur cinq, et il arrive vite : mesuré, le programme se bloque après $36$ à $58$ tours. Avec les deux fils prenant $(a, b)$ dans le même ordre : $200000$ tours menés à bien, cinq fois sur cinq.


/* fil 1 */                       /* fil 2 */
pthread_mutex_lock(&a);           pthread_mutex_lock(&b);   /* ordre INVERSE */
pthread_mutex_lock(&b);           pthread_mutex_lock(&a);
/* ... */                         /* ... */

L'entrelacement fatal tient en deux pas : le fil $1$ prend $a$ , le fil $2$ prend $b$ . Chacun réclame ensuite celui que l'autre détient, et aucun ne rendra le sien avant d'avoir obtenu le second. C'est le cycle d'attente du dîner des philosophes, réduit à deux convives.

Les cinquante tours méritent un commentaire. La probabilité de l'entrelacement fatal est faible à chaque tour — il faut que le fil $2$ prenne $b$ pendant l'intervalle, de quelques nanosecondes, où le fil $1$ détient $a$ sans avoir encore $b$ . Mais l'événement est répété, et une probabilité faible répétée assez souvent devient une certitude. En concurrence, un défaut improbable est un défaut qui arrivera — la seule question est de savoir en combien de tours.

Un cinquantième de cent mille : sur un service qui exécuterait cette boucle une fois par requête, l'incident surviendrait au bout d'une minute. Il n'y a pas de « suffisamment rare ».

Vérification exhaustive (problème 22.2) :

	états atteignables	états d'interblocage
ordres inversés $(a, b)$ et $(b, a)$	$10$	$1$
ordre total, $(a, b)$ des deux côtés	$7$	$0$

Dix états, un seul mauvais : la faute est atteignable dans un cas sur dix, et le programme la trouve en cinquante essais. Le graphe entier tient sur une ligne, et pourtant le code ne le montre pas.

En pratique — Un ordre total sur les verrous, écrit une fois pour toutes

La parade est celle du cours, et elle est la seule qui passe à l'échelle : on numérote les verrous, et on les prend toujours par numéro croissant. Un cycle d'attente exigerait alors qu'un fil attende un verrou de numéro inférieur à celui qu'il détient, ce que le protocole interdit.

En pratique, l'ordre se documente à côté de la déclaration des verrous, comme un invariant :


/* ORDRE DE PRISE : verrou_comptes (1), puis verrou_journal (2).
   JAMAIS l'inverse. */
pthread_mutex_t verrou_comptes;
pthread_mutex_t verrou_journal;

C'est une convention, non une vérification — rien ne l'impose au compilateur. C'est pourquoi elle s'écrit, et pourquoi le problème 22.2 existe.

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.