Mutex Implementierung

hustbaer

camper schrieb:

class mutex {
    std::atomic<bool> locked = false;
public:
    void lock()
    {
        bool wanted;
        do
            wanted = false;
        while ( !locked.compare_exchange_strong( wanted, true ) ); // busy wait
    }
    void unlock() { locked = false; }
};
löst erst einmal obiges Problem. Ein funktionierender Mutex ist das allerdings noch nicht, da von diesem erwartet wird, dass man mit diesem auch Zugriffe auf nicht-atomics synchronisieren kann. Es fehlen also noch Barrieren.

Huch?

http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

cppreference schrieb:

bool compare_exchange_strong( T& expected, T desired, std::memory_order order = std::memory_order_seq_cst );

Und operator = verwendet IIRC auch std::memory_order_seq_cst . Ich sehe also kein Problem bzw. keinen Grund dafür selbst mit Barriers rumzumachen.

camper

hustbaer schrieb:

camper schrieb:

Ein funktionierender Mutex ist das allerdings noch nicht, da von diesem erwartet wird, dass man mit diesem auch Zugriffe auf nicht-atomics synchronisieren kann. Es fehlen also noch Barrieren.

Huch?

http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange

cppreference schrieb:
bool compare_exchange_strong( T& expected, T desired, std::memory_order order = std::memory_order_seq_cst );
Und operator = verwendet IIRC auch std::memory_order_seq_cst . Ich sehe also kein Problem bzw. keinen Grund dafür selbst mit Barriers rumzumachen.

ähm, ja richtig. Das passiert, wenn man sich länger nicht mit solchen Sachen beschäftigt. memory_order_acq_rel für CAS und memory_order_release für store würde reichen (unlock darf nat. nur von dem Thread aufgerufen werden, das den Lock hat).
Am besten überlässt man solchen low-level-Kram fertigen Bibliotheken.

hustbaer

Ich find's auch gut dass die Defaults bei atomic "safe" sind. Was anderes zu verwenden wäre mMn. ein Fehler gewesen, eben weil man fast immer mit dem Atomic synchronisieren will, und dann braucht man zumindest acquire/release.

Kellerautomat

In Schleifen immer compare_exchange_weak verwenden.

camper

Kellerautomat schrieb:

In Schleifen immer compare_exchange_weak verwenden.

Sehe ich an dieser Stelle nicht als wesentlich, da der Tread in jedem Fall nur Fortschritte machen kann, wenn das CAS erfolgreich ist. Fraglich ist eher, ob man überhaupt ein busy-wait haben will.
Ist was anderes, wenn lock-freie Algorithmen implementiert werden.

hustbaer

camper schrieb:

Fraglich ist eher, ob man überhaupt ein busy-wait haben will.

Will man kaum jemals.

Für die meisten Anwendungen ist es IMO optimal erstmal ein paar zig bis paar hundert mal zu spinnen (mit rep nop dazwischen bzw. was die jeweilige CPU halt braucht um zu verstehen dass sie anderen Threads die sich den selben Core teilen mal kurz Vorrang geben kann), und danach den Thread auf ein passendes Dispatcher-Objekt warten zu lassen (EVENT, Condition-Variable, Semaphor - was der Dispatcher halt anbietet).

Bzw. einfacher gesagt: das was ne CRITICAL_SECTION macht

hustbaer

Achja...

camper schrieb:

Kellerautomat schrieb:

In Schleifen immer compare_exchange_weak verwenden.

Sehe ich an dieser Stelle nicht als wesentlich, da der Tread in jedem Fall nur Fortschritte machen kann, wenn das CAS erfolgreich ist.

compare_exchange_weak ist (vermute ich mal) oft so implementiert dass erstmal ein load(relaxed) gemacht wird, und wenn das nicht dem erwarteten Wert entspricht dann wird gar nicht erst mit CAS draufgekloppt.
Und das ist besser.

Ich vermute deswegen, weil mehrere Threads die gleichzeitig um die selbe Mutex kämpfen dann alle load(relaxed) machen, was dazu führt dass die beteiligten Cores die Cache-Row mit der Spin-Variable alle "shared" im Cache haben.
So lange die Mutex nicht freigegeben wird, wird die Cache-Row also aus keinem der Caches evakuiert.
Der shared L3 Cache/Front-Side-Bus bzw. wo auch immer dann alles zusammenläuft wird dabei viel weniger gestresst als wenn man dauernd mit CAS (von unterschidlichen Cores aus) auf die Cache-Row draufhaut.
Und das ist gut für Cores die mit der Mutex gar nix zu tun haben, aber auch gern hin und wieder nen Speicherzugriff machen würden.

Heisst: ich denke nicht dass es egal ist, sondern im Gegenteil dass das gerade der Paradefall für wo man compare_exchange_weak statt compare_exchange_strong verwenden sollte.

Zumindest macht man genau das wenn man es in Assembler implementiert. Erstmal nen Loop der mit nem normalen Load (atomic, relaxed) so lange spult bis man den erwarteten Wert gelesen hat, und dann mit CAS draufhauen. Wenns nicht geklappt hat wieder mit normalem Load loopen usw.

camper

hustbaer schrieb:

compare_exchange_weak ist (vermute ich mal) oft so implementiert dass erstmal ein load(relaxed) gemacht wird, und wenn das nicht dem erwarteten Wert entspricht dann wird gar nicht erst mit CAS draufgekloppt.

Das würde nicht funktionieren, weil der relaxed load eben nicht sicher erkennen würde, ob der lock frei ist (fehlende Synchronisation mit unlock). Die weak-Variante hat ihren Grund in Rechnerarchitekturen, die CAS durch LL/SC (load-link/store-conditional) implementieren.

hustbaer

Also ich hab' mal die Implementierung von MSVC gecheckt, und die verwendet seltsamerweise wirklich sofort nen InterlockedCompareExchange .

Funktionieren tut das aber super, wieso sollte es auch nicht? Dass es theoretisch dazu kommen könnte dass der lockende Thread den von unlock gesetzten Wert nie liest ist uninteressant, in der Praxis kommt das nicht vor. IIRC schreibt sogar der Standard dass Änderungen auch ohne Synchronisierung "bald mal" für alle anderen CPUs/Cores sichtbar werden sollten. Und danach kommt dann ja eh der normale CAS, der dann die entsprechenden Memory-Order-Garantien umsetzt.

camper

hustbaer schrieb:

Also ich hab' mal die Implementierung von MSVC gecheckt, und die verwendet seltsamerweise wirklich sofort nen InterlockedCompareExchange .

Auf x86 ist das sowieso uninteressant. Da bei dieser Architektur Schreib-/und Lesevorgänge so gut wie nie sichtbar umgeordnet werden, existieren "relaxed" loads dort praktisch nicht.

hustbaer schrieb:

Dass es theoretisch dazu kommen könnte dass der lockende Thread den von unlock gesetzten Wert nie liest ist uninteressant, in der Praxis kommt das nicht vor. IIRC schreibt sogar der Standard dass Änderungen auch ohne Synchronisierung "bald mal" für alle anderen CPUs/Cores sichtbar werden sollten.

Und dies irgendwann mal hälst du für ausreichend? Das sieht dann im nächsten Benchmark sicher nicht gut aus.

hustbaer schrieb:

Und danach kommt dann ja eh der normale CAS, der dann die entsprechenden Memory-Order-Garantien umsetzt.

Wenn er kommt, was ja nicht der Fall ist, falls dein relaxed load einen besetzten Mutex anzeigt, obwohl er frei ist.

hustbaer

Gibt es echt Plattformen auf denen das länger dauert?
Das wäre dann natürlich doof.

camper schrieb:

hustbaer schrieb:

Also ich hab' mal die Implementierung von MSVC gecheckt, und die verwendet seltsamerweise wirklich sofort nen InterlockedCompareExchange .

Auf x86 ist das sowieso uninteressant. Da bei dieser Architektur Schreib-/und Lesevorgänge so gut wie nie sichtbar umgeordnet werden, existieren "relaxed" loads dort praktisch nicht.

Gerade auf x86 wäre es deswegen gut zum Locken einer Mutex erstmal einen relaxed Load zu machen.