🍝 Dîner des Philosophes — Interblocage et Concurrence

Coffman et al. (1971) ont identifié quatre conditions nécessaires qui doivent toutes être vérifiées simultanément pour qu'un interblocage se produise : (1) Exclusion mutuelle — une ressource ne peut être détenue que par un seul processus à la fois ; (2) Attente en détenant des ressources — un processus détient au moins une ressource en attendant une autre ; (3) Absence de préemption — une ressource ne peut pas être retirée de force ; (4) Attente circulaire — un cycle existe dans le graphe d'allocation des ressources. Chaque stratégie de prévention de l'interblocage fonctionne en brisant au moins l'une de ces quatre conditions.

L'ordonnancement des ressources brise la condition d'attente circulaire en imposant une numérotation globale sur toutes les fourchettes (de 0 à 4) et en exigeant que chaque philosophe prenne toujours d'abord la fourchette de numéro le plus bas avant celle de numéro plus élevé. Cela signifie que le philosophe 4, qui créerait normalement le cycle en tendant la main vers la fourchette 4 puis la fourchette 0, tend plutôt d'abord la main vers la fourchette 0 — la même fourchette que veut le philosophe 0. L'un des deux l'obtient et progresse ; l'autre attend, mais aucun cycle ne peut se former car l'ordonnancement est strictement acyclique.

La stratégie de l'arbitre introduit un coordinateur central — un « serveur » — qui accorde une permission atomique de prendre les deux fourchettes à la fois, seulement lorsque les deux voisines sont libres. Comme un philosophe n'est jamais autorisé à tenir une fourchette en attendant la seconde, la condition de Coffman d'attente en détenant des ressources ne peut pas être satisfaite. Cela garantit l'absence d'interblocage mais peut réduire le débit car l'arbitre sérialise l'accès, ne permettant qu'à un seul philosophe d'acquérir des fourchettes à la fois lorsque la contention est élevée.

Avec cinq philosophes et cinq fourchettes, le pire cas est que chaque philosophe attrape une fourchette et crée une attente circulaire. En limitant la table à quatre philosophes assis à la fois, il y a cinq fourchettes partagées entre au plus quatre personnes — donc, par le principe des tiroirs, au moins un philosophe doit pouvoir attraper les deux fourchettes voisines et manger. Cela brise la condition d'attente circulaire au niveau de la table sans nécessiter d'arbitrage centralisé des prises de fourchettes individuelles.

Edsger W. Dijkstra a introduit le problème en 1965 comme exercice d'examen à l'Université Technologique d'Eindhoven, le formulant à l'origine avec des « baguettes » plutôt que des fourchettes. Il l'a conçu pour illustrer les pièges de l'utilisation naïve des sémaphores et pour motiver des primitives de concurrence structurées. Tony Hoare l'a ensuite reformulé sous la forme aujourd'hui largement enseignée — cinq philosophes, cinq fourchettes — dans son livre de 1985 « Communicating Sequential Processes », en faisant l'exemple pédagogique canonique de l'interblocage, de la famine et de l'exclusion mutuelle.

L'interblocage est un arrêt global du système : chaque participant est bloqué et aucun progrès ne peut jamais être fait sans intervention externe. La famine est un échec d'équité : le système dans son ensemble continue d'avancer, mais un ou plusieurs philosophes individuels sont systématiquement contournés et ne parviennent jamais à manger. Une solution peut être exempte d'interblocage tout en permettant la famine — par exemple, si deux philosophes qui partagent une fourchette alternent toujours parfaitement et qu'un troisième est toujours exclu. Des solutions robustes telles que le protocole de Chandy-Misra garantissent à la fois l'absence d'interblocage et un service éventuel pour chaque philosophe.

Tout système dans lequel des threads ou processus concurrents doivent acquérir plusieurs verrous en séquence fait face aux mêmes risques. Les systèmes de bases de données utilisent des protocoles d'ordonnancement des verrous (analogues à l'ordonnancement des ressources) pour éviter l'interblocage des transactions. Les noyaux de systèmes d'exploitation imposent un ordre strict d'acquisition des spinlocks pour éviter l'interblocage mutuel entre les gestionnaires d'interruption. Les gestionnaires de pools de connexions limitent les tentatives d'acquisition concurrentes (analogue à la limitation des places). Même les protocoles réseau tels que le commit en deux phases dans les bases de données distribuées intègrent l'évitement des conditions de Coffman dans leurs séquences de négociation.

Oui. L'algorithme de Chandy-Misra (1984) est une solution entièrement distribuée, par passage de messages, qui garantit à la fois l'absence d'interblocage et l'absence de famine sans aucun arbitre central : les philosophes échangent des jetons « sales » et « propres » avec les fourchettes selon un protocole de requête. Des travaux plus récents appliquent la mémoire transactionnelle (HTM/STM) pour faire apparaître l'acquisition multi-ressources comme atomique au niveau matériel ou d'exécution, éliminant le besoin d'un ordonnancement explicite. La recherche sur les protocoles d'héritage de priorité aborde le problème connexe de l'inversion de priorité, et des outils de vérification formelle tels que TLA+ sont couramment utilisés pour prouver l'absence d'interblocage dans les systèmes concurrents de production.