c++ - rslogix - que son los tags en plc

Cola libre de bloqueo-Productor individual, consumidores múltiples

Question

Estoy buscando un método para implementar una estructura de datos de cola sin bloqueo que admita un solo productor y varios consumidores. He visto el método clásico de Maged Michael y Michael Scott (1996) pero su versión usa listas enlazadas. Me gustaría una implementación que haga uso de un búfer circular acotado. ¿Algo que utiliza variables atómicas?

En una nota al margen, no estoy seguro de por qué estos métodos clásicos están diseñados para listas enlazadas que requieren una gran cantidad de administración dinámica de memoria. En un programa multihilo, 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 de datos dinámicos?

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

Gracias sherish

Answer 1

El uso de un amortiguador circular hace que sea necesario un bloqueo, ya que el bloqueo es necesario para evitar que la cabeza pase la cola. Pero por lo demás, los punteros de cabeza y cola pueden actualizarse fácilmente de forma atómica. O en algunos casos, el búfer puede ser tan grande que la sobrescritura no es un problema. (en la vida real, verá esto en los sistemas de comercio automatizado, con buffers circulares dimensionados para contener X minutos de datos del mercado. Si está X minutos atrás, tiene problemas peores que sobrescribir su buffer).

Cuando implementé la cola de MS en C ++, construí un asignador sin bloqueo utilizando una pila, que es muy fácil de implementar. Si tengo MSQueue entonces en el momento de la compilación sé sizeof (MSQueue :: node). Luego hago una pila de N buffers del tamaño requerido. La N puede crecer, es decir, si pop () devuelve un valor nulo, es fácil ir a pedir más bloques y estos se insertan en la pila. Fuera de la posible llamada de bloqueo para obtener más memoria, esta es una operación sin bloqueo.

Tenga en cuenta que la T no puede tener un dtor no trivial. Trabajé en una versión que permitía dorsores no triviales, que realmente funcionó. Pero descubrí que era más fácil hacer que la T fuera un puntero a la T que quería, donde el productor liberaba la propiedad y el consumidor adquiría la propiedad. Por supuesto, esto requiere que la propia T se asigne utilizando métodos de bloqueo libre, pero el mismo asignador que hice con la pila también funciona aquí.

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

1. lock free me hace independiente del programador. 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 suceda
2. Si soy independiente del programador, el sistema operativo tiene un tiempo mucho más fácil de administrar los intervalos de tiempo, y tengo mucho menos cambio de contexto
3. es más fácil escribir programas de multiproceso correctos usando métodos de bloqueo libre, ya que no tengo que preocuparme por el bloqueo, el bloqueo, la programación, la sincronización, etc. no hay manera de liberar la cerradura
4. Los métodos de bloqueo libre son mucho más fáciles de escalar. De hecho, he implementado métodos de bloqueo libre mediante el uso de mensajes a través de una red. Cerraduras distribuidas como esta son una pesadilla.

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

1. Al actualizar cosas que son caras 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 comprueban si la versión compartida sigue siendo la misma que cuando la copia, luego la versión actual que actualices. 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 identificadores de archivos, etc., entonces no se recomienda
2. La mayoría de los tipos son imposibles de acceder de forma libre de bloqueo, por ejemplo, cualquier contenedor STL. Estos tienen invariantes que requieren acceso no atómico, por ejemplo, aseverar (vector.size () == vector.end () - vector.begin ()). Por lo tanto, si está actualizando / leyendo un vector que se comparte, debe bloquearlo.

Answer 2

Esta es una pregunta antigua, pero nadie ha proporcionado una respuesta que responda con precisión. Dado que aún aparece alto en los resultados de búsqueda para (casi) la misma pregunta, debería haber una respuesta, dado que existe una.

Puede haber más de una solución, pero aquí hay una que tiene una implementación: https://github.com/tudinfse/FFQ El documento de conferencia al que se hace referencia en el archivo Léame detalla el algoritmo.

Answer 3

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

Este sitio web: http://www.1024cores.net

Proporciona algunas estructuras de datos realmente útiles de lockfree / waitfree con explicaciones detalladas.

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

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

Answer 4

Para un búfer circular de un bloque tradicional, creo que esto simplemente no se puede hacer de manera segura con operaciones atómicas. Necesitas hacer mucho en una lectura. Supongamos que tienes una estructura que tiene esto:

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, debe hacer lo siguiente (así es como lo implementé de todos modos, puede intercambiar algunos pasos, como veré más adelante):

1. Compruebe si la longitud de lectura no supera la longitud almacenada
2. Compruebe si la longitud de lectura offset + no supera los límites de la memoria intermedia
3. Leer datos
4. Aumente el offset, disminuya la longitud

¿Qué deberías hacer de forma sincronizada (tan atómica) para que esto funcione? En realidad, combine los pasos 1 y 4 en un paso atómico, o para aclarar: haga esto sincronizado:

1. verifique read_length, esto puede ser algo como read_length=min(read_length,length);
2. disminuir longitud con read_length: length-=read_length
3. obtener una copia local de offset unsigned int local_offset = offset
4. aumentar el desplazamiento con read_length: offset+=read_length

Luego, solo puede hacer un memcpy (o lo que sea) comenzando desde su local_offset, verifique si su lectura supera el tamaño del búfer circular (dividido en 2 memcpy), .... Esto es ''bastante'' seguro para subprocesos, su método de escritura aún podría escribir sobre la memoria que está leyendo, así que asegúrese de que su búfer 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 la lista enlazada) o incluso 1 y 2 en operaciones atómicas, no puedo ver que hagas todo esto en una sola operación atómica :).

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

Finalmente: mi consejo, solo vaya con candados, uso una clase CircularBuffer, completamente segura para leer y escribir, para un transmisor de video en tiempo real de 720p60 y no tengo problemas de velocidad en absoluto desde el bloqueo.