Ich habe eine Warteschlangensimulation in PHP geschrieben. Vereinfacht
ausgedrückt, erstellt das Programm für jeden der 7000 hinterlegten und
von unterschiedlichen Flughäfen startenden Passagiere Flugbuchungen für
den Zeitraum 2021-2023, die je nach Passagiertyp unterschiedlich
normalverteilt sind. Man möchte untersuchen, wie stark die verfügbaren
Flüge und Routen ausgelastet sein werden. Die Passagiere sind in einer
linearen Datenstruktur organisiert und werden der Reihe nach in der
Simulation behandelt.
Jetzt bin ich auf ein Problem gestoßen, das ich gar nicht so richtig in
Worte fassen kann. Ich bin der Meinung, dass die Passagiere, die sich
ganz am Ende der Datenstruktur befinden, im Nachteil sind, weil die
ersten Passagiere ganz vorn schon die meisten Flüge gebucht haben
würden. Folglich würde man fälschlicherweise annehmen, dass die
Passagiere am Flughafen X weniger Flüge buchen als an anderen Flughäfen,
obwohl die dort ansässigen Passagiere einfach nur vom System nachrangig
waren bedient worden.
Jetzt zu meinem eigentlichen Problem:
Ich würde es gern so machen, dass die Passagiere gleichzeitig und
gleichverteilt nach dem Zufallsprinzip Flüge buchen. So dass man nicht
vorhersagen kann, welcher Passagier als nächstes einen Flug buchen wird.
Das müsste mann IMHO mit Threads lösen können. Kann man für 7000
Passagiere einzelne Threads erstellen? Ist das technisch möglich? In den
Leistungsspezifikationen meines Intel Core i9-9900K Prozessors steht,
dass max. 16 Threads möglich sind. Hat das damit etwas zutun?
PS: PHP unterstützt ohne Weiteres kein Multithreading. Das ist mir
bekannt.
Grüße
> Das müsste mann IMHO mit Threads lösen können. Kann man für 7000> Passagiere einzelne Threads erstellen? Ist das technisch möglich? In den> Leistungsspezifikationen meines Intel Core i9-9900K Prozessors steht,> dass max. 16 Threads möglich sind. Hat das damit etwas zutun?
Warum um Himmels willen PHP?
Und Nein, das loesst man definitiv NICHT mit Threads
Warum nicht mit Threads?
-du kannst nicht so viele mit echten Threads simulieren, ab ein paar
tausend brauchst du ordentlich Resourcen - ja es gehen mehr als 16
-dann spielt deine Hardware so eine Art Scheduler für die Buchungen,
völlig intransparent für deine Simulation
-Du brauchst Locking-Strategien um Datenmüll mit den n Threads zu
verhindern, brauch auch sehr viel Resourcen
Die Frage ist warum erlaubt dein Simulationscode das die vorne stehenden
mehr dürfen? Normalerweise wird die Abfertigung am Flughafen durch
Anzahl Buchungs-Terminals und Buchungsobegrenzen definiert usw. Würden
die 7000 Passagiere in echt auch so ein ungleichgewicht erzeugen können,
ich denke nicht UND das ist das Kernproblem
Ein Schleifendurchlauf ist als Zeitscheibe zu sehen die jeder Passagier
bekommt um einen Teil seines Ziels zu erreich: am Warten, random dumm
rumstehen, buchen usw., es darf einfach nicht alles bei einem Passagier
pro Schleifendurchlauf passieren, weil das unrealistisch ist
Citii schrieb:> Ich bin der Meinung, dass die Passagiere, die sich> ganz am Ende der Datenstruktur befinden, im Nachteil sind
Dann randomisierst Du das einfach über mehrere Runs und vergleichst
erstmal, ob sich überhaupt was am Ergebnis ändert.
Dazu kannst Du im simpelsten Fall jedem Passagier ein Datenfeld
verpassen, das Du mit rand() oder so auffüllst, und danach sortierst Du
Deine Passagierliste.
Mußt Dich halt einlesen, wie Du den Zufallszahlengenerator
initialisieren mußt, damit er nicht jedesmal dieselbe Sequenz ausspuckt.
Typischerweise macht man das über die Systemzeit, die sich ja immer
ändert.
> Das müsste mann IMHO mit Threads lösen können.
Unsinn.
cppbert schrieb:> Ein Schleifendurchlauf ist als Zeitscheibe zu sehen
Stell dir einfach vor eine Schleifendurchlauf - egal wie viele
Passagiere ist 10sek Realzeit
P1 braucht 20sek für eine Buchung - dauert also zwei Schleifendurchläufe
bis er zu seinem nächsten Zustand kommt z.b. Boarding erwarten
P2 steht 1min in der vollen Warteschlange braucht also 6 Durchläufe dann
ist er auch im Buchungszustand wie P1 es schon am Anfang war, danach
wartet er auch aufs Boarding
Nach dem Prinzip kannst du tausende Passagiere paralell simulieren
Und die Frage ist wie wird gebucht:
-Telefonisch, ohne Zeit am Buchungsschalter
-in einer der n Buchungsschalter Schlangen an diesem Flughafen
Was sind Unterbrechungen, Verzögerung, Begrenzung z.B. nur 100 Buchungen
per Telefon pro Tag (ganz ganz ganz viele Schleifendurchläufe)
Threads sind dafür da, Rechenlast zu verteilen,
und nicht dafür, algorithmische Fehler zu beheben.
"für jeden der 7000 hinterlegten und
von unterschiedlichen Flughäfen startenden Passagiere"
Mach ein thread pro Flughafen, wieviele simulierst du? 10? 20?
Deine cpu kann und muss auch mehr als 16 threads verarbeiten, schau in
den taskmanager, da stehen tausende drin
Die Frage ist, ob du die Rechenlast effizient auf x thread aufteilen
kannst, dein Problem also auf effiziente kleine Rechenhäppchen
aufbrechen kannst.
Es gibt Bibliotheken fürs multithreading, in php sollte dies unter
pthreads zu finden sein.
Threads machen hier keinen Sinn, weil die Passagiere quasi in Echtzeit
auf die Buchungsterminals synchronisiert sind. Von daher ist irgendeine
Loop im Zeittakt das richtige.
Jeder Passagier wird also einmal pro Zeittakt durchgerechnet. Wenn er
nichts tut, sofort ein Return.
Die Bevorzugung kannst Du umgehen, indem du jede Loop 113 später
anfängst.
Citii schrieb:> Jetzt zu meinem eigentlichen Problem:> Ich würde es gern so machen, dass die Passagiere gleichzeitig und> gleichverteilt nach dem Zufallsprinzip Flüge buchen. So dass man nicht> vorhersagen kann, welcher Passagier als nächstes einen Flug buchen wird.>> Das müsste mann IMHO mit Threads lösen können.
Threads haben damit überhaupt nichts zu tun. Du musst zwischen der Zeit
in deiner Simulation und der Rechenzeit in deinem Prozessor
unterscheiden. Dinge, die in deiner simulierten Umgebung gleichzeitig
passieren, müssen nicht zwingend auf dem Rechner gleichzeitig simuliert
werden.
> Kann man für 7000 Passagiere einzelne Threads erstellen? Ist das technisch> möglich?
Ja, ist möglich, aber nicht der richtige Weg, um dein Problem zu lösen.
> In den Leistungsspezifikationen meines Intel Core i9-9900K Prozessors steht,> dass max. 16 Threads möglich sind. Hat das damit etwas zutun?
Die "Threads" dort sind nicht das selbe wie die Threads, die du in
deinem Programm erstellst, sondern eher sowas wie virtuelle CPU-Kerne.
Das ganze bedeutet konkret, dass aus Sicht der Software maximal 16
Threads echt gleichzeitig laufen. Für mehr wird schnell zwischen den
Threads hin- und hergeschaltet, so dass es aus Sicht des Anwenders
wirkt, als würden sie gleichzeitig laufen.
cppbert schrieb:> - ja es gehen mehr als 16> -dann spielt deine Hardware so eine Art Scheduler für die Buchungen,
Das ist nicht "so eine Art Scheduler", sondern es ist ein Scheduler. Und
der ist nicht Teil der Hardware, sondern des Betriebssystems.
> völlig intransparent für deine Simulation
Du meinst transparent - Die Simulation sieht es nicht.
> Ein Schleifendurchlauf ist als Zeitscheibe zu sehen die jeder Passagier> bekommt um einen Teil seines Ziels zu erreich: am Warten, random dumm> rumstehen, buchen usw., es darf einfach nicht alles bei einem Passagier> pro Schleifendurchlauf passieren, weil das unrealistisch ist
Genau. Man muss es in Zeitschritten simulieren und sich darum kümmern,
dass alles innerhalb eines Schritts sich so verhält, also ob es
gleichzeitig passiert. Der Algorithmus muss das berücksichtigen.
Das Problem besteht aktuell darin, dass die Passagiere einer nach dem
anderen bearbeitet werden und dadurch eine Reihenfolge entsteht, die in
der Simulation eigentlich nicht exisitert, weil alle Passagiere den
selben Zeitschritt auch gleichzeitig durchlaufen müssen. Du musst also
das Programm so umstellen, dass diese Reihenfolge verschwindet bzw keine
Rolle spielt.
Rolf M. schrieb:> Das Problem besteht aktuell darin, dass die Passagiere einer nach dem> anderen bearbeitet werden und dadurch eine Reihenfolge entsteht, die in> der Simulation eigentlich nicht exisitert, weil alle Passagiere den> selben Zeitschritt auch gleichzeitig durchlaufen müssen.
das würde sich ja durch einen Buchungsqueue (pro Buchungsterminal - da
es ja mehrere geben kann) automatisch ergeben - d.h. es gibt den Zustand
IchBucheGerade und ich WarteDaraufDasIchVorneStehe- und die Begrenzung
z.B. maximale länge der Schlange am Buchungsterminal oder die Anzahl an
Terminals verursacht dann das eben einigen gleichzeitig in
IchBucheGerade sind und viele andere in WarteDaraufDasIchVorneStehe -
durch die abgeschlossene Buchung wird der nächste in der Schlange auf
IchBucheGerade gesetzt - mehr oder minder ein paar einfache
Statemachines
cppbert schrieb:> und die Begrenzung> z.B. maximale länge der Schlange am Buchungsterminal oder die Anzahl an> Terminals verursacht dann das eben einigen gleichzeitig in> IchBucheGerade sind und viele andere in WarteDaraufDasIchVorneStehe
Aber was, wenn drei gerade buchen, aber nur noch ein Platz frei ist? Wer
bekommt ihn? Wenn man einfach die Liste der Passagiere durchgeht und
alle, die gerade im Buchungsstatus sind, auf gebucht setzt, solange noch
Plätze frei sind, dann werden Passagiere bevorzugt, die in der Liste
weiter vorne stehen. Ich denke, daher kommt die Idee von "Nop", das
zufallsgesteuert zu machen, damit nicht immer die selben das Pech haben,
keinen Flug mehr zu bekommen.
Rolf M. schrieb:> Aber was, wenn drei gerade buchen, aber nur noch ein Platz frei ist? Wer> bekommt ihn?
Wer zuerst kommt, mahlt zuerst? Oder wird dann am echten Flughafen auch
per Los entschieden? Wie sinnvoll ist die Simulation wenn sie nicht die
Wirklichkeit einigermaßen abbildet
Normalerweise sind die meisten Flüge ja schon zu Hause im Internet
gebucht worden und da gilt definitiv der schnellere Gewinnt, die Leute
die direkt am Flughafen buchen wollen stehen meistens doch eh vor einem
relativ vollen Flugzeug - wenn die das Flugzeug nicht voll bekommen
gehen die eben kurz vor Schluss mit dem Preis runter um die Ränge zu
füllen
Was soll eine homogen verteilte Buchung unter allen Passagieren
simulieren?
cppbert schrieb:> Rolf M. schrieb:>> Aber was, wenn drei gerade buchen, aber nur noch ein Platz frei ist? Wer>> bekommt ihn?>> Wer zuerst kommt, mahlt zuerst?
Und damit bist du wieder zurück am Anfang. Wie definierst du "zuerst"
bei Ereignissen, die exakt gleichzeitig eintreten?
> Oder wird dann am echten Flughafen auch per Los entschieden?
Vermutlich nicht. Da läuft die Zeit aber kontinuierlich ab und nicht
schrittweise wie in der Simulation. Es ist also in der Realität nicht
so, dass zwei Passagiere exakt zum selben Zeitpunkt buchen, aber in der
Simulation kann das passieren, da sie keine unendlich hohe zeitliche
Auflösung hat.
Wenn beispielsweise zwei Passagiere innerhalb der von dir
vorgeschlagenen Zeitscheibe von 10 Sekunden buchen, dann haben sie das
aus Sicht der Simulation exakt gleichzeitig getan, da die Simulation
immer nur in Schritten von 10 Sekunden weiterläuft und die unendlich
vielen Zeitpunkte dazwischen nicht separat berücksichtigt.
> Wie sinnvoll ist die Simulation wenn sie nicht die Wirklichkeit einigermaßen> abbildet
Simulation ist immer eine Vereinfachung der Realität. Man muss eben
versuchen, dafür zu sorgen, dass diese Vereinfachung das Ergebnis nicht
zu sehr beeinträchtigt.
> Was soll eine homogen verteilte Buchung unter allen Passagieren> simulieren?
Die Verteilung muss ja nicht gezwungenermaßen homogen sein, aber sie
muss irgendwie definiert und umgesetzt werden. "Der erste in der
globalen Liste der Passagiere kommt zuerst" ist jedenfalls keine
adäquate Umsetzung.
Rolf M. schrieb:> Wenn beispielsweise zwei Passagiere innerhalb der von dir> vorgeschlagenen Zeitscheibe von 10 Sekunden buchen, dann haben sie das> aus Sicht der Simulation exakt gleichzeitig getan, da die Simulation> immer nur in Schritten von 10 Sekunden weiterläuft und die unendlich> vielen Zeitpunkte dazwischen nicht separat berücksichtigt.
Das ist falsch.
Durch die Loop sind alle Passagiere wohlunterschieden. Alle 10s gehst Du
die Liste durch, und der erste (vom wechselnden Startpunkt aus) ist halt
1 fs schneller als der zweite. Usw.
A. S. schrieb:> Rolf M. schrieb:>> Wenn beispielsweise zwei Passagiere innerhalb der von dir>> vorgeschlagenen Zeitscheibe von 10 Sekunden buchen, dann haben sie das>> aus Sicht der Simulation exakt gleichzeitig getan, da die Simulation>> immer nur in Schritten von 10 Sekunden weiterläuft und die unendlich>> vielen Zeitpunkte dazwischen nicht separat berücksichtigt.>> Das ist falsch.>> Durch die Loop sind alle Passagiere wohlunterschieden. Alle 10s gehst Du> die Liste durch, und der erste (vom wechselnden Startpunkt aus) ist halt> 1 fs schneller als der zweite. Usw.
Ich wuerde nicht alle 10sek die Liste durch gehen, sondern volle power,
ein durchlauf wären bei mir irgendeine realzeit, wenn ueberhaupt nötig
Und warum nicht einfach immer die richtung der listenverarbeitung
invertieren also 0..n,n-1..0,1..n,...
Citii schrieb:> Ich habe eine Warteschlangensimulation in PHP geschrieben.
...
Hilfe, wo soll man da nur anfangen?
Lies einen Einführungstext über Diskrete Event-Simulation (DES).
Wirklich nur eine Einführungstext. Das reicht schon.
Nimm irgend einen existierenden DES Simulator. Die gibt es zu Hauf.
Wirklich irgendwas. Und sei es etwas, was das 50 Jahre alte GPSS
nachbildet.
Dann, dein Modell klingt völlig falsch.
Eine einzige Warteschlange? Merkwürdig.
Alle 7000 Passagiere auf einmal in der einen Warteschlange? Das ist wie
wenn am Montag Morgen pünktlich zur Öffnungszeit 08:00 Uhr 7000 Kunden
auf einmal vor einer einzigen Verkaufsstelle auftauchen. Warteschlangen
werden mit einer gewissen Rate und Verteilung gefüllt (Kunden kommen an)
und mit einer gewissen Rate und Verteilung abgearbeitet. Solche Raten
und Verteilungen realistisch zu modellieren gehört zum Erstellen einer
realistischen Simulation.
Ja, Kunden die später kommen haben eventuell nicht die gleiche Auswahl
wie Kunden die früh kommen. So ist das in der Realität. Wer in den
letzten Wochen zu spät im Supermarkt war bekam kein Klopapier.
Was weg ist ist weg. Wenn das anders sein soll, dann musst du das
Angebot modellieren. Also, dass Fluggesellschaften nicht alle Sitzplätze
in den Flügen gleichzeitig in den Verkauf geben. Zum Beispiel (und das
ist nur ein sehr einfaches Beispiel) eine Fluggesellschaft mag sich
entscheiden jeden Monat nur 10% ihrer Sitzplätze für einen Flug in den
Verkauf zu geben.
> Ich würde es gern so machen, dass die Passagiere gleichzeitig und> gleichverteilt nach dem Zufallsprinzip Flüge buchen. So dass man nicht> vorhersagen kann, welcher Passagier als nächstes einen Flug buchen wird.
"Welcher Passagier"? Behandelst du Passagiere (Kunden) als Individuen?
Das macht keinen Sinn. Für die Simulation ist ein Kunde nur ein
Arbeitspaket mit Eigenschaften das abgearbeitet (bedient) werden muss.
Es ist egal, ob zuerst Kunde 447 und dann Kunde 73 auftaucht, oder
zuerst 73, dann 447. Wichtig ist nur die Verteilung der Eigenschaften
der Kunden (z.B. welchen Flug sie wollen) und wann sie auftreten.
Man modelliert nicht das Buchen zufällig, man modelliert das Eintreten
der Kunden in Warteschlangen nach einer gewissen Zufallsverteilung.
Zur Vorhersagbarkeit. Das ist das was heraus kommen soll. Die Simulation
soll vorhersagen wie sich der Verkauf der Flüge verhält. 10 Mal die
Simulation laufen lassen soll 10 Mal +/- das gleiche Ergebnis liefern.
Wenn die Zufallszahlen noch vom gleichen Seed generiert werden, dann
soll 10 Mal exakt das gleiche Ergebnis heraus kommen.
> Das müsste mann IMHO mit Threads lösen können. Kann man für 7000> Passagiere einzelne Threads erstellen? Ist das technisch möglich? In den> Leistungsspezifikationen meines Intel Core i9-9900K Prozessors steht,> dass max. 16 Threads möglich sind. Hat das damit etwas zutun?
Vergiss das mal ganz schnell. Dein Simulationsmodell ist völlig falsch.
Es parallel auf 16 Threads auszuführen ändert nichts daran.
cppbert schrieb:>> Durch die Loop sind alle Passagiere wohlunterschieden. Alle 10s gehst Du>> die Liste durch, und der erste (vom wechselnden Startpunkt aus) ist halt>> 1 fs schneller als der zweite. Usw.>> Ich wuerde nicht alle 10sek die Liste durch gehen, sondern volle power,
Nicht 10 Sekunden in realer Zeit, sondern in simulierter Zeit.
> ein durchlauf wären bei mir irgendeine realzeit, wenn ueberhaupt nötig
Ja genau, darum ging es.
> Und warum nicht einfach immer die richtung der listenverarbeitung> invertieren also 0..n,n-1..0,1..n,...
Dann sind eben die in der Mitte gegenüber denen an den Enden
benachteiligt. Das Problem an sich bleibt das gleiche - du führst eine
Reihenfolge ein, die es eigentlich nicht geben dürfte.
Hannes J. schrieb:> Zum Beispiel (und das ist nur ein sehr einfaches Beispiel) eine> Fluggesellschaft mag sich entscheiden jeden Monat nur 10% ihrer Sitzplätze> für einen Flug in den Verkauf zu geben.
Und sie versucht, insgesamt mehr als 100% der Plätze zu verkaufen und
hofft, dass ein gewisser Anteil der Kunden den Flug nicht antritt. Und
wenn das nicht so hinhaut, das ist dann die Situation, in der am Gate
teils mehrere Hundert Euro für den geboten werden, der sich damit
einverstanden erklärt, auf den nächsten Flieger zu warten.
Rolf M. schrieb:> Dann sind eben die in der Mitte gegenüber denen an den Enden> benachteiligt. Das Problem an sich bleibt das gleiche - du führst eine> Reihenfolge ein, die es eigentlich nicht geben dürfte.
Brutal force wäre hier alle 7000 nach dem Zufallsprinzip auszuwählen,
mit Auswahl nur aus der Verbleibenden Menge.
Sehr einfach und trotzdem gemischt wird es, wenn man 2 verschiedene
Zufallszahlen nimmt und eine Liste der Primzahlen erstellt:
a: eine Primzahl im Bereich [-6998..6998]
idx: einen Startwert im Bereich [0..6999]
Und halt 7000 Interationen: idx=(idx+a+7000)%7000;
Das ist schon relativ nah an gut.
Ich hatte vor Jahren mal eine Vorlesung zur Warteschlangentheorie
gehört.
Da gibt es allerlei mathematische Modelle. Ich habe leider die
Mitschriften nicht mehr.
Aber vielleicht wäre es ganz praktisch, sich vorher mit der Theorie zu
beschäftigen.
https://de.wikipedia.org/wiki/Warteschlangentheorie
Multithreading macht einen Sinn um die Cores auszulasten, von denen
gibt's allerdings nur etwa 8 oder 16. Kann man machen, mehr bringt
allerdings nichts. Und des Task zu wechseln macht nur Sinn, wenn er
durch ist, oder eh warten muss, alles andere ist Quatsch fuer
Simulationen. Allenfalls muss man 's eben anpassen, dass er hinreichend
schnell "durch" ist.
Citii schrieb:> Ich habe eine Warteschlangensimulation in PHP geschrieben.
Du kannst mit "Dateianhang" die PHP hier posten. Sind es mehrere, packe
sie als zip und lade sie hier hoch
Citii schrieb:> Das müsste mann IMHO mit Threads lösen können. Kann man für 7000> Passagiere einzelne Threads erstellen? Ist das technisch möglich? In den> Leistungsspezifikationen meines Intel Core i9-9900K Prozessors steht,> dass max. 16 Threads möglich sind. Hat das damit etwas zutun?
Nuja man könnte das mit threads lösen, ist abber unfug..
sinnvoller mMn wäre es mit einer schlichten Pseudo Random funktion
Du kannst auch bei rrandom.org besser randomwerte erzeugen lassen;
aber ich denke das ist nichteinmal wirklich nötig hier.
Du nimmst Dir also Dein Passagier Array vor (sagen wir besagte 7000
Personen)
nennen wir es mal $passengers
Dann legst Du ein noch leeres Hilfsarray an für den Moment nennen wir es
mal $noticketpassengers
und dann ist der Rest leicht:
1
// zunächst füllst Du das Hilfsarray mit allen Passagieren (deren Index)
2
for($i=0; $i<count($passengers); $i++)
3
$noticketpassengers[]=$i;
4
5
//Nun kommt der etwas unansehnliche Teil, er macht aber später Sinn...
6
while(count($noticketpassengers)) //solange wir passagiere ohne Ticket haben
7
{
8
//wir nehmen "wahllos" einen index aus dem Hilfsarray
9
$ntpidx = rand(0,count($noticketpassengers)-1);
10
//und buchen dem dazugehörigen Passgier ein Ticket
11
$pidx = $noticketpassenger[$ntpidx]; // die passagiernummer
12
13
book_flight($passenger[$pidx]);
14
// oder wie auch immer du das Ticket buchst
15
16
// nun entfernen wir den index des Passagiers aus dem Hilfsarray
Ich möchte allen danken, die mir mit geschrieben haben.
Hannes J. schrieb:> Nimm irgend einen existierenden DES Simulator. Die gibt es zu Hauf.> Wirklich irgendwas. Und sei es etwas, was das 50 Jahre alte GPSS> nachbildet.
Dann bekomme ich an anderer Stelle andere Probleme. PHP ist nicht
grundsätzlich ungeeignet für diese Aufgabe. Es kann einzelne
Informationen der Simulation in HTML ausgeben und Transaktionen in
Datenbanken hinterlegen.
Hannes J. schrieb:> Warteschlangen> werden mit einer gewissen Rate und Verteilung gefüllt (Kunden kommen an)> und mit einer gewissen Rate und Verteilung abgearbeitet
Steht auch im Eröffnungsthread. Buchungen sind normalverteilt.
Hannes J. schrieb:> Man modelliert nicht das Buchen zufällig, man modelliert das Eintreten> der Kunden in Warteschlangen nach einer gewissen Zufallsverteilung
zufällig, aber nach einer bestimmten Zufallserteilung. Das habe ich so
geschrieben.
Ich habe mich nicht korrekt ausgedrückt. Ich wollte mit mehreren Threads
erreichen, dass Kunden parallel bzw. simultan buchen bzw. in die
Warteschlange eintreten. An einem Beispiel: Kunde A bucht am Flughafen
HAJ um 9:00 Uhr einen Flug von HAJ nach X. Kunde B bucht am Flughafen
LHR ebenfalls einen Flug um 09:00 Uhr nach Y.
Dass mein Ansatz unsinn ist, habe ich jetzt begriffen. Ich habe als
Student mit WinGPSS gearbeitet. Da war es so, dass die Kunden an einer
der drei offenen Kassen mit einer Ankunftszeit von z. B. 10 +- 2 Minuten
eintrafen. Manchmal sind dann zwei Kunden zur gleichen Zeit an
unterschiedliche Kassen eingetroffen und wurden vom System parallel
bedient. Ich hatte vermutet, dass man dies mit Threads löst.
Citii schrieb:> Dann bekomme ich an anderer Stelle andere Probleme. PHP ist nicht> grundsätzlich ungeeignet für diese Aufgabe. Es kann einzelne> Informationen der Simulation in HTML ausgeben und Transaktionen in> Datenbanken hinterlegen.
das kann auch jede andere Programmiersprache - in ungefähr gleich viel
Zeilen Code - kein wirklich gutes Argument
>Ich habe mich nicht korrekt ausgedrückt. Ich wollte mit mehreren Threads>erreichen, dass Kunden parallel bzw. simultan buchen bzw. in die>Warteschlange eintreten.
Das hat jeder hier auch so verstanden - nur versteht nur keiner so recht
warum deinen Simulation nicht selbst einen Parallelverarbeitung durch
Zeitscheiben erlaubt - was das gleiche wäre wie Threads nur eben viel
flexibler und in deinem Fall schneller
>Dass mein Ansatz unsinn ist, habe ich jetzt begriffen.
die meisten hier Fragen sich wie du überhaupt irgendeine Form von
Parallelität simuliert hast - normalerweise ist es das 1. was man bei
einer solchen Simulation braucht, es ist uns äußerst unklar wie du das
machst
>Ich hatte vermutet, dass man dies mit Threads löst.
wie schon erklärt deinen Simulations-Parallelität ist was ganz anderes
als echte Threads - verhält sich irgendwie ähnlich ab sind doch
grundverschieden
cppbert schrieb:> die meisten hier Fragen sich wie du überhaupt irgendeine Form von> Parallelität simuliert hast - normalerweise ist es das 1. was man bei> einer solchen Simulation braucht, es ist uns äußerst unklar wie du das> machst:
Ich habe den ersten Kunden genommen und für ihn die Zeit in einer
Schleife vergehen lassen. Er hat dann immer in einem normalverteilten
Abstand gebucht. Dann habe ich die Zeit wieder auf 0 gesetzt und den 2.
Kunden genommen. er hat dasselbe gemacht, wie der erste. Das habe ich
dann für alle anderen Kunden auch so umgesetzt.
Citii schrieb:> Ich habe mich nicht korrekt ausgedrückt. Ich wollte mit mehreren Threads> erreichen, dass Kunden parallel bzw. simultan buchen bzw. in die> Warteschlange eintreten. An einem Beispiel: Kunde A bucht am Flughafen> HAJ um 9:00 Uhr einen Flug von HAJ nach X. Kunde B bucht am Flughafen> LHR ebenfalls einen Flug um 09:00 Uhr nach Y.
Naja das würden in einer Schleife von 7000 Kunden wohl alle ;)
die läuft ja keine Minute
Wenn es Dir aber darum geht mit parallelen threads zu arbeiten,
dann ist vielleicht das hier eine geeignete Krücke
https://w-shadow.com/blog/2008/05/24/improved-thread-simulation-class-for-php/
Alt aber das Prinzip funktioniert auch in aktellen php Versionen
Die Sache ist die.. Du wirst dennoch nicht schaffen, dass zwei Kunden
zur exakt gleichen Zeit etwas buchen;
denn gestartet werden die threads nacheinander damit hat immer ein Kunde
"Vorsprung".
Es gab noch eine etwas komplexere thread-simulation für php
http://ajphpth.sourceforge.net
die ich mal getestet hab aber für die zwei drei banalen load tests hatte
mir die Andere besser gefallen.
Egal ..
es gibt noch dutzende andere PHP Multithreading klassen
aber es ist zuu lang her dass ich nach etwas solchem suchte
alsdass ich mich an auch nur deren url erinnern könnte;
die zwei da oben hab ich mir notiert (beide auch benutzt für diverse
testläufe) weder die eine noch die Andere hatte für mich dauerhaften
Nutzen.
Aber vielleicht für Dich #schulterzuck
Immerhin kannst Du so diverse Terminals (threads) öffnen in denen
jeweils
ein Teil der Kunden bedient wird
(zehn threads a 700 Kunden zB)
vielleicht reicht das schon um den von Dir gesuchten Sonderfall zu
erzeugen.. ich glaub nicht, aber ggf hast Du Glück.
'sid
PS Tipp: wenn Du Kollisionen erzwingen willst, kannst Du in php mit
microtime() die Mikrosekunden auslesen, da alle threads auf derselben
Maschine liegen erzeugen alle dieselebe microtime... das könnte man
einigermassen synchron bekommen wenn man sich bemüht
Citii schrieb:> Ich habe den ersten Kunden genommen und für ihn die Zeit in einer> Schleife vergehen lassen.
und genau das ist eben falsch - dann wird jeder Kunden sequenziell
verarbeitet
du brauchst was wie
Kunde
WasMachtErGerade Buchen,Warten,Laufen
WieLangeDauertDasNoch 0..n Schleifendurchläufe
for($kunde : alle kunden )
{
$kunden.WieLangerDauerDasNoch minus 1 // wieder ein bisschen Zeit
vergangen
if $kunden.WieLangerDauerDasNoch == 0 // Kunde ist fertig mit Aktion
WasMachtErGerade neu belegen
WieLangeDauertDasNoch neu belegen
}
damit können Kunden parallel Dinge machen
x = irgendein Simulations-Zyklus
Durchlauf x
Kunde1.Buchung läuft noch 3 Schleifendurchläufe
Kunde2.Warten läuft noch 1 Schleifendurchlauf
Kunde3.Buchung läuft noch 5 Schleifendurchläufe
Durchlauf x+1
Kunde1.Buchung läuft noch 2 Schleifendurchläufe
Kunde2.Warten läuft noch 0 Schleifendurchlauf
-> Kunde2 fängt an zu Buchen, dauert 3 Zyklen
Kunde3.Buchung läuft noch 4 Schleifendurchläufe
Durchlauf x+2
Kunde1.Buchung läuft noch 1 Schleifendurchläufe
Kunde2.Buchung läuft noch 3 Schleifendurchlauf
Kunde3.Buchung läuft noch 3 Schleifendurchläufe
Durchlauf x+3
Kunde1.Buchung läuft noch 0 Schleifendurchläufe
-> Kunde1.Boarding läuft 2 Durchlläufe
Kunde2.Buchung läuft noch 2 Schleifendurchlauf
Kunde3.Buchung läuft noch 2 Schleifendurchläufe
Durchlauf x+4
Kunde1.Boarding läuft noch 2 Schleifendurchläufe
Kunde2.Buchung läuft noch 1 Schleifendurchlauf
Kunde3.Buchung läuft noch 1 Schleifendurchläufe
Durchlauf x+5
Kunde1.Boarding läuft noch 1 Schleifendurchläufe
Kunde2.Buchung läuft noch 0 Schleifendurchlauf
-> Kunde1.Boarding läuft 2 Durchläufe
Kunde3.Buchung läuft noch 0 Schleifendurchläufe
-> Kunde1.Boarding läuft 2 Durchläufe
Durchlauf x+5
Kunde1.Boarding läuft noch 0 Schleifendurchläufe
Kunde1.Fliegt, Dauer: 12 Zyklen
Kunde2.Boarding läuft noch 2 Schleifendurchläufe
Kunde3.Boarding läuft noch 2 Schleifendurchläufe
alles andere ist einfach Quatsch
wenn du jeden Kunden einzeln behandelst machst du eine
Zwangsserialisierung
cppbert schrieb:> du brauchst was wie
okay ... deinen Vorschlag muss ich erstmal studieren und in Code gießen.
Frage: gibts in der Literatur einen Namen für dieses Paradigma?
Citii schrieb:> cppbert schrieb:>> du brauchst was wie>> okay ... deinen Vorschlag muss ich erstmal studieren und in Code gießen.
hättest du schon vor Tagen machen können :)
> Frage: gibts in der Literatur einen Namen für dieses Paradigma?
Das ist noch zu wenig um ein "Paradigma" zu sein - Statemachine +
Scheduling - aber hier auf so kleinem Niveau das jedes Dokument das du
findest wohl 100 mal umfangreicher ist
Es ist einfach ein Konzept das es dir erlaubt n Kunden in m Zuständen
über die Zeit (mit simulierter Zeit) parallel zu handhaben
und ganz wichtig:
Natürlich kann sich der Kundenzustand auch von außen forciert aendern
z.B.
weil das Terminal schliesst oder das Flugzeug voll ist usw.
so in der Art
1
for(simulation-schleife)
2
{
3
for($kunde : alle kunden )
4
{
5
$kunden.WieLangerDauerDasNoch minus 1 // wieder ein bisschen Zeit vergangen
6
7
if $kunden.WieLangerDauerDasNoch == 0 // Kunde ist fertig mit Aktion
8
{
9
WasMachtErGerade neu belegen
10
WieLangeDauertDasNoch neu belegen
11
}
12
}
13
14
//alle 100 Simulations-Durchlaeufe
15
//random 50% aller Kunden für 100 Zyklen ins Gefängnis stecken
16
//d.h. 50% auswählen und von denen den WasMachtErGerade auf SitztImGefängnis setzen und WieLangeDauertDasNoch auf 100
