Le Problème des Philosophes Dînant est un dilemme classique et fascinant en informatique, initialement proposé par Edsger Dijkstra. Il illustre les difficultés que l’on peut rencontrer lors de la gestion des ressources partagées et de la synchronisation dans un environnement multithreadé. Pour les développeurs Java, c’est un excellent banc d’essai pour comprendre les concepts critiques tels que le Deadlock et l’utilisation des mécanismes de verrouillage.
🤔 Qu’est-ce que le Problème des Philosophes Dînant ?
Imaginez cinq philosophes assis autour d’une table, qui alternent entre penser et manger. Au centre de la table se trouve un plat de spaghetti.
- Il y a cinq assiettes (une pour chaque philosophe).
- Il y a cinq fourchettes (ressources), chacune placée entre deux philosophes.
Pour manger, un philosophe a besoin de deux fourchettes : celle de gauche et celle de droite. Après avoir mangé, le philosophe repose les fourchettes pour que ses voisins puissent les utiliser.
Le problème survient lorsque les philosophes ne sont pas coordonnés et tentent de prendre les fourchettes simultanément.
💥 Le Piège du Deadlock (Étreinte Mortelle)
La principale menace de ce problème est l’Étreinte Mortelle (Deadlock).
Imaginez le scénario suivant :
- Chacun des cinq philosophes prend d’abord la fourchette située à sa gauche.
- Maintenant, chaque philosophe est bloqué, attendant indéfiniment que son voisin repose la fourchette de droite, qui est déjà tenue par ce voisin !
Chaque philosophe attend une ressource (fourchette de droite) détenue par un autre, et réciproquement. Aucun ne peut avancer, manger ou libérer la ressource qu’il détient. C’est le Deadlock.
💻 Implémentation en Java (Le Code Problématique)
En Java, nous modélisons les philosophes comme des Threads et les fourchettes comme des objets Lock (par exemple, ReentrantLock ou des verrous implicites synchronized).
1. Le Code sans Synchronisation (Qui mène au Deadlock)
Pour simuler le Deadlock, chaque thread (philosophe) tentera d’acquérir les verrous (fourchettes) dans le même ordre (gauche puis droite).
Java
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class PhilosopheDeadlock implements Runnable {
private final int id;
private final Lock fourchetteGauche;
private final Lock fourchetteDroite;
public PhilosopheDeadlock(int id, Lock fg, Lock fd) {
this.id = id;
this.fourchetteGauche = fg;
this.fourchetteDroite = fd;
}
private void manger() throws InterruptedException {
// Tenter d'acquérir les verrous dans le MÊME ORDRE pour tous
fourchetteGauche.lock(); // 1. Prend la fourchette de gauche
System.out.println("Philosophe " + id + " a pris la fourchette GAUCHE.");
// Simuler le temps de réflexion / délai avant de prendre la seconde
Thread.sleep(100);
fourchetteDroite.lock(); // 2. Tente de prendre la fourchette de droite
System.out.println("Philosophe " + id + " Mange. (G: " + fourchetteGauche.hashCode() + ", D: " + fourchetteDroite.hashCode() + ")");
// Libération
fourchetteDroite.unlock();
fourchetteGauche.unlock();
System.out.println("Philosophe " + id + " a fini de manger et PENSE.");
}
@Override
public void run() {
try {
while (true) { // Boucle de vie (manger, penser)
manger();
Thread.sleep(500); // Penser
}
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}
public static void main(String[] args) {
Lock[] fourchettes = new Lock[5];
for (int i = 0; i < 5; i++) {
fourchettes[i] = new ReentrantLock();
}
Thread[] philosophes = new Thread[5];
for (int i = 0; i < 5; i++) {
Lock fg = fourchettes[i];
Lock fd = fourchettes[(i + 1) % 5]; // La fourchette de droite est celle du voisin
// Les 5 philosophes tentent de prendre la gauche puis la droite.
PhilosopheDeadlock p = new PhilosopheDeadlock(i, fg, fd);
philosophes[i] = new Thread(p);
philosophes[i].start();
}
}
}
Ce code, surtout si on augmente le délai (Thread.sleep(100)), finira par se bloquer. Tous les philosophes prendront leur fourchette gauche, et s’arrêteront, attendant la droite.
✅ Solution pour Éviter le Deadlock
Pour résoudre le problème du Deadlock, il faut briser l’une des quatre conditions de Coffman (qui mènent au Deadlock). La solution la plus courante ici est d’éliminer la condition de l’attente circulaire.
2. La Stratégie du Tri des Ressources (Breaking the Circular Wait)
La solution la plus simple et la plus élégante est d’imposer un ordre d’acquisition des ressources.
- Quatre des philosophes prendront toujours la fourchette avec l’ID le plus bas en premier.
- Le cinquième philosophe (le dernier) fera l’inverse : il prendra la fourchette avec l’ID le plus haut en premier.
Cela garantit qu’il y aura toujours au moins un philosophe qui pourra acquérir les deux ressources, manger, et libérer les fourchettes, permettant au cycle de se briser.
Code Java Corrigé (La Stratégie du Dernier Philosophe)
On modifie la logique dans la fonction manger() pour le cinquième philosophe (ou l’un d’eux, nous choisirons le philosophe d’ID 4 dans le main).
Java
// ... (Classe Philosophe sans changement, mais nous devons changer comment elle est instanciée)
public static void main(String[] args) {
Lock[] fourchettes = new Lock[5];
for (int i = 0; i < 5; i++) {
fourchettes[i] = new ReentrantLock();
}
Thread[] philosophes = new Thread[5];
for (int i = 0; i < 5; i++) {
Lock fg = fourchettes[i];
Lock fd = fourchettes[(i + 1) % 5];
// Règle de l'ordre :
Lock firstLock = (i == 4) ? fd : fg; // Le philosophe 4 prend la fourchette de DROITE (ID la plus haute) en premier.
Lock secondLock = (i == 4) ? fg : fd; // Les autres prennent la fourchette de GAUCHE (ID la plus basse) en premier.
// Note: Nous pouvons réutiliser la même classe PhilosopheDeadlock,
// mais nous passons les verrous dans l'ordre CORRECT (firstLock, secondLock)
// dans le constructeur.
PhilosopheDeadlock p = new PhilosopheDeadlock(i, firstLock, secondLock); // L'ordre est maintenant contrôlé ici.
philosophes[i] = new Thread(p);
philosophes[i].start();
}
}
// ... et on modifie la fonction manger pour qu'elle utilise this.fourchetteGauche
// et this.fourchetteDroite dans l'ordre où elles ont été passées :
private void manger() throws InterruptedException {
// firstLock (fourchetteGauche) est la première ressource à prendre
fourchetteGauche.lock();
System.out.println("Philosophe " + id + " a pris la première fourchette.");
Thread.sleep(100);
// secondLock (fourchetteDroite) est la deuxième ressource
fourchetteDroite.lock();
System.out.println("Philosophe " + id + " Mange...");
// Libération
fourchetteDroite.unlock();
fourchetteGauche.unlock();
System.out.println("Philosophe " + id + " a fini et PENSE.");
}
Avec cette approche, le Deadlock est évité. Tous les philosophes sauf un essaient de prendre la plus petite ressource d’abord, et le dernier philosophe fait l’inverse, garantissant qu’un cycle d’attente ne peut pas se former.
Conclusion
Le Problème des Philosophes Dînant est plus qu’un simple jeu d’esprit ; c’est un miroir des défis réels de la programmation concurrente. En Java, il nous enseigne l’importance vitale d’une gestion correcte des verrous et de l’implémentation de stratégies d’acquisition de ressources pour prévenir le Deadlock. Bien que d’autres solutions existent (comme l’utilisation de Timeouts ou de l’approche Monitor), la stratégie du tri des ressources reste l’exemple le plus didactique pour illustrer la rupture de l’attente circulaire.
