data c++ algorithm multithreading concurrency lock-free

c++ - data - buffer en c



Buffer circular sin bloqueo (14)

Así es como lo haría:

  • mapear la cola en una matriz
  • mantener el estado con una próxima lectura y los siguientes índices de escritura
  • mantener un vector de bits completo vacío alrededor

La inserción consiste en usar un CAS con un incremento y volcar en la siguiente escritura. Una vez que tenga una ranura, agregue su valor y luego configure el bit vacío / completo que coincida.

Las eliminaciones requieren una comprobación del bit antes de probar en subdesbordamientos, pero aparte de eso, son las mismas que para la escritura, pero utilizando el índice de lectura y borrando el bit vacío / completo.

Ten cuidado

  1. No soy un experto en estas cosas
  2. Las operaciones atómicas de ASM parecen ser muy lentas cuando las uso, por lo que si terminas con más de ellas, es posible que utilices bloqueos integrados dentro de las funciones de insertar / quitar. La teoría es que una única operación atómica para agarrar la cerradura seguida de (muy) pocas operaciones ASM no atómicas podría ser más rápida que la misma cosa hecha por varias operaciones atómicas. Pero para que esto funcione, se requiere una alineación manual o automática, por lo que todo es un bloque corto de ASM.

Estoy en el proceso de diseñar un sistema que se conecta a una o más transmisiones de datos y hacer algunos análisis sobre los datos que desencadenar eventos en función del resultado. En una configuración típica de productor / consumidor de subprocesos múltiples, tendré varios subprocesos de productor que colocan datos en una cola, y múltiples subprocesos de consumidor que leen los datos, y los consumidores solo están interesados ​​en el último punto de datos más n puntos. Los hilos del productor deberán bloquearse si el consumidor lento no puede mantener el ritmo y, por supuesto, los hilos del consumidor se bloquearán cuando no haya actualizaciones sin procesar. Usar una cola simultánea típica con bloqueo de lector / escritor funcionará muy bien, pero la velocidad de los datos que ingresan podría ser enorme, por lo que quería reducir mi sobrecarga de bloqueo, especialmente los bloqueos de escritor para los productores. Creo que un búfer circular sin bloqueo es lo que necesitaba.

Ahora dos preguntas:

  1. ¿Es la solución buffer circular sin bloqueo la respuesta?

  2. Si es así, antes de lanzar mi propia cuenta, ¿conoces alguna implementación pública que se ajuste a mi necesidad?

Todos los punteros en la implementación de un búfer circular sin bloqueo son siempre bienvenidos.

Por cierto, haciendo esto en C ++ en Linux.

Alguna información adicional:

El tiempo de respuesta es crítico para mi sistema. Idealmente, los hilos del consumidor querrán ver las actualizaciones lo antes posible, ya que una demora adicional de 1 milisegundo podría hacer que el sistema no tenga valor, o que valga mucho menos.

La idea de diseño a la que me inclino es un búfer circular semiclock donde la cadena de producción coloca los datos en el búfer lo más rápido posible, llamemos a la cabecera del búfer A, sin bloquear a menos que el búfer esté lleno, cuando A se encuentra con el final del búfer Z. Cada uno de los subprocesos contiene dos punteros al búfer circular, P y P n , donde P es el encabezado de búfer local del subproceso y P n es el enésimo elemento después de P. Cada subproceso del consumidor avanzará su P y P n una vez que termina de procesar la P actual y el final del puntero Z de la memoria intermedia se avanza con la Pn más lenta. Cuando P alcanza un valor A, lo que significa que no hay más nuevas actualizaciones que procesar, el consumidor gira y está ocupado esperando que A avance nuevamente. Si el hilo del consumidor gira durante demasiado tiempo, se puede poner en reposo y esperar a que una condición varíe, pero estoy de acuerdo con que el consumidor tome el ciclo de la CPU esperando la actualización porque eso no aumenta mi latencia (tendré más núcleos de CPU que hilos). Imagínese que tiene una pista circular, y el productor se está ejecutando frente a un grupo de consumidores, la clave está en ajustar el sistema para que el productor generalmente esté corriendo solo un paso por delante de los consumidores, y la mayoría de estas operaciones pueden ser hecho usando técnicas sin cerradura. Entiendo que obtener los detalles de la implementación correcta no es fácil ... está bien, es muy difícil, es por eso que quiero aprender de los errores de los demás antes de hacer algunos por mi cuenta.

Aunque esta es una vieja pregunta, nadie mencionó el DPDK sin anillo de DPDK. Es un buffer de anillo de alto rendimiento que admite múltiples productores y múltiples consumidores. También proporciona modos de consumidor único y de un solo productor, y el búfer en anillo está libre de espera en modo SPSC. Está escrito en C y admite múltiples arquitecturas.

Además, es compatible con los modos Bulk y Burst donde los artículos pueden ser enrutados / dequerados al por mayor. El diseño permite que múltiples consumidores o múltiples productores escriban en la cola al mismo tiempo simplemente reservando el espacio moviendo un puntero atómico.

Eche un vistazo a Disruptor ( Cómo usarlo ) que es un buffer de anillo al que múltiples hilos pueden suscribirse:

El requisito de que los productores o consumidores bloqueen si el almacenamiento intermedio está vacío o lleno sugiere que debe usar una estructura de datos de bloqueo normal, con semáforos o variables de condición para bloquear a los productores y consumidores hasta que haya datos disponibles. El código de bloqueo generalmente no bloquea en tales condiciones: hace girar o abandona operaciones que no se pueden hacer en lugar de bloquear usando el sistema operativo. (Si puede permitirse esperar hasta que otro hilo produzca o consuma datos, ¿por qué está esperando un bloqueo para que otro hilo termine de actualizar la estructura de datos?)

En (x86 / x64) Linux, la sincronización entre subprocesos con mutexes es razonablemente barata si no hay contención. Concéntrese en minimizar el tiempo que los productores y consumidores necesitan para mantener sus cerraduras. Dado que has dicho que solo te importan los últimos N puntos de datos registrados, creo que un buffer circular sería hacerlo razonablemente bien. Sin embargo, realmente no entiendo cómo encaja esto con el requisito de bloqueo y la idea de que los consumidores realmente consuman (eliminen) los datos que leen. (¿Desea que los consumidores solo observen los últimos N puntos de datos y no los eliminen? ¿Desea que a los productores no les importe si los consumidores no pueden mantener el ritmo y simplemente sobrescriben los datos antiguos?)

Además, como ha comentado Zan Lynx, puedes agregar / almacenar tus datos en trozos más grandes cuando tienes muchos de ellos entrando. Puedes almacenar un número fijo de puntos, o todos los datos recibidos dentro de una cierta cantidad de tiempo. . Esto significa que habrá menos operaciones de sincronización. Sin embargo, introduce latencia, pero si no está utilizando Linux en tiempo real, tendrá que lidiar con eso de todos modos.

Hay una serie bastante buena de artículos sobre esto en DDJ . Como una señal de lo difícil que puede ser esto, es una corrección en un artículo anterior que lo hizo mal. Asegúrate de entender los errores antes de tirar los tuyos) -;

He hecho un estudio particular de las estructuras de datos sin bloqueo en los últimos años. He leído la mayoría de los artículos sobre el terreno (solo hay unos cuarenta, aunque solo unos diez o quince son útiles) :-)

AFAIK, un búfer circular sin bloqueo no se ha inventado. El problema será lidiar con la compleja condición en que un lector se adelanta a un escritor o viceversa.

Si no has pasado al menos seis meses estudiando las estructuras de datos sin bloqueo, no intentes escribir una tú mismo. Se equivocará y puede que no sea obvio para usted que existen errores, hasta que su código falle, después de la implementación, en nuevas plataformas.

Sin embargo, creo que hay una solución a su requerimiento.

Debe emparejar una cola libre de bloqueos con una lista libre sin bloqueos.

La lista libre le dará preasignación y así obviará el requisito (fiscalmente costoso) de un asignador sin bloqueo; cuando la lista libre está vacía, se replica el comportamiento de un búfer circular al quitar de forma instantánea un elemento de la cola y usarlo en su lugar.

(Por supuesto, en un búfer circular basado en bloqueo, una vez que se obtiene el bloqueo, la obtención de un elemento es muy rápida, básicamente una desreferencia del puntero, pero no se obtiene en ningún algoritmo sin bloqueos; a menudo tienen que irse bien fuera de su camino para hacer cosas, la sobrecarga de fallar un pop de lista libre seguido de una dequeue está a la par con la cantidad de trabajo que cualquier algoritmo de lock-free deberá estar haciendo).

Michael y Scott desarrollaron una muy buena cola libre de bloqueos en 1996. Un enlace a continuación le dará los detalles suficientes para rastrear el PDF de su trabajo; Michael y Scott, FIFO

Una lista libre sin bloqueos es el algoritmo de bloqueo más simple y, de hecho, no creo haber visto un documento real.

La cola de Sutter no es óptima y él lo sabe. La programación de Art of Multicore es una gran referencia, pero no confíes en los chicos de Java en los modelos de memoria, punto. Los enlaces de Ross no le darán una respuesta definitiva porque tenían sus bibliotecas en tales problemas y demás.

Hacer una programación sin bloqueos es buscar problemas, a menos que quieras pasar mucho tiempo en algo que claramente estás sobreingeniería antes de resolver el problema (a juzgar por la descripción del mismo, es una locura común "buscar la perfección"). ''en coherencia del caché). Lleva años y lleva a que no se resuelvan primero los problemas y luego se optimice, una enfermedad común.

La implementación en la biblioteca de impulso vale la pena considerarla. Es fácil de usar y tiene un rendimiento bastante alto. Escribí una prueba y la ejecuté en una computadora portátil quad core i7 (8 hilos) y obtuve ~ 4M enqueue / dequeue operaciones por segundo. Otra implementación no mencionada hasta ahora es la cola de MPMC en http://moodycamel.com/blog/2014/detailed-design-of-a-lock-free-queue . He hecho algunas pruebas simples con esta implementación en la misma computadora portátil con 32 productores y 32 consumidores. Es, como se anuncia, más rápido que la cola impulso sin bloqueo.

Como la mayoría de las otras respuestas indican que la programación sin bloqueos es difícil. La mayoría de las implementaciones tendrán casos de esquina difíciles de detectar que requieran una gran cantidad de pruebas y depuración para solucionarlos. Estos se suelen solucionar con una colocación cuidadosa de las barreras de memoria en el código. También encontrará pruebas de corrección publicadas en muchos de los artículos académicos. Prefiero probar estas implementaciones con una herramienta de fuerza bruta. Se debe verificar la corrección de cualquier algoritmo sin bloqueo que planee usar en producción con una herramienta como http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html .

No soy experto en modelos de memoria de hardware y bloqueo las estructuras de datos libres y tiendo a evitar usar esos en mis proyectos y voy con las estructuras de datos bloqueadas tradicionales.

Sin embargo, hace poco noté ese video: cola SPSC sin bloqueo basada en el buffer de anillo

Esto se basa en una biblioteca Java de alto rendimiento de código abierto llamada distrupto LMAX utilizada por un sistema comercial: LMAX Distruptor

Según la presentación anterior, los punteros de la cabeza y la cola son atómicos y atómicos para verificar si la cabeza atrapa la cola desde atrás o viceversa.

A continuación puede ver una implementación muy básica de C ++ 11:

// USING SEQUENTIAL MEMORY #include<thread> #include<atomic> #include <cinttypes> using namespace std; #define RING_BUFFER_SIZE 1024 // power of 2 for efficient % class lockless_ring_buffer_spsc { public : lockless_ring_buffer_spsc() { write.store(0); read.store(0); } bool try_push(int64_t val) { const auto current_tail = write.load(); const auto next_tail = increment(current_tail); if (next_tail != read.load()) { buffer[current_tail] = val; write.store(next_tail); return true; } return false; } void push(int64_t val) { while( ! try_push(val) ); // TODO: exponential backoff / sleep } bool try_pop(int64_t* pval) { auto currentHead = read.load(); if (currentHead == write.load()) { return false; } *pval = buffer[currentHead]; read.store(increment(currentHead)); return true; } int64_t pop() { int64_t ret; while( ! try_pop(&ret) ); // TODO: exponential backoff / sleep return ret; } private : std::atomic<int64_t> write; std::atomic<int64_t> read; static const int64_t size = RING_BUFFER_SIZE; int64_t buffer[RING_BUFFER_SIZE]; int64_t increment(int n) { return (n + 1) % size; } }; int main (int argc, char** argv) { lockless_ring_buffer_spsc queue; std::thread write_thread( [&] () { for(int i = 0; i<1000000; i++) { queue.push(i); } } // End of lambda expression ); std::thread read_thread( [&] () { for(int i = 0; i<1000000; i++) { queue.pop(); } } // End of lambda expression ); write_thread.join(); read_thread.join(); return 0; }

Solo para completar: hay un buffer circular sin bloqueos bien probado en OtlContainers , pero está escrito en Delphi (TOmniBaseBoundedQueue es un buffer circular y TOmniBaseBoundedStack es una pila limitada). También hay una cola ilimitada en la misma unidad (TOmniBaseQueue). La cola ilimitada se describe en la cola Dynamic lock-free: hacer las cosas bien . La implementación inicial de la cola acotada (memoria intermedia circular) se describió en una cola libre de bloqueos, ¡por fin! pero el código se actualizó desde entonces.

Una técnica útil para reducir la controversia es agrupar los elementos en múltiples colas y hacer que cada consumidor se dedique a un "tema".

Para la cantidad más reciente de artículos que les interesan a sus consumidores: no desea bloquear toda la cola e iterar sobre ella para encontrar un elemento que anular; simplemente publique artículos en N-tuplas, es decir, todos los N artículos recientes. Puntos de bonificación para la implementación en los que el productor bloquearía la cola completa (cuando los consumidores no pueden mantener el ritmo) con un tiempo de espera, actualizando su caché de tupla local, de esa manera no se reduce la presión sobre la fuente de datos.

Estoy de acuerdo con este artículo y recomiendo evitar el uso de estructuras de datos sin bloqueo. Un artículo relativamente reciente sobre colas de fifo libres de cerrojo es this , búsqueda de más documentos del mismo autor (es); también hay una tesis doctoral sobre Chalmers sobre estructuras de datos sin bloqueo (perdí el enlace). Sin embargo, no dijiste qué tan grandes son tus elementos: las estructuras de datos sin bloqueo funcionan eficientemente solo con elementos de tamaño de palabra, por lo que tendrás que asignar dinámicamente tus elementos si son más grandes que una palabra de máquina (32 o 64) bits). Si asigna dinámicamente elementos, cambia el supuesto (dado que no ha perfilado su programa y básicamente realiza una optimización prematura) cuello de botella al asignador de memoria, por lo que necesita un asignador de memoria sin bloqueo, por ejemplo, Streamflow , e integrar con tu aplicación