TNSI : OS - TD Le Dîner des Philosophes

Introduction

Ce TD débranché illustre un deuxième type de problèmes pouvant survenir durant l'exécution de plusieurs processus: une famine.

La Situation

Col

• \(5\) philosophes (initialement, mais il peut y en avoir beaucoup plus) 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

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

Col

Des Contraintes

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 à droite (c'est-à-dire les deux fourchettes qui entourent sa propre assiette)
• si un philosophe n'arrive pas à s'emparer d'une des fourchettes (parmi les deux requises), il reste affamé pendant un temps déterminé, en attendant de renouveler sa tentative.

Questions

Le problème consiste à trouver un ordonnancement des philosophes tel qu'ils puissent tous manger, chacun à leur tour.

1. Décrire une situation d’interblocage, en détaillant les conditions de Coffman.
2. Que faire si un philosophe meurt de faim alors qu’il a une fourchette en main (i.e. un processus se crashe alors qu’il utilise une ressource) ? La question est assez rhétorique, elle est là juste pour que vous réalisiez le problème dans ce cas.
3. On propose une solution, basée sur la règle suivante : « un philosophe ayant une seule fourchette la repose après 10 minutes, et attend 10 minutes avant de la reprendre ». Cette règle permet-elle d’éviter l’interblocage ? Justifier.
4. Une autre solution est basée sur la hiérarchisation des ressources. Les fourchettes sont numérotées de 1 à 5, pas forcément dans l’ordre de leur emplacement sur la table. Les philosophes connaissent les numéros des fourchettes dont ils ont besoin pour manger. Un philosophe prendra d’abord la fourchette de numéro le plus bas, avant de prendre celle de numéro le plus haut. Cette méthode permet-elle d’éviter l’interblocage ? Justifier
5. On reprend la méthode précédente. On rajoute du parmesan à table, de numéro 0. Les philosophes ont maintenant besoin de 3 ressources : les deux fourchettes et le parmesan. Supposons que le parmesan soit libre, et qu’un philosophe ait les fourchettes 1 et 4. Que doit-il faire pour manger ? Conclure sur un des défauts de cette méthode.

6. Une méthode générale est proposée, pour un nombre quelconque de philosophes nécessitant un nombre quelconque de ressources.

7. Les fourchettes sont soit propres, soit sales.

8. Pour chaque paire de philosophes pouvant accéder à la même fourchette, on commence par la donner à celui qui est en premier dans l’ordre alphabétique.
9. Un philosophe qui veut manger doit obtenir les fourchettes de ses deux voisins. Pour chaque fourchette qui lui manque, il émet poliment une requête.
10. 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.
11. 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.
    Montrer qu’il reste une situation d’interblocage possible, au démarrage. Préciser la condition à rajouter pour que cette situation ne puisse pas parvenir. Expliquer qu’alors ces règles permettent d’éviter l’interblocage (on pourra se contenter de deux philosophes). Une rédaction correcte est exigée.
12. Trouver une solution simple pour éviter l’interblocage, dans le cas où le nombre de philosophes est pair (on les numérotera et raisonnera sur la parité).