Dîner des philosophes

Quelques trucs à comprendre au préalable :

L'idiome de classe Incopiable
Les Mutex portables
Les verrous RAII tels que la classe Autoverrou

Notez que le code proposé ici est du code C++ 11, ce qui explique que nous y utilisions les outils standards plutôt que les outils maison.

J'utiliserai aussi un monitor<T>, bonne idée proposée par Herb Sutter.

Ce qui suit montre quelques solutions possibles au célèbre problème du dîner des philosophes, mis de l'avant par Edgser W. Dijkstra en 1965. L'article se décline en plusieurs parties :

Quelques éléments de base, utiles pour implémenter chacune des solutions :
- une classe monitor<T> permettant des affichages synchronisés
- un programme de test, qui a chaque fois la même forme, puis
Une partie spécifique à chacune des propositions de solution. Vous trouverez bien sûr dans ce cas une partie pour :
- la solution 0, qui est une non-solution parce qu'elle est justement trop naïve, et mène occasionnellement (ou souvent, selon le contexte) à des conditions de course
- la solution 1, qui repose sur la présence d'un serveur (un Waiter)
- la solution 2, qui repose sur un protocole et sur un ordonnancement particulier des baguettes, et
- la solution 3, qui repose sur un moniteur capable de poser un regard objectif sur l'état du système.

Le programme principal (deux version possibles) sera essentiellement le même dans chaque cas. Par la suite, chacune des solutions (incluant la non-solution) sera expliquée en détail. Chacune se compose d'une représentation de la table à laquelle les philosophes s'assoient, qui regroupera les données que ces derniers partagent pour l'implémentation de l'algorithme décrit, et de la description du thread philosophe représentant les actions d'un philosophe dans l'algorithme. Évidemment, dans chaque cas, tous les philosophes s'exécutent concurrement.

Sur le plan historique, ce problème exploré ici précède chronologiquement l'idée de mutex, même si j'utilise des mutex pour exprimer certaines solutions.

Programme principal

Le programme principal sera quelque peu banal. Son rôle sera de « mettre la table » et de permettre aux philosophes d'y déguster leur repas. Son exécution va comme suit :

créer une table
créer les philosophes, chacun étant représenté par un thread, et leur faire partager la table, puis
attendre la fin du repas (la fin de l'exécution des threads)

int main() {
   Table table;
   random_device rd;
   mt19937 prng{ rd() };
   vector<thread> v;
   for (int i = 0; i < Table::NB_PHILOSOPHES; ++i)
      v.emplace_back(thread{philosophe, ref(table), i, prng});
   for (auto & th : v) th.join();
}

Il y aura de petites variations d'une solution à l'autre, mais ces variations se limiteront au passage (ou non) d'un générateur de nombres pseudoaléatoires. Certaines solutions y ont recours, d'autres non.

La version n'ayant pas recours à un tel générateur est proposée à droite.

int main() {
   Table table;
   vector<thread> v;
   for (int i = 0; i < Table::NB_PHILOSOPHES; ++i)
      v.emplace_back(thread{philosophe, ref(table), i});
   for (auto & th : v) th.join();
}

Solution 0 (« non-solution »)

Ce qui suit détaille une solution (en fait, une non-solution) naïve au problème du dîner des philosophes. C'est une non-solution parce qu'elle est justement trop naïve, et mène occasionnellement (ou souvent, selon le contexte) à des conditions de course.

La table à laquelle les philosophes se partageront un copieux repas (de riz, avec des baguettes) sera représentée par une classe Table. Une instance de Table avec toutes ses particularités, en particulier les baguettes, est partagée, donc rendue accessible aux divers philosophes.

Dans cette version, seuls les accès directs aux baguettes sont synchronisés, dans le seul but d'éviter que deux philosophes pensent avoir la même baguette en même temps.

class Table {
public:
   enum { NB_PHILOSOPHES = 5 };
private:
   bool baguette_prise[NB_PHILOSOPHES] {};
   mutex acces_baguette[NB_PHILOSOPHES];
public:
   Table() = default;
   void prendre(int id, int n) {
      acces_baguette[n].lock();
      baguette_prise[n] = true;
      sync_out([id, n](ostream &os) { os << "Baguette " << n << " prise par " << id << endl; });
   }
   void relacher(int id, int n) {
      baguette_prise[n] = false;
      acces_baguette[n].unlock();
      sync_out([id, n](ostream &os) { os << "Baguette " << n << " relachée par " << id << endl; });
   }
   static int suivant(int n) {
      return (n + 1) % NB_PHILOSOPHES;
   }
   static int precedent(int n) {
      return (n + NB_PHILOSOPHES - 1) % NB_PHILOSOPHES;
   }
};

L'implémentation naïve d'un philosophe choisit, au hasard, laquelle des deux baguettes les plus proches de lui sera prise en premier. Ensuite, elle tente de prendre deux baguettes, de « manger », et de remettre les baguettes à leur place.

Le réel risque d'interblocage (de Deadlock) ici tient du fait que, si tous les philosophes prennent la baguette à leur gauche (ou à leur droite) d'abord, il est possible (et, en pratique, ça arrive assez souvent) que toutes les baguettes soient prises immédiatement, et qu'aucun philosophe n'en ait deux. Ce faisant, il ne reste aucune baguette et personne ne peut manger.

Remettre les baguettes est-il une solution?

Une alternative naïve serait de mettre un délai maximal d'attente pour la seconde baguette d'un philosophe donné : la naïveté de cette alternative tient du fait que les philosophes pourraient alors déposer la baguette entre leurs mains, puis essayer à nouveau d'avoir deux baguettes, et se paralyser mutuellement à nouveau, ceci de manière récurrente.

On parlerait alors de Livelock, ce qui n'est pas vraiment mieux qu'un Deadlock...

void philosophe(Table &table, int id, mt19937 prng) {
   auto precedent = Table::precedent(id),
        suivant = Table::suivant(id);
   uniform_int_distribution<int> de{ 0, 1 };
   if (de(prng)) {
      table.prendre(id, precedent);
      table.prendre(id, suivant);
   } else {
      table.prendre(id, suivant);
      table.prendre(id, precedent);
   }
   // manger...
   table.relacher(id, suivant);
   table.relacher(id, precedent);
}

Solution 1

Cette solution au problème du dîner des philosophes fonctionne parce qu'elle a recours à un serveur (un Waiter, en anglais) qui fera en sorte qu'il ne soit pas possible d'atteindre une situation telle que le système se trouverait en interblocage. Ici, le serveur est un médiateur pour l'accès aux baguettes.

Dans cette version, un seul mutex est utilisé : le Waiter chargé de déterminer, à titre de médiateur externe, le droit d'accès ou non à une baguette.

La règle est simple : un philosophe ne peut prendre une baguette que s'il en reste au moins deux sur la table, ou s'il a déjà une autre baguette avec lui (car dans ce cas, il pourrait manger!).

Cela signifie que le code client (le thread philosophe, plus bas) devra tester le code retourné par la méthode prendre() pour savoir s'il a obtenu (ou non) la baguette convoitée. Ceci évite un TOCTTOU, car prendre ne retournera true que si la baguette a bel et bien été prise.

Notez que l'attribut nb_pris n'est pas à strictement parler nécessaire; il aurait été possible de calculer la somme des valeurs dans combien_baguettes, par exemple à l'aide de la fonction standard std::accumulate().

class Table {
public:
   enum { NB_PHILOSOPHES = 5 };
   enum { NB_BAGUETTES = NB_PHILOSOPHES };
private:
   bool baguette_prise[NB_BAGUETTES] {};
   int combien_baguettes[NB_PHILOSOPHES] {};
   mutex waiter;
   int nb_pris = {};
   int baguettes_disponibles() const {
      return NB_BAGUETTES - nb_pris;
   }
   bool ne_peut_pas_prendre_baguette(int id) const {
      return baguettes_disponibles() < 2 && combien_baguettes[id] == 0;
   }
public:
   Table() = default;
   bool prendre(int id, int n) 
      lock_guard<mutex> _ { waiter };
      if (ne_peut_pas_prendre_baguette(id))
         return false;
      baguette_prise[n] = true;
      ++combien_baguettes[id];
      ++nb_pris;
      sync_out([n, id](ostream &os) { os << "Baguette " << n << " prise par " << id << endl; });
      return true;
   }
   void relacher(int id, int n) {
      lock_guard<mutex> _ { waiter };
      baguette_prise[n] = false;
      --combien_baguettes[id];
      --nb_pris;
      sync_out([id, n](ostream &os) { os << "Baguette " << n << " relachee par " << id << endl; });
   }
   static int suivant(int n) {
      return (n + 1) % NB_PHILOSOPHES;
   }
   static int precedent(int n) {
      return (n + NB_PHILOSOPHES - 1) % NB_PHILOSOPHES;
   }
};

L'implémentation d'un philosophe donné choisit l'ordre de prise de baguettes aléatoirement, puis essaie de prendre une première baguette, et essaie ensuite de prendre la deuxième.

Tant que le Waiter n'aura pas déterminé qu'il est sécuritaire d'accorder au philosophe le droit d'accéder à une baguette, le philosophe réalisera de l'attente active.

void philosophe(Table &table, int id, mt19937 prng) {
   auto precedent = Table::precedent(id),
        suivant = Table::suivant(id);
   uniform_int_distribution<int> de{ 0, 1 };
   sync_out([id](ostream &os) { os << "Philosophe " << id << " pense..." << endl; });
   int ordre[2] = { precedent, suivant };
   if (de(prng) == 0)
      swap(ordre[0], ordre[1]);
   while (!table.prendre(id, ordre[0]))
      ;
   while (!table.prendre(id, ordre[1]))
      ;
   // manger...
   sync_out([id](ostream &os) { os << "Philosophe " << id << " mange..." << endl; });
   table.relacher(id, ordre[1]);
   table.relacher(id, ordre[0]);
   sync_out([id](ostream &os) { os << "Philosophe " << id << " pense..." << endl; });
}

Solution 2

Cette solution au problème du dîner des philosophes fonctionne parce qu'elle impose un ordre de prise de baguettes qui dépend d'un accord préalable entre les philosophes (un protocole), et que cette solution, qui repose sur un ordonnancement entre les baguettes, fait en sorte de définir une hiérarchie entre les instances de cette ressource fort convoitée. Cette approche est encore utilisée aujourd'hui dans bien des cas.

Dans cette version, les accès concurrents aux baguettes prises individuellement sont évités par un recours à un mutex. Pour le reste, la Table n'assure aucune synchronisation; tout repose sur le protocole établi au préalable entre les philosophes.

class Table {
public:
   enum { NB_PHILOSOPHES = 5 };
   enum { NB_BAGUETTES = NB_PHILOSOPHES };
private:
   bool baguette_prise[NB_BAGUETTES] {};
   mutex acces_baguette[NB_BAGUETTES];
public:
   Table() = default;
   bool prendre(int id, int n) {
      acces_baguette[n].lock();
      baguette_prise[n] = true;
      sync_out([id, n](ostream &os) { os << "Baguette " << n << " prise par " << id << endl; });
      return true;
   }
   void relacher(int id, int n) {
      baguette_prise[n] = false;
      acces_baguette[n].unlock();
      sync_out([id, n](ostream &os) { os << "Baguette " << n << " relachée par " << id << endl; });
   }
   static int suivant(int n) {
      return (n + 1) % NB_PHILOSOPHES;
   }
   static int precedent(int n) {
      return (n + NB_PHILOSOPHES - 1) % NB_PHILOSOPHES;
   }
};

L'implémentation d'un philosophe impose l'ordre de prise de baguettes. Ici, nous allons toujours de la baguette ayant le plus petit indice à celle ayant le plus grand indice, mais la littérature fait habituellement l'inverse. Évidemment, le recours à std::sort() ici est abusif, mais bon..

La clé de cette solution est l'ordre d'appropriation de la ressource et l'ordre de libération de cette ressource. Les deux doivent être symétriques.

void philosophe(Table &table, int id) {
   auto precedent = Table::precedent(id),
        suivant = Table::suivant(id);
   uniform_int_distribution<int> de{ 0, 1 };
   sync_out([id](ostream &os) { os << "Philosophe " << id << " pense..." << endl; });
   int ordre[2] = { precedent, suivant };
   sort(begin(ordre), end(ordre)); // hum...
   while (!table.prendre(id, ordre[0]))
      ;
   while (!table.prendre(id, ordre[1]))
      ;
   // manger...
   sync_out([id](ostream &os) { os << "Philosophe " << id << " mange..." << endl; });
   table.relacher(id, ordre[1]);
   table.relacher(id, ordre[0]);
   sync_out([id](ostream &os) { os << "Philosophe " << id << " pense..." << endl; });
}

Solution 3

Cette solution au problème du dîner des philosophes fonctionne parce qu'elle utilise un moniteur capable de poser un regard objectif sur l'état du système : un philosophe ne mangera que si aucun de ses deux voisins ne mange déjà.

Une implémentation naïve regarderait le voisin de gauche, puis le voisin de droite, puis prendrait une décision; la naïveté tiendrait du fait qu'entre le premier et le second regard, tout comme entre le second regard et la prise de décision, l'état du système pourrait changer (un TOCTTOU).

Remarquez que, dans cette version, un seul mutex apparaît, et il s'agit du moniteur. De même, un seul état est pertinent : savoir qui est en train de manger. Les baguettes perdent même leur intérêt.

Le moniteur, de par son action, n'accorde de permission de manger à un philosophe que si la condition clé (les deux voisins immédiats de mangent pas) est respectée; la prise de décision est synchronisée.

class Table {
public:
   enum { NB_PHILOSOPHES = 5 };
private:
   bool mange[NB_PHILOSOPHES] {};
   mutex moniteur;
   bool voisin_mange(int id) const { // le moniteur seul peut y accéder
      return mange[precedent(id)] || mange[suivant(id)];
   }
public:
   Table() = default;
   bool debuter_manger(int id) {
      lock_guard<mutex> _ { moniteur };
      if(voisin_mange(id))
         return false;
      mange[id] = true;
      return true;
   }
   void cesser_manger(int id) {
      mange[id] = false;
   }
   static int suivant(int n) {
      return (n + 1) % NB_PHILOSOPHES;
   }
   static int precedent(int n) {
      return (n + NB_PHILOSOPHES - 1) % NB_PHILOSOPHES; }
   }
};

L'implémentation d'un philosophe donné attend la permission du moniteur avant de procéder à la consommation de riz.

Le code placé en commentaires montre une solution naïve, à rejeter ici parce qu'elle mènerait à des états incohérents.

void philosophe(Table &table, int id) {
   auto precedent = Table::precedent(id),
        suivant = Table::suivant(id);
   sync_out([id](ostream &os) { os << "Philosophe " << id << " pense..." << endl; });
   int ordre[2] = { precedent, suivant };
   // Ceci serait dangereux...
   //while (table.mange(ordre[0]) || table.mange(ordre[1]))
   //   ;
   // manger...
   while (!table.debuter_manger(id))
      ;
   sync_out([id](ostream &os) { os << "Philosophe " << id << " mange..." << endl; });
   table.cesser_manger(id);
   sync_out([id](ostream &os) { os << "Philosophe " << id << " pense..." << endl; });
}

Lectures complémentaires

Quelques liens pour enrichir le propos.

En 2014, Howard Hinnant explore le problème du dîner des philosophes sous un angle plus contemporain : http://howardhinnant.github.io/dining_philosophers.html
Résoudre le problème des philosophes à l'aide de Java 8, par Bruce Eckel en 2016 : http://bruceeckel.github.io/2016/12/29/dining-philosophers-in-java-8/
Implémentation en C++ 11, proposée par Marius Bancilla en 2017 : http://mariusbancila.ro/blog/2017/01/16/dining-philosophers-in-cpp11/