threadsafe list
-
dot schrieb:
hustbaer schrieb:
Bei doppelt verketteten Listen sehe ich gerade halbwegs finster.
Es ist theoretisch möglich, aber imo nicht sehr praktikabel: http://www.cse.chalmers.se/~tsigas/papers/deques-dlls-jpdc.pdf
Bitte was?
Ich hab mir das Paper ja nur kurz angekuckt, aber anstelle eines Mutexes verwenden wir ein Flag, das gesetzt wird und nun wird in einer Schleife immer wieder gekuckt, ob das Flag gesetzt ist, bis es dann einmal nicht gesetzt ist...Was hat das mit lockfree zu tun?
Jetzt ist man nicht an einer bestimmten Stelle gelockt, sondern läuft über sie immer wieder drüber, bis die Ressource verfügbar ist...
Großer Unterschied...Habe ich das richtig verstanden?
-
XSpille schrieb:
Was hat das mit lockfree zu tun?
Jetzt ist man nicht an einer bestimmten Stelle gelockt, sondern läuft über sie immer wieder drüber, bis die Ressource verfügbar ist...
Großer Unterschied...Habe ich das richtig verstanden?
Du zahlst keine Lock-Kosten und keine Context-Switches. Das ist Lockfree. Was haettest du erwartet? Dass magisch keine Race Conditions entstehen koennen?
Aber es gibt keinen Lock der eine Resource sperrt. Das ganze laeuft ueber CAS (Compare and Swap) welches sooft probiert die Aktion zu setzen bis sie nicht von einem anderen thread interruptet wird. Das ist in gewissermassen natuerlich ein Spinlock - aber eben nicht ganz.
Aber streng genommen stimmt es natuerlich: echtes lockfree gibt es nicht. Denn wir brauchen immer eine Art mit concurrenten Schreibzugriffen umgehen zu koennen.
-
XSpille schrieb:
dot schrieb:
hustbaer schrieb:
Bei doppelt verketteten Listen sehe ich gerade halbwegs finster.
Es ist theoretisch möglich, aber imo nicht sehr praktikabel: http://www.cse.chalmers.se/~tsigas/papers/deques-dlls-jpdc.pdf
Bitte was?
Ich hab mir das Paper ja nur kurz angekuckt, aber anstelle eines Mutexes verwenden wir ein Flag, das gesetzt wird und nun wird in einer Schleife immer wieder gekuckt, ob das Flag gesetzt ist, bis es dann einmal nicht gesetzt ist...Was hat das mit lockfree zu tun?
Jetzt ist man nicht an einer bestimmten Stelle gelockt, sondern läuft über sie immer wieder drüber, bis die Ressource verfügbar ist...
Großer Unterschied...Habe ich das richtig verstanden?
Der Knackpunkt ist dass es kein Lock gibt das für die ganze Liste gilt.
Diverse Retriy-Mechanismen wirst du in allen Lock-free Datenstrukturen finden. Ob's nun mit "delete" Flags ist oder mit Change-Countern oder noch anderen Verfahren, irgendwas muss immer sein. Selbst für einen atomaren Zähler braucht man auf Plattformen die nur CAS und kein FAA/... können Retries.
-
hustbaer schrieb:
Der Knackpunkt ist dass es kein Lock gibt das für die ganze Liste gilt.
Dann kann ich doch aber auch mehrere Mutexe mit unterschiedlichen Aufgaben verwenden. Wo ist der Unterschied?
EDIT: Also meine naive Vorstellung eines Mutexes ist, dass er beim locken eine Schleife hat, die atomar kuckt, ob der Mutex gesperrt werden kann (und ggf. sperrt) und ansonsten ein yield aufruft. (Obwohl kann nicht ganz stimmen, da man sonst eine volle Prozessorauslastung hätte... Ist da ein Sleep mit drin?
-
pumuckl schrieb:
Statement von der Parallel2012: "Es gibt vielleicht 20-30 Leute, die Lockfree Algorithmen fehlerfrei hinbekommen. Weltweit."
Kann ich bestaetigen. Die Thematik ist wirklich alles andere als trivial. Wenns irgendwie geht, was fertiges nehmen. Wenn mans selber macht, hat man eh immer irgendwelche Bugs drinnen und dann debuggt man sich zu Tode (Multithreaded Anwendungen debuggen is die Hoelle!)
-
XSpille schrieb:
Dann kann ich doch aber auch mehrere Mutexe mit unterschiedlichen Aufgaben verwenden. Wo ist der Unterschied?
Der Unterschied ist iirc, dass Mutexe relativ Performance-intensiv sind, während das bei atomics nicht der Fall ist, vorausgesetzt, die Hardware unterstützt CAS.
-
Man kann atomics nicht einfach mit Spin Locks vergleichen. Was eine Atomic Operation ausmacht ist, dass sie garantiert in einer gewissen Zeit fertig wird und es eben kein Lock gibt (kein busy wait, kein Contextswitch, nichts).
Atomics sind auf Hardwareebene implementiert und nicht nur einfache "Retry Mechanismen". Die Zugriffe werden direkt von der Hardware serialisiert.@XSpille: Deine naive Vorstellung von einem Mutex ist korrekt, genau so funktioniert das.
-
XSpille schrieb:
(Obwohl kann nicht ganz stimmen, da man sonst eine volle Prozessorauslastung hätte... Ist da ein Sleep mit drin?
Einen Mutex zu locken ist ähnlich wie das Ĺesen aus einer Datei.
Beim Lesen aus einer Datei läuft der Thread direkt weiter, falls die Daten schon gepuffert waren, ansonsten ignoriert der Kernelscheduler den Thread bis alles von der Festplatte in den RAM geschrieben wurde.
Beim Mutex ist es praktisch gleich, der Thread macht garnichts mehr, bis der Kernel weiß dass der Mutex frei ist.
-
pumuckl schrieb:
XSpille schrieb:
Dann kann ich doch aber auch mehrere Mutexe mit unterschiedlichen Aufgaben verwenden. Wo ist der Unterschied?
Der Unterschied ist iirc, dass Mutexe relativ Performance-intensiv sind, während das bei atomics nicht der Fall ist, vorausgesetzt, die Hardware unterstützt CAS.
Und warum ist ein Mutex nicht einfach ein atomic?
Weil der Mutex zusätzlich dem Betriebssystem sagt, dass dieser Thread nicht mehr beachtet werden muss, bis der die Resource wieder verfügbar ist? Aber das müßte doch auch mit einem atomic-Flag möglich sein. Ok... Dann fliegt er im unglücklichen Fall mit warte auf Flag raus, obwohl das Flag schon wieder zurückgesetzt wurde da das Prozedere nicht atomic ist... Aber who cares?
Warum kann man in einem Mutex kein einfaches Atomic verwenden?Gruß,
XSpille
-
Mutexe sind doch über Atomics implementiert!?
-
dot schrieb:
Mutexe sind doch über Atomics implementiert!?
Und warum sind sie dann relativ Performance intensiv?
-
Weil ein Mutex eben mehr ist als einfach nur eine Atomic Operation?
Wieso ist 3D Grafik performanceintensiver als eine Addition?
-
dot schrieb:
Weil ein Mutex eben mehr ist als einfach nur eine Atomic Operation?
Wieso ist 3D Grafik performanceintensiver als eine Addition?Dann erklär mir mal das "eben mehr" ^^
Also wenn er nicht blockt, dann ist es ein einfacher Atomic Zugriff(?).
Wenn er blockt, sagt er dem OS noch wielange der Thread nicht berücksichtigt werden muss... Aber das ist doch quasi nur eine Referenz auf das Atomic und evtl. welcher Wert... Aber dafür spart er sich die Kontextwechsel und unnötige Schleifenwiederholungen, wenn er noch geblockt ist...
-
[quote="XSpille"]Also wenn er nicht blockt, dann ist es ein einfacher Atomic Zugriff(?).[quote]Nein.
Wenn er blockt, sagt er dem OS noch wielange der Thread nicht berücksichtigt werden muss
Nein.
... Nein.
Dann erklär mir mal das "eben mehr" ^^
Nein, ich bin nicht fuer deine Bildung verantwortlich. Komm wieder, wenn du eine konkrete Frage hast!
Mutexe sind doch über Atomics implementiert!?
Welche Rolle spielt deren Implementation? Sie koennen auch anders implementiert sein, beispielsweise durch das Deaktivieren aller Interrupts.
-
Eine Atomic Operation ist einfach nur eine Operation die, von außen betrachtet, immer nur ganz oder gar nicht ausgeführt wird.
Ein Mutex schützt einen ganzen Codeabschnitt. Es sorgt dafür, dass niemals mehr als ein Thread gleichzeitig den selben Code ausführt. (Die Verallgemeinerung eines Mutex wär eine Semaphore, die dafür sorgt dass niemals mehr als N Threads den selben Code ausführen.)
Streng genommen könnte man natürlich auch eine Critical Section als Atomic Operation betrachten. Die Mechanismen wie diese Atomizität realisiert ist, sind aber Grundverschieden. Daher verwendet man den Begriff Atomic Operation normalerweise nur für entsprechende Operationen der ISA.
-
knivil schrieb:
Mutexe sind doch über Atomics implementiert!?
Welche Rolle spielt deren Implementation? Sie koennen auch anders implementiert sein, beispielsweise durch das Deaktivieren aller Interrupts.
Das ist natürlich richtig. Diese Art von Mutex findet man aber normalerweise nur direkt im Kernel und auch dort nur an ganz bestimmten Stellen
-
