Die Tücken der parallelen Programmierung

Sculletto

Ensign
Dabei seit
Aug. 2008
Beiträge
233
Hi Leutz,

Ich wollte euch mal von meinen Erfahrungen mit paralleler Programmierung (mittels Multithreading auf einer Mehrkern-CPU) berichten, insbesondere von deren Tücken, die ganz unvorhergesehenermaßen auftreten können.

Einst, vor vielen Jahren, noch zu Single-Core-Zeiten, habe ich die eine oder andere wissenschaftliche Simulation programmiert. Als ich dann 2007 meine erste Dual-Core-CPU, einen Athlon64 X2, hatte, dachte ich mir, ich könnte es mal angehen, meine Programme auf Multithreading umzustellen, um mehr Performance rauszuholen. Damals klappte das allerdings noch nicht so recht, ich bekam zwar mehrere Threads zum laufen, aber eine Performance-Steigerung stellte sich nicht ein. Ich berichtete seinerzeit in diesem Thread auf www.3dcenter.de davon:

http://www.forum-3dcenter.org/vbulletin/showthread.php?t=378301

(ich nannte mich dort Arokh). Meine Vermutung ist, dass das daran lag, dass beim X2 jeder Kern einen separaten L2-Cache hat, was dann, wenn beide Kerne an derselben Datenstruktur werkeln, nachteilig ist.

Mittlerweile habe ich jedoch einen Intel Core 2 Duo, und so dachte ich mir kürzlich, ich könnte es doch darauf noch einmal versuchen (der Core 2 Duo hat einen shared L2-Cache für beide Kerne, das sollte die bessere Voraussetzung bieten). Gesagt, getan, und in der Tat konnte ich mit 2 Threads einen Performance-Zuwachs von knapp 50% erzielen. Dass es nicht mehr geworden ist, liegt vermutlich einmal daran, dass die Ergebnisse im Hauptthread grafisch ausgegeben werden, und andererseits an der ziemlich aufwendigen Synchronisation zwischen den Threads. Ich habe hier mal das Prinzip, wie die parallele Verarbeitung abläuft (bzw. theoretisch ablaufen soll), als Diagramm skizziert:

Parallel processing.png

Zunächst sendet der Hauptthread ein Start-Signal an die Worker-Threads, dass sie loslegen können (dunkel orange). Die Worker-Threads beginnen dann mit der Verarbeitung (grüne Abschnitte) und synchronisieren sich dabei zwischendurch immer wieder (hell orange). Der Hauptthread wartet solange (grauer Abschnitt). Wenn die Worker-Threads mit einem Durchlauf fertig sind, senden sie ein Ready-Signal an den Hauptthread (lila), der daraufhin die Rechenergebnisse grafisch ausgibt (türkiser Abschnitt), während die Worker-Thread warten (graue Abschnitte). Anschließend sendet er für den nächsten Durchlauf wieder das Signal an die Worker-Threads, usw.

Soweit die Theorie. Jedoch musste ich feststellen, dass mein Programm immer wieder sporadisch hängenblieb (die Ausgabe fror ein, und die im Taskmanager angezeigte CPU-Last ging auf 0 herunter). Ich vermutete die Ursache zunächst in der Synchronisation zwischen den Worker-Threads, dass es da irgendwo zu einem Deadlock kommen würde. Nach eingehender Analyse des Phänomens gelangte ich aber schließlich zu der Erkenntnis, dass das Problem an einer ganz anderen Stelle lag, nämlich am Zusammenspiel mit dem Hauptthread!

Es zeigte sich nämlich, dass es ab und zu mal vorkam, dass in dem Augenblick, in dem der Haupthread das Start-Signal sendete (dunkel orange im Diagramm), gar nicht alle Worker-Threads bereit waren, das Signal entgegenzunehmen. Konsequenz: der Hauptthread hatte das Signal abgeschickt und wartete darauf, dass die Worker-Threads fertig wurden, aber einer der Worker-Threads hatte das Signal nicht empfangen und wartete noch auf dieses. Ein typischer Deadlock! Um dem vorzubeugen, habe ich dann die Routine zum Absenden des Start-Signals modifiziert, und zwar so, dass der Hauptthread die wartenden Worker-Threads zählte, bevor er das Signal losschickte, und in dem Fall, dass noch nicht alle Worker-Threads im Wartezustand waren, eine kurze Pause machte und es dann erneut versuchte.

Die sporadischen Freezes traten aber immer noch auf! Abermals fiel mein Verdacht auf die Synchronisation zwischen den Worker-Threads. Aber an der lag es auch diesmal nicht. Vielmehr stellte sich heraus, dass das, was passieren konnte, wenn der Hauptthread den Worker-Threads signalisierte, weiterzumachen, auch im umgekehrten Fall eintreten konnte, wenn die Worker-Threads dem Hauptthread signalisierten, dass sie fertig waren (lila im Diagramm). Es konnte nämlich sein, dass der Hauptthread aus irgendwelchen Gründen in diesem Augenblick noch gar nicht soweit war, auf das Ready-Signal von den Worker-Threads zu warten. Da muss man aber auch erstmal drauf kommen: theoretisch sollte ja der Haupthread sofort in den Wartezustand gehen, nachdem er das Start-Signal abgeschickt hat, aber in der Praxis ist das offenbar nicht immer sichergestellt.

Des Rätsels Lösung war also: der Hauptthread muss mit dem Senden des Start-Signals warten, bis alle Worker-Threads bereit sind, und die Worker-Threads müssen beim Senden des Ready-Signals warten, bis der Haupthread bereit ist.

Hier das ganze als Programmcode, in C++ mit boost als Multithreading-Bibliothek. Zunächst die ursprüngliche Lösung:

Code:
boost::condition_variable condStart, condReady, condSync;
boost::mutex mut;
int readyCounter = 0;
int waitingCounter = 0;

// Haupthread sendet Start-Signal
void notifyStart()
{
    condStart.notify_all();
}

// Worker-Threads warten auf Start-Signal
void awaitStart()
{
    boost::unique_lock<boost::mutex> lock(mut);
    condStart.wait(lock);
}

// Synchronisation zwischen den Worker-Threads
void synchronize()
{
    boost::unique_lock<boost::mutex> lock(mut);
    waitingCounter++;
    if (waitingCounter < NUM_THREADS)
    {
        condSync.wait(lock);      // auf die übrigen Worker-Threads warten
    }
    else
    {
        waitingCounter = 0;
        condSync.notify_all();    // alle Worker-Threads warten → weitermachen
    }
}

// Worker-Threads senden Ready-Signal an Haupthread
void notifyReady()
{
    boost::unique_lock<boost::mutex> lock(mut);
    readyCounter++;
    if (readyCounter >= NUM_THREADS)
    {
        // alle Worker-Threads sind fertig → Signal schicken
        readyCounter = 0;
        condReady.notify_one();
    }
}

// Haupthread wartet auf Ready-Signal
void awaitReady()
{
    boost::unique_lock<boost::mutex> lock(mut);
    condReady.wait(lock);
}
Und hier die finale Version:

Code:
boost::condition_variable condStart, condReady, condSync;
boost::mutex mut;
int readyCounter = 0;
int waitingCounter = 0;

// Senden/Empfangen des Start-Signals
void synchronizeStart()
{
    boost::unique_lock<boost::mutex> lock(mut);
    waitingCounter++;
    if (waitingCounter < NUM_THREADS + 1)
    {
        // auf die übrigen Threads (Worker und Haupthread) warten
        condStart.wait(lock);		
    }
    else
    {
        // alle Threads warten → Start-Signal senden
        waitingCounter = 0;
        condStart.notify_all();	
    }
}

// Senden/Empfangen des Ready-Signals
void synchronizeReady()
{
    boost::unique_lock<boost::mutex> lock(mut);
    readyCounter++;
    if (readyCounter < NUM_THREADS + 1)
    {
        // auf die übrigen Threads (Worker und Haupthread) warten
        condReady.wait(lock);		
    }
    else
    {
        // alle Threads warten → Ready-Signal senden
        readyCounter = 0;
        condReady.notify_all();	
    }
}

// Haupthread sendet Start-Signal
void notifyStart()
{
    synchronizeStart();
}

// Worker-Threads warten auf Start-Signal
void awaitStart()
{
    synchronizeStart();
}

// Synchronisation zwischen den Worker-Threads
void synchronize()
{
    boost::unique_lock<boost::mutex> lock(mut);
    waitingCounter++;
    if (waitingCounter < NUM_THREADS)
    {
        condSync.wait(lock);    // auf die übrigen Worker-Threads warten
    }
    else
    {
        waitingCounter = 0;
        condSync.notify_all();   // alle Worker-Threads warten → weitermachen
    }
}

// Worker-Threads senden Ready-Signal an Haupthread
void notifyReady()
{
    synchronizeReady();
}

// Haupthread wartet auf Ready-Signal
void awaitReady()
{
    synchronizeReady();
}
 
Zuletzt bearbeitet:

Mika911

Captain
Dabei seit
Juni 2007
Beiträge
3.328
Die Thematik ist nicht ganz einfach.
Schön, dass du darüber berichtest.
Ich hab auch mal ein altes Programm von mir auf Mehrkernbetriebt umgeschrieben und dabei auch nur ~40-50% Mehrleistung von einem auf zwei Kerne erreicht. Was auch zum einen daran lag, dass ein Thread für die grafische Ausgabe der Ergebnisse zustädig war.
Mit zunehmender Laufzeit näherte ich mich der +50% wobei sehr geringe Laufzeiten sogar negative Effekte hatten.
Bei dem Programm handelte es sich um Primzahlenberechnung unter Java.
 
1

1668mib

Gast
Die Tücken der deutschen Sprache ...
Ich muss mal kurz klugscheissen :-)
"parallele Programmierung" ist falsch. Das würde heißen, es wird parallel programmiert - aber das könnte auch eine Single-Threaded-Anwendung sein. Es ist nicht die Entwicklung von Anwendungen mit parallel arbeitenden Threads.
"agile Programmierung" heißt ja auch nicht, dass die Anwendung agil ist...

Edit: Mir ist schon klar, dass es den Ausdruck gibt: http://de.wikipedia.org/wiki/Parallele_Programmierung
Gut finden muss ich ihn dennoch nicht ;-)
Da lobe ich mir das Englische mal...

Edit: und natürlich kann man auch anfangen, das selbe über "prozedurale Programmierung", "objektorientierte Programmierung", "funktionale Programmierung" zu sagen ;-)
 
Zuletzt bearbeitet:

fuyuhasugu

Commander
Dabei seit
Dez. 2012
Beiträge
2.396
Mi Kanonen auf Spatzen. Und auch wenn es schön anzusehen ist, sind Semaphore und Pipes effizienter und sicherer.
 

ice-breaker

Commodore
Dabei seit
Nov. 2008
Beiträge
4.133
Das Multithreading komplex ist, ist eine bekannte Wahrheit. Du hast es dir aber in deinem Fall mit der manuellen Steuerung von Threads auch wirklich schwer gemacht. Eine Work-Queue im Master-Prozess von dem sich jeder der Worker-Prozesse Arbeit abholen würde, hätte deinen Implementierungsaufwand deutlich gesenkt. Man sollte möglichst gar nicht direkt mit Threads arbeiten, sondern eine Abstraktionsebene höher wie z.B. mit Work-Queues, denn da wurde dann schon viel für dich implementiert und deine Arbeit ist nachher trivial - gerade für das Programmbeispiel:
Die grünen Phasen sind die Work-Queue-Aufgaben, die sich die Worker abholen sollen. Und die orange Phase ist einfach eine Synchronisierung auf die Workqueue und dessen Änderung, an der Menge der Aufgaben. Ist diese 0 werden neue Aufgaben eingestellt. Oder es wird einfach gleich alles eingestellt und man wartet bis es fertig wird.
 

kelox

Ensign
Dabei seit
Juli 2009
Beiträge
234
Ich bin mir nicht sicher, aber es klingt so, als ob du eine Datenmenge hast, die nach einem bestimmten Muster bearbeitet werden soll, wobei das Zwischenergebnis fortlaufend graphisch dargestellt werden soll, richtig? Falls ja würde ich eine andere Architektur wählen. Je nachdem ob es Abhängigkeiten zwischen den Daten gibt, gibt es da verschiedene Ansätze. Man könnte Da ein Publish/Subscriber Model wählen - hier könnte sich das Disruptor Pattern eignen (diese ist allerdings auch nen bisschen komplizierter).
 

Sculletto

Ensign
Ersteller dieses Themas
Dabei seit
Aug. 2008
Beiträge
233
Mi Kanonen auf Spatzen. Und auch wenn es schön anzusehen ist, sind Semaphore und Pipes effizienter und sicherer.
wenn man nach

http://de.wikipedia.org/wiki/Semaphor_(Informatik)

und

https://de.wikipedia.org/wiki/Pipe_(Informatik)

geht, sind beide Konstrukte für meine Zwecke ungeeignet.

Ein Semaphor ist demnach so etwas wie ein Mutex: er sorgt dafür, dass mehrere Threads, die auf dieselbe Ressource zugreifen wollen, dies zeitlich nacheinander tun, anders gesagt: er serialisiert den Zugriff auf die Ressource. Hier aber geht es nicht um einen serialisierten Zugriff auf eine Ressource, sondern darum, dass ein Thread erst dann eine Operation ausführen darf, wenn alle anderen Threads mit der vorherigen Operation fertig sind. Zur Verdeutlichung ein Codebeispiel für den Aufruf der Funktion synchronize:
Code:
// Operation 1 ausführen
synchronize();
// Operation 2 ausführen
Zuerst führen alle Threads die Operation 1 aus, und dann, wenn alle Threads mit Operation 1 fertig sind, führen alle Operation 2 aus. Kein Thread fängt mit Operation 2 an, bevor alle anderen mit Operation 1 fertig sind. Das entsprechende Entwurfsmuster nennt sich Monitor:

http://de.wikipedia.org/wiki/Monitor_(Informatik)

In der boost-Lib ist dieses als condition_variable realisiert. In meinen Code findest du zwar auch boost::mutex und boost::unique_lock, die aber dienen nur dazu, den Zugriff auf die Thread-Zähler zu schützen, und werden überdies von condition_variable::wait() benötigt.

Eine Pipe dient zur Kommunikation zwischen zwei Threads. Hier aber haben wir nicht zwei Threads, sondern mehrere. Selbst in der einfachsten Lösung mit 2 Worker-Threads sind es mit dem Hauptthread zusammen schon drei.

Überdies glaube ich dir nicht, dass Semphore und Pipes nicht ein mindestens genauso großes Kanonen-Kaliber wären wie Monitore. Und inwiefern sollen die "sicherer" sein?
 

antred

Lt. Commander
Dabei seit
Juni 2010
Beiträge
1.288
Ich wollte euch mal von meinen Erfahrungen mit paralleler Programmierung [...]
Mir fällt an deiner ursprünglichen Lösung was kritisches auf. Schauen wir uns mal deine awaitStart()-Funktion im Urzustand an.

Code:
// Worker-Threads warten auf Start-Signal
void awaitStart()
{
	boost::unique_lock<boost::mutex> lock(mut);
	condStart.wait(lock);
}
Du gehtst hier davon aus, daß wenn boost::condition_variable::wait() zurückkehrt, das Ereignis, auf das du warten wolltest, auch wirklich in 100% der Fälle eingetreten ist. Das ist mit Nichten so! Stichwort "spurious wakeups". Der wait()-Aufruf kann völlig spontan zurückkehren, ohne daß das gewünschte Ereignis tatsächlich ausgelöst worden ist. Aus der Doku von boost::thread für die boost::condition_variable::wait()-Methode:

LINK ZUR DOKU: http://www.boost.org/doc/libs/1_54_0/doc/html/thread/synchronization.html#thread.synchronization.condvar_ref
Atomically call lock.unlock() and blocks the current thread. The thread will unblock when notified by a call to this->notify_one() or this->notify_all(), or spuriously. When the thread is unblocked (for whatever reason), the lock is reacquired by invoking lock.lock() before the call to wait returns. The lock is also reacquired by invoking lock.lock() if the function exits with an exception.
Aus diesem Grund mußt du eigentlich noch irgend ein Nutzdatum an deine condition_variable knüpfen. Beispiel:



Code:
boost::condition_variable condStart;
bool ereignisEingetreten = false;
boost::mutex mut;

// Worker-Threads warten auf Start-Signal
void awaitStart()
{
	boost::unique_lock<boost::mutex> lock(mut);
	
	while ( ! ereignisEingetreten )
	{
		condStart.wait(lock);
	}
}
Und natürlich auf der anderen Seite:

Code:
// Haupthread sendet Start-Signal
void notifyStart()
{
	{
		const boost::unique_lock<boost::mutex> lock(mut);
		ereignisEingetreten = true;
	}

	condStart.notify_all();
}
Ergänzung ()

Mi Kanonen auf Spatzen. Und auch wenn es schön anzusehen ist, sind Semaphore und Pipes effizienter und sicherer.
Schmarn. boost::thread ist ein sehr geeignetes Mittel für solche Zwecke. Garantiert besser als irgend welches plattformabhängiges Gefrickele mit pthread oder WIN32 APIs und obendrein auch weniger fehleranfällig, da boost::thread auf gewisse Konstrukte setzt, die falsche Verwendung erschweren (wenn auch nicht unmöglich machen).
 

Sculletto

Ensign
Ersteller dieses Themas
Dabei seit
Aug. 2008
Beiträge
233
Ich habe mein Diagramm nochmal etwas überarbeitet, um noch etwas deutlicher zu machen, um was es mir geht. Die grünen Abschnitte haben jetzt leicht unterschiedliche Grüntöne, um zu betonen, dass sie nicht austauschbar sind, sondern strikt in der richtigen Reihenfolge ausgeführt werden müssen. Daneben zusätzlich noch, wie es in der Singlethreaded-Lösung aussehen würde.

@antred: ah, danke für den Hinweis, der betrifft ja auch meine finale Lösung :)
 

Anhänge

fuyuhasugu

Commander
Dabei seit
Dez. 2012
Beiträge
2.396
Semaphor ... serialisiert den Zugriff auf die Ressource. Hier aber geht es ... darum, dass ein Thread erst dann eine Operation ausführen darf, wenn alle anderen Threads mit der vorherigen Operation fertig sind.
Bedingung A folgt auf Bedingung B ergo Abfolge seriell und nicht parallel

Eine Pipe dient zur Kommunikation zwischen zwei Threads. Hier aber haben wir nicht zwei Threads, sondern mehrere. Selbst in der einfachsten Lösung mit 2 Worker-Threads sind es mit dem Hauptthread zusammen schon drei.
Als erstes kannst Du sogar Zugriffe auf Pipes regeln, brauuchtest dann halt nur eine Verwaltungsschicht dazwischen, was Dein Problem nur verschieben wuerde. Aber niemand hindert Dich mehrere Pipes aufzumachen, von einer Verwaltungseinheit.

Semphore und Pipes ... inwiefern sollen die "sicherer" sein?
Solch Tiimingsprobleme habe ich damit noch nicht mal in den 90ern gehabt.
 

antred

Lt. Commander
Dabei seit
Juni 2010
Beiträge
1.288
Solche Timingprobleme hätte er meines Erachtens auch hier nicht gehabt, hätte er von Anfang an den zuvor genannten spurious wakeups Rechnung getragen.

Ich habe boost::thread schon haufenweise in diversen mehr oder weniger parallelisierten Programmen verwendet und habe damit eigentlich keinerlei Probleme gehabt. Multithreading ist sicherlich kein triviales Thema, und es bietet einem haufenweise Möglichkeiten, sich selbst in den Fuß zu schießen, aber die gängigen Thread-APIs (und auch boost::thread) sind, glaube ich, mittlerweile ziemlich ausgereift und verhalten sich sehr stabil und zuverlässig. Solch scheinbar indeterministisches Verhalten zeigen sie nur dann, wenn sie falsch benutzt werden.
 
Zuletzt bearbeitet:

Sculletto

Ensign
Ersteller dieses Themas
Dabei seit
Aug. 2008
Beiträge
233
Bedingung A folgt auf Bedingung B ergo Abfolge seriell und nicht parallel
aber seriell innerhalb des jeweiligen Threads, nicht seriell in dem Sinne, dass erst der eine Thread eine Ressource benutzt und dann der andere. Die im Diagramm im selben Grünton gehaltenen Abschnitte werden parallel ausgeführt.

Um die im Wiki-Artikel zum Semaphor verwendete Analogie mit den Stellsignalen im Schienenverkehr zu bedienen: ein Semaphor ist für den Fall gedacht, dass man N Züge hat, aber nur ein Gleis, und die Züge daher nacheinander über das Gleis fahren müssen, um nicht zu kollidieren. In meinem Fall aber sind es N Züge und N Gleise, aber jedes Gleis ist in M Abschnitte unterteilt, und jeder Zug darf auf seinem Gleis einen Abschnitt erst dann befahren, wenn alle anderen Züge auf ihren jeweiligen Gleisen den vorherigen Abschnitt hinter sich gebracht haben.

Oder nimm als näher am Computer gehaltene Analogie zwei Schnittstellen, von denen die eine seriell ist, die andere parallel, und die aber beide mit der gleichen Taktfrequenz betrieben werden. Stell dir vor, 3 Datenpakete zu je 8 Bit sollen übertragen werden. Die serielle Schnittstelle überträgt nacheinander die 8 Bits des ersten Paketes, dann die des zweiten und schließlich die des dritten. Die parallele Schnittstelle kann 8 Bits parallel übertragen, also können die 8 Bits jedes Paketes gleichzeitig übermittelt werden. Jedoch müssen die 8 Leitungen synchronisiert werden, damit beim Empfänger die 8 Bits des ersten Pakets zugleich ankommen und nicht etwa die ersten 3 Bits des ersten Pakets zeitgleich mit dem vierten bis siebten Bit des zweiten Pakets und dem achten Bit des dritten Pakets.

Ein Semaphor wäre da allenfalls für die serielle Schnittstelle brauchbar, um sicherzustellen, dass mit der Übertragung des zweiten Bits des ersten Pakets erst dann begonnen wird, wenn das erste Bit gesendet ist. Für die Synchronisation der parallelen Schnittstelle ist ein Semaphor nutzlos, dafür braucht man einen Monitor.

Als erstes kannst Du sogar Zugriffe auf Pipes regeln, brauuchtest dann halt nur eine Verwaltungsschicht dazwischen, was Dein Problem nur verschieben wuerde. Aber niemand hindert Dich mehrere Pipes aufzumachen, von einer Verwaltungseinheit.
da alle Threads miteinander und mit dem Hauptthread kommunizieren können müssen, wären das O(N^2) Pipes. Das wäre doch erst recht mit Kanonen auf Spatzen geschossen.

Solch Tiimingsprobleme habe ich damit noch nicht mal in den 90ern gehabt.
hast du denn überhaupt vor einer vergleichbaren Problemstellung gestanden? Ich sehe jedenfalls nicht, in welcher Weise Semaphore oder Pipes bei den von mir beschriebenen Timingproblemen in irgendeiner Weise von Nutzen sein könnten.

Ein Semaphor hat generell keinen Nutzen, da für einen ganz anderen Anwendungsfall konzipiert. Außer halt in der Weise, wie ich ihn in Form von boost::mutex und boost::unique_lock bereits verwende.

Pipes wären letztlich nichts anderes als der mittels boost::condition_variable realisierte Monitor, nur halt aufwendiger, da O(N^2) davon benötigt würden. Würde der Hauptthread über Pipes das Start-Signal an die Worker-Threads senden, bestünde gegenüber meiner ersten Lösung unverändert das Problem, dass es passieren könnte, dass einer der Worker-Threads nicht bereit ist, das über seine Pipe hereinkommende Signal zu empfangen. Wenn man sich die Threads als Elemente eines Netzwerks denkt, wären Pipes eine vollvermaschte Netztopologie, ein Monitor (in boost eine condition_variable) dagegen ein Bus:

https://de.wikipedia.org/wiki/Netztopologie

Ein Bus reicht für meine Zwecke aber völlig aus, eine Vollvermaschung bringt keinen Vorteil.
 

F_GXdx

Captain
Dabei seit
März 2006
Beiträge
4.028
Nicht zuletzt deswegen rücken Sprachen wie Erlang aktuell in den Fokus. Auf Dauer müssen wir umdenken.
 

Sculletto

Ensign
Ersteller dieses Themas
Dabei seit
Aug. 2008
Beiträge
233
Solche Timingprobleme hätte er meines Erachtens auch hier nicht gehabt, hätte er von Anfang an den zuvor genannten spurious wakeups Rechnung getragen.
die Timingprobleme, die ich in der ersten Lösung hatte, lassen sich auf die fehlerhaften Annahmen betreffend des Zeitpunktes, wann das Start- und Ready-Signal gesendet werden dürfe, zurückführen. Auffallend ist ja auch, dass die Freezes immer beim Senden des Start- oder Ready-Signals auftraten, aber nie bei der Synchronisation zwischen den Worker-Threads (synchronize() in meinen Code), obwohl die ja viel öfter durchlaufen wurde. Ich habe jetzt mal einen Langzeit-Test laufen lassen und auf das Auftreten von spurious wakeups geprüft. Nach über 100 Millionen Aufrufen von condition_variable::wait() hat es noch kein einziges spurious wakeup gegeben. Der Code sieht so aus:

Code:
bool waitFlag[NUM_THREADS]; // zur Prüfung auf spurious wakeups für jeden Thread ein Flag
// ...
// Synchronisation zwischen den Worker-Threads
void synchronize(int threadIndex)
{
    boost::unique_lock<boost::mutex> lock(mut);
    waitingCounter++;
    if (waitingCounter < NUM_THREADS)
    {
        while (waitFlag[threadIndex])
        {
            condSync.wait(lock); // auf die übrigen Worker-Threads warten
            if (waitFlag[threadIndex])   // Warte-Bedingung noch erfüllt -> es muss ein spurious wakeup vorliegen
            {
                std::cerr << "warning, spurious wakeup in thread " << threadIndex << std::endl; 
            }
        }
    }
    else
    {
        waitingCounter = 0;
        // Bedingungen für alle Threads auf false setzen, zur spurious wakeup-Erkennung
        for (int i = 0; i < NUM_THREADS; i++)  
            waitFlag[i] = false;
        condSync.notify_all(); // alle Worker-Threads warten → weitermachen
    }
}

Kann es sein, dass die Gefahr dafür plattformabhängig ist? Ich arbeite unter Windows, da wird wait() über die Win32-Funktion WaitForMultipleObjects() realisiert (siehe interruptible_wait() in \libs\thread\src\win32\thread.cpp im boost-Verzeichnis), das ist nach meiner Erfahrunge eigentlich sehr zuverlässig. Sorgen hat mir eher bereitet, dass unter Win32 kein echter Monitor realisierbar ist: das Verlassen des Locks und der Aufruf von WaitForMultipleObjects() ist nicht atomar, dazwischen kann theoretisch noch was passieren. pthreads unterstützt Monitore nativ mit pthread_cond_wait(), da würde ich mich wohler fühlen.
 

antred

Lt. Commander
Dabei seit
Juni 2010
Beiträge
1.288
die Timingprobleme, die ich in der ersten Lösung hatte, lassen sich auf die fehlerhaften Annahmen betreffend des Zeitpunktes, wann das Start- und Ready-Signal gesendet werden dürfe, zurückführen. Auffallend ist ja auch, dass die Freezes immer beim Senden des Start- oder Ready-Signals auftraten, aber nie bei der Synchronisation zwischen den Worker-Threads (synchronize() in meinen Code), obwohl die ja viel öfter durchlaufen wurde. Ich habe jetzt mal einen Langzeit-Test laufen lassen und auf das Auftreten von spurious wakeups geprüft. Nach über 100 Millionen Aufrufen von condition_variable::wait() hat es noch kein einziges spurious wakeup gegeben. Der Code sieht so aus:

[...]
Ok, da ich deinen Code sicher nicht so gut verstehe wie du, glaube ich dir das einfach mal. Dann entschuldige ich mich für meine vorschnelle Aussage.

Kann es sein, dass die Gefahr dafür plattformabhängig ist?
Möglich, aber ich selbst bin (auch unter Windows) schon einmal Opfer eines solchen spurious wakeups geworden (das war dann für mich der Anlaß, mich zu diesem Thema aufzuschlauen).

Ich arbeite unter Windows, da wird wait() über die Win32-Funktion WaitForMultipleObjects() realisiert (siehe interruptible_wait() in \libs\thread\src\win32\thread.cpp im boost-Verzeichnis), das ist nach meiner Erfahrunge eigentlich sehr zuverlässig. Sorgen hat mir eher bereitet, dass unter Win32 kein echter Monitor realisierbar ist: das Verlassen des Locks und der Aufruf von WaitForMultipleObjects() ist nicht atomar, dazwischen kann theoretisch noch was passieren. pthreads unterstützt Monitore nativ mit pthread_cond_wait(), da würde ich mich wohler fühlen.
Also das kann ich mir jetzt nicht vorstellen. Das würde heißen, condition_variable wäre unter Windows nur eine solala-Implementierung und eigentlich für echte Synchronisierung schlichtweg nicht zu gebrauchen. Bist du auch sicher, daß du die boost-Sourcen richtig gelesen hast?
Wenn ich der Implementierung von condition_variable::wait() folge, führt mich das z.B. über folgende Schritte:

void condition_variable::wait(unique_lock<mutex>& m) [definiert in boost\1_53_0\boost\thread\win32\condition_variable.hpp, Zeile 316]

bool basic_condition_variable::do_wait(lock_type& lock,timeout abs_time) [definiert in boost\1_53_0\boost\thread\win32\condition_variable.hpp, Zeile 217]

Von da an komme ich dann noch in entry_ptr basic_condition_variable::get_wait_entry() [definiert in boost\1_53_0\boost\thread\win32\condition_variable.hpp, Zeile 167], und dann wird's mir ehrlich gesagt schon zu kompliziert. Aber ich persönlich bin zu diesem Zeitpunkt noch nicht über interruptible_wait() gestolpert.

EDIT: Ok, hab's noch mal ein bißchen weiter verfolgt und komme dann auch über detail::basic_cv_list_entry::wait() auf den von dir genannten this_thread::interruptible_wait().
 
Zuletzt bearbeitet:

Sculletto

Ensign
Ersteller dieses Themas
Dabei seit
Aug. 2008
Beiträge
233
Also das kann ich mir jetzt nicht vorstellen. Das würde heißen, condition_variable wäre unter Windows nur eine solala-Implementierung und eigentlich für echte Synchronisierung schlichtweg nicht zu gebrauchen. Bist du auch sicher, daß du die boost-Sourcen richtig gelesen hast?
Wenn ich der Implementierung von condition_variable::wait() folge, führt mich das z.B. über folgende Schritte:

void condition_variable::wait(unique_lock<mutex>& m) [definiert in boost\1_53_0\boost\thread\win32\condition_variable.hpp, Zeile 316]

bool basic_condition_variable::do_wait(lock_type& lock,timeout abs_time) [definiert in boost\1_53_0\boost\thread\win32\condition_variable.hpp, Zeile 217]
In boost 1.49.0 sieht die Implementierung von do_wait() so aus:
Code:
bool do_wait(lock_type& lock,timeout wait_until)
{
    relocker<lock_type> locker(lock);

    entry_manager entry(get_wait_entry());

    locker.unlock();

    bool woken=false;
    while(!woken)
    {
        if(!entry->wait(wait_until))
        {
             return false;
        }

        woken=entry->woken();
    }
    return woken;
}
Wesentlich ist hier das locker.unlock() vor dem entry->wait(wait_until), da wird der Lock tatsächlich gelöst. Vielleicht haben die das bis boost 1.53.0 ja geändert?
 

antred

Lt. Commander
Dabei seit
Juni 2010
Beiträge
1.288
Nee, ist in boost 1.53.0 noch genau so. Aber wo siehst du da eigentlich ein Problem? Klar, das lock wird freigegeben, und erst dann legt sich der Thread schlafen. Kann schon sein, daß selbst bevor dieser Thread dazu gekommen ist, sich schlafen zu legen, ein anderer Thread den eben frei gewordenen Mutex lockt und ein von ihm geschütztes Datum modifiziert. Na und? Mir fällt im Moment kein Szenario ein, in dem das ein Problem verursachen würde, so fern der Thread im Anschluß ein notify_one / notify_all auslöst.
 

Sculletto

Ensign
Ersteller dieses Themas
Dabei seit
Aug. 2008
Beiträge
233
Also es hängt immer nur bei der Synchronisation mit dem Hauptthread?
nein, es hängt nicht, es hing. Ich wollte ja nicht nach einer Lösung des Problems fragen, sondern hatte diese bereits gefunden, und wollte nur von meinen Erfahrungen berichten :)

Kann es sein, dass der Hauptthread versucht, sich mit den Workern zu synchronisieren, wenn die es eigentlich nur untereinander versuchen?
(Du verwendest die Variable waitingCounter zwei Mal.)
In der ersten Version, in der das beschriebene Problem auftrat, wurde waitingCounter nur einmal verwendet, in synchronize(), das zur Synchronisation zwischen den Worker-Threads dient. In der zweiten Version hast du recht, da wird es sowohl in synchronize() als auch in synchronizeStart() benutzt, da tritt aber das Problem nicht auf. Und wenn der Fall eintreten würde, dass die Worker-Threads gerade in synchronize() sind, wenn der Hauptthread in synchronizeStart() reingeht, dann wäre die zweimalige Verwendung von waitCounter die geringste Sorge, die man sich machen müsste.

Hier nochmal die Art, wie die Funktionen vom Hauptthread und den Worker-Threads aufgerufen werden. Hauptthread:
Code:
while (isRunning())
{
    notifyStart(); // Start-Signal an die Worker-Threads absetzen (dunkel orange im Diagramm)
    awaitReady();  // auf Ready-Signal von den Worker-Threads warten (lila im Diagramm)
    
    // grafische Ausgabe der Ergebnisse (türkis im Diagramm)
    // ...
}
Worker-Threads:
Code:
while (isRunning())
{
    awaitStart();    // auf Start-Signal vom Hauptthread warten (dunkel orange im Diagramm)
    for (int i = 0; i < ITERATIONS_PER_LOOP; i++)
    {
         // Berechnung ausführen (grüne Abschnitte im Diagramm)
         // ...

         // mit den anderen Worker-Thread synchronisieren (hell orange im Diagramm)
         synchronize();
    }
    notifyReady();  // Ready-Signal an Hauptthread senden (lila im Diagramm)
}
 

fuyuhasugu

Commander
Dabei seit
Dez. 2012
Beiträge
2.396
Um die im Wiki-Artikel zum Semaphor verwendete Analogie mit den Stellsignalen im Schienenverkehr zu bedienen: ein Semaphor ist für den Fall gedacht, dass man N Züge hat, aber nur ein Gleis, und die Züge daher nacheinander über das Gleis fahren müssen, um nicht zu kollidieren. In meinem Fall aber sind es N Züge und N Gleise, aber jedes Gleis ist in M Abschnitte unterteilt, und jeder Zug darf auf seinem Gleis einen Abschnitt erst dann befahren, wenn alle anderen Züge auf ihren jeweiligen Gleisen den vorherigen Abschnitt hinter sich gebracht haben.
Ob Du die Unterteilung nach Gleisen oder nach Gleisabschnitten hast, ist letztlich egal.

da alle Threads miteinander und mit dem Hauptthread kommunizieren können müssen, wären das O(N^2) Pipes.
Wenn Du sie alle miteinander kommunizieren lassen willst, werden es eben entsprechend mehr. Aber wozu?

Ein Semaphor hat generell keinen Nutzen, da für einen ganz anderen Anwendungsfall konzipiert. Außer halt in der Weise, wie ich ihn in Form von boost::mutex und boost::unique_lock bereits verwende.
Eben, es ist doch egal, wofür etwas ursprünglich kozipiert worden sein mag, wichtig ist doch, was, man damit alles machen kann. Das die Art der Synchronisation letztendlich Deiner jetzigen Variante ähneln würde, liegt in der Natur der Sache.

bestünde gegenüber meiner ersten Lösung unverändert das Problem, dass es passieren könnte, dass einer der Worker-Threads nicht bereit ist, das über seine Pipe hereinkommende Signal zu empfangen.
Da liegt dann wohl eher das Problem. Wobei ich netyt erst überlegen müsste, wie man es "versehentlich" so programmiert, dass ein Thread trotz Schnittstelle zeitweise keine Signale empfängt, bzw. diese sogar im Nirwana verschwinden.

[QUOTE Wenn man sich die Threads als Elemente eines Netzwerks denkt, wären Pipes eine vollvermaschte Netztopologie. Ein Bus reicht für meine Zwecke aber völlig aus, eine Vollvermaschung bringt keinen Vorteil.[/QUOTE]
Meine Rede. Wieso Du immer daran denkst alle miteinander kommuniyieren lassen zu müssen, nur weil die Art der Kommunikation sich ändert, ist unklar. Vielleicht weil es bei dieser Art sonst i.a. so umgesetzt wird oder weil es in irgendeiner Spezifikation bzw. dem typischhen Programmierbeispiel so steht?
 
Top