¿Cola segura para subprocesos sin bloqueo en C ++?

StackOverflow https://stackoverflow.com/questions/1645326

  •  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.

¿Fue útil?

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 ++

https://github.com/cameron314/readerwriterqueue

El Boost.Lockfree es actualmente no oficial Algo a tener en cuenta. Yo uso los tipos FIFO y atómico.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top