Haciendo esta pregunta con la etiqueta C#, pero si es posible, debería ser posible en cualquier idioma.¿Es posible un bloqueo (espera) de una lista doblemente vinculada?
¿Es posible implementar una lista doblemente enlazada usando operaciones interbloqueadas para proporcionar bloqueo sin espera? Me gustaría insertar, agregar y eliminar, y borrar sin esperar.
Una simple búsqueda en Google revelará muchos documentos de la lista doblemente vinculados sin bloqueos.
Sin embargo, se basan en CAS atómico (comparar y cambiar).
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
operaciones de C# sólo se garantizan para ser atómica para la lectura y escritura de un campo de 32 bits. Sin mención de CAS.
C# (.NET) tiene absolutamente un comparar y cambiar atómico. Se llama Interlocked.CompareExchange. http://msdn.microsoft.com/en-us/library/system.threading.interlocked.compareexchange.aspx – Cheeso
@ Cheeso, entonces en ese caso, es posible. – Unknown
Se podría usar para implementar una interfaz de usuario de subprocesos múltiples, no más subprocesos únicos de interfaz de usuario. – luvieere
No creo que esto sea posible, ya que tiene que establecer múltiples referencias en una sola toma, y las operaciones entrelazadas tienen un poder limitado.
Por ejemplo, tome la operación de agregar: si está insertando el nodo B entre A y C, debe configurar B-> siguiente, B-> prev, A-> siguiente y C-> prev en uno operación atómica Interbloqueado no puede manejar eso. Preseleccionar los elementos de B ni siquiera ayuda, porque otro hilo podría decidir hacer una inserción mientras estás preparando "B".
Me centraría más en conseguir el bloqueo lo más fino posible en este caso, sin tratar de eliminarlo.
"conseguir el bloqueo tan fino como sea posible" - eso podría hacerlo más lento, ya que el costo de sacar muchos bloqueos cortos puede ser más significativo que el tiempo de espera evitado, dependiendo del comportamiento macro de la aplicación. –
Buen punto, Earwicker. La creación de perfiles sería beneficiosa aquí –
Esta respuesta es incorrecta. Se han implementado listas doblemente vinculadas. La clave es que el puntero trasero no siempre está actualizado y, por lo tanto, cuando retrocede, debe hacer un trabajo adicional. –
Yo diría que la respuesta es una muy calificada "sí, es posible, pero difícil". Para implementar lo que estás pidiendo, básicamente necesitarías algo que compilara las operaciones juntas para asegurar que no haya colisiones; como tal, sería muy difícil crear una implementación general para ese fin, y aún tendría algunas limitaciones significativas. Probablemente sería más simple crear una implementación específica adaptada a las necesidades precisas, e incluso entonces, no sería "simple" de ninguna manera.
"algo que compilaría las operaciones juntas para asegurar que no haya colisiones". ¿Qué significa eso? –
Piense en cómo las CPU modernas utilizan múltiples unidades de ejecución en un núcleo para lograr un alto rendimiento de la instrucción; se comprueba que las interacciones de las instrucciones con las unidades de ejecución no son interdependientes, y las microinstrucciones están intercaladas para preservar cualquier operación dependiente del orden. Es fundamentalmente una operación de compilación. –
Esto no es un problema, ya que la mayoría de los lenguajes proporcionan algún tipo de "barrera de memoria" que impide que el compilador y la CPU muevan operaciones de lectura/escritura más allá, por lo que puede asegurarse de que no reorganice las operaciones de una manera que invalida tu código. (Es por eso que se inventó la palabra clave volátil en c/C++, aunque volátil solo asegura esto contra otras variables volátiles, de ahí la introducción de barreras de memoria). –
Aquí hay un paper que describe una lista enlazada doble libre de bloqueo.
se presenta una implementación libre -bloqueo eficiente y práctica de un deque concurrente que es disjuntos paralelo accesible y utiliza primitivas atómicas que están disponibles en los sistemas informáticos modernos. Anteriormente algoritmos sin bloqueo conocidos de deques se basan bien en no disponibles primitivas de sincronización atómicas, única implementar un subconjunto de la funcionalidad , o no están diseñados para accesos disjuntos. Nuestro algoritmo se basa en una lista doblemente enlazada, y sólo requiere una sola palabra de 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 "Some notes on lock-free and wait-free algorithms".
Creo, sin embargo, que AFAIK, * TODAS * las listas doblemente enlazadas (y, de hecho, puede que incluso todas las listas con enlaces individuales) requieren GC. –
Creo que la lista de Valois de 1995 con un solo enlace no requiere GC; sin embargo, necesito leer el periódico. –
El papel Valois utiliza el recuento de referencias para garantizar la gestión de memoria sin bloqueo. El recuento de referencias representa el número de punteros globales al nodo. Además, cada subproceso mantiene una lista de riesgos de punteros a los nodos que está utilizando actualmente. Si un hilo desea eliminar un puntero de su lista de peligros que tiene un recuento de referencia de 0, tiene que escanear las listas de peligros de todos los otros hilos para ver si alguien todavía lo está usando, y solo eliminarlo de nadie. Existen algunos trucos relacionados con el escaneo seguro de las listas de peligros sin tener que realizar bloqueos. – JanKanis
FWIW, .NET 4.0 está agregando un ConcurrentLinkedList, una lista encuadernada con doble enlace en el sistema.Colecciones. Espacio de nombres concurrente. Puede leer el documentation o el blog post describiéndolo.
Threadsafe de ninguna manera significa que no tenga cerradura. –
Lea la nota - que planean sacar ConcurrentLinkedList de 4,0 antes de la versión final de VS2010
bien no se ha hecho se le preguntó cómo hacerlo. Pero, siempre que pueda hacer un CAS atómico en C#, es completamente posible.
De hecho, estoy trabajando en una implementación de una lista de espera doblemente enlazada en C++ en este momento.
Aquí hay un artículo que lo describe. http://www.cse.chalmers.se/~tsigas/papers/Haakan-Thesis.pdf
Y una presentación que también puede proporcionarle algunas pistas. http://www.ida.liu.se/~chrke/courses/MULTI/slides/Lock-Free_DoublyLinkedList.pdf
Sí, es posible, aquí está mi implementación de un STL-like Lock-Free Doubly-Linked List en C++.
Sample code that spawns threads to randomly perform ops on a list
Requiere un 64-bit de comparación y de intercambio para operar sin problemas ABA. Esta lista solo es posible debido a un lock-free memory manager.
Revisa el benchmarks on page 12. El rendimiento de la lista se escala linealmente con el número de subprocesos a medida que aumenta la contienda. El algoritmo admite el paralelismo para accesos disjuntos, por lo que a medida que aumenta el tamaño de la lista, la contienda puede disminuir.
Es posible escribir algoritmos sin bloqueo para todas las estructuras de datos copiables en la mayoría de las arquitecturas [1]. Pero es difícil escribir palabras eficientes.
Escribí implementation del lock-free doubly linked list by Håkan Sundell and Philippas Tsigas para .Net. Tenga en cuenta que no es compatible con PopLeft atómico debido al concepto.
[1]: Maurice Herlihy: Impossibility and universality results for wait-freesynchronization (1988)
bloqueo de la libre y esperar libre son diferentes .... cerradura libre significa algunos hilos pueden progresar, espere medio libre de todas las discusiones pueden hacer proceso. – user997112