Overblog
Editer l'article Suivre ce blog Administration + Créer mon blog

fredericgrolleau.com


Le problème dit du "dîner des philosophes"

Publié le 9 Décembre 2021, 09:53am

Catégories : #Philo (Notions)

Le problème dit du "dîner des philosophes"

Le problème du « dîner des philosophes » est un cas d'école classique sur le partage de ressources en informatique système. Il concerne l'ordonnancement des processus et l'allocation des ressources à ces derniers et a été énoncé par Edsger Dijkstra (« Hierarchical ordering of sequential processes », Acta Informatica, vol. 1,‎ 1971, p. 115-138).

Le dîner des philosophes est un problème particulièrement intéressant, car il met en oeuvre dasn sa réalisation, deux techniques d'utilisations différentes des sémaphores : l'exclusion mutuelle classique, mais aussi la possibilité de bloquer un processus grâce à un sémaphore privé.

  1. Présentation du problème

    Considérons cinq philosophes, installés autour d'une table circulaire, et qui passent leurs temps à penser et à manger.

    NB : le nombre des philosophes peut être quelconque, mais il doit être au moins égal à cinq pour garantir le bon fonctionnement du programme.

     

    Figure 1 : Données initiales du problème des philosophes
     

    La table est mise avec cinq couverts qui sont disposés entre chacun des philosophes.

    De temps en temps, un philosophe a faim et essaye de prendre les couverts qui sont immédiatement a cotés de lui (ceux qui sont entre lui et son voisin de gauche et de droite). Un philosophe a besoin de deux couverts pour manger, et ne peut évidemment pas prendre un couvert qui est dans la main d'un voisin.

    Quand un philosophe affamé a ses deux couverts dans les mains en même temps, il mange sans libérer ses couverts. Dans le cas contraire, il doit attendre que ceux-ci deviennent libres.

     

    Figure 2 : Changements d'état des philosophes
     
     

    Enfin, quand il a finit de manger, il repose ses deux couverts et commence à penser à nouveau.

    Précisons que les philosophes mangent et pensent durant des temps aléatoires différents, leur changements d'état, se produisent donc de manière totalement asynchrone.

    Le problème même du dîner des philosophes consiste donc à réguler les changements d'état de ces derniers suivant la disponibilité des couverts, qui dépend bien entendu de l'état des voisins du philosophe concerné.

    Figure 3 : Dîner des philosophes à un instant donné

     

    Par exemple, dans notre hypothèse d'un dîner de cinq philosophes, seulement deux philosophes peuvent manger à un instant donné car les couverts ne sont pas suffisants.

    Dans ce cas, trois philosophes n'ont la possibilité que de penser ou d'être en attente de vouloir manger.

    NB : quelque soit le nombre de philosophes, on ne peut jamais avoir deux philosophes mangeant cote à cote, pour de "conflit de couverts" .
     

    Pour réaliser ce problème, nous allons supposer que, pour chaque philosophe, nous allons attribuer un processus dans la machine.

    L'état des philosophes sera stocké dans un tableau alloué dans un segment de mémoire partagé.
     

  2. L'exclusion mutuelle sur la table d'état des philosophes

    Le stockage de l'état des philosophes dans un tableau alloué en mémoire partagéimplique immédiatement l'usage d'un sémaphore d'exclusion mutuelle. Ainsi, on peut alors décrire les procédures de changement d'état des philosophes, de la manière suivante :

    Philosophe désirant manger :

    Début

        P(mutex)

        Si les deux voisins immédiats ne mangent pas Alors

            Etat = mange

        Sinon

            Etat = veut manger

            attente ...

        FSi

        V(mutex)

        mange ...

    Fin

    Philosophe arrêtant de manger, passage à l'état "pense" :

    Début

        P(mutex)

        Etat = pense

        V(mutex)

        pense ...

    Fin

    Un problème demeure, comment gérer le fait que le philosophe qui veut manger, attende avant de pouvoir le faire, et surtout sache lorsqu'il peut le faire ?
     

  3. Utilisation d'un sémaphore privé pour bloquer un processus

    Pour faire patienter le philosophe qui veut manger, nous allons utiliser pour chacun des philosophes, un sémaphore privé initialisé à 0.

    Cette pratique, particulièrement astucieuse, va servir à bloquer (en endormant le processus) le philosophe pour le faire attendre. Ce sont ces voisins, lorsqu'ils arrêteront de manger, qui le réveilleront pour qu'il puisse manger à son tour.

    Philosophe désirant manger :

    Début

        P(mutex)

        Si les deux voisins immédiats ne mangent pas Alors

            V(sémaphore privé)

            Etat = mange

        Sinon

            Etat = veut manger

        FSi

        V(mutex)

        P(sémaphore privé)

        mange ...

    Fin

    Pour expliquer l'utilisation du sémaphore privé, nous pouvons conserver cette analogie avec le distributeur de tickets.

    Si le philosophe détecte que les conditions sont remplies pour qu'il puisse manger, il effectue un appel à V pour se donner un ticket de passage : le sémaphore privé passe de 0 à 1. Alors, dans ces conditions, lorsqu'il effectue l'opération P sur ce même sémaphore privé, l'appel ne devient pas bloquant, le sémaphore repassant de 1 à 0, le philosophe mange ...

    Par contre, si le philosophe ne peut pas manger (état "veut manger"), lorsqu'il effectue uniquement son appel à P sur le sémaphore privé qui est resté à 0, il se retrouve bloqué (le processus est endormit)...

    Examinons maintenant les conditions pour que celui-ci soit libérer.

    Philosophe arrêtant de manger, passage à l'état "pense" :

    Début

        P(mutex)

        Si le voisin de gauche veut manger ET son voisin ne mange pas Alors

            Etat du voisin = mange

            V(sémaphore privé du voisin)

        FSi

        (même chose pour le voisin de droite)

        Etat = pense

        V(mutex)

        pense ...

    Fin

    Un processus endormit, c'est à dire bloqué en état "veut manger" juste avant de se mettre à manger, n'est réveillé que par un de ses voisins (de gauche ou de droite), lorsque celui-ci pose ses couverts et qu'il s'est assuré que l'autre voisin du processus endormit n'occupe pas ses couverts.

    Alors, il effectue l'opération V sur le sémaphore privé du processus endormit : le sémaphore redevient positif (valeur 0), et le processus est réveillé, il poursuit son code en se mettant à manger.

    Du point de vue système, un des gros avantages de cette pratique, est qu'elle permet de supprimer le phénomène de l'attente active, en endormant le processus temporairement inutile.

 

source : http://renaudon.chez.com/semaphor/appli.htm

Pour être informé des derniers articles, inscrivez vous :

Commenter cet article