Query Free Queue - Productor único, múltiples consumidores

Question

Estoy buscando un método para implementar una estructura de datos de cola sin bloque que admita un único productor y múltiples consumidores. He visto el método clásico de Maged Michael y Michael Scott (1996), pero su versión utiliza listas vinculadas. Me gustaría una implementación que haga uso de un buffer circular delimitado. Algo que usa variables atómicas?

En una nota lateral, no estoy seguro de por qué estos métodos clásicos están diseñados para listas vinculadas que requieren una gran cantidad de gestión de memoria dinámica. En un programa de subprocesos múltiples, todas las rutinas de administración de memoria están serializadas. ¿No estamos derrotando los beneficios de los métodos sin bloqueo al usarlos junto con estructuras dinámicas de datos?

Estoy intentando codificar esto en C/C++ usando la biblioteca pthread en una arquitectura Intel de 64 bits.

Gracias, Shirish

Answer 1

Para un buffer circular tradicional de un solo bloque Creo que esto simplemente no se puede hacer de manera segura con operaciones atómicas. Necesita hacer tanto en una lectura. Suponga que tiene una estructura que tiene esta:

uint8_t* buf; 
unsigned int size; // Actual max. buffer size 
unsigned int length; // Actual stored data length (suppose in write prohibited from being > size) 
unsigned int offset; // Start of current stored data 

En una lectura que hay que hacer lo siguiente (así es como he implementado todas maneras, puede intercambiar algunas medidas como voy a discutir después):

1. Comprobar si la longitud de lectura no superan almacena longitud
2. Comprobar si el desplazamiento + leer longitud no supere los límites de amortiguamiento
3. datos leídos
4. Aumentar el offset, disminuir la longitud

¿Qué debe hacer sincronizado (tan atómico) para que funcione? En realidad combinar los pasos 1 y 4 en un solo paso atómico, o para aclarar: hacer esto sincronizado:

1. cheque read_length, esto puede ser algo como read_length=min(read_length,length);
2. longitud disminución con read_length: length-=read_length
3. conseguir una copia local desde el desplazamiento unsigned int local_offset = offset
4. compensado con read_length aumento: offset+=read_length

Después que sólo puede hacerlo un establecimiento de memoria (o w lo que sea) comenzando desde su local_offset, verifique si su lectura abarca el tamaño circular del búfer (dividido en 2 memcpy's), .... Esto es 'bastante' seguro, su método de escritura aún podría escribir sobre la memoria que está leyendo, así que asegúrese de que su memoria intermedia sea lo suficientemente grande como para minimizar esa posibilidad.

Ahora, aunque puedo imaginar que puedes combinar 3 y 4 (supongo que eso es lo que hacen en el caso de lista enlazada) o incluso 1 y 2 en operaciones atómicas, no veo que hagas todo esto en un atómico operación :).

Sin embargo, puede intentar eliminar la verificación de "longitud" si sus consumidores son muy inteligentes y siempre sabrán qué leer. También necesitaría una nueva variable de woffset, porque el antiguo método de (desplazamiento + longitud)% de tamaño para determinar el desplazamiento de escritura ya no funcionaría. Tenga en cuenta que esto está cerca del caso de una lista vinculada, donde en realidad siempre lee un elemento (= tamaño fijo, conocido) de la lista.También aquí, si lo convierte en una lista circular, puede leer mucho o escribir en un puesto que esté leyendo en ese momento.

Finalmente: mi consejo, solo use bloqueos, uso una clase CircularBuffer, completamente segura para leer & escribiendo) para un transmisor de video en tiempo real 720p60 y no tengo problemas de velocidad desde el bloqueo.

Answer 2

El uso de un búfer circular hace que sea necesario un bloqueo, ya que es necesario bloquearlo para evitar que la cabeza pase la cola. Pero, de lo contrario, los punteros de cabeza y cola se pueden actualizar fácilmente de forma atómica. O en algunos casos, el almacenamiento intermedio puede ser tan grande que la sobrescritura no sea un problema. (En la vida real, verá esto en los sistemas de comercio automatizados, con buffers circulares dimensionados para almacenar X minutos de datos del mercado. Si está X minutos atrás, tiene muchísimo más problemas que sobreescribir su búfer).

Cuando implementé la cola de MS en C++, construí un asignador libre de bloqueo usando una pila, que es muy fácil de implementar. Si tengo MSQueue, entonces, en tiempo de compilación, sé sizeof (MSQueue :: node). Luego hago una pila de N búferes del tamaño requerido. El N puede crecer, es decir, si pop() devuelve nulo, es fácil pedirle al montón más bloques, y estos se envían a la pila. Fuera de la posible llamada de bloqueo para más memoria, esta es una operación sin bloqueo.

Tenga en cuenta que la T no puede tener un controlador no trivial. Trabajé en una versión que permitía dtors no triviales, que realmente funcionaba. Pero descubrí que era más fácil simplemente convertir la T en un puntero a la T que yo quería, donde el productor liberaba la propiedad y el consumidor adquiría la propiedad. Esto, por supuesto, requiere que la T se asigne utilizando métodos sin bloqueo, pero el mismo asignador que hice con la pila también funciona aquí.

En cualquier caso, el punto de la programación sin bloqueos no es que las estructuras de datos sean más lentas. Los puntos son los siguientes:

1. lock free me hace independiente del planificador. La programación basada en bloqueo depende del programador para asegurarse de que los titulares de un bloqueo se estén ejecutando para que puedan liberar el bloqueo. Esto es lo que causa la "inversión de prioridad". En Linux hay algunos atributos de bloqueo para asegurarse de que esto ocurra.
2. Si soy independiente del planificador, el sistema operativo tiene un tiempo mucho más fácil para administrar timeslices, y obtengo mucho menos cambio de contexto
3. es más fácil escribir programas multiproceso correctos utilizando métodos sin bloqueo ya que no tengo que preocuparme por interbloqueo, sincronización, sincronización, etc. Esto es especialmente cierto con las implementaciones de memoria compartida, donde un proceso podría fallar mientras se mantiene un bloqueo en la memoria compartida. y no hay forma de liberar el bloqueo
4. los métodos de bloqueo son mucho más fáciles de escalar. De hecho, he implementado métodos sin bloqueo utilizando mensajes a través de una red. cerraduras distribuidos como este son una pesadilla

Dicho esto, hay muchos casos en los que los métodos basados ​​en la cerradura son preferibles y/o requeridos

1. al actualizar cosas que son costosas o imposibles de copiar. La mayoría de los métodos sin bloqueo utilizan algún tipo de control de versiones, es decir, hacen una copia del objeto, lo actualizan y verifican si la versión compartida sigue siendo la misma que cuando la copiaron, y luego crean la versión actual de la versión actual. Vuelva a copiarlo, aplique la actualización y vuelva a verificar. Sigue haciendo esto hasta que funcione. Esto está bien cuando los objetos son pequeños, pero son grandes, o contienen controladores de archivos, etc., entonces no se recomienda.
2. La mayoría de los tipos son imposibles de acceder sin bloqueo, p. cualquier contenedor STL. Estos tienen invariantes que requieren acceso no atómico, por ejemplo, assert (vector.size() == vector.end() - vector.begin()). Entonces, si está actualizando/leyendo un vector compartido, debe bloquearlo.

Answer 3

Esta es una pregunta anterior, pero nadie ha proporcionado una solución aceptada. Entonces ofrezco esta información para otros que pueden estar buscando.

Esta página web: http://www.1024cores.net

proporciona algunas estructuras de datos lockfree/waitfree muy útiles con explicaciones detalladas.

Lo que está buscando es una solución sin bloqueos para el problema del lector/escritor.

Ver: http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem