Lesen/Schreiben von Speicher Multithreaded

Finnegan

@It0101 sagte in Lesen/Schreiben von Speicher Multithreaded:

LockFree 25,6 Sekunden, 370% CPU ( von 400% )

Nochmal am Rande: Wenn der Schreiber angehalten wird, während er das Lock hält, dann geht gar nix mehr. Daher ist das nicht "Lock-Free". Das ist eher Userspace-Spinlock vs. Standard-Mutex.

Lock-Free könnte man es vielleicht hinbekommen, wenn der Schreiber z.B. zunächst nur in seine eigene, thread-lokale, unsynchronisierte Kopie schreibt (zum Kopieren muss er ja nur Lesen) und das geteilte synchronisierte Objekt dann mit dieser z.B. in einem atomaren Pointer-Swap austauscht. Dann könnte man jeden beliebigen Thread pausieren und dennoch würden alle anderen weiterarbeiten können. Das sollte dann wirklich "Lock-Free" sein (korrigiert mich, wenn ich da nen Denkfehler drin habe).

It0101

@Finnegan
Es ist nicht lockfree, das ist klar. Ich verwende den Namen einfach nur weiter, damit ich meine Klassen nicht ständig umbenennen muss

Zur Richtigstellung für zukünftige Lesende: Das Konzept ist nicht Lockfree, es ist nur eine andere Herangehensweise als Mutex.

hustbaer

@Finnegan Ich glaube der Autor des verlinkten Artikels der die Formulierung "lock free reader-writer lock" verwendet hat meint damit dass die Implementierung des "reader-writer lock" selbst keinen klassischen "lock" verwendet. Also im Gegensatz zu z.B. "reader-writer lock" Implementierungen die sich einer Mutex + Condition-Variable bedienen.

Und natürlich hat so eine "lock free" Variante Vorteile gegenüber Mutex + Condition-Variable, weil sie weniger Nukularoperationen benötigt und daher vor allem im "non contended" Fall deutlich schneller ist.

Aber der Begriff "lock free" im Zusammenhang mit nem Lock ist natürlich komisch, das ist klar
(Und IMO nicht nur komisch sondern Quatsch -- auch wenn ich meine zu verstehen wie es gemeint war.)

Finnegan

@hustbaer sagte in Lesen/Schreiben von Speicher Multithreaded:

@Finnegan Ich glaube der Autor des verlinkten Artikels der die Formulierung "lock free reader-writer lock" verwendet hat meint damit dass die Implementierung des "reader-writer lock" selbst keinen klassischen "lock" verwendet. Also im Gegensatz zu z.B. "reader-writer lock" Implementierungen die sich einer Mutex + Condition-Variable bedienen.

Und natürlich hat so eine "lock free" Variante Vorteile gegenüber Mutex + Condition-Variable, weil sie weniger Nukularoperationen benötigt und daher vor allem im "non contended" Fall deutlich schneller ist.

Ich habe mich noch nicht viel mit den Innereien eines Mutex beschäftigt, aber ist es nicht so, dass die guten Implementierungen sogar erstmal sehr ähnlich arbeiten, wie hier vorgeschlagen? Ich meine gelesen zu haben, dass manche Mutex-Implementierungen erstmal mit ein paar Atomics auf Contention testen und einige sogar eine kurze Zeit spinnen, bevor dann das OS für einen vollwertigen Mutex involviert wird. Das sollte doch eigentlich gerade im Non-Contended-Fall genau so effizient sein (?).

Aber der Begriff "lock free" im Zusammenhang mit nem Lock ist natürlich komisch, das ist klar
(Und IMO nicht nur komisch sondern Quatsch -- auch wenn ich meine zu verstehen wie es gemeint war.)

Nun, "Lock" und "Lock-Free" schliessen sich nicht unbedingt aus, da sich letzteres durch das Verhalten des Algorithmus definiert und ersteres ein konkretes Objekt bescheibt. So könnte ich - wenn ich das richtig verstanden habe - durchaus einen "Lock-Free"-Algorithmus mit einem Standard-Mutex bauen, solange sich die Threads nicht gegenseitig blockieren können. Der Algorithmus könnte z.B. ein try_lock auf eine synchroisierte Ressource machen und wenn das fehlschlägt eben nicht blockieren, sondern einfach auf einer anderen freien Ressource weiterarbeiten.

Ich glaube "Lock-free" bedeutet hier eher "blockadefrei" und nicht "ohne Lock-Objekt".

hustbaer

@Finnegan
Ich glaube du hast mich falsch verstanden
Davon abgesehen hast du mit vielem was du schreibst Recht.

ist es nicht so, dass die guten Implementierungen sogar erstmal sehr ähnlich arbeiten, wie hier vorgeschlagen?

Ja. Eine gute Mutex Implementierung die auf Speed optimiert ist (im Gegensatz z.B. zu einer auf FIFO/Fairness optimierten) tut genau gleich wie nen Spin-Lock -- bis zu dem Zeitpunkt wo sie länger spinnen müsste. Das ganze sleep-Gedöns per Event/Condition-Variable/... kommt erst danach.

Das sollte doch eigentlich gerade im Non-Contended-Fall genau so effizient sein (?).

Gleich effizient wie ein Spin-Lock, ja. Aber das meinte ich nicht.

Ich meinte: wenn man keine "Shared Mutex" (=Reader/Writer Lock) hat, sondern nur ne Mutex + Condition-Variable, dann ist die typische Variante eine Shared Mutex daraus zu basteln diese:

void MySharedMuhTex::lock() {
    std::unique_lock<std::mutex> lk(m_mutex);
    m_condvar.wait(lk, [this](){ return !m_writer; });
    m_writer = true;
    m_condvar.wait(lk, [this](){ return m_readers == 0; });
}
...

Das wäre die "nicht lock free" Variante. Und diese ist logischerweise weniger effizient als ne einfache std::mutex, weil ein lock-unlock Zyklus meiner MySharedMuhTex ja mindestens zwei lock-unlock Zyklen der std::mutex benötigt. Und auch weniger effizient als ein mit Nukularen selbstgebastelter "lock free" Reader/Writer Lock