Diner des philosophes

Diner des philosophes

Dîner des philosophes

Le problème des philosophes et des spaghettis est le cas d'école concernant le problème classique de partage de ressources en informatique système. Il concerne l'ordonnancement des processus et l'allocation des ressources à ces derniers. Ce problème a été énoncé par Edsger Dijkstra[1].

Sommaire

Le problème

Illustration du problème

La situation est la suivante :

  • cinq philosophes (initialement mais il peut y en avoir beaucoup plus, du moment que leur nombre soit impair) se trouvent autour d'une table ;
  • chacun des philosophes a devant lui un plat de spaghetti ;
  • à gauche de chaque assiette se trouve une fourchette.

Un philosophe n'a que trois états possibles :

  • penser pendant un temps indéterminé ;
  • être affamé (pendant un temps déterminé et fini sinon il y a famine) ;
  • manger pendant un temps déterminé et fini.

Des contraintes extérieures s'imposent à cette situation :

  • quand un philosophe a faim, il va se mettre dans l'état « affamé » et attendre que les fourchettes soient libres ;
  • pour manger, un philosophe a besoin de deux fourchettes : celle qui se trouve à gauche de sa propre assiette, et celle qui se trouve à gauche de celle de son voisin de droite (c'est-à-dire les deux fourchettes qui entourent sa propre assiette) ;
  • si un philosophe n'arrive pas à s'emparer d'une fourchette, il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative.

Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger, chacun à leur tour. Cet ordre est imposé par la solution que l'on considère comme celle de Dijkstra avec sémaphores ou Courtois avec des compteurs.

Remarques

Le problème du crash de processus : Socrate boit la ciguë et meurt avec sa fourchette gauche en main, empêchant définitivement Voltaire de manger.
  • Les philosophes, s'ils agissent tous de façons naïves et identiques, risquent fort de se retrouver en situation d'interblocage. En effet, il suffit que chacun saisisse sa fourchette de gauche et, qu'ensuite, chacun attende que sa fourchette de droite se libère pour qu'aucun d'entre eux ne puisse manger, et ce pour l'éternité.
  • On considère qu'un philosophe qui meurt (crash du processus) reste dans une phase « penser » infiniment. Il en résulte donc un problème : quid d'un philosophe qui meurt avec ses fourchettes en main ?
  • Ce problème beaucoup plus complexe qu'il n'en a l'air est l'un des plus intéressants parmi les problèmes de systèmes distribués.

Solutions

  • L'une des principales solutions à ce problème est celle du sémaphore, proposée également 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 embêtés par une telle situation. Notamment une toute simple se basant sur 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 élégant et générique est le suivant :

  1. 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.
  2. Lorsqu'un philosophe veut manger, il doit obtenir les fourchettes de ses deux voisins. Pour chaque fourchette qu'il lui manque, il émet poliment une requête.
  3. 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, alors il la nettoie et il la donne.
  4. 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. On numérote les philosophes selon leur place à la table. Et l'on fait que les philosophes ayant un nombre pair prennent d'abord leur fourchette gauche, puis leur droite et l'inverse avec les philosophes ayant un nombre impair.

Preuve de l'exactitude de cette solution

Étudions le cas d'un philosophe qui prend d'abord sa fourchette gauche. S'il arrive à la prendre, 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 nos philosophes ne se bloqueront jamais.

La compréhension de cette solution est plus aisée en prenant pour exemple la présence de deux philosophes.

Notes et références

  1. Edsger W. Dijkstra, « Hierarchical ordering of sequential processes », dans Acta Informatica, vol. 1, 1971, p. 115-138 [texte intégral (page consultée le 2007-11-10)] 

Voir aussi

Lien externe

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « D%C3%AEner des philosophes ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Diner des philosophes de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Dîner Des Philosophes — Le problème des philosophes et des spaghettis est le cas d école concernant le problème classique de partage de ressources en informatique système. Il concerne l ordonnancement des processus et l allocation des ressources à ces derniers. Ce… …   Wikipédia en Français

  • Dîner des philosophes — Le problème des philosophes et des spaghettis est le cas d école concernant le problème classique de partage de ressources en informatique système. Il concerne l ordonnancement des processus et l allocation des ressources à ces derniers. Ce… …   Wikipédia en Français

  • Problème des philosophes aux spaghettis — Dîner des philosophes Le problème des philosophes et des spaghettis est le cas d école concernant le problème classique de partage de ressources en informatique système. Il concerne l ordonnancement des processus et l allocation des ressources à… …   Wikipédia en Français

  • Problème des philosophes et des spaghetti — Dîner des philosophes Le problème des philosophes et des spaghettis est le cas d école concernant le problème classique de partage de ressources en informatique système. Il concerne l ordonnancement des processus et l allocation des ressources à… …   Wikipédia en Français

  • Probleme des lecteurs et des redacteurs — Problème des lecteurs et des rédacteurs Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra,… …   Wikipédia en Français

  • Problème des lecteurs et des rédacteurs — Le problème des lecteurs et des rédacteurs est un problème classique en théorie informatique, qui permet de modéliser les accès à des bases de données. Il fut énoncé sous cette forme par Edsger Dijkstra, qui est également à l origine du problème… …   Wikipédia en Français

  • Liste d'athées célèbres (philosophes et penseurs) — Article principal : Liste d athées célèbres. Cet article contient une liste d athées qui étaient des philosophes ou des penseurs célèbres. Les athées sont des personnes qui ne conçoivent pas l’existence ou affirment l’inexistence des dieux… …   Wikipédia en Français

  • Le couvent des bernardines réformées de Grenoble — Monastère Sainte Cécile de Grenoble Le monastère Sainte Cécile de Grenoble est un couvent de femmes située à Grenoble dont toute l’existence se déroule entre deux bornes historiques : la contre réforme catholique et la révolution. Le… …   Wikipédia en Français

  • Régime alimentaire des Grecs antiques — Alimentation en Grèce antique Kylix, type de vase à boire le plus fréquent en Grèce antique, v. 500 av. J. C., British Museum Le régime alimentaire des Grecs antiques se caractérise par sa frugalité, reflet de conditions difficiles pour l… …   Wikipédia en Français

  • Culture des communications — Communication Pour les articles homonymes, voir Communication (homonymie). La communication (souvent abrégée en com) est l action, le fait de communiquer, d établir une relation avec autrui, de transmettre quelque chose à quelqu un, l ensemble… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”