Coda thread-safe multi-writer in C

Question

Sto lavorando ad un'applicazione C multi-thread usando pthreads. Ho un thread che scrive in un database (la libreria del database può essere utilizzata solo in un singolo thread) e diversi thread che raccolgono dati, li elaborano e quindi devono inviare i risultati al thread del database per l'archiviazione. Ho visto in menzionato che è "possibile" per rendere una coda sicura per più autori in C, ma ogni posto che vedo menzionato dice semplicemente che è "troppo complicato per questo esempio" e dimostra semplicemente una coda sicura per autore singolo.

Ho bisogno delle seguenti cose:

• Inserimento e rimozione efficienti. Suppongo che come qualsiasi altra coda O (1) sia possibile accodare e dequeueing.
• Memoria allocata dinamicamente, ovvero una struttura collegata. Non ho bisogno di avere un limite arbitrario sulla dimensione della coda, quindi un array non è proprio quello che sto cercando.

EDIT: I thread di lettura non devono girare su una coda vuota, poiché è probabile che ci siano minuti di tempo senza scritture, con brevi raffiche di un gran numero di scritture.

Answer 1

Certo, ci sono code senza lucchetto. Sulla base di ciò che hai detto nei commenti, tuttavia, le prestazioni qui non sono affatto critiche, poiché stai comunque creando un thread per scrittura.

Quindi, questo è un caso d'uso standard per una variabile di condizione. Renditi uno struct contenente un mutex, una variabile di condizione, un elenco collegato (o un buffer circolare se vuoi) e un flag di annullamento:

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

Se si utilizza un elenco con nodi esterni, è possibile che si desideri allocare la memoria all'esterno del blocco mutex, solo per ridurre il tempo di attesa. Ma se si progettano gli eventi con un nodo elenco invadente che è probabilmente il più semplice.

Modifica: puoi anche supportare più lettori (senza garanzie portatili per le quali si ottiene un determinato evento) se in annullamento si modifica il "segnale" " a "trasmettere". Anche se non ne hai bisogno, in realtà non costa nulla.

Answer 2

Se non hai bisogno di una coda senza blocco, puoi semplicemente avvolgere una coda esistente con un blocco.

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;
}

L'unica cosa dopo è aggiungere una sorta di handeling per mtQueueNext quando la coda è vuota.

EDIT: Se disponi di un singolo lettore, coda di blocco per singolo autore, devi solo avere un lucchetto intorno a mtQueuePush, per evitare più scrittori simultanei.

C'è un gran numero di code lockless per lettore / scrittore singolo, tuttavia la maggior parte di esse sono implementate come classi di modelli c ++. Tuttavia, esegui una ricerca su Google e, se necessario, scopri come riscriverli nella semplice C.

Answer 3

http://www.liblfds.org

Libreria di strutture dati senza lock scritta in C.

Ha la coda M & amp; S.

Answer 4

Vorrei scegliere più code per singolo writer (una per thread del writer). Quindi puoi controllare questo per sapere come far leggere le varie code al singolo lettore.