lista de enlaces simultáneos

Estoy tratando de diseñar una lista vinculada en C++ que permita el acceso simultáneo. Claramente, usar un solo bloqueo para esta lista es extremadamente ineficiente ya que las áreas disjuntas pueden actualizarse en paralelo. Ahora, ¿cuáles son mis opciones además de almacenar un bloqueo por nodo?lista de enlaces simultáneos

Además, ¿una versión sin bloqueo sería una mejor opción en este caso? Cualquier enlace relevante, alguien?

EDIT: Gracias por las respuestas personas. Un par de cosas que quisiera agregar:

¿Qué tal si guardo N bloqueos para cada M nodos en lugar de 1: 1 de bloqueo: proporción de nodos? Algunos hilos esperarían, pero es una especie de intercambio. ¿Qué piensas?
Si intento encontrar algún nodo en esta lista vinculada, parece que todos los mutex deben estar bloqueados. Esto es un problema, ya que bloquear y desbloquear todos los mutexes lleva mucho tiempo. ¿Alguien tiene una mejor alternativa?
Estoy abierto a algoritmos sin bloqueo. Pero, ¿cómo uso CAS en el buen viejo C++ sin usar el ensamblado? Escuché que gcc tiene algunos atributos __sync que hacen un trabajo similar pero no estoy seguro.
Con un enfoque sin bloqueo, ¿cómo se hace una búsqueda en la lista vinculada?

Fuente

2010-11-12 Fanatic23

Considere utilizar algo que ya existe en lugar de reinventar esta rueda. Un ejemplo podría ser 'concurrent_vector' del TBB de Intel: http://www.threadingbuildingblocks.org/ –

También puede haber una solución de Boost, no estoy seguro. –

Es posible implementar una lista de no-bloqueo de enlace simple usando las funciones entrelazadas:

Interlocked Singly Linked Lists

No creo que es posible implementar una lista de no-bloqueo doblemente enlazada sin compare- entrelazada and-swap (CAS), que no está ampliamente disponible.

Fuente

2010-11-12 18:03:20

¿Sugiere esta pregunta ventanas de alguna manera? – Falmarri

CAS está en todos los procesadores modernos y creo que durante algunos años. DCAS es el que no siempre está disponible. –

Sí, CAS es muy común. Es una función específica de la implementación, pero la mayoría de los usos de ella se transfiere a un bloqueo/exclusión mutua en los casos en que CAS no está disponible (ARM viene a la mente). –

¿Estás seguro de que este es un problema que vale la pena resolver? ¿Sería quizás más útil encapsular el uso final real en una clase que maneja el bloqueo de un list normal y proporciona una interfaz segura para subprocesos? De esta forma, no intentes poner el bloqueo a un nivel demasiado bajo (que, como supusiste, no es un problema fácil de resolver).

Fuente

2010-11-12 18:17:10

Estoy seguro de que este es un problema que vale la pena resolver. Si bloqueo la clase de lista normal usando un solo mutex claramente, podré hacer el trabajo. Pero este no es un sistema rápido e impone serias restricciones a la escalabilidad del sistema. Considere la posibilidad de varios hilos de escritura que deseen anexar/editar diferentes secciones disjuntas de la lista vinculada. Podrían funcionar sin un solo candado. – Fanatic23

Linked lists are inherently sequential data structures. Independientemente del tipo de maquinaria que utilice para implementarlo, la interfaz y el comportamiento esperado implican una lógica secuencial.

¿Qué estás tratando de hacer? Eso debería determinar qué estructura de datos utiliza, no la familiaridad de las estructuras de datos con las que ya se siente cómodo.

Fuente

2010-11-12 18:24:36 MSN

No son necesariamente inherentemente secuenciales. Diferentes subprocesos pueden contener punteros a diferentes áreas de la lista y moverse independientemente hacia adelante/atrás. –

Una lista vinculada implica un pedido global en toda la estructura de datos. Si no desea un pedido global en toda la estructura de datos, no use una sola lista vinculada como una estructura de datos compartida. – MSN

@MSN Varios hilos de escritura intentan insertar/agregar datos de diferentes partes de la lista al mismo tiempo. Claramente, usar un solo candado no es óptimo aquí. – Fanatic23

Existen muchas maneras diferentes de hacerlo, dependiendo de cómo va a utilizar la lista.

En primer lugar, para una lista, un solo bloqueo de exclusión mutua no es necesariamente un gran problema porque las listas pueden admitir el empalme. Digamos que tiene una lista de caracteres AF y otra lista BCDE. No tiene que bloquear el mutex, insertar B, bloquearlo de nuevo, insertar C, etc. Puede insertar BCDE todo de una vez entre A y F configurando el siguiente puntero de A a B y E el siguiente puntero a F, formando ABCDEF. No importa cuántos elementos quiera insertar de una vez, solo necesita un candado. Esto es cierto incluso para una lista doblemente vinculada. Por lo tanto, puede no ser un cuello de botella en su aplicación.

Suponiendo que sea un cuello de botella, debe considerar si va a tener uno o varios escritores y uno o varios lectores.

Suponiendo que tiene una sola grabadora y varios lectores, puede evitar bloqueos de mutex por completo mediante el uso de instrucciones atómicas, suponiendo que estén disponibles para su arquitectura. En GCC están disponibles a través de las funciones incorporadas __sync_ * y en Visual C++ están disponibles a través de Interbloqueado *, pero si está atrapado con un compilador que carece de soporte directo para ellos, puede usarlos a través del ensamblaje en línea. El escritor utilizará las instrucciones atómicas para establecer atómicamente los siguientes punteros para parchar elementos dentro y fuera de la lista.

Espero que eso te sirva para empezar. Para obtener una respuesta profunda, sugiero hacer otra pregunta e incluir:

¿Hay uno o varios lectores?
¿Hay uno o varios escritores?
¿Lista simple o doblemente vinculada?
Alguna idea de cuál es su caso de uso.

Fuente

2010-11-12 18:43:10

Muchas gracias por la respuesta, +1 por mi parte. Preferiría quedarme con mutexes por ahora. Mi preocupación son las soluciones de implementación, lo que funciona y cuándo: tener un solo mutex no es bueno y un único mutex por nodo es quizás demasiado caro. – Fanatic23

¿Qué pasa? ¿Obedece las listas? Eche un vistazo a la implementación de Java en el paquete "concurrente".

Fuente

2011-07-24 22:22:14 Stas

Respuesta

Cuestiones relacionadas