Le problème du philosophe à manger est le problème classique de synchronisation qui dit que cinq philosophes sont assis autour d'une table circulaire et que leur travail est de penser et de manger alternativement. Un bol de nouilles est placé au centre de la table ainsi que cinq baguettes pour chacun des philosophes. Pour manger, un philosophe a besoin de sa baguette droite et de sa baguette gauche. Un philosophe ne peut manger que si les baguettes gauche et droite immédiates du philosophe sont disponibles. Dans le cas où les baguettes gauche et droite immédiates du philosophe ne sont pas disponibles, le philosophe pose sa baguette (gauche ou droite) et recommence à réfléchir.
Le philosophe de la restauration démontre une large classe de problèmes de contrôle de concurrence, il s'agit donc d'un problème de synchronisation classique.
Cinq philosophes assis autour de la table
Problème des philosophes de la restauration - Comprenons le problème des philosophes de la restauration avec le code ci-dessous, nous avons utilisé la figure 1 comme référence pour vous faire comprendre exactement le problème. Les cinq philosophes sont représentés par P0, P1, P2, P3 et P4 et les cinq baguettes par C0, C1, C2, C3 et C4.
Void Philosopher { while(1) { take_chopstick[i]; take_chopstick[ (i+1) % 5] ; . . . EATING THE NOODLE . put_chopstick[i] ); put_chopstick[ (i+1) % 5] ; . . THINKING } } Discutons du code ci-dessus :
Supposons que Philosopher P0 veuille manger, il entrera dans la fonction Philosopher() et exécutera prends_baguette[i]; en faisant ça ça tient baguette C0 après cela, il exécute take_chopstick[ (i+1) % 5]; en faisant ça ça tient baguette C1 (puisque i =0, donc (0 + 1) % 5 = 1)
De la même manière, supposons que Philosopher P1 veuille manger, il entrera dans la fonction Philosopher() et exécutera prends_baguette[i]; en faisant ça ça tient baguette C1 après cela, il exécute take_chopstick[ (i+1) % 5]; en faisant ça ça tient baguette C2 (puisque i =1, donc (1 + 1) % 5 = 2)
Mais pratiquement, Chopstick C1 n'est pas disponible car il a déjà été pris par le philosophe P0, donc le code ci-dessus génère des problèmes et produit une condition de concurrence critique.
La solution du problème des philosophes de la restauration
Nous utilisons un sémaphore pour représenter une baguette et cela constitue véritablement une solution au problème des philosophes de la restauration. Les opérations d'attente et de signal seront utilisées pour la solution du problème des philosophes de la salle à manger, pour choisir une opération d'attente de baguette peut être exécutée tandis que pour libérer un signal de baguette, un sémaphore peut être exécuté.
conventions de dénomination Java
Sémaphore : un sémaphore est une variable entière dans S, à laquelle, outre l'initialisation, on accède par seulement deux opérations atomiques standard : attendre et signaler, dont les définitions sont les suivantes :
1. wait( S ) { while( S <= 0) ; s--; } 2. signal( s ) { s++; < pre> <p>From the above definitions of wait, it is clear that if the value of S <= 0 then it will enter into an infinite loop(because of the semicolon; after while loop). whereas job signal is to increment value s.< p> <p>The structure of the chopstick is an array of a semaphore which is represented as shown below -</p> <pre> semaphore C[5]; </pre> <p>Initially, each element of the semaphore C0, C1, C2, C3, and C4 are initialized to 1 as the chopsticks are on the table and not picked up by any of the philosophers.</p> <p>Let's modify the above code of the Dining Philosopher Problem by using semaphore operations wait and signal, the desired code looks like</p> <pre> void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } </pre> <p>In the above code, first wait operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows philosopher i have picked up the chopsticks from its left and right. The eating function is performed after that.</p> <p>On completion of eating by philosopher i the, signal operation is performed on take_chopstickC[i] and take_chopstickC [ (i+1) % 5]. This shows that the philosopher i have eaten and put down both the left and right chopsticks. Finally, the philosopher starts thinking again.</p> <h3>Let's understand how the above code is giving a solution to the dining philosopher problem?</h3> <p>Let value of i = 0( initial value ), Suppose Philosopher P0 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C0 chopstick</strong> and reduces semaphore C0 to 0 <strong>,</strong> after that it execute <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C1 chopstick</strong> ( since i =0, therefore (0 + 1) % 5 = 1) and reduces semaphore C1 to 0</p> <p>Similarly, suppose now Philosopher P1 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it will try to hold <strong>C1 chopstick</strong> but will not be able to do that <strong>,</strong> since the value of semaphore C1 has already been set to 0 by philosopher P0, therefore it will enter into an infinite loop because of which philosopher P1 will not be able to pick chopstick C1 whereas if Philosopher P2 wants to eat, it will enter in Philosopher() function, and execute <strong>Wait( take_chopstickC[i] );</strong> by doing this it holds <strong>C2 chopstick</strong> and reduces semaphore C2 to 0, after that, it executes <strong>Wait( take_chopstickC[(i+1) % 5] );</strong> by doing this it holds <strong>C3 chopstick</strong> ( since i =2, therefore (2 + 1) % 5 = 3) and reduces semaphore C3 to 0.</p> <p>Hence the above code is providing a solution to the dining philosopher problem, A philosopher can only eat if both immediate left and right chopsticks of the philosopher are available else philosopher needs to wait. Also at one go two independent philosophers can eat simultaneously (i.e., philosopher <strong>P0 and P2, P1 and P3 & P2 and P4</strong> can eat simultaneously as all are the independent processes and they are following the above constraint of dining philosopher problem)</p> <h3>The drawback of the above solution of the dining philosopher problem</h3> <p>From the above solution of the dining philosopher problem, we have proved that no two neighboring philosophers can eat at the same point in time. The drawback of the above solution is that this solution can lead to a deadlock condition. This situation happens if all the philosophers pick their left chopstick at the same time, which leads to the condition of deadlock and none of the philosophers can eat.</p> <p>To avoid deadlock, some of the solutions are as follows -</p> <ul> <li>Maximum number of philosophers on the table should not be more than four, in this case, chopstick C4 will be available for philosopher P3, so P3 will start eating and after the finish of his eating procedure, he will put down his both the chopstick C3 and C4, i.e. semaphore C3 and C4 will now be incremented to 1. Now philosopher P2 which was holding chopstick C2 will also have chopstick C3 available, hence similarly, he will put down his chopstick after eating and enable other philosophers to eat.</li> <li>A philosopher at an even position should pick the right chopstick and then the left chopstick while a philosopher at an odd position should pick the left chopstick and then the right chopstick.</li> <li>Only in case if both the chopsticks ( left and right ) are available at the same time, only then a philosopher should be allowed to pick their chopsticks</li> <li>All the four starting philosophers ( P0, P1, P2, and P3) should pick the left chopstick and then the right chopstick, whereas the last philosopher P4 should pick the right chopstick and then the left chopstick. This will force P4 to hold his right chopstick first since the right chopstick of P4 is C0, which is already held by philosopher P0 and its value is set to 0, i.e C0 is already 0, because of which P4 will get trapped into an infinite loop and chopstick C4 remains vacant. Hence philosopher P3 has both left C3 and right C4 chopstick available, therefore it will start eating and will put down its both chopsticks once finishes and let others eat which removes the problem of deadlock.</li> </ul> <p>The design of the problem was to illustrate the challenges of avoiding deadlock, a deadlock state of a system is a state in which no progress of system is possible. Consider a proposal where each philosopher is instructed to behave as follows:</p> <ul> <li>The philosopher is instructed to think till the left fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to think till the right fork is available, when it is available, hold it.</li> <li>The philosopher is instructed to eat when both forks are available.</li> <li>then, put the right fork down first</li> <li>then, put the left fork down next</li> <li>repeat from the beginning.</li> </ul> <hr></=></p></=> Initialement, chaque élément du sémaphore C0, C1, C2, C3 et C4 est initialisé à 1 car les baguettes sont sur la table et ne sont ramassées par aucun des philosophes.
Modifions le code ci-dessus du problème du philosophe de la restauration en utilisant les opérations de sémaphore wait et signal, le code souhaité ressemble à
void Philosopher { while(1) { Wait( take_chopstickC[i] ); Wait( take_chopstickC[(i+1) % 5] ) ; . . . EATING THE NOODLE . Signal( put_chopstickC[i] ); Signal( put_chopstickC[ (i+1) % 5] ) ; . . THINKING } } Dans le code ci-dessus, la première opération d'attente est effectuée sur take_chopstickC[i] et take_chopstickC [ (i+1) % 5]. Cela montre au philosophe que j'ai ramassé les baguettes à gauche et à droite. La fonction alimentaire est ensuite assurée.
À la fin du repas du philosophe i the, une opération de signal est effectuée sur take_chopstickC[i] et take_chopstickC [ (i+1) % 5]. Cela montre que le philosophe a mangé et posé les baguettes gauche et droite. Finalement, le philosophe se remet à réfléchir.
Comprenons comment le code ci-dessus donne une solution au problème du philosophe de la restauration ?
Soit la valeur de i = 0 (valeur initiale), supposons que le philosophe P0 veuille manger, il entrera dans la fonction Philosopher() et exécutera Attendez( take_chopstickC[i] ); en faisant ça ça tient baguette C0 et réduit le sémaphore C0 à 0 , après cela, il exécute Attendez( take_chopstickC[(i+1) % 5] ); en faisant ça ça tient baguette C1 (puisque i =0, donc (0 + 1) % 5 = 1) et réduit le sémaphore C1 à 0
De même, supposons maintenant que Philosopher P1 veuille manger, il entrera dans la fonction Philosopher() et exécutera Attendez( take_chopstickC[i] ); en faisant cela, il essaiera de tenir baguette C1 mais je ne pourrai pas faire ça , puisque la valeur du sémaphore C1 a déjà été mise à 0 par le philosophe P0, il entrera donc dans une boucle infinie à cause de laquelle le philosophe P1 ne pourra pas piocher la baguette C1 alors que si le philosophe P2 veut manger, il entrera dans le philosophe P2. () fonction et exécutez Attendez( take_chopstickC[i] ); en faisant ça ça tient baguette C2 et réduit le sémaphore C2 à 0, après quoi il exécute Attendez( take_chopstickC[(i+1) % 5] ); en faisant ça ça tient baguette C3 (puisque i =2, donc (2 + 1) % 5 = 3) et réduit le sémaphore C3 à 0.
Par conséquent, le code ci-dessus fournit une solution au problème du philosophe à manger. Un philosophe ne peut manger que si les baguettes gauche et droite immédiates du philosophe sont disponibles, sinon le philosophe doit attendre. De plus, deux philosophes indépendants peuvent manger simultanément en même temps (c'est-à-dire le philosophe P0 et P2, P1 et P3 & P2 et P4 peuvent manger simultanément car tous sont des processus indépendants et ils suivent la contrainte ci-dessus du problème du philosophe de la restauration)
L'inconvénient de la solution ci-dessus du problème du philosophe à manger
À partir de la solution ci-dessus du problème du philosophe dînant, nous avons prouvé que deux philosophes voisins ne peuvent pas manger au même moment. L’inconvénient de la solution ci-dessus est qu’elle peut conduire à une situation de blocage. Cette situation se produit si tous les philosophes prennent leur baguette gauche en même temps, ce qui conduit à une situation d’impasse et aucun des philosophes ne peut manger.
Pour éviter une impasse, certaines des solutions sont les suivantes :
- Le nombre maximum de philosophes sur la table ne doit pas être supérieur à quatre, dans ce cas, la baguette C4 sera disponible pour le philosophe P3, donc P3 commencera à manger et après avoir fini de manger, il posera ses deux baguettes C3. et C4, c'est-à-dire que les sémaphores C3 et C4 seront désormais incrémentés à 1. Désormais le philosophe P2 qui tenait la baguette C2 aura également la baguette C3 à sa disposition, donc de la même manière, il posera sa baguette après avoir mangé et permettra aux autres philosophes de manger.
- Un philosophe dans une position paire devrait choisir la baguette droite puis la baguette gauche tandis qu'un philosophe dans une position impaire devrait choisir la baguette gauche puis la baguette droite.
- Seulement dans le cas où les deux baguettes (gauche et droite) sont disponibles en même temps, alors seulement un philosophe devrait être autorisé à choisir ses baguettes.
- Les quatre philosophes de départ (P0, P1, P2 et P3) doivent choisir la baguette gauche puis la baguette droite, tandis que le dernier philosophe P4 doit choisir la baguette droite puis la baguette gauche. Cela forcera P4 à tenir d'abord sa baguette droite puisque la baguette droite de P4 est C0, qui est déjà tenue par le philosophe P0 et sa valeur est fixée à 0, c'est-à-dire que C0 est déjà 0, à cause de quoi P4 sera piégé dans un monde infini. la boucle et la baguette C4 restent vacantes. Par conséquent, le philosophe P3 dispose des baguettes gauche C3 et droite C4, il commencera donc à manger et posera ses deux baguettes une fois terminé et laissera les autres manger, ce qui élimine le problème de l'impasse.
La conception du problème visait à illustrer les défis consistant à éviter les blocages. Un état de blocage d'un système est un état dans lequel aucune progression du système n'est possible. Considérons une proposition où chaque philosophe est invité à se comporter comme suit :
- Il est demandé au philosophe de réfléchir jusqu'à ce que la fourche gauche soit disponible, et lorsqu'elle est disponible, de la maintenir.
- Il est demandé au philosophe de réfléchir jusqu'à ce que la bonne fourchette soit disponible, et lorsqu'elle est disponible, de la maintenir.
- Il est demandé au philosophe de manger lorsque les deux fourchettes sont disponibles.
- puis posez d'abord la fourchette droite
- puis posez ensuite la fourche gauche
- répéter depuis le début.