Cola segura para subprocesos de escritor múltiple en C

Question

Estoy trabajando en una aplicación C multiproceso usando pthreads. Tengo un subproceso que escribe en una base de datos (la biblioteca de la base de datos solo se puede usar de manera segura en un solo subproceso) y varios subprocesos que recopilan datos, los procesan y luego necesitan enviar los resultados al subproceso de la base de datos para su almacenamiento. He visto en mencionar que es "posible" para hacer una cola segura de múltiples escritores en C, pero cada lugar que veo esto mencionado simplemente dice que es "demasiado complicado para este ejemplo". y simplemente demuestra una cola segura de un solo escritor.

Necesito lo siguiente:

• Inserción y extracción eficientes. Supongo que, como cualquier otra cola O (1), es posible poner y poner en cola.
• Memoria asignada dinámicamente, es decir, una estructura vinculada. Necesito no tener un límite arbitrario en el tamaño de la cola, por lo que una matriz realmente no es lo que estoy buscando.

EDITAR: Los hilos de lectura no deben girar en una cola vacía, ya que es probable que haya minutos de tiempo sin escrituras, con ráfagas cortas de grandes cantidades de escrituras.

Answer 1

Claro, hay colas sin bloqueo. Sin embargo, según lo que ha dicho en los comentarios, el rendimiento aquí no es del todo crítico, ya que de todos modos está creando un hilo por escritura.

Entonces, este es un caso de uso estándar para una variable de condición. Conviértase en una estructura que contenga un mutex, una variable de condición, una lista vinculada (o un búfer circular si lo desea) y un indicador de cancelación:

write:
    lock the mutex
    (optionally - check the cancel flag to prevent leaks of stuff on the list)
    add the event to the list
    signal the condition variable
    unlock the mutex

read:
   lock the mutex
   while (list is empty AND cancel is false):
       wait on the condition variable with the mutex
   if cancel is false:  // or "if list non-empty", depending on cancel semantics
       remove an event from the list
   unlock the mutex
   return event if we have one, else NULL meaning "cancelled"

cancel:
   lock the mutex
   set the cancel flag
   (optionally - dispose of anything on the list, since the reader will quit)
   signal the condition variable
   unlock the mutex

Si está utilizando una lista con nodos externos, es posible que desee asignar la memoria fuera del bloqueo de exclusión mutua, solo para reducir el tiempo de espera. Pero si diseña los eventos con un nodo de lista intrusivo, probablemente sea más fácil.

Editar: también puede admitir varios lectores (sin garantías portátiles para los que se obtiene un evento determinado) si al cancelar cambia la señal de " para "transmitir". Aunque no lo necesita, tampoco cuesta nada.

Answer 2

Si no necesita una cola libre de bloqueo, entonces podría terminar una cola existente con un bloqueo.

Mutex myQueueLock;
Queue myQueue; 
void mtQueuePush(int value)
{
    lock(myQueueLock);
    queuePush(myQueue, value);
    unlock(myQueueLock);
}
int mtQueueNext()
{
    lock(myQueueLock);
    int value = queueFront(myQueue);
    queuePop(myQueue);
    unlock(myQueueLock);
    return value;
}

Lo único después de eso es agregar algún tipo de manipulación para mtQueueNext cuando la cola está vacía.

EDITAR: Si tiene un solo lector, una cola sin bloqueo de un solo escritor, solo necesita tener un bloqueo alrededor de mtQueuePush, para evitar múltiples escritores simultáneos.

Hay una gran cantidad de colas sin bloqueo de un solo lector / escritor, sin embargo, la mayoría de ellas se implementan como clases de plantillas de C ++. Sin embargo, haga una búsqueda en Google y, si es necesario, descubra cómo reescribirlos en la letra C.

Answer 3

http://www.liblfds.org

Biblioteca de estructura de datos sin bloqueo escrita en C.

Tiene la cola M & amp; S.

Answer 4

Iría por múltiples colas de escritor único (una por hilo de escritor). Luego puede consultar this para saber cómo hacer que el lector individual lea las diversas colas.