Philosophenproblem
Beim Philosophenproblem (englisch dining philosophers problem) handelt es sich um ein Fallbeispiel aus dem Bereich der theoretischen Informatik. Damit soll das Problem der Nebenläufigkeit und die Gefahr der Verklemmung von Prozessen veranschaulicht werden. Das Problem wurde von Edsger W. Dijkstra formuliert.
Aufbau
Fünf Philosophen, nummeriert von 0 bis 4, leben in einem Haus, in dem der Tisch für sie gedeckt ist, wobei jeder Philosoph seinen eigenen Platz am Tisch hat. Ihr einziges Problem – neben dem der Philosophie – ist, dass es sich bei dem servierten Gericht um eine sehr schwierige Sorte Spaghetti handelt, die mit zwei Gabeln gegessen werden muss. Neben jedem Teller befinden sich zwei Gabeln, so dass dies kein Problem darstellt: Dadurch dürfen jedoch keine zwei Nachbarn gleichzeitig essen.[1]
Ablauf
Die Philosophen sitzen am Tisch und denken über philosophische Probleme nach. Wenn einer hungrig wird, greift er zuerst die Gabel links von seinem Teller, dann die auf der rechten Seite und beginnt zu essen. Wenn er satt ist, legt er die Gabeln wieder zurück und beginnt wieder zu denken. Sollte eine Gabel nicht an ihrem Platz liegen, wenn der Philosoph sie aufnehmen möchte, so wartet er, bis die Gabel wieder verfügbar ist.
Solange nur einzelne Philosophen hungrig sind, funktioniert dieses Verfahren. Es kann aber passieren, dass sich alle fünf Philosophen gleichzeitig entschließen, zu essen. Sie ergreifen also alle gleichzeitig ihre linke Gabel und nehmen damit dem jeweils links von ihnen sitzenden Kollegen dessen rechte Gabel weg. Nun warten alle fünf darauf, dass die rechte Gabel wieder auftaucht. Das passiert aber nicht, da keiner der fünf seine linke Gabel zurücklegt. Die Philosophen verhungern. Bei der Ressourcenhierarchie-Lösung wird immer zuerst die Gabel mit der niedrigeren Nummer und dann die Gabel mit der höheren Nummer von den beiden Gabeln ausgewählt.
Variante: Jeder hungrige Philosoph nimmt die zwei nächsten verfügbaren Gabeln, unabhängig davon, ob sie zuletzt von einem Nachbarn benutzt wurden. Damit wird z. B. der Fall möglich, dass je zwei Philosophen immer denselben anderen zwei Philosophen ihre Gabeln übergeben und der fünfte Philosoph verhungern müsste.
Der folgende Quellcode ist eine C++11-Implementierung der Ressourcenhierarchie-Lösung für drei Philosophen. Die Funktion sleep_for() simuliert die Zeit, die normalerweise mit Geschäftslogik verbracht wird.
#include <iostream>
#include <chrono>
#include <mutex>
#include <thread>
#include <cstdlib>
#include <ctime>
using namespace std;
void phil(int ph, mutex& ml, mutex& mh, mutex& mo) {
for (;;) { // verhindert, dass Thread beendet wird
int duration = rand() % 100 + 1;
{
// Block { } begrenzt Gueltigkeit von lock
lock_guard<mutex> moGuard(mo);
cout<<ph<<" denkt "<<duration<<"ms\n";
}
this_thread::sleep_for(chrono::milliseconds(duration));
{
lock_guard<mutex> moGuard(mo);
cout<<"\t\t"<<ph<<" ist hungrig\n";
}
{
lock_guard<mutex> mlGuard(ml);
this_thread::sleep_for(chrono::milliseconds(30));
lock_guard<mutex> mhGuard(mh);
duration = rand() % 100 + 1;
{
lock_guard<mutex> moGuard(mo);
cout<<"\t\t\t\t"<<ph<<" isst "<<duration<<"ms\n";
}
this_thread::sleep_for(chrono::milliseconds(duration));
}
}
}
int main() {
cout<<"speisende Philosophen C++11 mit Ressourcenhierarchie\n";
srand(time(nullptr)); // zufaellige Zufallszahlen
mutex m1, m2, m3; // 3 Gabeln sind 3 Mutexe
mutex mo; // fuer 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();
}
Anwendung
Das Szenario der fünf (gelegentlich auch nur drei oder vier) speisenden Philosophen wird oft gebraucht, um das Problem der Interprozesskommunikation und Ressourcenverwaltung bei der Entwicklung von Betriebssystemen zu illustrieren. Das Beispiel soll darstellen, was passieren kann, wenn parallele Prozesse auf mehrere gemeinsame Ressourcen angewiesen sind und gleichzeitig darauf zugreifen. Dann kann es passieren, dass alle blockiert sind und auf ein Ereignis warten, das durch diese Blockade nie eintreffen wird. Ein solcher Zustand wird als Deadlock oder Verklemmung bezeichnet.
Zur Lösung des Problems werden typischerweise fortschrittliche Mutexe oder Semaphore zur Sequentialisierung verwendet, zum Beispiel scoped_lock von C++17.[2]
Literatur
- Abraham Silberschatz & James L. Peterson: Operating Systems Concepts. Addison-Wesley 1988, ISBN 0-201-18760-4
- K. Mani Chandy & Jayadev Misra: The Drinking Philosophers Problem. In: ACM Transactions on Programming Languages and Systems. Vol. 6, No. 4, Oktober 1984, S. 632–646 (PDF; 960 kB)
- Edsger W. Dijkstra: Hierarchical ordering of sequential processes. In: Acta Informatica. 1(2), 1971, S. 115–138 (PDF; 1,0 MB)
- Daniel J. Lehmann & Michael O. Rabin: On the Advantages of Free Choice: A Symmetric and Fully Distributed Solution to the Dining Philosophers Problem. In: Principles Of Programming Languages 1981 (POPL ’81). 1981, S. 133–138
Weblinks
- Discussion of the problem with solution code for 2 or 4 philosophers (englisch)
- Discussion of various solutions 1 (englisch)
- Discussion of various solutions 2 (englisch)
- Interactive example of the Philosophers problem (englisch) [als Java-Applet, gelten inzwischen als veraltet]
- Satan Comes to Dinner (englisch)
- ThreadMentor (englisch)
Einzelnachweise
- Dijkstra, E. W. (1971, June). EWD310 Hierarchical ordering of sequential processes. Acta Informatica 1(2): 115–138
- std::scoped_lock - cppreference.com. Abgerufen am 15. Januar 2022.