Dîner des philosophes
Le problème du dîner des philosophes, énoncé par Edsger Dijkstra[1], met en scène une tablée de philosophes qui se partagent des fourchettes pour déguster des spaghettis. Son but est d'illustrer le phénomène d'interblocage pouvant survenir dans un système informatique lors d'un partage de ressources, ici représentées par des fourchettes. Il permet d'illustrer les conditions de cet interblocage, puis de trouver des solutions pour le prévenir.
Ce problème est utilisé principalement dans l'étude de l'ordonnancement des processus et l'allocation des ressources à ces derniers.
Énoncé du problème
Les conditions initiales sont les suivantes :
- N philosophes (dans cet exemple, 5) se trouvent autour d'une table ;
- Chacun des philosophes a devant lui un plat de spaghettis ;
- À gauche de chaque plat de spaghettis se trouve une fourchette ;
- Pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à gauche de sa propre assiette, et celle qui se trouve à droite (c'est-à-dire les deux fourchettes qui entourent sa propre assiette).
Un philosophe a trois états possibles :
- Penseur : Le philosophe pense durant une période indéterminée. Il n'a aucune fourchette dans la main et ne cherche pas à en avoir. Cet état peut être comparé à un processus qui dort.
- Affamé : Le philosophe souhaite manger et pour cela, il cherchera à acquérir la fourchette à sa gauche ainsi que celle à sa droite. Dans le cas où il attend jusqu'à ce qu'il réussisse, le système peut se retrouver en état de famine.
- Mangeur : Le philosophe mange durant une période déterminée et finie.
Dans ces conditions, le système peut se trouver en situation d'interblocage. Par exemple, si tous les philosophes se mettent simultanément en état Affamé et prennent la fourchette située à leur gauche, aucun philosophe ne pourra alors prendre la fourchette située à sa droite (puisque celle-ci a déjà été prise par le philosophe situé à sa droite). Le système sera alors bloqué à l'infini si aucun philosophe ne libère sa fourchette.
La solution à ce problème consiste à trouver un ordonnancement du partage des fourchettes entre les philosophes qui permet à chacun d'entre eux de manger. Dijkstra a proposé une solution basée sur des sémaphores et Courtois en a proposé une utilisant des compteurs.
Remarques
- On considère qu'un philosophe qui meurt (crash du processus) reste indéfiniment Penseur. Cependant, si un philosophe meurt alors qu'il tient une fourchette, cette fourchette reste bloquées, empêchant potentiellement les autres philosophes de manger.Ce cas illustre un problème de gestion des ressources en présence de défaillances.
- Autre appellation : Ce problème est parfois appelé "problème des baguettes chinoises", car la situation est identique si les philosophes utilisent des baguettes au lieu de fourchettes.
Solutions
- L'une des principales solutions à ce problème est celle du sémaphore, proposée par Dijkstra.
- Une autre solution consiste à attribuer à chaque philosophe un temps de réflexion aléatoire en cas d'échec (cette solution est en réalité incorrecte).
- Il existe des compromis qui permettent de limiter le nombre de philosophes gênés par une telle situation. Par exemple, la technique hiérarchique de Havender limite le nombre de philosophes touchés à un d'un côté et deux de l'autre.
La solution de Chandy/Misra
En 1984, K. M. Chandy et J. Misra proposèrent une nouvelle solution permettant à un nombre arbitraire n d'agents identifiés par un nom quelconque d'utiliser un nombre m de ressources. Le protocole générique est le suivant :
- Pour chaque paire de philosophes pouvant accéder à la même fourchette, on commence par la donner à celui des deux qui a le plus petit nom (selon une certaine relation d'ordre). Toute fourchette est soit propre, soit sale. Au début, toutes les fourchettes sont sales.
- Lorsqu'un philosophe veut manger, il doit obtenir les fourchettes de ses deux voisins. Pour chaque fourchette qui lui manque, il émet poliment une requête.
- Lorsqu'un philosophe qui a une fourchette en main entend une requête pour celle-ci :
- Soit la fourchette est propre et il la garde.
- Soit la fourchette est sale, auquel cas il la nettoie et la donne.
- Après qu'un philosophe a fini de manger, ses deux fourchettes sont devenues sales. Si un autre philosophe avait émis une requête pour obtenir une de ses fourchettes, il la nettoie et la donne.
Solution dans le cas pair
Dans le cas pair, une solution simple existe : numéroter les philosophes selon leur place, et les séparer en deux groupes, pairs et impairs. L'un des groupes commence par prendre la fourchette gauche, puis la droite, tandis que le deuxième groupe fait l'inverse.
Preuve de l'exactitude de cette solution
Étudions le cas d'un philosophe qui prend d'abord sa fourchette gauche. S'il y arrive, il ne lui reste plus qu'à prendre sa fourchette droite. Celle-ci ne peut être définitivement bloquée : si le philosophe de droite la tient, c'est qu'il est en train de manger (il tient dans ce cas ses deux fourchettes). Ainsi, les philosophes ne se bloqueront jamais.
La compréhension de cette solution est plus aisée en prenant pour exemple l'instance à deux philosophes.
Notes et références
- ↑ (en) Edsger W. Dijkstra, « Hierarchical ordering of sequential processes », Acta Informatica, vol. 1, , p. 115-138 (lire en ligne, consulté le )
Voir aussi
Articles connexes
Lien externe
- « Illustration du problème des philosophes »(Archive.org • Wikiwix • Archive.is • Google • Que faire ?) (consulté le ) (applet Java)
