threadsafe list
-
Es war einfach mein Bauchgefühl, das mir gesagt hat, dass Listen bei Multithreading am besten funktionieren, da Knoten unabhängig voneinander im Speicher liegen und es damit zu keinen Reallokationen wie bei einem dynamischen Array ala std::vector kommen kann.
Liege ich damit falsch?
-
Kellerautomat schrieb:
Es war einfach mein Bauchgefühl, das mir gesagt hat, dass Listen bei Multithreading am besten funktionieren, da Knoten unabhängig voneinander im Speicher liegen und es damit zu keinen Reallokationen wie bei einem dynamischen Array ala std::vector kommen kann.
Liege ich damit falsch?
Jein.
Ein Knoten ist immer von seinen Nachbarknoten abhänig und das ist eigentlich schon der Kern des Problems:
Wann ist ein Container Threadsafe?
Oft ist ein brutales Locken wenn man auf den Container zugreift das simpelste. Denn einfügen und löschen wirkt sich immer auch auf andere Elemente aus. Will man nur lesezugriff haben, ists einfacher - aber irgendwann braucht man auch Schreibzugriff.
Ein Read und Write Lock ist deshalb manchmal eine gute Idee. Aber im Prinzip geht es darum: Was will ich mit dem Container eigentlich machen.
-
Einfach verkettete Listen können was bringen, da man die Lock-free implementieren kann.
Bei doppelt verketteten Listen sehe ich gerade halbwegs finster.
-
hustbaer schrieb:
Einfach verkettete Listen können was bringen, da man die Lock-free implementieren kann.
Kann man, aber nicht mal eben zur Übung als Einsteiger in die ganze Parallel-Thematik.
-
pumuckl schrieb:
hustbaer schrieb:
Einfach verkettete Listen können was bringen, da man die Lock-free implementieren kann.
Kann man, aber nicht mal eben zur Übung als Einsteiger in die ganze Parallel-Thematik.
Ja, da haste auch wieder Recht
Zum Einstieg in die ganze Threading-Thematik wäre etwas mit klassischen Mutexen angesagt.
z.B. eine Producer-Consumer-Queue.
Also ne bounded FIFO mit threadsafe TryGet/TimedGet, TryPut/TimedPut.
-
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
-
pumuckl schrieb:
Kann man, aber nicht mal eben zur Übung als Einsteiger in die ganze Parallel-Thematik.
Ich bin kein "Einsteiger in die Parallel-Thematik". Ich habe ein ungefähres Verständnis von Threads, Locking-Mechanismen und Atomics.
-
Quasi mal 'n Buch druebergelesen .... aber alte Hasen mit viel Erfahrung haben Papers veroeffentlich, die falsch waren.
-
Kellerautomat schrieb:
Ich habe ein ungefähres Verständnis von Threads, Locking-Mechanismen und Atomics.
Das wäre meine Definition von "gerade eingestiegen". Zumindest klingt es nicht nach Erfahrung mit parallelen Datenstrukturen.
Statement von der Parallel2012: "Es gibt vielleicht 20-30 Leute, die Lockfree Algorithmen fehlerfrei hinbekommen. Weltweit."
-
Ich habe schon threadsichere Datenstrukturen über Mutexes implementiert. Aber keine Lock-freien.
-
pumuckl schrieb:
Statement von der Parallel2012: "Es gibt vielleicht 20-30 Leute, die Lockfree Algorithmen fehlerfrei hinbekommen. Weltweit."
Sehr gut.
Jetzt muss ich mir nimmer so doof vorkommen
-
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
