Kleine Sachen mit Python

Die 9 speisenden Philosophen



Fast die reale Welt


Eine oder zwei handvoll chinesischer Philosophen, heute sind es genau neun an der Zahl, nehmen am Geburtstag des weisen Konfuzius um einen runden Tisch herum hockend Platz. Sie pflegen ein besonderes Zeremoniell - sie speisen gemeinsam zarte Bambusssprossen und meditieren in sich ver­sun­ken über die weisen Lehren des verehrten Konfuzius, sie meditieren über die fünf Tugenden.

Neun Philosophen
mit begrenzten Ressourcen

Alle zur Linken
und schon ist Endstation

Einer macht eine Pause
und Einer kann essen

Vier könnten doch wohl essen!

Der Zeremonienmeister läutet das Glöckchen und jeder Philosph greift zur Linken nach dem Eßstäbchen und dann zur Rechten – aber da liegt nun kein Stäbchen mehr, denn zwischen zwei Philosophen lag nur eines davon.

Die althergebrachten Tischsitten verbieten es, mit nur einem Stäbchen etwa die Sprossen aufspießen zu wollen. Da ist auch eine Rauferei um ein zweites Stäbchen ausgeschlossen. Und die Kampfkunst ist dem frühen Morgen, dem Frühsport vorbehalten. Hat ein Philosoph nur ein Stäbchen, muss er warten, bis er das zweite erhält, erst dann darf er sich dem Essen zuwenden.

Der Zeremonienmeister lässt erneut das Glöckchen bimmeln und verkündet, er wolle eine Runde aussetzen, um an der nächsten Runde teil­zu­neh­men, ein anderer möge dann aussetzen. Acht Philosphen greifen nach dem linken Eßstäbchen und nach dem rechten – ein Philosoph von sieben hat nun zwei Eßstäbchen aufgenommen und widmet sich gleich den Bambussprossen. Und die anderen? Die sind bei aller Tugendhaftigkeit un­ge­hal­ten. Der Tisch war immerhin mit neun Stäbchen eingedcekt, vier und nicht nur ein Philosoph sollten also zur gleichen Zeit doch wohl speisen können.

Es ist guter Brauch bei Tisch, nach einer kleinen Essensweile innezuhalten, die Eßstäbchen abzulegen und der Meditation die Zeit zugeben, unser spros­sen­ge­nie­ße­nder Philisoph legt denn auch bald sein Essbesteck wieder ab. Nun endlich sind zwei weitere Philosophen an der Reihe, nehmen die Stäbchen auf und speisen.

Nein, das war wohl auch kein guter Anfang.

Der Zeremonienmeister bimmelt auf ein Neues, man greift nach links, man greift nach rechts – zwei Herren greifen mit beherztem Eifer und zur gleichen Zeit nach einem Stäbchen - das dünne Stäbchen zerbricht unter dem ungestümen Ansturm.

Ein Stirnerunzeln zeigt sich beim Zeremonienmeister und die Zeremonie wird unterbrochen. Dienstbare Geister haben bald ein Ersatzstäbchen bereitgelegt und das Glöckchen erklingt.

Die hungrigen Herren zu Tisch sind ungehalten. Da vergisst man schon einmal die gute Erziehung. Zwei Philosophen haben ein Ränkespiel zu Lasten eines Drittten geschmiedet. Der Dritte im Bunde hockt zwischen den Beiden und wenn diese Beiden abwechselnd ihre zwei Stäbchen aufnehmen, kommt der Mann in der Mitte auf ewig nicht zum Zuge, der Arme verhungert – es sei denn, der Zeremonienmeister bemerkt die Intrige und weiß sie zu unterbinden.

Das Glöckchen erklingt so noch einmal. Aber die Philosophen haben die Nase voll, sie wollten doch einfach nur mit den Eßstäbchen klappern und genießen. Also werden aus einem Stäbchen zwei geknickt – und neun Philisophen machen sich frank und frei und ungehemmt über die Sprossen her.

Fazit

Die Herren hatten sich im Nu in einer ausweglosen Situation festgefahren, jeder hatte nur ein Stäbchen und es ging nicht weiter, der klassische deadlock ist eingetreten, sie sind in eine Todesfalle getappt, das Philosophensystem steht still.

Regellos geht so ein Unterfangen nicht.



Ein Systemmodell


An der Tischrunde nehmen nur 8 von den 9 Philosophen teil, jeder Philosoph meldet seine Teilnahme an der Tischrunde an, der 9. Philosoph wartet solange, bis sich ein Teilnehmer von der Tischrunde abgemeldet hat. Ansonsten sind die Herren alle gleichberechtigt, es gibt also keinen Zeremonienmeister, der mit Geklingel einen neuen Anfang einleiten könnte.

Die Eßstäbchen sind die reaktiven, passiven Entitäten des Systems. Jedes Eßstäbchen wird (möglichst) abwechselnd von den benachbarten Philosophen benutzt. Der eine Philosoph wartet, bis der andere das Eßstäbchen abgelegt hat.

Die Philosophen sind die aktiven Entitäten im System, sie agieren selbstständig aus sich heraus. Der Lebenszyklus jedes Philisophen gliedert sich in Runden, in zeitlich begrenzten Abschnitten der Zeremonie. Jede Runde beginnt mit der Anmeldung an der Tischrunde - wobei der Philosoph gegebenfalls warten muss. Dann wird das linke und danach das rechte Eßstäbchen aufgenommen - wobei der Philosoph jeweils gegebenfalls warten muss. Mit 2 Eßstäbchen in den Händen beginnt die begrenzte Essenszeit. Danach meldet sich der Philosoph von der Tischrunde ab und beginnt mit der begrenzten Denkzeit.

Hat ein Philosoph die vorgegeben maximale Essenszeit erreicht, so scheidet er nach der Denkzeit ganz aus der Philosophenrunde aus.

Das wäre mein Grundablaufmodell.



Weitere mögliche Modellmodifikationen


Jeder Philosoph darf solange essen, bis er eine obere Essenszeitgrenze erreicht hat. Von daher erfüllt das Modell auf natürliche Weise das Gebot der Fairness – alle Philosophen dürfen im gegbenen Rahmen satt werden. Eine andere Möglichkeit wäre die, eine absolute Zeitschränke vorzugeben und zu fordern, dass kein Philosoph ungebührlich benachteiligt werden soll.

Man könnte den Philosphen mehr Freiheit bei der Wahl Eßstäbchen geben, im Extremfall greift jeder Philosoph per Zufall nach dem rechten oder linken Stab.

Es gibt schnellere Esser - aber auch sehr langsame. In unserem Phi­lo­so­phen­sys­tem könnte man Essgeschwindigkeiten berücksichtigen. Ein sehr schneller Esser könnte dann einen zu langsamen Esser für eine Weile aus der Essensrunde verdrängen, der langsame Esser müsste dann warten.

Die Philosophen könnten auch in einer Rangordnung stehen, ein Großphilosoph darf etwa bevorzugt speisen, sein Essenswunsch würde mit einer höheren Priorität behandelt, in der Wartschlange könnte er rangniedrigere Philosophen überholen. Auch könnte der Großphilosph rangniedrigere aus der Essensrunde verdrängen.



Die Implementierung


Das Systemmodell wird mit threads (Ablauffäden) für die Philosophen und Semaphore für den Schutz der Ressourcen in Python-Code gegossen. Die Denk- und Essenszeit wird schlicht durch ein sleep realisiert, in diesen Phasen wird keine CPU-Last erzeugt, das Laufzeitsystem wird hier einen anderen thread zum Ablauf bringen.



Analyse (I) – Einfaches Systemmodell


Und was tut sich so bei der Ausführung des Modells? Für den ersten Eindruck habe ich habe ich die Denk- und Essenszeiten auf eine festen Wert, nämlich eine Zeiteinheit, gesetzt.

Ich hatte eigentlich ein wenig mehr Determiniertheit erwartet, hier zweimal dasselbe Programm in der Ausführung:

Philosoph P6 beginnt

Philosoph P2 beginnt

Alle Philosophen beginnen mit einem Nachdenken, und zwar in der Reihenfolge, in der die Ablauffäden gestartet wurden. Dann beginnt Philosoph P6, das andere Mal aber Philosoph P2 den Essensreigen.

Ich sollte einmal nachbohren, woher der Indeterminismus herrührt. Meine anfängliche Annahme war, dass der Python-Interpreter das thread-System gewissermaßen wie ein sequentielles Programm ausführen würde, denn durch die vorgegebene Startreihenfolge der Ablaufeinheiten und die festen Denk- und Essenszeiten ist der Ablauf eigentlich vorgegeben oder vorbestimmt.

In dem einem Lauf bilden sich Dreiergruppen zum gemeinsamen Speisen, im anderen Vierergrupen. Was für Gruppen sich bilden, hängt davon ab, welche Philosophen zuerst ein Stäbchen aufnehmen. Speisen 4 Philosophen zur gleichen Zeit, ist der Durchsatz natürlich größer, der letzte Esser beginnt in diesem Fall 4 Zeiteinheiten früher.

Die (fast) gleichen Zeiten beim Essen und Denken könnten den Eindruck vermitteln, der Python-Interpreter führe die threads in der Tat parallel aus. Dem ist aber nicht so, während des Essens legen die threads sich mit einem sleep danieder und geben den Prozessor frei und der nächste Pilosoph kann fast zur gleichen Zeit mit dem Essen beginnen.

Meist Dreiergruppen

Meist Vierergruppen

Der Philosoph P1, wie er leibt und lebt und denkt:

Der Lebenslauf von Eßstäbchen E0:

Der farblose Lebenslauf von Philosoph P1

Der Lebenslauf von Eßstäbchen E0

Die Angabe „Eßstäbchen auf“ ist etwas irreführend, gemeint ist 'Ich möchte ein Stäbchen aufnehmen!'.

Wie die Zeiten zeigen, kann dieser Philosoph P1 immer sofort beide Eßstäbchen aufnehmen.

Den Zeiten kann man entnehmen, dass Philosoph P9 eine Zeiteinheit auf seinen Stab E0 warten muss. Es hat seine Richtigkeit, er legt E0 erst nach 2 Zeiteinheiten ab. Ich hätte wohl noch eine weitere Zeitausgabe spen­die­ren sollen.

Eine kleine Frage: 9 Philosophen brauchen auf meinem Rechner 14 bis 18 Zeiteinheiten für einen Programmlauf.

Wieviele Zeiteinheiten brauchen dann 99 Philosophen?

Bei 999 Philosophen gab es nach einiger nicht sehr langen Zeit mit sehr vielen Ausgaben ein Nichts geht mehr – ein wortlose Stillstand.

Was für einen Durchmesser müsste der runde Tisch für 999 Philosophen denn haben? Na, grob geschätzt, so um die 650 Meter.

# Beginn mit 99 Philosophen...
 0.00038 | P1  |     | DENKEN
 0.00138 | P2  |     | DENKEN
 0.00405 | P3  |     | DENKEN

 0.03773 | P98 |     | DENKEN
 0.03786 | P99 |     | DENKEN
 1.01100 | P3  | E2  | Eßstäbchen AUF
 1.01111 | P3  | E3  | Eßstäbchen AUF
 1.01116 | P3  |     | ESSEN

21.32148 | P39 |     | EZ: 5.0; DZ: 5.0
21.32168 | P36 |     | EZ: 5.0; DZ: 5.0
21.32190 | P35 | E34 | Eßstäbchen AB
21.32195 | P35 | E35 | Eßstäbchen AB
21.32201 | P35 |     | DENKEN
22.33558 | P35 |     | EZ: 5.0; DZ: 5.0
# Ende.



Analyse - Erweitertes Systemmodell


Im leicht erweiterten Modell variieren die Essens- und Denkzeiten nun etwas, sie werden zufällig aus einem vorgegebenen Intervall gewählt.

Zudem können Philosophen freiwillig oder unfreiwillig ausscheiden, freiwillig etwa, wenn er ausreichend gesättigt ist, und unfreiwillig, wenn er in einer vorgegenen Zeit kein Eßstäbchen erhält, der Philosoph ist dann beleidigt und trollt sich.

Der Ausscheidende wird aber durch einen nachrückenden Philosophen ersetzt, der – ausgestattet mit den bisherigen Essens- und Denkzeiten des Ausscheidenen – dann an der Zeremonie teilnimmt.

Einer steigt aus - Einer rückt nach

Dem Philosophen P9 beliebt es, bereits gesättigt auszusteigen.

Ein Philospph rückt nach, für ihn ist aber nur noch wenig Essenszeit übrig, es reicht nur für eine Essensrunde.

Damit das Programm sich ordentlich beenden kann, muss Vorsorge getroffen werden. Das Hauptprogramm erhält Zeiger auf die neu erzeugten Ablaufobjekte in einer Warteschlange.

Das Hauptprogramm (main thread) holt sich die Zeiger auf die neu erzeugten Philosophen aus der Warteschlange neuePhilos und wartet mit einem join() jeweils auf das Ende der Ab­lauf­fä­den.

(Ich meine, ich hätte wohl einen Grund für die if-Abfrage gehabt?)

Ein sauberes Finale

Unter ungünstigen Umständen, wenn etwa alle Philosophen nacheinander erst nach links greifen würden – was in diesem Modell nicht möglich ist – kann die Wartezeit auf ein Stäb­chen schon etliche Zeiteinheiten betragen. Hier hatte ich die Auszeit auf eine ungesund kurze Zeit eingestellt (1 Zeit­ein­heit).

Ausstieg und Neustart

Nach einigen Versuchen ergab sich für mein System die Auszeit von 3,5 Zeiteinheiten, bei der (im Experiment!) keine Ausreißer mehr auftraten. Auszuschließen sind sie aber nicht – oder doch? Wo ist die Theorie!

Ein thread, der sich verabschiedet, erzeugt bei mir auch gleich seinen Nachfolger und gibt zuden die belegten Ressourcen frei – wohl ein etwas realitätsfernes Szenario, will ich meinen. Nun denn, das wäre die Aufgabe einer überwachenden Instanz oder vielleicht eines Kontextmanagers.

Wie ist das Modell denn zu bewerten? Nun, die Philosophen speisen in Dreier- und Vie­rer­grup­pen, der zeitliche Durchsatz ist gut – so meine ich.

Alle Philosophen erhalten eine Mindest-Es­sens­zeit mit einer Spanne nach oben von rund 20%. Spontan sage ich, das ist doch ein recht faires Ergebnis, kein Philosoph ist deutlich benachteiligt.

Alle Philosophen sind fertig



Analyse (II) – Einfaches Systemmodell


Ich war neugierig auf das einfache Modell mit einem modifizierten Aus­wahl­al­go­rith­mus für die Stäbchenwahl: Jeder Philosoph nimmt die beiden Stäbchen nun in zufälliger Reihenfolge auf, entweder das linke oder doch erst das rechte?

Fast nur in Vierergruppen

Und wieder fast nur in Vierergruppen

Ich hatte einen wesentlich unruhigeren Ablauf erwartet, das Gegenteil ist der Fall: Es treten keine Dreiergruppen auf, sondern überwiegend Vierergruppen. Die Verläufe sind gleichförmiger und die Gesamtlaufzeiten schwanken weniger.

Eine Visualisierung mit PyQt wäre wohl ganz hübsch
– ein andermal.



Systemstillstand? Eine späte Einsicht


Es gibt sie, die deadlocks. Ich hatte das Vergnügen, in einem großen Ada-Programm mit Dutzenden von Ada-Tasks mehrere solcher Systemstillstände aufspüren zu dürfen, im laufenden Programm wurden diese schlicht durch (ziemlich sinnlose) Auszeiten aufgelöst.

Die speisenden Philosophen werden in Lehrbüchern gerne herangezogen, um die Total­blockade in einem System zu erläutern. Diese Blockade wird hier erreicht, wenn alle Philosophen gleichzeitig den linken (oder alle gleichzeitig den rechten) Eßstab aufnehmen. Ich meine, diese beiden Situationen sind die einzigen Blo­cka­de­si­tua­tio­nen im System der speisenden Philosophen.

Modelliert man solch ein System mit Hilfe von Software aus, so muss man sich bei der algorithmischen Abwicklung für gewisse Abläufe entscheiden. In aller Regel wird man dann aber definitiv die beiden Blo­cka­de­si­tua­tio­nen ausschließen können: das Software-System ist blockadefrei.

Das bedeutet: Alle Philosophen können an der Tischrunde teilnehmen, die Beschränkung auf 8 essen­wollende Teilnehmer ist nicht notwendig, kann aber auch zu Problemen führen (ich verweise auf das Beispiel am Ende). Hier und mir ging es vor allem darum, die Sprachmittel Pythons einzusetzen und zu erforschen.



Eines Schmetterlings Flügelschlag


Ich versuche eine Blockade zu provozieren. Alle Philpsophen beteiligen sich nun gleichberechtig am Geschehen. Die Essens- und Denkzeit beträgt immer 1 Zeiteinheit.

Und ich füge eine (1) kurze Anweisung zwischen dem Aufnehmenwollen des ersten Stäbchen und dem des zweiten hinzu (sleep(0) zeigte keine Wirkung):

essStaebchen[self.EssStaebchen1].nehmeStaebchenAuf();
time.sleep(0.0001 );
essStaebchen[self.EssStaebchen2].nehmeStaebchenAuf();
 

Der Lufthauch eines Flügelschlags und das Verhalten hat sich gänzlich gewandelt.

Das Laufzeitsystem, beziehungsweise der Scheduler hat nun mit der sleep-Anweisung einen weiteren Syn­chro­ni­sa­tions­punkt, an der er die nebenläufugen Objekte ver­pla­nen kann, mit dem Ergebnis, dass die Phi­lo­so­phen nun alle die Stäbchen auf­neh­men wollen. Bis auf Philosoph P3, der be­reits isst, haben alle anderen Herren ein Stäb­chen und/oder sie warten auf ein Stäb­chen. Nach einer Zeiteinheit erhält P2 das ab­ge­leg­te Essbesteck E2 und kann essen.

Wie lange braucht das Geschehen nun? Neun mal fünf ist fünfundvierig.

Und was ist mit Vierergruppen? Zunächst nichts.

Beim zweiten Lauf gab es dann er­staun­li­cher­wei­se Vierergruppen und einen schnel­len Durch­lauf - wer hätte das gedacht, eine Über­ra­schung.

Alle an die Eßstäbe!

 
Essen strikt im Einer-Takt!
Das grenzt doch fast schon an eine Blockade.
 

Einmal nur im Einer-Takt

Und jetzt brav in Vierergruppen!

Der dritte Lauf brauchte 26 Zeiteinheiten und der vierte endete im Systemstillstand – ich hatte meinen deadlock, großartigst.

9 Philosophen haben ein Stäbchen auf­ge­nom­men und/oder warten auf ein Stäb­chen, das macht 18 Stäbchen in der Hand oder in der Warteschlange – und nichts geht mehr, end­loses Warten auf einen Zeremonienmeister.

(Nebenbei: Ein weiteres sleep im Pro­gramm änderte nichts an der wilden Ver­hal­tens­wei­se.)

Ein wildes Programm,
dessen Ver­hal­tens­wei­se schon fast an Chaos grenzt.

Nur ein Lüftchen, welches Sturm sät? Es ist zwar nur eine Anweisung, die ich hinzugefügt habe, aber die bringt gänzlich neue Freiheitsgrade ins Ablaufgeschehen, die der Scheduler in recht zufälliger Weise zu nutzen scheint. Und ich war ja auch gewissermaßen so leicht­sin­ning und habe alle 9 Philosophen am Es­sens­ge­sche­hen teilnehmen lassen.

Weitere Steuerungsmöglichkeiten etwa durch die Vergabe von Prioritäten sind mir in Python bisher nicht aufgefallen. Weitere Struk­tu­rie­rungs­mög­lich­kei­ten, um ein Ab­lauf­ge­sche­hen zu beschreiben, gibt es aber noch in großer Zahl, als da sind Prozesse, Koroutinen und Ereignisschleifen, futures, und und und.
 

So oder ähnlich sieht es aus -
und schon ist Endstation

Alle auf die Eßstäbchen
Und dann war Schluss - Stillstand



Quellcode für Python 3


philosophen-1-py.html

philosophen-2-py.html

philosophen-3-py.html

philosophen-1.py    (Basis)      

philosophen-2.py    (Erweitert)

philosophen-3.py    (deadlock)




© 2015 Bernd Ragutt
Alle Rechte vorbehalten
 ... hier kann man hinschreiben letzte Änderung: 6. Februar 2016
Kruschtkiste