Mutex Implementierung

manni66 schrieb:

Frage doch "man" nach einer Erklärung.

Wieso würde ich hier fragen wenn ich das könnte?

manni66 schrieb:

Aber vermutlich ist das eine Hausaufgabe, die du von uns gelöst haben möchtest.

Ne.

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.

Sofern ich das korrekt mitbekommen habe löst es bei std::mutex einfach UB aus wenn ein anderer Thread unlocken möchte. Daher ist es doch schlussendlich egal ob ich das prüfe oder nicht. Bei std::mutex dürfen ja auch andere Threads nicht unlocken, weil das Programm sonst illformed ist.

Wäre der Code abseits dem etwa korrekt?

Columbo

Wäre der Code abseits dem etwa korrekt?

Zuallererst brauchst du einen atomic bool.

Sofern ich das korrekt mitbekommen habe löst es bei std::mutex einfach UB aus wenn ein anderer Thread unlocken möchte.

Das ist korrekt.

SeppJ

Was passiert denn, wenn zwei Threads gleichzeitig try_lock und/oder lock aufrufen?

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

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.