[C++] Threads

[[Moepi]1]

Der folgende Thread liest sich vielleicht etwas seltsam - das Problem ist auch seltsam. Ich hoffe, es denkt sich doch jemand rein. Also Folgendes:

Ich habe ein kleines "Benchmark" in C++ geschrieben. Dazu hab ich mir ne Benchmarkklasse geschrieben, welche das Setup der Testdaten, die Anzahl an Schleifendurchläufen mit identischen Werten und das Zählen der Prozessor Ticks übernimmt.
Zusätzlich existieren eine Reihe von Algorithmenklassen, welche jeweils eine bestimmte Implementierung eines algorithmischen Problems darstellen, das die CPU in Schwitzen bringen soll. Das funtkioniert bis hier hin auch prächtig. Allerdings hab ich jetzt doch noch einen Weg gefunden, besagten Algorithmus zu Threaden. Das sieht jetzt so aus:

1) Benchmarkklasse bereitet Testdaten vor

2) Benchmarkklasse läuft in eine while(loops > 0) Schleife, in der iterativ mehrmals hintereinander der gethreadede Algorithmus ausgeführt wird (er ist ein eigenes C++ Objekt)

2a) Eine kleine Vorbereitungsmethode im Algorithmus erstellt nach dem Aufruf durch die Benchmarkklasse die beiden Threads (und macht noch ein bisschen was anderes).

2b) Diese Vorbereitungsmethode ruft dann den eigentlichen Algorithmus auf (durch Übergabe der Methode an die beiden Threads und join der beiden Threads)

3) Nach Rückkehr aus der Algorithmenmethode wird der Loopcounter um 1 dekrementiert (das passiert bereits wieder in der Benchmarkklasse) und der Algorithmus neu gestartet.


Die Anzahl der Loopcounts wird via Kommandozeile gesteuert und dient der Verringerung des Messfehler - bei kleinen Eingabewerten terminiert der Algorithmus binnen weniger als 1ms. Und ja, das ist mit Zählen von CPU Ticks messbar

Jetzt kommt aber das eigentlich interessante:
Wenn die Loopcount auf 1 steht, wird nach jedem Algorithmenlauf das Testdatenarray zerstört und etwas größer neu erstellt. Das Benchmark läuft dann in etwa in der zu erwartenden Geschwindigkeit.
Wenn ich aber die Loopcount meinetwegen auf 200 setze, dann wird das Benchmark grottenlahm. Ich spreche hier von einem Faktor von ca. 1000! (dass der Algorithmus 200 mal durchlaufen wird hab ich schon rausgerechnet)

Es sieht "fast" so aus, als könnte das Betriebssystem zur Ausführungszeit nach Terminierung des Algorithmus und damit der beiden Threads nicht sofort wieder 2 neue Workerthreads erstellen. Mach ich aber zwischen den einzelnen Loops eine kurze Pause, klappts zunehmend besser. Nur das steht im Konflikt mit der Zeitmessung.
Daher jetzt meine Frage: Weiß jemand, ob ein Thread wirklich dann vernichtet ist, wenn er terminiert hat, oder wird der vom Betriebssystem erst irgendwann wirklich "terminiert"? Kann es in diesem Zeitraum (zeitliche) Probleme geben, wenn neue Threads erstellt werden sollen? Kann man einen Thread, wenn er denn nach seiner Terminierung noch nicht wirklich weg ist, irgendwie von Hand töten (also im Source Code)? pthread_exit hat leider nicht geklappt....


Achja, derzeit läuft das ganze unter Linux mit pthreads. Unter Windows hat es ganz ähnliche Symptome gegeben!

Bin für jedwede Anregungen dankbar!

 

[Enigma]

Ich hab zwar noch nie etwas mit Threads richtig programmiert - aber was mir spontan einfallen würde: Benchmark doch die Erstellung von Threads unter Linux

Hast du eventuell einen Überlauf beim auswerten der Ticks im Prozessor? Afik ist das ne ziemlich große Zahl.

Dass der Scheduler diese enormen Verzögerungen verursacht wäre denkbar, wenn du mehrere zig tausend Threadwechsel in der Sekunde hast - ist das der Fall?

 

[7H3 N4C3R]

Das Erstellen von Threads ist eine vergleichsweise extrem teure Aktion. Sowas sollte man immer vermeiden. Wann die Threads real zerstört werden ist Sache des Betriebssystem. Nach dem Join hat der Thread aus Programmsicht abgelebt. (nicht direkt nach Ende der Thread-Einstiegspunkts, da evtl. noch Daten übergeben werden müssen)

Die Threaderstellung kann also ein Problem sein. Unter Windows gibt's dafür den Thread-Pool. Pthreads bietet afaik keine Alternative. Alternativ bastelst du dir selber einen Thread-Pool.

Möglicherweise hast du auch einfach das Locking ungünstig implementiert. Hast Du Mutexe/Sempaphoren/Critical Sections? Wie oft werden die gelockt?

Jag doch auch mal einen Profiler drüber. Da du unter Linux bist, z.B. gprof.

 

[[Moepi]1]

Möglicherweise hast du auch einfach das Locking ungünstig implementiert. Hast Du Mutexe/Sempaphoren/Critical Sections? Wie oft werden die gelockt?

Naja also es is so. Normalerweise lass ich pro Gesamtdurchlauf die Testdatengröße um 32 Felder inkrementieren und pro Größe solls 200 Durchläufe geben. Bei kleinen Werten für die Testdaten ist klar, dass die Threaderstellung mehr Zeit kosten wird, als ich durch das Threading wieder raushole. Lohnen wird sich das ganze frühestens ab ner Arraygröße von 32k oder sowas in der Richtung.
Critical Sections - naja, das ganze Ding is ne Critical Section. Schau Dir nen Datenflussgraphen der schnellen Fourier Transformation an: Am Ende jeder Stufe müssen die Threads aufeinander warten. Das heißt ich habe ld(n) Synchronisationen mit Hilfe von Mutexes (Barrieren). Aber die kosten, soweit ich das feststellen konnte, (überraschenderweise) nur sehr sehr wenig Zeit. Die schließe ich als Fehlerquele hierfür eigentlich aus.

Die Betriebssysteme scheinen sich irgendwie an der Erstellung und Vernichtung der Threads zu stören. Aber da kann ich auch nur schwer Zusammenhänge erkennen:
Bei nem kleinen n ist klar, dass das System meinetwegen alle paar Hunder Mikrosekunden (!) 2 Threads erstellen soll. Dass es hier bremst ist logisch.
Das sollte sich aber bei zunehmend größerem n irgendwann realtivieren, wenn nur noch meinetwegen alle paar Hundert Millisekunden Threads zu erstellen sind. Aber eben das tut es offensichtlich nicht mal ansatzweise, zumindest dann, wenn ich diese verflixte Loopcount hochdrehe...

 

[7H3 N4C3R]

Naja ich weiß nun nicht wie der Datenflussgraph der FFT aussieht.

Schonmal ein erstes - Mutexe sind nicht zum Warten sondern zum Locken. Das ist ein subtiler, aber fundamentaler Unterschied. Zum Warten nimmt man unter Windows Events bzw. mit pthreads Condition Variables.

Kannst du mal ein wenig Code zeigen, wo die Algorithmen-Stufen gestartet werden?

Achso, bei 200 Durchläufen, wieviele Threads werden da gestartet und beendet?
Ich erinnere mich gerade an so Sachen, dass das zumindest unter Windows 2-3 Sekunden dauern kann, bis du wieder einen neuen Thread bekommst.

 

[[Moepi]1]

Danke Dir ich hab das Problem grade beim Telefonat mit nem Kommilitonen erkannt. Das Problem ist folgendes:

Man kann Barrieren mit Mutexes realisieren. Allerdings sind das "Einwegbarrierern". Das Ding steht aber bei mir am Ende einer Schleife (Kernelschleife der FFT). Das hat zur Folge, dass bereits nach dem ersten Schleifendurchlauf eine Desychronistation der beiden Threads entstehen KANN (aber nicht muss - das ist Murphys Law). Durch diese Desynchronisation laufen die beiden Threads fortan sequentiell statt parallel, wodurch das Programm allein dadurch schon mal doppelt solang brauchen muss um zu terminieren. Je nach dem was da sonst noch passiert im Laufe der Zeit, kann ich mir gut vorstellen, dass das ganze Programm anfängt hohlzudrehen.

Die Lösung ist dank der Datenflussgraphen aber straight forward: Ich muss nur die erste Stufe etwas krank threaden und am Ende der ersten Stufe einmal die Threads synchronisieren. Anschließend habe ich die Daten in zwei Teiläume aufgespalten und kann fortan meinen "Urkernel" (also die Version völlig ohne Threadimplementierung) mit etwas angepassten Indizes aus jedem der beiden Threads heraus auf den Rest der FFT ansetzen. Das werd ich jetzt probieren und das Problem so umgehen.

Ach, Datenflussgraph FFT für n=8. Den Code erspar ich Dir - es sei denn Du willst ihn UNBEDINGT sehen (und nein, es macht keinen Spaß!)

 

[7H3 N4C3R]

Okay, prima. Und zu den Barrieren, das ist ansich richtig, dass man das mit Mutexes lösen kann, ist aber unschön. Falls du dir mal das Buch "Unix Network Programming Vol 2 - Inter Process Communication" besorgen kannst, da ist das sehr schön erklärt. (Habe es leider auch nicht greifbar. Müsste ich erst auf Arbeit nachlesen) Gruß.

 

[arc_user]

in einem richtigen multi-tasking OS wird normal der Task nur angeregt sich zu zerstoeren.
der zerstoerung erfolgt dann meist im task selber, da eine zerstoerung aus einem dritten system unsynchron sein wuerde und man nicht weiss was durch die zerstoerung alles im speicher nicht zurueckgesetzt wird.
bei der aufforderung zur zerstorung muss man nachher noch solange warten bis der task
aus der OSTCBPrioTbl geloescht ist, oder die neue erzeugung dieser preoritaet durch abfrage OS_PRIO_EXIST uebrepruefen.
wenn zwei task auf einen speicher zugreifen, muss dies natuerlich mit semaphoren verriegelt werden.
wenn diese beiden systeme dann nichts anderes machen als diesen speicher lesen und schreiben muss eine sequentielle verarbeitung zwingend rauskommen.
paralelle verarbeitung geht nur mit reentranten code, alles ander is sequentiell.
was ich aber ueberhaupt nicht verstehe ist, dass die systemauslastung dadurch steigen soll. normal muss die auslastung des gesamtsystem sinken, wenn die verarbeitung sequenziell wird, da der blockierte task auf sleep geht und keine leistung benoetigt wogegen wenn zwei unterschiedliche speicher verwendet werden ohne blockade das system die maximale leistung verbraten muesste.