spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Der größte Unterschied zwischen Semaphore und einem Lock ist, dass der Zugriff/die Reservierung und die Freigabe bei einem Semaphore nicht vom gleichen owner bzw. Thread passieren muss. Das macht sie für asynchrone Vorgänge interessant.

Ein fence ist in dem Sinn eigentlich etwas anderes da dieser die Reihenfolge der Abarbeitung an der CPU vorgibt, so dass ggf. vollzogene Optimierungen nicht deine Ausführungsreihenfolge durcheinander bringen. Eine Semaphore-Implementierung bedient sich aber oft an fences die aber recht hardwareabhängig sind.

Es gibt da allgemein viele verschiedene Ansätze. Je nach Anforderung ergeben die einzelnen Ansätze dann mehr oder weniger Sinn. Geht es dir zum Beispiel darum dass nur eine Komponente auf eine Ressource zugreifen kann oder dürfen das mehrere? Guck mal allgemein nach Mutual Exclusion. Das hilft vielleicht erst mal weiter.

Na ja, in einem System, wo die Threads vom Prozessor selbst unterstützt werden, ist es ohne seine Hilfe nicht möglich einen Mutex selbst zu implementieren. Mit plain C++ schon gar nicht. Da musst Du auf CPU-Instructions zurückgreifen, die es Dir wirklich ermöglichen einen atomaren Zugriff (z.B. swap/exchange) vornehmen zu können. Ohne atomaren Zugriff, kannst Du nicht gewährleisten, dass Deine Reads/Writes parallel ausgeführt nicht dazu führen, dass mehrere Threads denselben Code-Block parallel ausführen (mutual exclusion also nicht möglich). Betriebssysteme bieten für das Problem oft eine entsprechende Implementierung, die von C++ dann genutzt wird. Eben jene nutzt dann die Features der CPU, um das Ziel zu erreichen.

Seit C++11 gibt es die <atomic> Library womit du selber Mutexes/Semaphores/... basteln kannst.
Du kannst natürlich auch zB direkt std::mutex verwenden.
Sind im Prinzip nur Wrapper für die OS-Implementierung.
Also Plain-C++ ist es nicht, aber mittlerweile "OS unabhängig" möglich.

In nebenläufigem Code hast du rein prinzipiell zwei grundlegende Probleme: Wenn mehrere Threads mit dem selben Objekt arbeiten, muss sichergestellt sein, dass das Objekt sich zu jedem Zeitpunkt in einem gültigen Zustand befindet. Stell dir vor ein Thread schreibt einen neuen Wert in einen Pointer während ein anderer Thread parallel den Wert des Pointers liest. Es könnte nun passieren, dass die ersten 4 Byte des Pointers schon den neuen Wert haben, während die restlichen 4 Byte noch vom alten Wert sind und der Thread somit einen völlig ungültigen Müllpointer liest. Um solche Situationen zu vermeiden, muss jeder Zugriff (lesen und schreiben) auf nebenläufig verwendete Objekte atomar erfolgen, d.H. auf eine Art und Weise die Sicherstellt, dass jeder Thread immer nur entweder den neuen oder alten Zustand eines Objektes sieht, aber niemals irgendwas dazwischen. Dies muss sowohl seitens der Hardware als auch seitens des Compilers sichergestellt werden (entsprechende Verwendung entsprechender Maschineninstruktionen).

Das zweite Problem ist die Reihenfolge in der Zustandsänderungen sichtbar werden. Selbst wenn du schon sichergestellt hast, dass nebenläufige Zugriffe auf ein geteiltes Objekt atomar sind, gibt es im Allgemeinen keine Garantie darüber, ab wann welcher Thread welchen konkreten Zustand eines Objektes sieht (durch die Atomizität ist nur garantiert, dass jeder Thread zu jedem Zeitpunkt irgendeinen der gültigen Zustände sieht, den das Objekt irgendwann einmal hatte). Insbesondere gibt es keine Garantie darüber, in welcher Reihenfolge nichtatomare Zugriffe auf anderen Objekten relativ zu atomaren Zugriffen passieren. Auf Hardwareebene gibt es beispielsweise Dinge wie Caches und Store-Buffer, die gerade erst verhindern sollen, dass jeder Zugriff immer bis ganz runter zum langsamen RAM gehen muss bevor weitergemacht werden kann. Eine Folge davon ist aber eben, dass für eine Speicherstelle nicht auf jedem Core zu jedem Zeitpunkt der selbe Wert aufscheint (während ein Core eine Speicherstelle modfiziert hat, kann sich im Cache eines anderen Core noch ein alter Wert für diese Speicherstelle befinden; je nachdem auf welchem Core dein Thread gerade läuft, sieht er also einen anderen Wert für die selbe Speicherstelle).

Eine sinnvolle Kommunikation zwischen Threads ist aber erst möglich, wenn bestimmte Bedingungen bezüglich der Reihenfolge, in der die Modifikation der Zustände von Objekten relativ zueinander passieren, eingehalten werden. Wenn Thread A beispielsweise Daten generiert und über ein atomares Flag einem anderen Thread B signalisieren will, wann die Daten verfügbar sind, ist es wesentlich, für Thread B zu garantieren, dass er niemals den veränderten Wert des Flag sehen kann, bevor er auch die neuen Werte der Daten sehen kann. Memory Fences dienen dazu, solche Bedingungen bezüglich der Reihenfolge, in der bestimmte Modifikationen relativ zueinander sichtbar werden, auszudrücken (der "Zaun" verhindert je nachdem dass der Effekt späterer Zugriffe vor einem bestimmten Punkt bzw. der Effekt früherer Zugriffe nach einem bestimmten Punkt eintritt; er hält also Speicherzugriffe von ihrer Wanderschaft über einen bestimmten Punkt hinaus ab, hence the name).

Wie du dir sicher vorstellen kannst, ist es extrem schwer, auf Ebene von atomaren Operationen und Fences korrekten Code zu schreiben. Daher gibt es auf höherer Ebene Konzepte wie das eines kritischen Abschnittes, der durch Objekte wie Mutexe bzw. Semaphoren so abgesichert wird, dass zu jedem Zeitpunkt immer nur ein Thread bzw. eine bestimmte Anzahl an Threads den darin befindlichen Code ausführen können. Diese Objekte werden in der Regel vom Betriebssystem zur Verfügung gestellt. Versucht ein Thread einen solchen Abschnitt zu betreten während ein anderer Thread sich darin befindet, wird er vom Betriebssystem angehalten bis der erste Thread den Abschnitt verlassen hat. Das Betriebssystem wird unter der Haube atomare Operationen und Fences verwenden, um solche Threadsynchronisation auf der jeweiligen Hardware korrekt zu implementieren. Man sollte festhalten, dass (entgegen frühreren Behauptungen hier ) derartiges Verhalten im Allgemeinen nicht einfach so selbst gemacht werden kann, sondern rein prinzipiell im Betriebssystem implementiert werden muss, da man so Dinge wie Threads schlafen legen und richtig wieder aufwecken nur im Kernel machen kann (an denjenigen, der jetzt gleich mit Fibers ankommt: let's not go there)...

Das mit den 4 Byte vom Pointer sollte nicht passieren können, da auf einen 64-Bit-Prozessor die 64 Bit auf einmal geschrieben werden sollten und nicht jedes Byte einzeln. Addition ist z.B. eher geeignet, um das Problem zu beschreiben: Wenn zwei Threads gleichzeitig ++i ausführen, ist i am Ende nur um 1 erhöht worden, statt um 2, weil beide den alten Wert um 1 erhöhen.

Auch Daten verschieben ist unter Umständen nicht atomar durch Pipelining und andere wilde Späße. Also nein, theoretisch könnten Read/Write Probleme auch bei Pointern auftreten.

Zitat von »Magogan«

Das mit den 4 Byte vom Pointer sollte nicht passieren können, da auf einen 64-Bit-Prozessor die 64 Bit auf einmal geschrieben werden sollten und nicht jedes Byte einzeln.

Wo steht denn das? Die x86-Architektur ist generell ein schlechtes Beispiel wenn es um solche Dinge geht, da sie ein ungewöhnlich starkes Memory Model garantiert. Aber selbst auf x86 sind Zugriffe auf Quadwords nur in Ausnahmefällen (8-Byte-aligned oder zumindest alles in einer Cacheline) atomar. Und auf der anderen Seite gibt es 64-Bit Architekturen auf denen ein 64-Bit Wert nichtmal ganz in ein Register passt; ich darf tagtäglich mit so einer arbeiten und es ist gar nicht unwahrscheinlich, dass du in deinem Rechner so einen Chip hast (ich rede natürlich nicht von der CPU)...

Zitat von »Magogan«

Addition ist z.B. eher geeignet, um das Problem zu beschreiben: Wenn zwei Threads gleichzeitig ++i ausführen, ist i am Ende nur um 1 erhöht worden, statt um 2, weil beide den alten Wert um 1 erhöhen.

Ich habe das Beispiel durchaus bewusst gewählt, weil ich ganz grundlegend das Problem des atomaren Zugriffes illustrieren wollte, insbesondere die Tatsache, dass es nicht genügt, nur manche Zugriffe atomar zu gestalten, welche im komplexeren Beispiel mit der Addition sehr leicht untergeht (was wenn ein weiterer Thread den Wert der Variable nur beobachten aber nicht modifizieren will? Einfach normal den Wert lesen ist im Allgemeinen nicht ausreichend). Abgesehen davon ist das Additionsbeispiel so ziemlich das Standardbeispiel zur Race-Condition schlechthin und ich wollte vermeiden, dass da irgendwo Missverständnisse entstehen (atomarer Zugriff allein ist nicht hinreichend zur Vermeidung von Race-Conditions). Dein Beispiel basiert auf der Annahme, dass das Lesen und Schreiben des Wertes von i an sich atomar wäre, was eben rein prinzipiell nicht garantiert ist. Nur um zu zeigen, dass das, wovon ich hier rede, nicht nur rein theoretischer Natur ist: Ein Kollege von mir hat es sogar auf einem Standard x86 PC schon geschafft, sich einen Concurrency-Bug aufgrund eines nichtatomaren Zugriffes auf ein DWORD einzufangen. Das DWORD im konkreten Fall kam per DMA von der GPU...