PhilosophenProblem – Wikipedia

Construire le problème philosophe

Au Problème de philosophe ( Anglais Problème de philosophes de restauration ) est une étude de cas du domaine de l’informatique théorique. Ceci est destiné à illustrer le problème de la liberté auxiliaire et le risque du criminel des processus. Le problème a été formulé par Edsger W. Dijkstra.

Cinq philosophes, numérotés de 0 à 4, vivent dans une maison où la table est couverte pour eux, chaque philosophe ayant sa propre place à la table. Son seul problème – en plus de celui de la philosophie – est que le plat servi est une variété très difficile de spaghettis qui doit être mangée avec deux fourchettes. Il y a une fourche entre les plaques, de sorte que ce n’est pas un problème pour un seul philosophe. Cependant, deux voisins ne peuvent pas manger en même temps. ^[d’abord]

Les philosophes sont assis à la table et réfléchissent à des problèmes philosophiques. Quand quelqu’un a faim, il attrape d’abord la fourche à gauche de son assiette, puis à droite et commence à manger. Quand il est plein, il remet les fourches et recommence à réfléchir. Si une fourche n’est pas à sa place si le philosophe veut l’enregistrer, il attend que la fourche soit à nouveau disponible.

Tant que seuls les philosophes individuels ont faim, ce processus fonctionne. Cependant, il peut arriver que les cinq philosophes décident de manger en même temps. Ils prennent donc tous leur fourche gauche en même temps et enlèvent ainsi la fourche droite du collègue assis à gauche. Maintenant, les cinq attendent que la bonne fourche réapparaît. Mais cela ne se produit pas parce qu’aucun des cinq couvrait sa fourche gauche. Les philosophes sont affamés. Dans la solution de hiérarchie des ressources, la fourche avec le nombre inférieur, puis la fourche avec le nombre plus élevé des deux fourches est toujours sélectionnée en premier.

Variante: Chaque philosophe affamé prend les deux fourches disponibles suivantes, qu’elles aient été récemment utilisées par un voisin. Donc z. Par exemple, l’affaire est possible que deux philosophes remettent toujours leurs fourches aux mêmes deux autres philosophes et le cinquième philosophe devrait mourir de faim.

Le code source suivant est une implémentation C ++ 11 de la solution de hiérarchie des ressources pour trois philosophes. La fonction sleep_for () simule le temps qui est généralement passé avec la logique métier.

#inclure   #inclure   #inclure   #inclure   #inclure   #inclure   using namespace std;
int myrand(int min, int max) {
  static mt19937 rnd(time(nullptr));
  return uniform_int_distribution<>(min,max)(rnd);
}
void phil(int ph, mutex& ml, mutex& mh, mutex& mo) {
  for (;;) {  // verhindert, dass Thread beendet wird
    int duration = myrand(200, 800);
    {
      // Block { } begrenzt Gueltigkeit von lock
      lock_guard<mutex> moGuard(mo);
      cout<<ph<<" denkt "<<duration<<"msn";
    }
    this_thread::sleep_for(chrono::milliseconds(duration));
    {
      lock_guard<mutex> moGuard(mo);
      cout<<"tt"<<ph<<" ist hungrign";
    }
    {
      lock_guard<mutex> mlGuard(ml);
      this_thread::sleep_for(chrono::milliseconds(400));
      lock_guard<mutex> mhGuard(mh);
      duration = myrand(200, 800);
      {
        lock_guard<mutex> moGuard(mo);
        cout<<"tttt"<<ph<<" isst "<<duration<<"msn";
      }
      this_thread::sleep_for(chrono::milliseconds(duration));
    }
  }
}
int main() {
  cout<<"speisende Philosophen C++11 mit Ressourcenhierarchien";
  mutex m1, m2, m3;   // 3 Gabeln sind 3 Mutexe
  mutex mo;           // für ordentliche Ausgabe
  // 3 Philosophen sind 3 Threads
  thread t1([&] {phil(1, m1, m2, mo);});
  thread t2([&] {phil(2, m2, m3, mo);});
  thread t3([&] {phil(3, m1, m3, mo);});  // Ressourcenhierarchie
  t1.join();  // verhindert, dass Threads beendet werden
  t2.join();
  t3.join();
}

Le scénario des cinq philosophes d’alimentation (parfois seulement trois ou quatre) est souvent utilisé pour illustrer le problème de la communication inter-processus et de la gestion des ressources dans le développement des systèmes d’exploitation.
L’exemple devrait montrer ce qui peut arriver si les processus parallèles reposent sur plusieurs ressources communes et y accédez en même temps. Ensuite, il peut arriver que tout le monde soit bloqué et attend un événement qui n’arrivera jamais de ce blocus. Une telle condition est appelée une impasse ou un criminel.

Le problème est généralement utilisé pour résoudre le problème de séquentialisation, par exemple Scoped_lock de C ++ 17. ^[2]

• Abraham Silberschatz et James L. Peterson: Concepts de systèmes d’exploitation. Addison-Wesley 1988, ISBN 0-201-18760-4
• K. Mani Chandy et Jayadev Misra: Le problème des philosophes à boire. Dans: Transactions ACM sur les langages et systèmes de programmation. Vol. 6, No. 4, octobre 1984, S. 632–646 (art. PDF; 960 Ko )
• Edsger W. Dijkstra: Ordonnance hiérarchique des processus séquentiels. Dans: Acte informatique. 1 (2), 1971, S. 115–138 ( PDF; 1,0 Mb )
• Daniel J. Lehmann et Michael O. Rabin: Sur les avantages du libre choix: une solution symétrique et entièrement distribuée au problème des philosophes de restauration. Dans: Principes des langages de programmation 1981 (Popl ’81). 1981, S. 133–138

1. ↑ Dijkstra, E. W. (1971, juin). Ordonnance hiérarchique EWD310 des processus séquentiels . ACTION INFORMATIQUE 1 (2): 115–138
2. ↑ std :: scoped_lock – cppreference.com. Consulté le 15 janvier 2022 .