lockfree

sin cerradura

lockfree es una colección de estructuras de datos sin bloqueo escritas en C++ 11 estándar y adecuadas para todas las plataformas, desde profundamente integradas hasta HPC.

¿Qué son las estructuras de datos sin bloqueo?

Las estructuras de datos sin bloqueo son estructuras de datos que son seguras para subprocesos e interrupciones para uso simultáneo sin tener que utilizar mecanismos de exclusión mutua. Son más útiles para la comunicación entre procesos y, a menudo, escalan mucho mejor que las estructuras basadas en bloqueos con la cantidad de operaciones y subprocesos.

¿Por qué usar lockfree

• Escrito en C++ 11 estándar, compatible con todas las plataformas que lo soportan.
• Todas las estructuras de datos son seguras para subprocesos e interrupciones en sus respectivos casos de uso.
• Sin asignación dinámica
• Optimizado para un alto rendimiento
• Licencia MIT
• API adicionales para versiones más recientes de C++

¿Qué estructuras de datos están disponibles?

Estructuras de datos de un solo productor y un solo consumidor

• Cola: la mejor para operaciones de un solo elemento, API simple y extremadamente rápida que consta de solo 2 métodos.
• Ring Buffer: una estructura de datos más general con la capacidad de manejar múltiples elementos a la vez, utiliza copias de biblioteca estándar, lo que la hace muy rápida para operaciones masivas.
• Búfer bipartito: una variación del búfer en anillo con la capacidad de proporcionar siempre un espacio lineal en el búfer, permite el procesamiento dentro del búfer.
• Cola de prioridad: una variación de la cola con la capacidad de proporcionar diferentes prioridades para los elementos, muy útil para cosas como señales, eventos y paquetes de comunicación.

Estas estructuras de datos tienen más rendimiento y generalmente deben usarse siempre que solo haya un hilo/interrupción enviando datos y otro recuperándolos.

Estructuras de datos multiproductor y multiconsumidor

• Cola: la mejor para operaciones de un solo elemento, API simple y extremadamente rápida que consta de solo 2 métodos.
• Cola de prioridad: una variación de la cola con la capacidad de proporcionar diferentes prioridades para los elementos, muy útil para cosas como señales, eventos y paquetes de comunicación.

Estas estructuras de datos son más generales y admiten múltiples productores y consumidores al mismo tiempo; sin embargo, tienen una sobrecarga de almacenamiento y rendimiento en comparación con las estructuras de datos de un solo productor y un solo consumidor. También requieren instrucciones atómicas que pueden faltar en algunos microcontroladores de gama baja.

como llegar

Hay tres formas principales de obtener la biblioteca:

• Usando CMake FetchContent()
• Como un submódulo de git
• Descargando una versión de GitHub

Configuración

lockfree utiliza la alineación de la línea de caché para los índices para evitar el fenómeno de intercambio falso de forma predeterminada, evitando la pérdida de rendimiento de la invalidación de la línea de caché en sistemas coherentes con la caché. Esto alinea los índices con LOCKFREE_CACHELINE_LENGTH , 64 de forma predeterminada.

En sistemas integrados, LOCKFREE_CACHE_COHERENT casi siempre debe establecerse como false para evitar desperdiciar memoria.

Además, algunos sistemas tienen una longitud de línea de caché no típica (por ejemplo, las CPU Apple M1/M2 tienen una longitud de línea de caché de 128 bytes), y LOCKFREE_CACHELINE_LENGTH debe configurarse en consecuencia en esos casos.

Limitaciones conocidas

Todas las estructuras de datos en lockfree solo deben usarse para tipos triviales.

Preguntas frecuentes

¿Por qué debería usar esto para bloquear estructuras de datos en una máquina alojada?

La razón principal por la que desearía utilizar una estructura de datos sin bloqueos en entornos alojados sería evitar problemas relacionados con el bloqueo, como interbloqueos, inversión de prioridad y latencia de acceso no determinista. Cuando se usan correctamente, las estructuras de datos sin bloqueos también pueden mejorar el rendimiento en algunos escenarios.

Además, lockfree proporciona una forma de crear aplicaciones y bibliotecas que se pueden compilar para funcionar en entornos POSIX y no POSIX sin #ifdef so polimorfismo.

¿Por qué utilizar esto en lugar de los mecanismos IPC proporcionados por RTOS en un sistema integrado?

Si bien el bloqueo generalmente no es costoso en sistemas integrados como los microcontroladores, existe una amplia variedad de RTOS y no hay una API estandarizada para el bloqueo. El hecho de que haya múltiples arquitecturas desde 8051 hasta RISC-V significa que los métodos de gestión de interrupciones tampoco están estandarizados.

lockfree proporciona una forma de crear código integrado portátil con un costo de rendimiento insignificante en comparación con el bloqueo; el código que utiliza lockfree se puede compilar para ejecutarse en cualquier plataforma integrada que admita C++ 11. Además, el código se puede probar fácilmente en una máquina host sin necesidad de burlarse.

¿Qué ventajas ofrece a la biblioteca el uso de C++ sobre C?

• Seguridad de tipos, ya que las estructuras de datos tienen plantillas de tipo y tamaño.
• Creación de instancias mucho más simple y menos propensa a errores
• Mayor rendimiento debido al tamaño conocido en tiempo de compilación y la implementación de solo encabezado
• Encapsulación, el búfer de datos es un miembro de la clase en lugar de ser pasado por un puntero

¿Cuál es la clasificación formal de las estructuras de datos en lockfree ?

Todas las estructuras en lockfree están limitadas , basadas en matrices y sin bloqueos , las estructuras de datos spsc también están libres de espera y son seguras para la terminación .

Teoría y referencias.

Para obtener más información sobre la programación sin bloqueos, consulte:

• Esta brillante serie de charlas de Herb Sutter
• Serie de charlas Live Lock-Free o Deadlock de Fedor Pikus
• Excelente blog de Dmitry Vyukov