He pasado hoy buscando colas sin cerradura. Tengo un productor múltiple, situación de múltiples consumidores. Implementé, para probar, un sistema que utiliza la función de lista de interbloqueo bajo Win32 y duplicó el rendimiento de mi código basado en tareas fuertemente subprocesado. Desafortunadamente, sin embargo, deseo soportar múltiples plataformas. El enclavamiento en múltiples plataformas en sí mismo no es un problema y puedo asumir con seguridad que puedo enclavar sin problemas. Sin embargo, la implementación real me pierde.

El gran problema parece ser que necesita garantizar que una lista de inserción / pop utilizará solo una llamada entrelazada. De lo contrario, está dejando espacio para que otra rosca se pellizque y estropee las cosas. No estoy seguro de cómo funciona la implementación de Microsoft bajo el capó y me encantaría saber más.

¿Alguien puede indicarme información útil (la plataforma y el lenguaje son bastante irrelevantes)?

Además, me encantaría saber si es posible implementar un vector sin bloqueo. Eso tendría enormes cantidades de uso para mí :) ¡Saludos!

Edición: Habiendo leído el artículo de DDJ de herb, puedo ver una cola de bloqueo reducida que es bastante similar a la que ya tenía. Sin embargo, me doy cuenta de que hay papeles al final que pueden hacer la verdadera cola sin bloqueo usando una operación doble de comparación e intercambio (DCAS). ¿Alguien ha implementado una cola usando cmpxchg8b (o cmpxchg16b para el caso)?

Solo estoy reflexionando en este punto (no habiendo leído los artículos) pero podría usar este sistema para actualizar el puntero de la cabeza y la cola simultáneamente y así evitar cualquier problema con otro salto de hilo entre las dos operaciones atómicas. Sin embargo, aún debe obtener el siguiente puntero de cabeza para probar eso contra el puntero de la cola para ver si acaba de modificar la cola. ¿Cómo evita que otro hilo cambie esta información mientras el otro hilo se está preparando para hacerlo? ¿Cómo se implementa esto de una manera segura? ¿O estoy mejor leyendo la indescifabilidad que es un trabajo de investigación? ;)