¿Cola segura para subprocesos sin bloqueo en C ++?
-
10-07-2019 - |
Pregunta
¿Hay una clase de cola sin bloqueo y segura para subprocesos en C ++?
Probablemente una pregunta básica, pero no he estado haciendo C ++ durante mucho tiempo ...
EDITAR: eliminó el requisito de STL.
Solución
Suponiendo que su CPU tiene una comparación e intercambio de doble puntero (compxchg8b en 486 o superior, compxchg16b en la mayoría de las máquinas amd64 [no está presente en algunos modelos anteriores de Intel]) ... Hay un algoritmo aquí .
Actualización: no es difícil traducir esto a C ++ si no tienes miedo de hacer un poco de trabajo. : P
Este algoritmo asume un "puntero con etiqueta" estructura que se ve así:
// Be aware that copying this structure has to be done atomically...
template <class T>
struct pointer
{
T *ptr;
uintptr_t tag;
};
Entonces desea ajustar las instrucciones lock cmpxchg {8 | 16} b
con algunos asm en línea ...
Quizás pueda escribir el nodo de la cola de esta manera:
template <class T>
struct queue_node
{
T value;
pointer<queue_node<T> > next;
};
El resto es más o menos una transcripción del algoritmo que he vinculado a ...
Otros consejos
Dado que el estándar actual de C ++ ni siquiera reconoce la existencia de subprocesos, ciertamente no hay nada seguro para subprocesos en el STL o en cualquier otra parte de la biblioteca estándar.
Esto parece haber sido un tema popular en el último año del Dr. Dobb:
Debe implementarlo usted mismo o usar una biblioteca que lo implemente. Para hacerlo usted mismo, puede echarle un vistazo a esto:
Implementando un hilo -Cola segura usando variables de condición
Respuesta corta: no. STL no se preocupa por la concurrencia (al menos en el nivel de especificación). El estándar actual de C ++ no dice nada acerca de los hilos.
Sin embargo, puede crear fácilmente una cola de este tipo sobre STL y Boost: simplemente envuelva std :: queue
y boost :: mutex
en su clase personalizada.
Los contenedores STL no son seguros para subprocesos, debe implementar su tratamiento para el acceso concurrente.
Existe este proyecto (C ++) que tiene como objetivo servir accesos concurrentes: CPH STL
y documento sobre .
Puede ser demasiado tarde ahora. Para referencia futura, esta es una buena implementación de colas sin bloqueo (seguridad integrada de subprocesos con algunas advertencias).
Productor múltiple - Consumidor múltiple
http: // moodycamel. com / blog / 2014 / a-fast-general-purpose-lock-free-queue-for-c ++
https://github.com/cameron314/concurrentqueue
Productor único - Consumidor único
http://moodycamel.com/blog/ 2013 / a-fast-lock-free-queue-for-c ++
El Boost.Lockfree es actualmente no oficial Algo a tener en cuenta. Yo uso los tipos FIFO y atómico.