Le problème des philosophes de la restauration à Java

1. Introduction

Le problème Dining Philosophers est l'un des problèmes classiques utilisés pour décrire les problèmes de synchronisation dans un environnement multithread et illustrer les techniques permettant de les résoudre . Dijkstra a d'abord formulé ce problème et l'a présenté concernant les ordinateurs accédant aux périphériques de lecteur de bande.

La formulation actuelle a été donnée par Tony Hoare, qui est également connu pour avoir inventé l'algorithme de tri par tri rapide. Dans cet article, nous analysons ce problème bien connu et codons une solution populaire.

2. Le problème

Le diagramme ci-dessus représente le problème. Il y a cinq philosophes silencieux (P1 - P5) assis autour d'une table circulaire, passant leur vie à manger et à réfléchir.

Il y a cinq fourchettes à partager (1 à 5) et pour pouvoir manger, un philosophe doit avoir des fourchettes dans ses deux mains. Après avoir mangé, il les pose tous les deux, puis ils peuvent être choisis par un autre philosophe qui répète le même cycle.

Le but est de proposer un schéma / protocole qui aide les philosophes à atteindre leur objectif de manger et de penser sans mourir de faim.

3. Une solution

Une première solution serait de faire suivre à chacun des philosophes le protocole suivant:

while(true) { // Initially, thinking about life, universe, and everything think(); // Take a break from thinking, hungry now pick_up_left_fork(); pick_up_right_fork(); eat(); put_down_right_fork(); put_down_left_fork(); // Not hungry anymore. Back to thinking! } 

Comme le décrit le pseudo code ci-dessus, chaque philosophe réfléchit au départ. Au bout d'un certain temps, le philosophe a faim et souhaite manger.

À ce stade, il prend les fourchettes de chaque côté et une fois qu'il les a tous les deux, il se met à manger . Une fois le repas terminé, le philosophe pose alors les fourchettes pour qu'elles soient disponibles pour son voisin.

4. Mise en œuvre

Nous modélisons chacun de nos philosophes comme des classes qui implémentent l' interface Runnable afin de pouvoir les exécuter en tant que threads séparés. Chaque philosophe a accès à deux fourches sur ses côtés gauche et droit:

public class Philosopher implements Runnable { // The forks on either side of this Philosopher private Object leftFork; private Object rightFork; public Philosopher(Object leftFork, Object rightFork) { this.leftFork = leftFork; this.rightFork = rightFork; } @Override public void run() { // Yet to populate this method } }

Nous avons également une méthode qui demande à un philosophe d'effectuer une action - manger, penser ou acquérir des fourchettes en préparation pour manger:

public class Philosopher implements Runnable { // Member variables, standard constructor private void doAction(String action) throws InterruptedException { System.out.println( Thread.currentThread().getName() + " " + action); Thread.sleep(((int) (Math.random() * 100))); } // Rest of the methods written earlier }

Comme indiqué dans le code ci-dessus, chaque action est simulée en suspendant le thread appelant pendant une durée aléatoire, de sorte que l'ordre d'exécution ne soit pas appliqué uniquement par le temps.

Maintenant, implémentons la logique de base d'un philosophe .

Pour simuler l'acquisition d'un fork, nous devons le verrouiller afin que deux threads Philosopher ne l' acquièrent pas en même temps.

Pour ce faire, nous utilisons le mot-clé synchronized pour acquérir le moniteur interne de l'objet fork et empêcher les autres threads de faire de même. Un guide sur le mot-clé synchronisé en Java peut être trouvé ici. Nous procédons maintenant à l'implémentation de la méthode run () dans la classe Philosopher :

public class Philosopher implements Runnable { // Member variables, methods defined earlier @Override public void run() { try { while (true) { // thinking doAction(System.nanoTime() + ": Thinking"); synchronized (leftFork) { doAction( System.nanoTime() + ": Picked up left fork"); synchronized (rightFork) { // eating doAction( System.nanoTime() + ": Picked up right fork - eating"); doAction( System.nanoTime() + ": Put down right fork"); } // Back to thinking doAction( System.nanoTime() + ": Put down left fork. Back to thinking"); } } } catch (InterruptedException e) { Thread.currentThread().interrupt(); return; } } } 

Ce schéma met en œuvre exactement celui décrit précédemment: un philosophe réfléchit un moment puis décide de manger.

Après cela, il acquiert les fourchettes à sa gauche et à sa droite et commence à manger. Une fois terminé, il pose les fourches. Nous ajoutons également des horodatages à chaque action, ce qui nous aiderait à comprendre l'ordre dans lequel les événements se produisent.

Pour lancer l'ensemble du processus, nous écrivons un client qui crée 5 Philosophes en tant que threads et les démarre tous:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; philosophers[i] = new Philosopher(leftFork, rightFork); Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } }

Nous modélisons chacune des fourches en tant qu'objets Java génériques et en fabriquons autant que de philosophes. On passe à chaque Philosophe ses fourches gauche et droite qu'il tente de verrouiller à l'aide du mot-clé synchronized .

L'exécution de ce code entraîne une sortie similaire à ce qui suit. Votre sortie sera très probablement différente de celle donnée ci-dessous, principalement parce que la méthode sleep () est appelée pour un intervalle différent:

Philosopher 1 8038014601251: Thinking Philosopher 2 8038014828862: Thinking Philosopher 3 8038015066722: Thinking Philosopher 4 8038015284511: Thinking Philosopher 5 8038015468564: Thinking Philosopher 1 8038016857288: Picked up left fork Philosopher 1 8038022332758: Picked up right fork - eating Philosopher 3 8038028886069: Picked up left fork Philosopher 4 8038063952219: Picked up left fork Philosopher 1 8038067505168: Put down right fork Philosopher 2 8038089505264: Picked up left fork Philosopher 1 8038089505264: Put down left fork. Back to thinking Philosopher 5 8038111040317: Picked up left fork

Tous les Philosophe commencent d'abord à penser, et nous voyons que Philosophe 1 procède à ramasser la fourche gauche et droite, puis mange et se met à les placer tous les deux, après quoi «Philosophe 5» le prend.

5. Le problème avec la solution: blocage

Bien qu'il semble que la solution ci-dessus soit correcte, il y a un problème de blocage.

Un blocage est une situation dans laquelle la progression d'un système est interrompue car chaque processus attend d'acquérir une ressource détenue par un autre processus.

Nous pouvons confirmer la même chose en exécutant le code ci-dessus plusieurs fois et en vérifiant que parfois, le code se bloque. Voici un exemple de sortie qui illustre le problème ci-dessus:

Philosopher 1 8487540546530: Thinking Philosopher 2 8487542012975: Thinking Philosopher 3 8487543057508: Thinking Philosopher 4 8487543318428: Thinking Philosopher 5 8487544590144: Thinking Philosopher 3 8487589069046: Picked up left fork Philosopher 1 8487596641267: Picked up left fork Philosopher 5 8487597646086: Picked up left fork Philosopher 4 8487617680958: Picked up left fork Philosopher 2 8487631148853: Picked up left fork

Dans cette situation, chacun des Philosophe a acquis sa fourche gauche, mais ne peut pas acquérir sa fourche droite, car son voisin l'a déjà acquise. Cette situation est communément appelée attente circulaire et est l'une des conditions qui entraîne un blocage et empêche la progression du système.

6. Résolution de l'impasse

Comme nous l'avons vu ci-dessus, la principale raison d'un blocage est la condition d'attente circulaire où chaque processus attend une ressource détenue par un autre processus. Par conséquent, pour éviter une situation de blocage, nous devons nous assurer que la condition d'attente circulaire est rompue. Il existe plusieurs façons d'y parvenir, la plus simple étant la suivante:

Tous les Philosophes atteignent d'abord leur fourche gauche, sauf un qui atteint d'abord sa fourche droite.

Nous implémentons cela dans notre code existant en apportant une modification relativement mineure au code:

public class DiningPhilosophers { public static void main(String[] args) throws Exception { final Philosopher[] philosophers = new Philosopher[5]; Object[] forks = new Object[philosophers.length]; for (int i = 0; i < forks.length; i++) { forks[i] = new Object(); } for (int i = 0; i < philosophers.length; i++) { Object leftFork = forks[i]; Object rightFork = forks[(i + 1) % forks.length]; if (i == philosophers.length - 1) { // The last philosopher picks up the right fork first philosophers[i] = new Philosopher(rightFork, leftFork); } else { philosophers[i] = new Philosopher(leftFork, rightFork); } Thread t = new Thread(philosophers[i], "Philosopher " + (i + 1)); t.start(); } } } 

Le changement intervient aux lignes 17-19 du code ci-dessus, où nous introduisons la condition qui oblige le dernier philosophe à atteindre sa fourche droite en premier, au lieu de la gauche. Cela brise la condition d'attente circulaire et nous pouvons éviter l'impasse.

La sortie suivante montre l'un des cas où tous les Philosophe ont la possibilité de réfléchir et de manger, sans provoquer de blocage:

Philosopher 1 88519839556188: Thinking Philosopher 2 88519840186495: Thinking Philosopher 3 88519840647695: Thinking Philosopher 4 88519840870182: Thinking Philosopher 5 88519840956443: Thinking Philosopher 3 88519864404195: Picked up left fork Philosopher 5 88519871990082: Picked up left fork Philosopher 4 88519874059504: Picked up left fork Philosopher 5 88519876989405: Picked up right fork - eating Philosopher 2 88519935045524: Picked up left fork Philosopher 5 88519951109805: Put down right fork Philosopher 4 88519997119634: Picked up right fork - eating Philosopher 5 88519997113229: Put down left fork. Back to thinking Philosopher 5 88520011135846: Thinking Philosopher 1 88520011129013: Picked up left fork Philosopher 4 88520028194269: Put down right fork Philosopher 4 88520057160194: Put down left fork. Back to thinking Philosopher 3 88520067162257: Picked up right fork - eating Philosopher 4 88520067158414: Thinking Philosopher 3 88520160247801: Put down right fork Philosopher 4 88520249049308: Picked up left fork Philosopher 3 88520249119769: Put down left fork. Back to thinking 

Il peut être vérifié en exécutant le code plusieurs fois, que le système est libre de la situation de blocage qui s'est produite auparavant.

7. Conclusion

Dans cet article, nous avons exploré le célèbre problème des philosophes de la restauration et les concepts d'attente circulaire et de blocage . Nous avons codé une solution simple qui a provoqué une impasse et apporté une modification simple pour rompre l'attente circulaire et éviter une impasse. Ce n'est qu'un début et des solutions plus sophistiquées existent.

Le code de cet article se trouve à l'adresse over sur GitHub.