Probleme – Le dîner des philosophes : l'interblocage, puis l'équité

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

Énoncé

Cinq philosophes, cinq fourchettes, chacun en boucle infinie. On mesure le nombre de repas de chacun au bout d'une seconde.

Vérifier que « tous prennent la gauche d'abord » interbloque vraiment.
Mesurer les trois parades du cours.
Que révèle la répartition des repas ?
Conclure sur le rapport entre interblocage, équité et débit.

Corrigé

1. L'interblocage. On distingue « bloqué » de « lent » en relevant le total à $0, 3$ s puis à $1, 0$ s : si les deux nombres sont égaux, plus rien ne progresse.

repas à $0, 3$ s	repas à $1, 0$ s	verdict
$1760$	$1760$	aucune progression
$1770$	$1770$	aucune progression
$1103$	$1103$	aucune progression

Trois exécutions sur trois, et le blocage survient en moins de $0, 3$ seconde après un ou deux milliers de repas. Le philosophe $4$ n'a mangé aucune fois dans les trois cas : il est le dernier de la ronde, et c'est lui que la symétrie sacrifie.

2. Les trois parades, mesurées sur une seconde. La colonne min/max est le rapport entre le philosophe le moins servi et le plus servi : $1$ signifie parfaitement équitable.

	repas en $1$ s	min/max	interblocage
$0$ . tous la gauche d'abord	$\approx 1500$ puis arrêt	$0$	oui
$1$ . un philosophe inverse	$554$ millions	$0, 0035$	non
$2$ . fourchettes numérotées	$729$ millions	$0, 0001$	non
$3$ . sémaphore à $4$ places	$0, 32$ million	$0, 9997$	non

3. Ce que la répartition révèle, et c'est le cœur du problème.

Avec la parade 2 — celle que le cours recommande, et à juste titre pour l'interblocage — un philosophe obtient $72352282$ repas quand un autre en obtient $3684$ . Un rapport de vingt mille. Le système avance à toute vitesse, et trois convives sur cinq ne mangent quasiment jamais. C'est la définition même de la famine.

La parade 3 est l'inverse : $0, 32$ million de repas seulement — deux cents fois moins — mais une répartition qui ne s'écarte pas de $0, 03 %$ de l'égalité parfaite. Le sémaphore sérialise l'entrée à table, et cette sérialisation est l'équité.

ImportantUne nuance à apporter au cours

Le cours écrit que « la parade 3 évite l'interblocage, sans garantir qu'un philosophe malchanceux finisse par manger ». C'est exact au sens strict : elle ne garantit rien, l'équité dépendant de l'ordonnanceur et de la file d'attente du sémaphore.

Mais la mesure dit qu'en pratique, elle est de loin la plus équitable des trois — et que les parades 1 et 2, présentées sans réserve, produisent une famine sévère. Il faut donc lire l'avertissement pour ce qu'il est : aucune des trois parades ne garantit l'équité. On ne peut pas classer les trois sur ce critère par le raisonnement seul ; il faut mesurer.

C'est une leçon générale : une propriété garantie et une propriété observée sont deux choses différentes, et l'ordre entre les solutions n'est pas le même selon celle qu'on regarde.

4. La conclusion, en trois propriétés à ne pas confondre.

Propriété	ce qu'elle dit	mesurée par
Sûreté	rien de mauvais n'arrive	exclusion mutuelle
Vivacité	quelque chose finit par arriver	absence d'interblocage
Équité	chacun finit par être servi	répartition min/max

Elles sont indépendantes, et il est vain de chercher l'une en croyant obtenir les autres. Un programme qui ne fait rien du tout est parfaitement sûr. Un programme qui laisse tout le monde entrer partout est parfaitement vivace. Le vrai travail est de tenir les trois à la fois, et le seul protocole du chapitre qui garantisse les trois est la boulangerie — au prix d'une attente active et d'un examen de tous les autres fils à chaque entrée.

Rien n'est gratuit : les $72$ millions de repas de la parade 2 et les $0, 32$ million de la parade 3 mesurent exactement ce que coûte l'équité.

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.