Mutex Implementierung

[Mutal]

Ok, das stimmt, wenn es wirklich ganz genau im gleichen Takt geschieht, dann glauben beide Threads, dass sie gelockt haben. Und wie kann ich einen atomic_bool selbst implementieren?

[Skym0sh0]

Ich werf einfach mal sowas wie Petersons Algorithmus, test&set, test&test&set und sowas in den Raum...

[nwp3]

Mutal schrieb:

Ok, das stimmt, wenn es wirklich ganz genau im gleichen Takt geschieht, dann glauben beide Threads, dass sie gelockt haben. Und wie kann ich einen atomic_bool selbst implementieren?

Das Problem ist, dass du ein Data Race gebaut hast. Das ist UB. Die Folge ist nicht nur, dass manchmal Threads gleichzeitig lock aufrufen und es zu doofen Interleavings kommt, sondern dass das Programm nicht mehr sequentiell ausgeführt wird und du gar keine Aussagen mehr über das Verhalten machen kannst. Der Peterson Algorithmus ist in C++ einfach nur falsch. Die Lösung ist memory barriers zu benutzen, aber die sind extrem schwer korrekt hinzukriegen. Wenn du alles selbst machen willst musst du inline assembler benutzen. Außerdem musst du per Compiler intrinsics gewisse Optimierungen ausschalten. Wenn du es korrekt und fertig haben willst nimm atomic<bool> oder gleich std::mutex.

DocShoe schrieb:

Der Trick bei einem Mutex ist der, dass nur derjenige Thread, der den Mutex gelockt hat, ihn auch wieder unlocken kann. Du brauchst also auf jeden Fall eine Möglichkeit, den aufrufenden Thread zu identifizieren.

Finde ich extrem doof. Das macht so viele sinnvolle Algorithmen unmöglich bzw. man braucht Alternativen. Ein Mutex ohne diese Einschränkung ist besser.

[TyRoXx]

Mutal schrieb:

Und wie kann man das (selber) richtig machen ohne WinAPI oder so?

Gar nicht.
Die Implementierung ist etwas komplizierter als dein falsches Beispiel. boost::mutex kann man gut nachvollziehen.

[tntnet]

Mutal schrieb:

Man sagte mir, das kann so nicht funktionieren:

class mutex {
	bool locked;
public:
	mutex() : locked(false) { }
	void lock() { while(locked); locked = true; }
	bool try_lock() { if(locked) return false; return locked = true; }
	void unlock() { locked = false; }
};

Wieso? Und wie kann man das (selber) richtig machen ohne WinAPI oder so?

Das Problem ist nicht atomic bool oder Reihenfolge der Ausführung oder so was sondern liegt einfach in der lock-Methode. Dort is eine Race-condition.

Ein thread wartet erst mal in der while-Schleife, bis jemand lock auf false setzt. Und wenn das geschehen ist, setzt es den lock dann auf true. Aber was ist, wenn 2 Threads das gleiche machen. Beide stellen fest, dass ein dritter thread den lock auf false gesetzt hat und nehmen sich vor, als nächstes den lock auf true zu setzen. Und damit bekommen beide Threads den lock.

Umsetzen kannst Du das mit std::atomic_compare_exchange_strong. Such mal nach "Spinlock".

[camper]

Mutal schrieb:

Und wie kann ich einen atomic_bool selbst implementieren?

In reinem C++ gar nicht.

tntnet schrieb:

Das Problem ist nicht atomic bool

Es ist schon eines der Probleme, oder besser ein Aspekt des ganzen komplexen Problems.

Sehr vereinfacht:
Das (ok: ein) fundamentale Synchronisationsproblem ist sequentielle Konsistenz - es bedarf eines Mechanismus, der es erlaubt für zwei Operationen A und B (es um Lesen und Schreiben von Objekten, nicht um reine Wertberechnungen), die möglicherweise in verschiedenen Threads stattfinden, entscheiden zu können, welche Operation vor der anderen stattfindet, so dass (o.B.d.A. sei dass mal A) das Ergebnis von A als Operand von B auftreten kann.

Innerhalb desselben Threads garantiert C++ dies auf die übliche Weise (früher: sequence points). Zwischen Threads wird dies zunächst nur für atomics definiert. Barriers vermitteln die dadurch hergestellte Ordnung von Operation auf atomics an andere Operationen, die nicht mit atomics arbeiten; C++ garantiert, dass wenn A vor B (innerhalb eines Threads oder zwischen Threads) passiert und B vor C passiert, dass dann auch A vor C passiert.

Atomics sind also der Mechanismus, der erst eine Ausführungsreihenfolge zwischen Threads definiert.

tntnet schrieb:

Das Problem ist nicht atomic bool oder Reihenfolge der Ausführung oder so was sondern liegt einfach in der lock-Methode. Dort is eine Race-condition.

Ist fehlende Festgelegtheit der Ausführungsreihenfolge nicht genau das, was eine Race-condition ausmacht?

[camper]

class mutex {
    std::atomic<bool> locked = false;
public:
    void lock() { while(locked) /*A*/; locked = true /*B*/; }
    void unlock() { locked = false /*C*/; }
};

ist erst mal frei von race-conditions. Es macht aber nicht das was es soll. Warum? Weil als Nebendingung gelten soll, dass ein locked=true stets nur dann gesetzt werden darf, wenn zu diesem Zeitpunkt locked==false gilt. Der Code erfüllt diese Bedingung nicht, sofern wenigstens 2 Threads existieren, die lock aufrufen können (und wenn es diese nicht gibt, braucht man auch keinen Mutex). C++ garantiert dass jeder Zugriff A aus Thread 1 (A1) entweder vor oder nach einem beliebigen Zugriff A in Thread 2 (A2) passiert und natürlich (weil innerhalb des gleichen Threads) stets B1 nach A1 und B2 nach A2 passiert.
Nicht garantiert wird aber mit diesem Code, dass A2, wenn es nach A1 passiert, auch nach B1 passieren muss.
Es bedarf also eines speziellen Mechanismus, der garantiert, dass ein beliebiger anderer Zugriff auf das Objekt nur entweder vor Zugriff A oder nach Zugriff B stattfinden kann.
Das angesprochene std::atomic_compare_exchange_strong hat diese Eigenschaft, std::atomic_compare_exchange_weak hat sie auch.
Alternativ bedient man sich anderer Algortithmen, wie etwa des angesprochenen Algorithmus von Peterson (wobei nat. klar ist, dass eine Methode, die direkt durch die Hardware abgebildet werden kann, effizienter ist).

also

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.

class mutex {
    std::atomic<bool> locked = false;
public:
    void lock()
    {
        bool wanted;
        do
            wanted = false;
        while ( !locked.compare_exchange_strong( wanted, true ) ); // busy wait
        std::atomic_thread_fence(std::memory_order_aquire);
    }
    void unlock()
    {
        std::atomic_thread_fence(std::memory_order_release);
        locked = false;
    }
};

[tntnet]

camper schrieb:

tntnet schrieb:

Das Problem ist nicht atomic bool oder Reihenfolge der Ausführung oder so was sondern liegt einfach in der lock-Methode. Dort is eine Race-condition.

Ist fehlende Festgelegtheit der Ausführungsreihenfolge nicht genau das, was eine Race-condition ausmacht?

Richtig. Ich habe die Reihenfolge innerhalb eines Threads gemeint, also das reordering durch den optimizer. Das war missverständlich.

[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.