lock-freie Datenstruktur - wie synchronisieren?

Hallo

ich benötige eine Datenstruktur, welche Einfügen am Ende sowie Entfernen von Elementen an beliebigen Positionen unterstützt. In meinen Augen bietet sich hier eine doppelt verkettete Liste an.
Wie kann ich eine solche am effizientesten Synchronisieren? Einfach eine std::list mit einem std::mutex scheint mir zu einfach. Ich tendiere zu einer eigenen Listen-Implementierung, welche intern mit einem einfachen SpinLock nur die Stellen sichert, in denen die Listen-Zeiger umgeschrieben werden. Allokation von neuen Listen-Knoten z.B. wären also nicht synchronisiert.

Ist dies sinnig? Gibt es performantere Lösungen?

theta

Hier noch zwei Artikel dazu:
http://www.ddj.com/architect/210604448
http://www.ddj.com/architect/211601363
Simon

knivil

Ist dies sinnig? Gibt es performantere Lösungen?

Fuer welches Problem?

knivil schrieb:

Ist dies sinnig? Gibt es performantere Lösungen?

Fuer welches Problem?

Ist die Datenstruktur (doppelt verkettete Liste) in Ordnung? Ist der Synchronisationsmechanismus (Spinlock, nur für die eigentlichen Pointer-Verschiebungen bei Einfügen und Entfernen) gut?

unskilled

Thead0r schrieb:

knivil schrieb:

Ist dies sinnig? Gibt es performantere Lösungen?

Fuer welches Problem?

Ist die Datenstruktur (doppelt verkettete Liste) in Ordnung? Ist der Synchronisationsmechanismus (Spinlock, nur für die eigentlichen Pointer-Verschiebungen bei Einfügen und Entfernen) gut?

um das zu beurteilen, müsste man dein problem genauer kennen...
nur stellenweise locken ist zwar an und für sich ne gute idee, aber wird sicherlich ab und an ins auge gehen...
auch kann man 0 beurteilen, ob die liste wirklich die optimale datenstruktur ist, oder vll doch eher eine deque besser wäre(die man dann auch wieder komplett schreiben kann, wenn man das für nötig hält und dort immer nur einzelne bereiche lockt... hätte auch den vorteil, dass der iterator(den du ja sicherlich anbieten wirst), ein ganzes stück laufen könnte, auch wenn parallel iwo was eingefügt/entfernt wird. bei ner liste würdest du den iterator gar nicht laufen lassen können, wenn du entfernst... beim einfügen sollte es hier hingegen aber gar kein problem geben(muss nicht mal gelockt werden), wenn ich jz keinen denkfehler habe(edit: oh - ist ja ne doppeltverkettete - da bin ich mir gerade zu unsicher^^)... die deque könnte das wiederrum nicht - erzähl mal bissl, wofür du die struktur brauchst, welche operationen wie oft ausgeführt werden und interessant wäre auch, in wie fern versch. threads darauf operieren...

bb

hustbaer

Die meisten Programme schaffen es garnicht, auch nur in die Nähe von "Lock Contention" zu kommen. Soll heissen: es ist egal, ob man hier optimiert oder nicht.

Wenn man ein Programm hat, wo man es doch schafft, dann kann es schon Sinn machen, bestimmte Dinge ausserhalb des Locks zu machen (wie z.B. "new" aufzurufen etc.).
In dem Fall würde es was bringen, selbst eine Liste, oder auch einen Red-Black-Tree oder sowas zu programmieren, die/der "in sich" synchronisiert ist, und nur dort lockt, wo es nötig ist. (Man sollte dann auch zu jeder Funktion eine "no-lock" Variante anbieten, die der Aufrufer verwenden kann, wenn er den Lock bereits hält, aber das ist wieder eine andere Geschichte)

Das hat allerdings mit "lock free" bzw. "wait free" Datenstrukturen nichts zu tun. Diese verwenden *garkeine* Locks, weder Spin-Locks noch sonst was.

Würde ich aber die Finger von lassen, die sind viel zu heikel zu programmieren. Nahezu unmöglich sowas auf anhieb richtig hinzubringen.

Vielen Dank für eure Antworten.

Ich habe eingesehen, dass ich lieber die Liste komplett vermeiden soll. Gerade bei entsprechender Skalierung kann es in meinem Fall mit dem Spin-Lock doch nicht mehr so cool werden. Ich will die Problematik komplett vermeiden und lieber das Design komplett überdenken. Ich habe da schon etwas mit boost::shared_ptr im Kopf :=)

Gruß