Dining Philiosophers Problem I
Andre Adrian hat das klassische Dining Philosophers Problem, das sich um die Synchronisation von Threads dreht, auf verschiedene Weise mit modernem C++ gelöst.
- Rainer Grimm
Zur Weihnachtszeit hatte ich einige nette Gespräche mit Andre Adrian. Er hat das klassische Dining Philosophers Problem auf verschiedene Weise mit modernem C++ gelöst. Ich habe ihn leicht dazu gewinnen können, einen Artikel über dieses klassische Synchronisationsproblem zu schreiben. Nun freue ich mich, diesen Artikel in drei aufeinanderfolgenden Beiträgen zu veröffentlichen.
Das Dining Philosophers Problem von Andre Adrian
By Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559
Das Problem der speisenden Philosophen wurde von Edsger W. Dijkstra beschrieben: "Fünf Philosophen, die von 0 bis 4 nummeriert sind, 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 denen der Philosophie - ist, dass das Gericht eine schwierige Art von Spaghetti ist, die mit zwei Gabeln gegessen werden müssen. Es gibt zwei Gabeln neben jedem Teller, sodass das kein Problem darstellt. Folglich dürfen jedoch keine zwei Nachbarn gleichzeitig essen." [ref Dijkstra; 1971; EWD310 Hierarchical Ordering of Sequential Processes; https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD310.html]
Wir verwenden folgende geänderte Problembeschreibung: 4 Philosophen leben ein einfaches Leben. Jeder Philosoph führt die gleiche Routine durch: Er denkt für eine zufällige Dauer, holt sich seine erste Gabel, holt sich seine zweite Gabel, isst für eine zufällige Dauer, legt die Gabeln hin und beginnt wieder zu denken. Um das Problem interessant zu machen, haben die 4 Philosophen nur 4 Gabeln. Philosoph Nummer 1 muss zum Essen Gabeln Nummer 1 und 2 nehmen. Philosoph 2 braucht Gabeln 2 und 3, und so weiter bis Philosoph 4, der Gabeln 4 und 1 zum Essen braucht. Nach dem Essen legt der Philosoph die Gabeln wieder auf den Tisch.
Verwendung mehrerer Ressourcen
Auf dem Weg von der Problembeschreibung zur Programmierung übersetzen wir Philosophen in Threads und Gabeln in Ressourcen. In unserem ersten Programm - dp_1.cpp - erstellen wir 4 "Philosophen"-Threads und 4 "Gabeln"-Ressourcen als Ganzzahlen.
Die Funktion main() erstellt Zufallszahlen in Zeile 42. Wir setzen den Seed-Wert des Zufallszahlengenerators auf die Anzahl der Sekunden seit dem 1. Januar 1970. Wir definieren unsere Gabel-Ressourcen in Zeile 44. Dann starten wir vier Threads beginnend in Zeile 46. Um eine vorzeitige Thread-Beendigung zu vermeiden, rufen wir ab Zeile 51 join() auf.
Die Thread-Funktion phil() hat eine Endlosschleife. Die while(true)-Anweisung ist immer wahr, daher wird der Thread nie beendet.
Die Problembeschreibung sagt "er denkt für eine zufällige Dauer". Zunächst berechnen wir mit der Funktion myrand() eine zufällige Dauer, siehe Zeile 20 und Zeile 6. Die Funktion myrand() liefert einen pseudozufälligen Rückgabewert im Bereich von [min, max). Für die Programmverfolgung protokollieren wir die Nummer des Philosophen, seinen aktuellen Zustand von "thinks" und die Dauer auf der Konsole. Die sleep_for()-Anweisung lässt den Scheduler den Thread für die Dauer in den Wartezustand versetzen. In einem "echten" Programm verbraucht der Quellcode der Anwendung Zeit anstelle von sleep_for(). Nachdem die Denkzeit des Philosophen vorbei ist, bekommt er "seine erste Gabel". Siehe Zeile 24. Wir verwenden eine Funktion lock(), um die "Gabel bekommen"-Sache durchzuführen. Im Moment ist die Funktion lock() sehr einfach, weil wir es nicht besser wissen. Wir setzen einfach die Gabel-Ressource auf den Wert 1 (Zeile 10). Nachdem der Philosophen-Thread seine erste Gabel erhalten hat, verkündet er stolz den neuen Zustand mit einer "got ma"-Konsolenausgabe. Jetzt bekommt der Thread "seine zweite Gabel". Siehe Zeile 28. Die entsprechende Konsolenausgabe ist "got mb".
Der nächste Zustand ist "eats". Wieder bestimmen wir die Dauer, erzeugen eine Konsolenausgabe und beschäftigen den Thread mit sleep_for(). Siehe Zeile 31. Nach dem Zustand "eats" legt der Philosoph seine Gabeln hin. Siehe Zeilen 35 und 14. Die Funktion unlock() ist wieder ganz einfach und setzt die Ressource auf 0 zurück.
Das Programm muss ohne Compiler-Optimierung kompiliert werden. Den Grund werden wir später sehen. Die Konsolenausgabe unseres Programms sieht vielversprechend aus:
Haben wir das Problem der Speisephilosophen schon gelöst? Nun, die Programmausgabe ist nicht detailliert genug, um diese Frage zu beantworten.
Verwendung mehrerer Ressourcen mit Logging
Wir sollten etwas mehr Protokollierung hinzufügen. Im Moment prüft die Funktion lock() nicht, ob die Gabel verfügbar ist, bevor die Ressource verwendet wird. Die verbesserte Version von lock() im Programm dp_2.cpp ist:
void lock(int& m) {
if (m) {
std::cout<<"\t\t\t\t\t\tERROR lock\n";
}
m=1;
}
Programmversion 2 erzeugt folgende Ausgabe:
Wir sehen die Konsolenausgabe "ERROR lock". Diese Ausgabe sagt uns, dass zwei Philosophen gleichzeitig dieselbe Ressource verwenden. Was können wir tun?
Fehlerhaftes Busy Waiting ohne Ressourcehierarchien
Wir können die if-Anweisung in lock() in eine while-Anweisung ändern. Diese while-Anweisung erzeugt einen Spinlock. Ein Spinlock ist ein schickes Wort für busy waiting (geschäftiges Warten). Während die Gabel-Ressource verwendet wird, ist der Thread damit beschäftigt, auf eine Änderung von Zustand "in Benutzung" auf den Zustand "frei" zu warten. In diesem Moment setzen wir die Gabel-Ressource wieder auf den Zustand Status "in Benutzung". Im Programm dp_3.cpp haben wir:
void lock(int& m) {
while (m)
; // busy waiting
m=1;
}
Allerdings ist diese kleine Änderung immer noch keine KORREKTE Lösung für das Problem der Speisephilosophen. Wir haben keine falsche Ressourcennutzung mehr, aber wir haben ein anderes Problem. Siehe Ausgabe der Programmversion 3:
Jeder Philosophen-Thread nimmt seine erste Gabel-Ressource und kann dann die zweite Gabel nicht nehmen. Was können wir tun? Andrew S. Tanenbaum schrieb: "Ein anderer Weg zur Vermeidung der geschlossenen Kette besteht in der globalen Nummerierung.
Die Regel: Prozesse können Betriebsmittel anfordern, wann immer sie es wünschen, aber alle Anforderungen müssen gemäß der numerischen Anordnung erfolgen." [ref Tanenbaum; 1990; Betriebssysteme Entwurf und Realisierung, Kapitel 3.3.5 Verhinderung von Verklemmungen]
Falsches Busy Waiting mit Ressourcehierarchien
Diese Lösung wird als Ressourcenhierarchie (resource hierarchy) oder Halbordnung (partial ordering) bezeichnet. Für das Problem der speisenden Philosophen ist Halbordnung einfach. Die erste genommene Gabel muss diejenige mit der niedrigeren Nummer sein. Bei den Philosophen 1 bis 3 werden die Ressourcen in der richtigen Reihenfolge genommen. Nur Philosophenthread 4 benötigt eine Änderung für eine korrekte Halbordnung. Holen Sie zuerst die Gabel-Ressource 1, dann die Gabel-Ressource 4. Siehe Zeile 51 in der Datei dp_4.cpp:
int main() {
std::cout<<"dp_4\n";
srand(time(nullptr));
int m1{0}, m2{0}, m3{0}, m4{0};
std::thread t1([&] {phil(1, m1, m2);});
std::thread t2([&] {phil(2, m2, m3);});
std::thread t3([&] {phil(3, m3, m4);});
std::thread t4([&] {phil(4, m1, m4);});
t1.join();
t2.join();
t3.join();
t4.join();
}
Die Ausgabe der Programmversion 4 sieht gut aus:
Jetzt gibt es keine falsche Ressourcennutzung mehr und auch keine Verklemmung (deadlock). Wir werden mutig und setzen die Compiler-Optimierung ein. Wir wollen ein gutes Programm haben, das schnell ausgeführt wird! Dies ist die Ausgabe der Programmversion 4 mit Compiler-Optimierung:
Es ist immer der gleiche Philosophen-Thread, der isst. Kann die Einstellung der Compileroptimierung das Verhalten eines Programms verändern? Ja, es ist möglich: Die Philosopher-Threads lesen den Wert der Gabel-Ressource aus dem Speicher. Die Compiler-Optimierung optimiert einige dieser Speicher-Lese-Zugriffe weg. Alles hat seinen Preis!
Immer noch falsches Busy Waiting mit Ressourcehierarchien
Die Programmiersprache C++ hat das atomic Template, um einen atomaren Typ zu definieren. Wenn ein Thread in ein atomares Objekt schreibt, während ein anderer Thread daraus liest, ist das Verhalten klar definiert. In der Datei dp_5.cpp verwenden wir atomic<int> für die Gabel-Ressourcen. Siehe Zeilen 11, 17, 21 und 47. Wir fügen #include <atomic> in Zeile 5 ein:
Die Ausgabe der Programmversion 5 ist:
Diese Ausgabe sieht toll aus. Jetzt sind wir an die Grenzen unserer Testmethodik gestoßen. Es gibt immer noch eine winzige Chance für Fehlverhalten. Die beiden Operationen "ist eine Ressource verfügbar" und "Ressource als in Gebrauch markieren" in der Funktion lock() sind atomar, aber sie sind immer noch zwei Operationen. Zwischen diesen beiden Operationen kann der Scheduler einen Threadwechsel platzieren. Und dieser Threadwechsel zu diesem ungünstigsten Zeitpunkt kann sehr schwer zu findende Fehler im Programm erzeugen.
Wie geht's weiter?
Die Fortsetzung des Dining Philosophers Problems im nächsten Artikel löst diese winzige Chance für Fehlverhalten auf. Bisher war noch kein Programm korrekt.
Zum Abschluss möchte ich noch mein neues, englisches Mentoring Programm vorstellen.
My Mentoring Program "Fundamentals for C++ Professionals"
The general idea of the mentoring program is straightforward. I will teach you what you should know about modern C++. Modern C++ includes the core language and the library based on C++17 in 28 stations. Each week, I publish a new station. To master a station, you have to invest about three hours a week. Therefore, you can integrate my program into your workday.
After my general idea, here are more details: Fundamentals for C++ Professionals. ()
