Qualsiasi implementazione di coda libera con blocco singolo produttore single-consumer in C?

Question

Sto scrivendo un programma con un thread di consumo e un thread di produzione, ora sembra che la sincronizzazione delle code sia un grosso sovraccarico del programma, e ho cercato alcune implementazioni di lock free, ma ho trovato solo la versione di Lamport e una versione migliorata PPoPP '08:

enqueue_nonblock(data) { 
    if (NULL != buffer[head]) { 
     return EWOULDBLOCK; 
    } 
    buffer[head] = data; 
    head = NEXT(head); 
    return 0; 
} 

dequeue_nonblock(data) { 
    data = buffer[tail]; 
    if (NULL == data) { 
     return EWOULDBLOCK; 
    } 
    buffer[tail] = NULL; 
    tail = NEXT(tail); 
    return 0; 
} 

Entrambe le versioni richiedono una serie di pre-assegnato per i dati, la mia domanda è che esiste un unico produttore di implementazione di coda senza blocchi singolo consumatore che utilizza malloc() per allocare lo spazio in modo dinamico ?

E un'altra domanda correlata è: come posso misurare l'overhead esatto nella sincronizzazione della coda? Ad esempio quanto tempo ci vuole per pthread_mutex_lock(), ecc.

Answer 1

Se si è preoccupati per le prestazioni, l'aggiunta di malloc() al mix non aiuterà le cose. E se non sei preoccupato per le prestazioni, perché non controllare semplicemente l'accesso alla coda tramite un mutex. Avete effettivamente misurato le prestazioni di tale implementazione? Mi sembra che tu stia percorrendo la famosa strada dell'ottimizzazione prematura.

Answer 2

L'algoritmo che mostri riesce a funzionare perché sebbene i due thread condividano la risorsa (cioè la coda), la condividono in un modo molto particolare. Poiché solo un thread altera l'indice della coda (il produttore) e solo un thread altera l'indice di coda (consumatore, ovviamente), non è possibile ottenere uno stato incoerente dell'oggetto condiviso. È inoltre importante che il produttore inserisca i dati effettivi in ​​prima del aggiornando l'indice principale e che il consumatore legga i dati che desidera prima dello aggiornando l'indice di coda.

Funziona bene come fa b/c l'array è abbastanza statico; entrambi i thread possono contare sull'archiviazione per gli elementi presenti. Probabilmente non è possibile sostituire completamente la matrice, ma ciò che si può fare è modificare per che cosa viene utilizzata la matrice.

I.e., anziché conservare i dati nell'array, utilizzarlo per mantenere i puntatori ai dati. Quindi puoi malloc() e free() gli elementi di dati, passando i riferimenti (puntatori) a loro tra i tuoi thread tramite l'array.

Inoltre, posix supporta la lettura di un orologio in nanosecondi, anche se la precisione effettiva dipende dal sistema. Puoi leggere questo orologio ad alta risoluzione prima e dopo e solo sottrarre.

Answer 3

Mi ricordo di aver visto uno che sembrava interessante qualche anno fa, anche se non riesco a trovarlo ora. :(L'implementazione lock-free proposta richiedeva l'uso di uno CAS primitive, sebbene anche l'implementazione di blocco (se non si volesse utilizzare la primitiva CAS) avesse caratteristiche di perfezionamento piuttosto buone --- i blocchi impedivano solo più lettori o più produttori contemporaneamente non hanno mai corso con il consumatore

Io ricordo che il concetto fondamentale dietro la coda era creare un elenco collegato che aveva sempre un nodo "vuoto" in più Questo nodo in più significava che i puntatori di testa e di coda della lista si sarebbero riferiti sempre agli stessi dati quando la lista era vuota. Vorrei poter trovare la carta, non sto facendo giustizia all'algoritmo con la mia spiegazione. ..

AH-ha!

Ho trovato qualcuno che ha trascritto the algorithm without the remainder of the article. Questo potrebbe essere un utile punto di partenza.

Answer 4

Ho lavorato con un'implementazione di coda abbastanza semplice che soddisfa la maggior parte dei criteri. Ha usato un pool di byte di dimensioni massime statiche e quindi abbiamo implementato i messaggi all'interno di esso. C'era un puntatore di testa che si sarebbe mosso un processo e un puntatore di coda che l'altro processo avrebbe spostato.

I blocchi erano ancora necessari, ma abbiamo utilizzato Peterson's 2-Processor Algorithm, che è piuttosto leggero poiché non prevede chiamate di sistema. Il blocco è richiesto solo per un'area molto piccola e ben delimitata: pochi cicli CPU al massimo, quindi non si blocca mai a lungo.

Answer 5

Penso che l'allocatore possa essere un problema di prestazioni. Puoi provare a utilizzare un allocatore di memoria multithread personalizzato, che utilizza un elenco collegato per mantenere i blocchi liberati. Se i tuoi blocchi non hanno (quasi) le stesse dimensioni, puoi implementare un "allocatore di memoria del sistema Buddy", che è molto veloce. Devi sincronizzare la coda (ring buffer) con un mutex.

Per evitare troppe sincronizzazioni, è possibile provare a scrivere/leggere più valori su/dalla coda ad ogni accesso.

Se si desidera ancora utilizzare gli algoritmi lock-free, è necessario utilizzare i dati preassegnati o utilizzare un allocatore lock-free. C'è un articolo su un allocatore senza blocchi "scalabile Lock-Free Memory allocazione dinamica", e l'implementazione Streamflow

Prima di iniziare con la roba gratis-Lock, guarda: Circular lock-free buffer

Answer 6

Sì.

Esistono numerose code multiple-writer multiple-lock senza blocco.

Ne ho implementato uno, di Michael e Scott, dal loro articolo del 1996.

I will (dopo altri test) rilascia una piccola libreria di strutture di dati lock-free (in C) che includerà questa coda.

Answer 7

L'aggiunta di malloc può annullare qualsiasi guadagno di prestazioni che si può ottenere e una struttura basata su lucchetto sarebbe altrettanto efficace. Questo perché Malloc richiede una sorta di blocco CAS sull'heap e quindi alcune forme di malloc hanno il loro lock in modo da poter bloccare il Memory Manager.

Per utilizzare malloc si avrebbe bisogno di pre allocare tutti i nodi e gestirli con un'altra coda ...

Nota si può fare qualche forma di matrice espandibile che avrebbe bisogno di bloccarlo se è stato ampliato.

Anche mentre i dispositivi di blocco sono bloccati sulla CPU, eseguono il blocco della memoria della placea e bloccano la memoria per la durata dell'istruzione e spesso bloccano la pipeline.

Answer 8

Si dovrebbe guardare la libreria FastFlow