xenium
v0.0.2: Merge pull request #19 from rbalint
xenium es una biblioteca de solo encabezado que proporciona una colección de estructuras de datos concurrentes y algoritmos de recuperación de memoria. Las estructuras de datos están parametrizadas para que puedan usarse con varios esquemas de recuperación (similar a cómo STL permite la personalización de asignadores).
La documentación proporciona más detalles.
Este proyecto se basa en mi trabajo anterior en https://github.com/mpoeter/emr
# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >
struct msg { ... };
xenium::ramalhete_queue<
std::unique_ptr<msg>,
xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
xenium::policy::entries_per_node< 2048 >
> queue;
queue.push(std::make_unique<msg>());
std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
// do something with data
}Por el momento, el número de estructuras de datos proporcionadas es bastante pequeño, ya que hasta ahora la atención se centraba en los esquemas de recuperación. Sin embargo, el plan es agregar varias estructuras de datos más en un futuro próximo.
michael_scott_queue : una cola multiproductor/multiconsumidor ilimitada y sin bloqueos propuesta por Michael y Scott [MS96].ramalhete_queue : una cola rápida, ilimitada y sin bloqueos para múltiples productores/multiconsumidores propuesta por Ramalhete [Ram16].vyukov_bounded_queue : una cola FIFO multiproductor/multiconsumidor limitada basada en la versión propuesta por Vyukov [Vyu10].kirsch_kfifo_queue : una cola k-FIFO ilimitada de múltiples productores/multiconsumidores propuesta por Kirsch et al. [KLP13].kirsch_bounded_kfifo_queue : una cola k-FIFO multiproductor/multiconsumidor limitada propuesta por Kirsch et al. [KLP13].nikolaev_queue : una cola ilimitada de múltiples productores/multiconsumidores propuesta por Nikolaev [Nik19].nikolaev_bounded_queue : una cola delimitada de múltiples productores/multiconsumidores propuesta por Nikolaev [Nik19].harris_michael_list_based_set : un contenedor sin cerradura que contiene un conjunto ordenado de objetos únicos. Esta estructura de datos se basa en la solución propuesta por Michael [Mic02] que se basa en la propuesta original de Harris [Har01].harris_michael_hash_map : un mapa hash sin bloqueo basado en la solución propuesta por Michael [Mic02] que se basa en la propuesta original de Harris [Har01].chase_work_stealing_deque - un deque de robo de obras basado en la propuesta de Chase y Lev [CL05].vyukov_hash_map : un mapa hash concurrente que utiliza bloqueo detallado para operaciones de actualización. Esta implementación está fuertemente inspirada en la versión propuesta por Vyukov [Vyu08].left_right : una implementación genérica del algoritmo LeftRight propuesto por Ramalhete y Correia [RC15].seqlock : una implementación del bloqueo de secuencia (también denominado a menudo "bloqueo secuencial"). La implementación de los esquemas de recuperación se basa en una versión adaptada de la interfaz propuesta por Robison [Rob13].
Se implementan los siguientes esquemas de recuperación:
lock_free_ref_count [Val95, MS95]hazard_pointer [Mic04]hazard_eras [RC17]quiescent_state_basedgeneric_epoch_based : este es un recuperador basado en épocas generalizado que se puede configurar de varias maneras. Para simplificar, los siguientes alias están predefinidos para las configuraciones correspondientes.epoch_based [Fra04]new_epoch_based [HMBW07]debra [hermano15]stamp_it [PT18a, PT18b] xenium es una biblioteca de solo encabezado, por lo que para usarla es suficiente incluir la carpeta xenium en su lista de directorios de inclusión. No se requieren otras bibliotecas de terceros. Sin embargo, la implementación utiliza características de C++17, por lo que se requiere un compilador con suficiente soporte para C++17. Los siguientes compiladores se utilizan en las compilaciones de CI y, por lo tanto, se sabe que son compatibles:
La prueba unitaria requiere googletest y los puntos de referencia requieren taocpp/json y taocpp/config . Estas dependencias se incluyen como submódulos, por lo que las pruebas unitarias y/o los puntos de referencia se pueden construir de la siguiente manera:
git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark
| [Hermano15] | Trevor Alexander Brown. Recuperar memoria para estructuras de datos sin bloqueos: tiene que haber una manera mejor. En Actas del Simposio ACM de 2015 sobre principios de informática distribuida (PODC) , páginas 261–270. ACM, 2015. |
| [CL05] | David Chase y Yossi Lev. Deque circular dinámico de robo de trabajo. En Actas del 17º Simposio Anual de ACM sobre Paralelismo en Algoritmos y Arquitecturas (SPAA) , páginas 21–28. ACM, 2005. |
| [fra04] | Keir Fraser. Práctica libertad de bloqueo . Tesis doctoral, Laboratorio de Computación de la Universidad de Cambridge, 2004. |
| [Har01] | Timoteo L. Harris. Una implementación pragmática de listas enlazadas sin bloqueo. En Actas de la 15ª Conferencia Internacional sobre Computación Distribuida (DISC) , páginas 300–314. Springer-Verlag, 2001. |
| [HMBW07] | Thomas E. Hart, Paul E. McKenney, Angela Demke Brown y Jonathan Walpole. Rendimiento de recuperación de memoria para sincronización sin bloqueo. Revista de Computación Paralela y Distribuida, 67(12):1270–1285, 2007. |
| [KLP13] | Christoph Kirsch, Michael Lippautz y Hannes Payer. Colas k-FIFO rápidas, escalables y sin bloqueos. En Actas de la Conferencia Internacional sobre Tecnologías de Computación Paralela (PaCT) , páginas 208–223, Springer-Verlag, 2013. |
| [Mic02] | Maged M. Michael. Tablas hash dinámicas sin bloqueos de alto rendimiento y conjuntos basados en listas. En Actas del 14º Simposio Anual de ACM sobre Arquitecturas y Algoritmos Paralelos (SPAA) , páginas 73–82. ACM, 2002. |
| [Mic04] | Maged M. Michael. Indicaciones de peligro: recuperación segura de memoria para objetos sin bloqueo. Transacciones IEEE en sistemas distribuidos y paralelos, 15(6):491–504, 2004. |
| [MS95] | Maged M. Michael y Michael L. Scott. Corrección de un método de gestión de memoria para estructuras de datos sin bloqueo. Informe técnico, Universidad de Rochester, 1995. |
| [MS96] | Maged M. Michael y Michael L. Scott. Algoritmos de colas concurrentes con bloqueo y sin bloqueo simples, rápidos y prácticos. En Actas del 15º Simposio Anual de ACM sobre Principios de Computación Distribuida (PODC) , páginas 267–275. ACM, 1996. |
| [Nik19] | Ruslan Nikolaev Una cola FIFO sin bloqueos, escalable, portátil y con un uso eficiente de la memoria. En Actas del 33º Simposio Internacional sobre Computación Distribuida (DISC) , 2019. |
| [PT18a] | Manuel Pöter y Jesper Larsson Träff. Breve anuncio: Stamp-it, un esquema de recuperación de memoria concurrente más eficiente para subprocesos en el modelo de memoria C++. En Actas del 30º Simposio Anual de ACM sobre Paralelismo en Algoritmos y Arquitecturas (SPAA) , páginas 355–358. ACM, 2018. |
| [PT18b] | Manuel Pöter y Jesper Larsson Träff. Stamp-it, un esquema de recuperación de memoria concurrente más eficiente para subprocesos en el modelo de memoria C++. Informe técnico, 2018. |
| [Ram16] | Pedro Ramalhete. FAAArrayQueue: cola sin bloqueo MPMC (parte 4 de 4). Blog, noviembre de 2016. |
| [RC15] | Pedro Ramalhete y Andreia Correia. Izquierda-Derecha: una técnica de control de concurrencia con lecturas ajenas a la población sin espera. octubre 2015 |
| [RC17] | Pedro Ramalhete y Andreia Correia. Breve anuncio: Eras de peligro: recuperación de memoria sin bloqueo. En Actas del 29º Simposio Anual de ACM sobre Paralelismo en Algoritmos y Arquitecturas (SPAA) , páginas 367–369. ACM, 2017. |
| [rob13] | Arco D. Robinson. Diseño basado en políticas para destrucción segura en contenedores concurrentes. Documento del comité de estándares de C++, 2013. |
| [Val95] | Juan D. Valois. Estructuras de datos sin bloqueo . Tesis doctoral, Instituto Politécnico Rensselaer, 1995. |
| [Vyu08] | Dmitri Vyukov. Mapa hash escalable. Publicación en Grupos de Google, 2008. |
| [Vyu10] | Dmitri Vyukov. Cola MPMC limitada simple y eficiente. Publicación en Grupos de Google, 2010. |
