Forum: PC-Programmierung Multithreading für Simulation


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Citii (Gast)


Bewertung
-2 lesenswert
nicht lesenswert
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

von cppbert (Gast)


Bewertung
2 lesenswert
nicht lesenswert
> 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

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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)

von Mike B. (mike_b97) Benutzerseite


Bewertung
-1 lesenswert
nicht lesenswert
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.

von A. S. (achs)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Rolf M. (rmagnus)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Rolf M. (rmagnus)


Bewertung
-1 lesenswert
nicht lesenswert
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.

von cppbert (Gast)


Bewertung
1 lesenswert
nicht lesenswert
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?

von Rolf M. (rmagnus)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von A. S. (achs)


Bewertung
0 lesenswert
nicht lesenswert
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.

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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,...

von Hannes J. (Firma: professional Professional) (pnuebergang)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Rolf M. (rmagnus)


Bewertung
0 lesenswert
nicht lesenswert
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.

von A. S. (achs)


Bewertung
0 lesenswert
nicht lesenswert
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.

: Bearbeitet durch User
von PittyJ (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Joggel E. (jetztnicht)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Anita H. (anita1995)


Bewertung
0 lesenswert
nicht lesenswert
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

von sid (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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:
// zunächst füllst Du das Hilfsarray mit allen Passagieren (deren Index)
for($i=0; $i<count($passengers); $i++)
    $noticketpassengers[]=$i;

//Nun kommt der etwas unansehnliche Teil, er macht aber später Sinn...
while(count($noticketpassengers)) //solange wir passagiere ohne Ticket haben
{
    //wir nehmen "wahllos" einen index aus dem Hilfsarray
    $ntpidx = rand(0,count($noticketpassengers)-1);
    //und buchen dem dazugehörigen Passgier ein Ticket
    $pidx = $noticketpassenger[$ntpidx]; // die passagiernummer
    
    book_flight($passenger[$pidx]);
    // oder wie auch immer du das Ticket buchst

    // nun entfernen wir den index des Passagiers aus dem Hilfsarray
    unset($noticketpassengers[$ntpidx]);
    // und lassen das array neu durchnummerieren
    $noticketpassengers = array_values($noticketpassengers);

    // nun haben wir wieder ein sauber durchnummeriertes array
    // das Hilfsarray wird dabei immer kürzer
    // und enthält immer nur ids von Passagieren die noch ohen Ticket sind
    // das ist schneller als wenn man solange random laufen lässt bis
    // man einen Passagier erwischt der noch ohne Ticket ist
}

'sid

von Citii (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
>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

von Citii (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von sid (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Citii (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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?

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von cppbert (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

for(simulation-schleife)
{
  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
    }
  }

  //alle 100 Simulations-Durchlaeufe
  //random 50% aller Kunden für 100 Zyklen ins Gefängnis stecken
  //d.h. 50% auswählen und von denen den WasMachtErGerade auf SitztImGefängnis setzen und WieLangeDauertDasNoch auf 100
}

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.