threadsafe list
-
Hallo liebe Community,
Ich möchte (zur Übung) eine threadsichere Liste (doppelt verkettet) implementieren. Allerdings scheint das STL-Interface dafür per Design nicht besonders gut geeignet zu sein, da Operationen auf Ranges schwierig zu locken sind, das geht vermutlich nur auf User-Seite. Ich suche eine Liste als Referenz, die für Multithreading designt wurde.
Habt ihr irgendwelche nützlichen Links für mich?
Grüße,
Der Kellerautomat
-
Bau dir eben einen Wrapper um std::list der auch noch ein Mutex enthält. Dann kannst du eben die List locken wenn du was damit tust und unlocken wenn du fertig bist. Eine doppelt verkettete Liste ist schwer lockfree hinzubekommen (wenn auch theoretisch möglich). Imo solltest du dir zuerst aber lieber mal überlegen, ob eine Liste wirklich eine gute Wahl für deine Datenstruktur ist...
-
dot schrieb:
Bau dir eben einen Wrapper um std::list der auch noch ein Mutex enthält. Dann kannst du eben die List locken wenn du was damit tust und unlocken wenn du fertig bist.
Das klingt aber doof, gleich die ganze Datenstruktur zu locken, wenn man ein einzelnes Element zugreift.
Imo solltest du dir zuerst aber lieber mal überlegen, ob eine Liste wirklich eine gute Wahl für deine Datenstruktur ist...
+1. Threadparallelisierung klingt nach Performanceprogrammierung. Verkettete Listen klingen nach, Verzeihung an alle Informatiker, Theoretikerquatsch.
-
Naja, nehmen wir mal ein Simples Beispiel: Ein Server, der Clients in mehreren Threads bearbeitet. Irgendwo müssen die Clients ja auch in einer Liste gespeichert werden. Wie würde man sowas realisieren?
-
SeppJ schrieb:
Das klingt aber doof, gleich die ganze Datenstruktur zu locken, wenn man ein einzelnes Element zugreift.
Bei Einfüge/Lösch-Operationen kommt er kaum drum herum, bzw. im Fall der std::list garnicht, weil hand-over-hand-Locking hier nicht umsetzbar ist. Wenn er nur auf bestehende Elemente zugreift könnte er einen etwas entspannteren Locking-Algorithmus verwenden, wobei er dann aber wieder für jedes Listenelement einen eigenen Mutex braucht.
Listen sind generell ziemlich eklig, was das Locking angeht, weshalb man auch nur schwer was dazu im Netz findet.Imo solltest du dir zuerst aber lieber mal überlegen, ob eine Liste wirklich eine gute Wahl für deine Datenstruktur ist...
+2. Wenn du überhaupt wirklich parallel drauf zugreifen musst, eignen sich für Container normalerweise eher random-access Datenstrukturen.
-
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?
