¿Hay una clase de cola no bloqueable y segura para subprocesos en C++?cola segura para hilos sin bloqueo en C++?
Probablemente una pregunta básica pero no he estado haciendo C++ desde hace mucho tiempo ...
EDIT: eliminado el requisito de STL.
Suponiendo que su CPU tiene una comparación y intercambio de doble puntero (compxchg8b en 486 o superior, compxchg16b en la mayoría de las máquinas amd64 [no presente en algunos de los primeros modelos de Intel]) ... Hay un algoritmo here .
Actualización: No es difícil traducir esto a C++ si no tiene miedo de hacer un poco de trabajo. : P
Este algoritmo supone un "puntero con la etiqueta" estructura que se parece a esto:
// Be aware that copying this structure has to be done atomically...
template <class T>
struct pointer
{
T *ptr;
uintptr_t tag;
};
entonces usted quiere envolver las instrucciones lock cmpxchg{8|16}b con algunos asm en línea ...
Tal vez entonces puede escribir el nodo de cola de la siguiente 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 vincula a ...
@jldupont: -1 es demasiado harash para eso. Asveikau te dio un buen enlace a un algoritmo y solo lleva unos minutos traducirlo a C++. -1 está totalmente fuera de lugar aquí – Rom
... es por eso que no lo he votado a la baja ... solo le he dejado una marca. Si miras mi perfil, verás que soy muy generoso ... no verás muchos votos negativos entregados por mí. – jldupont
@asveikau: buena actualización ... ¡gracias! – jldupont
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.
OK, entonces: ¿qué tal, fuera de STL? – jldupont
Nada de lo que las garantías estándar serán seguras para hilos de todos modos. Sin embargo, las implementaciones reales pueden proporcionar sus propias garantías. –
Los contenedores STL no son seguros para subprocesos, debe implementar su tratamiento para el acceso concurrente.
Existe este proyecto (C++) que tiene como objetivo dar servicio a los accesos concurrentes: CPH STL
y paper about.
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 sobre los hilos.
Puede construir fácilmente una cola de este tipo además de STL y Boost, simplemente ajuste std::queue y boost::mutex en su clase personalizada.
es el impulso normalmente empaquetado en las distribuciones populares, p. Ubuntu, Fedora? – jldupont
Creo que sí, al menos las instalaciones de RHEL vanilla en mi trabajo siempre tienen una versión anterior de Boost en/usr/include que se pone en marcha. –
Tenga en cuenta que la pregunta original era sobre una cola * non-blocking *. Un mutex es una forma de bloqueo, por lo que es poco probable que califique. –
Debe implementarlo usted mismo o utilizar una biblioteca que lo implemente. Para hacerlo usted mismo, es posible que desee echar un vistazo a esto:
Gracias por el enlace. Parece que agregaría otra dependencia a mi proyecto: impulsar la biblioteca. ¿No? – jldupont
Eso es correcto. De todos modos, eventualmente usarás Boost si eres un desarrollador de C++. La sugerencia de Nikolai N Fetissov sobre boost :: mutex es buena. – KeatsPeeks
Ser un desarrollador de C++ no siempre conduce a Boost. Sé que todos aquí parecen encantarlo, pero muchos proyectos se llevan bien con él (e incluso lo prohíben). Eche un vistazo a cómo Chromium implementa esto. –
Esto parece haber sido un tema popular en el último año del Dr. Dobb:
El actualmente no oficial Boost.Lockfree es algo a tener en cuenta. Yo uso los tipos FIFO y atómico.
Puede ser demasiado tarde ahora. Para futuras referencias, esta es una buena implementación de colas sin bloqueo (integradas en seguridad de subprocesos con algunas advertencias).
Multi productor - consumidor Multi
http://moodycamel.com/blog/2014/a-fast-general-purpose-lock-free-queue-for-c++
https://github.com/cameron314/concurrentqueue
solo productor - consumidor individual
http://moodycamel.com/blog/2013/a-fast-lock-free-queue-for-c++
'boost :: lockfree :: queue'? – javapowered