Unix forever!

The Dining Philosophers Problem revisited

Monad: Monoid in the Category of Endofunctors

Endofunctor: A functor that maps a category to that same category

This tutorial is based on the idea of the 'Dijkstra' monad:

https://www.microsoft.com/en-us/research/publication/verifying-higher-order-programs-with-the-dijkstra-monad/

Paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2013/06/paper-pldi13.pdf

Slides: https://fstar-lang.org/papers/dm4free/slides.pdf

Lespie Lamport Papers: https://research.microsoft.com/en-us/um/people/lamport/pubs/deroever-festschrift.pdf

Long version (27 pages): https://www.microsoft.com/en-us/research/publication/computation-state-machines/

Leslie Lamport teaching concurrency paper: https://www.microsoft.com/en-us/research/publication/teaching-concurrency/

The perhaps most idiotic C++ programming course you see here:

https://www.heise.de/blog/Dining-Philiosophers-Problem-I-6320973.html
https://www.heise.de/blog/Dining-Philosopher-Problem-II-6327946.html
https://www.heise.de/blog/Dining-Philosophers-Problem-III-6335228.html

The author is a well known C++ specialist: https://grimm-jaud.de/index.php/dining-philosophers-problem-i

The 'Dijkstra' monadic solution

English: 🇬🇧

https://www-heise-de.translate.goog/forum/heise-Developer/Kommentare/Dining-Philiosophers-Problem-I/Die-Mona-de-die-Mona-de-die-kennt-kei-ne-Blocka-de/posting-40853206/show/?_x_tr_sl=de&_x_tr_tl=en&_x_tr_hl=de&_x_tr_pto=wapp

German: đŸ‡©đŸ‡Ș

Warum das Problem nicht mit einer monadischen Funktion lösen, die ĂŒber (freie) Ressourcen zuerst nachdenkt, bevor sie handelt!? Threads zuhauf starten und gegen die Wand laufen lassen? Das geht besser!

Man nehme: Einen String, unterteile in drei logische Gruppen von observablen ZustĂ€nden (Gabeln), Behaviors ("L"eftpicker, "R"ightpicker, "B"othpicker) und (stets neuen) Ereignissen mit den ZustandsĂ€nderungen der Philosophen ("T"hinking, "H"ungry, "E"ating). RĂŒckgabewert sei ein String mit den verĂ€nderten ZustĂ€nden.

Implementiert wird das "Neighbour LOCK - Pattern" im von ELM bekannten "Model View Update" Pattern. Kapiert ĂŒbrigens jedes Kind:

Model View Update!

Also: m("_fffffLRBLRttHHt") - Philosoph #3 und #4 werden aktiv und melden "Hunger" an.

"_ff33fLRBLRttHHt" <- m("_fffffLRBLRttHHt") - abgearbeitet wird von links nach rechts, wobei man eine verÀnderte Abarbeitungsreihenfolge in einem zusÀtzlichen Feld mitgeben könnte.

Obige Monade habe also nun gearbeitet: Fork #3 und #4 sind nun "owned by" - also in Besitz von Philosoph #3. Der habe sich entsprechend seinem Behaviour #3 im 2. Feld "LRBLR" beide Gabeln zugleich gegriffen. Den Zustand gebe ich noch einmal in die Monade, ein "recursive call":

"ff33fLRBLRttEht" <- m("ff3ffLRBLRttHHt") - Philosoph #3, in Besitz der Gabeln, konnte nun mit Essen beginnen, wÀhrend Philosoph #4 nach der linken Gabel entsprechend seinem Behavior in Feld 2 "LRBLR" greift. Die aber ist besetzt. Der nicht erreichbare Zustand "E" wird durch ein kleines "h" - "weiter hungrig, aber keine Gabel frei" signalisiert. Ein Appell an die aufrufende Funktion, woran es liegen könnte, wenn Philosoph #4 dauernd "verhungert".

Wohlgemerkt: Kein Error, kein Lock, kein Semaphor, kein Mutex. Und auch noch keine sĂ€mliche Memory Ressourcen belegenden Threads: "Erst nachdenken, dann handeln!", sagte meine Großmutter bereits.

Die Monade betreibt auch kein "Error handling". Sie ist generell "stateless", liefert also immer ein Ergebnis zurĂŒck, "hĂ€ngt" niemals. Sie signalisiert dennoch der aufrufenden Funktion, ob da ein Problem ist und wo das Problem liegt. Einen Error könnte man durch ein "E" am Anfang des Strings (anstatt "_") signalisieren und sogar weiter durchreichen, unter Umgehung von stderr. Errorhandling? ÜberflĂŒssig!

Der fleißige Biber "Busy Beaver" hĂ€tte seinen Endzustand also nun erreicht. Jeder weitere Aufruf der Monade wĂ€re sinnlos. Also warten auf neue ZustĂ€nde.

Ein neuer Zustand: Philosoph #5 möchte auch essen, Zustand "H"

"5f335LRBLRttEhE" <- m("ff33fLRBLRttEhH")

Der jeweils letzte Philosoph (Strings kann man zuvor durchzÀhlen, hier ist es #5) erfÀhrt eine gesonderte Behandlung. Er darf Gabel 5 und 1 (von sich aus RHS) ergreifen und bekommt dann den Zustand "E" nach nur drei rekursiven DurchlÀufen erteilt, weil er "seine" beiden Gabeln nacheinander greifen konnte.

Die Monade hÀtte die obigen ZustÀnde jetzt alle nun durchlaufen und returniert den letzten String, nachdem sich keine weitere ZustandsÀnderung mehr ergeben habe.

Die Implementierung als einfache, monadische Funktion hat zwei Vorteile: Sie ist einfach testbar. Und man kann, in eine Ă€ußere Funktion gewrappt, verschiedene ZustĂ€nde durchspielen, versuchen, die Deadlocks entsprechend der "cat fight" - Hinweise im Outputstring der Monade aufzulösen.

Wie entdecke ich einen Deadlock? Zustand A XOR Zustand B auf die Gabeln. Wenn sich an der Besitzaufteilung der Gabeln im ersten Feld - ĂŒber ein paar Zyklen hinweg gemessen - nix mehr tut, ist wohl ein Deadlock eingetreten:

"522f5"
"522f5" XOR
==========
"00000" - Count +=1 < 20

Man kann so recht einfach Deadlocks detektieren und z.B. durch Herumspielen im "LRBLR" Feld - das "Miteinander" von "Behaviors" testen. Zudem kann man Statistiken fĂŒhren und mal hier, mal da einen (oder mehrere) Philosophen suspendieren, um eine Konkurrenz - Situation zu bereinigen: "LR0L0".

Da wir uns hier bereits in einem hochdimensionalen Zustandsraum befinden, kann man entweder durch Caching der TOP 10 der hÀufigsten "cat fight" - Situationen proaktiv sogar den Deadlock vermeiden, indem ich ihn vorhersage, weitere Handlungen im Voraus plane. Man kann auch ein winziges, Neurales Netzwerk darauf ansetzen.

Eine statistische Auswertung wĂŒrde dann wohl ergeben, daß die Zahl der Deadlocks exponential zunimmt, je mehr gierige, egoistische "B" - Philosophen - am Dinner teilnehmen. Das hat sogar soziale Implikationen.

Man hĂŒte sich aber, wechselnde Strategien oder gar Zufall in die Monade selber hinein zu programmieren. Die Monade wĂ€re nicht mehr deterministisch, nicht mehr testbar.

Merke: Es gibt Dinge, die ich testen kann, und die ich testen muß Man ist also gut beraten, den Zustandsraum der Monade nicht zu groß werden zu lassen. Besser, man teilt dann eine Monade (funktional oder auch nur horizontal) in viele kleine Monaden mit ĂŒberschaubaren, jeweils begrenzten und noch leicht testbaren (durchpermutierbaren) ZustandsrĂ€umen auf.

Insgesamt ist eine Monade ein recht universelles, gut zu testendes Programmier - Pattern. Übrigens ist "Monade" nicht an funktionale Programmiersprachen gebunden. Das Pattern funktioniert mit jeder beliebigen String verarbeitenden Programmiersprache, wie C/C++, Rust, Free Pascal, VisualBasic, Python, Assembler ... Die Ressourcen sind minimal, also ideal fĂŒr Embedded Systems geeignet.

Mit dieser Monade lĂ€ĂŸt sich auch ein sehr effizienter Scheduler bauen, der Ressourcen erst auf "frei" testet, und sich dann eine passende (möglichst reentrante) Funktion aus einer "Todo - Queue" heraus pickt und startet. Also genau anders herum, in den drei Artikeln. So realisiert man einen Scheduler fĂŒr z.B. einen ESP32, der unterbricht, wenn ein Pin auf +5V springt, z.B. Netzwerkkarte signalisiert, daß Daten herein kommen.

Auch kann ich eine Zeitachse einfĂŒhren, also eine "Wiedervorlage" nach imaginĂ€ren "x Sekunden". Mit Warp-Speed kann ich so eine Simulation durchfĂŒhren, meine Monade vorab komplett mit allen denkbaren "Deadlock Avoidance" - Strategien testen.

Zudem kann ich den Energieverbrauch oder Memory Footprint begrenzen, indem ich die Zahl der gleichzeitig essenden Philosophen begrenze. Interessant auch bei Multiprozessorsystemen und hunderttausenden "Philosophen" - "distributed" im Cluster. So ein String ist einfach zwischen Maschinen repliziert. FĂŒr andere Sitzordungen und AbhĂ€ngigkeiten - "Modelle" - ĂŒberlege man sich einfach eine andere String - Kodierung. Code kann ggf. bleiben. Siehe dazu: "Random (Quantum) Walks on Cayley Graphs"

https://www.researchgate.net/publication/283761547_Virtually_Abelian_Quantum_Walks

Have fun!

Back to last lesson - https://rentry.co/DSRsecuritycoursepart3 Next lesson: https://rentry.co/DSRsecuritycoursepart5

Edit
Pub: 26 Jun 2024 20:15 UTC
Edit: 19 Jul 2024 11:27 UTC
Views: 267