Es un bloqueo (esperar) libre de lista doblemente vinculada posible?

Question

Esta pregunta con C# etiqueta, pero si es posible, debe ser posible en cualquier idioma.

Es posible la aplicación de una lista doblemente vinculada mediante las operaciones de bloqueo para ofrecer sin esperar bloqueo?Me gustaría insertar, agregar y quitar, y claro sin tener que esperar.

Answer 1

Una simple búsqueda en Google revelará muchos papeles lista doblemente enlazada sin bloqueo.

Sin embargo, ellos se basan en CAS atómica (comparar y de intercambio).

No sé cómo atómica las operaciones en C # son, pero de acuerdo con este sitio web

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

C # operaciones sólo se garantizan para ser atómica para la lectura y escritura de un campo de 32 bits. No se hace mención de la CAS.

Answer 2

Sí, es posible, aquí está mi implementación de un STL-como Lock-libre doblemente enlazada lista en C ++.

código de ejemplo que genera subprocesos para llevar a cabo al azar ops en una lista

Se requiere una de 64 bits de comparación y de intercambio para operar sin problemas ABA. Esta lista sólo es posible a causa de una lock-libre administrador de memoria .

Salida del noreferrer puntos de referencia en la página 12 . El rendimiento de la lista escala de forma lineal con el número de hilos a medida que aumenta la contención. El algoritmo soporta paralelismo para accesos disjuntos, así como el tamaño de la lista aumenta la contención puede disminuir.

Answer 3

Aquí es un papel, que discribes una lista libre de bloqueo doublly vinculado.

  

Se presenta un eficiente y práctica   lock-libre de la implementación de un   deque concurrente que es   disjuntos-paralelo accesible y usos   primitivas atómicas que están disponibles   en los sistemas informáticos modernos. Previamente   algoritmos libre de bloqueo conocidos de deques   se basan ya sea en no disponible   primitivas de sincronización atómicos,   Sólo implementar un subconjunto de la   funcionalidad, o no están diseñados para   disjuntos accesos. Nuestro algoritmo es   basado en una lista doblemente enlazada, y   sólo requiere una sola palabra   comparación y de intercambio ...

Ross Bencina tiene muy buenos enlaces que acabo de encontrar con papeles numerious y trata, por ejemplo el código fuente para " Algunas notas sobre los algoritmos sin bloqueo y esperar libre ".

Answer 4

Yo no creo que esto sea posible, ya que vamos a tener que establecer varias referencias en una sola toma, y las operaciones de bloqueo están limitados en su poder.

Tomemos, por ejemplo, la operación de añadir - si desea insertar el nodo B entre a y C, es necesario establecer B->siguiente, B->prev, A->siguiente, y C->prev en una operación atómica.Enclavada no puede manejar eso.Preajuste de B elementos no ayuda, ya que el otro hilo se podría decidir hacer un insert, mientras que usted se está preparando "B".

Me concentraría más en conseguir el bloqueo como de grano fino como sea posible, en este caso, no tratando de eliminarlo.

Answer 5

Leer la nota - que planean sacar ConcurrentLinkedList de 4,0 antes de la versión final de VS2010

Answer 6

Bueno, en realidad no han preguntado cómo hacerlo. Sin embargo, siempre se puede hacer un CAS atómica en C # es completamente posible.

De hecho estoy trabajando a través de una implementación de una lista doblemente enlazada libre de espera en C ++ en este momento.

Aquí es papel describirla. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

Y una presentación que también le puede dar algunas pistas. http://www.ida.liu.se/ ~ chrke / cursos / Multi / diapositivas / Lock-Free_DoublyLinkedList.pdf

Answer 7

Es posible escribir algoritmos bloquear gratuitas para todos estructuras de datos copiable en la mayoría de las arquitecturas [1]. Pero es difícil escribir otras de bajo consumo.

escribí una implementación rel="nofollow"> sin bloqueo lista doblemente enlazada por Håkan Sundell y Philippas Tsigas para .Net. Tenga en cuenta, que no admite PopLeft atómica debido al concepto.

[1]: Maurice Herlihy: imposibilidad y resultados universalidad para espera- freesynchronization (1988)

Answer 8

Fwiw, .NET 4.0 es la adición de un ConcurrentLinkedList, un multi-hilo doblemente lista enlazada en el espacio de nombres System.Collections.Concurrent. Puede leer el documentación o el entrada de blog describirla.

Answer 9

Yo diría que la respuesta es un muy profundamente "sí, es posible , pero es difícil". Para poner en práctica lo que estás pidiendo, usted necesita básicamente algo que compilar las operaciones en conjunto para asegurar que no hay colisiones; como tal, sería muy duro para crear una aplicación general para ese propósito, y sería aún tienen algunas limitaciones significativas. Probablemente sería más simple para crear una implementación específica adaptada a las necesidades precisas, y aún así, no sería "simple" por cualquier medio.