Ist eine Sperre (wait) kostenlos doppelt verknüpfte Liste möglich?

Question

diese Frage mit C # Tag, aber wenn es möglich ist, sollte es in jeder Sprache möglich sein.

Ist es möglich, eine doppelt verknüpfte Liste mit Verschlungene Operationen zu implementieren, ohne Warte Verriegelung zu schaffen? Ich mag einfügen, hinzufügen und entfernen, und klar, ohne zu warten.

Answer 1

Eine einfache Google-Suche werden viele schleusenfreien doppelt verknüpften Liste Papiere zeigen.

Sie werden jedoch basierend auf Atom CAS (Vergleichen und swap).

Ich weiß nicht, wie atomare Operationen in C #, aber nach dieser Webseite

http://www.albahari.com/threading/part4.aspx

C # Operationen werden nur sein Atom für das Lesen und das Schreiben eines 32-Bit-Feld garantiert. Keine Erwähnung von CAS.

Answer 2

Ja, es ist möglich, hier ist meine Implementierung eines STL-like? Lock-Free doppelt verketteten Liste in C ++.

Beispielcode, die Threads laicht um zufällig ops durchführt auf einem Liste

Es erfordert einen 64-Bit-Vergleichs- und Swap ohne ABA Probleme zu arbeiten. Diese Liste ist nur möglich, weil ein Lock-freie Speicher-Manager .

die Benchmarks auf Seite 12 . Leistung der Liste skaliert linear mit der Anzahl der Fäden als Konkurrenz zunimmt. Der Algorithmus unterstützt Parallelität für disjunkte Zugriffe, um die Listengröße erhöht Konkurrenz verringern kann.

Answer 3

Hier ist ein Papier , die eine Sperre frei doublly verkettete Liste discribes.

  

Wir stellen ein effizientes und praktisches   Lock-freie Implementierung eines   gleichzeitiger deque, die ist   disjunkt parallel zugänglich und Verwendungen   Atom-Primitiven, die verfügbar sind   in modernen Computersystemen. Vorher   bekannt schleusenfreien Algorithmen von deques   entweder auf der Grundlage nicht verfügbar   Atom-Synchronisation Primitiven,   implementieren nur eine Teilmenge der   Funktionalität ist oder nicht für die   disjoint zugreift. Unser Algorithmus ist   basiert auf einer doppelt verknüpften Liste, und   nur erfordert Einzelwort   Vergleichs- und Swap ...

Ross Bencina hat einige wirklich gute Links, die ich nur mit numerious Papiere und Quellcode excamples für " Einige Hinweise auf Lock-frei und warten freie Algorithmen ".

Answer 4

Ich glaube nicht, dies möglich ist, da Sie mehrere Verweise auf einem Schlag gesetzt haben sollte, und die miteinander verflochtenen Operationen in ihrer Macht beschränkt.

Nehmen wir zum Beispiel das Add-Betrieb - wenn Sie Knoten B zwischen A und C sind Einfügen, Sie müssen B- einstellen> weiter, B-> zurück, A-> weiter, und C-> zurück in ein Atom Betrieb. Verschlungene kann nicht damit umgehen. Voreinstellen Elemente B nicht einmal helfen, weil ein anderer Thread einen Einsatz entscheiden könnte, zu tun, während Sie die Vorbereitung auf „B“.

ich die Verriegelung mehr konzentrieren würde, wie auf immer feinkörnig wie möglich in diesem Fall nicht versuchen, sie zu beseitigen.

Answer 5

Lesen Sie die Fußnote - sie planen ConcurrentLinkedList von 4,0 vor der endgültigen Version von VS2010 zu ziehen

Answer 6

Nun, Sie haben nicht wirklich gefragt, wie es zu tun. Aber, vorausgesetzt, Sie können in C # eine atomare CAS tun, es ist durchaus möglich.

In der Tat arbeite ich nur durch eine Implementierung einer doppelt verknüpften Warte freien Liste in C ++ jetzt.

Hier ist Papier beschreibt es. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

Und eine Präsentation, die auch Ihnen einige Hinweise bereitstellen. http://www.ida.liu.se/ ~ chrke / Kurse / MULTI / Dia / Schloss-Free_DoublyLinkedList.pdf

Answer 7

Es ist möglich, frei Algorithmen für alle kopierbar Datenstrukturen auf den meisten Architekturen zu schreiben sperren [1]. Aber es ist schwer effizientesten zu schreiben.

Ich schrieb einen Implementierung der Lock-frei doppelt verknüpften Liste von Håkan Sundell und Philippas Tsigas für .Net. Beachten Sie, dass es nicht atomar PopLeft unterstützt aufgrund des Konzepts.

[1]: Maurice Herlihy: Unmöglichkeits und Universalität Ergebnisse für WAIT freesynchronization (1988)

Answer 8

FWIW, .NET 4.0 ist das Hinzufügen einer ConcurrentLinkedList, eine THREAD doppelt Liste im Namensraum System.Collections.Concurrent verknüpft. Sie können die Dokumentation oder die Blog-Post es beschreibt.

Answer 9

Ich würde sagen, dass die Antwort ist ein sehr tief qualifiziert „ja, es ist möglich , aber hart“. Um das umzusetzen, was Sie fragen, möchten Sie im Grunde brauchen etwas, das die Operationen zusammen kompilieren würde keine Kollisionen zu gewährleisten; als solche, wäre es sehr schwierig sein, eine allgemeine Einführung zu diesem Zweck zu schaffen, und es würde noch einige erhebliche Einschränkungen. Es wäre wahrscheinlich einfacher sein, eine spezifische Implementierung auf die genauen Bedürfnisse, und selbst dann zugeschnitten zu erstellen, wäre es nicht mit irgendwelchen Mitteln „einfach“ sein.