Buscando la derecha aplicación búfer de anillo en C

Question

Busco a una implementación de búfer de anillo (o pseudocódigo) en C con las siguientes características:

• productor múltiple único patrón de consumo (MPSC)
• bloques de consumo en vacíos
• productores bloquear en el pleno
• -cerradura libre (espero alta contención)

Hasta ahora yo' He estado trabajando solo con buffers SPSC, uno por productor, pero me gustaría evitar el giro continuo del consumidor para buscar nuevos datos en todos sus buffers de entrada (y quizás para deshacerme de algunos hilos de cálculo en mi sistema).

Desarrollo para Linux en máquinas Intel.

Answer 1

Creo que tengo lo que estás buscando. Es una implementación de búfer de anillo sin bloqueo que bloquea productor/consumidor. Solo necesita acceder a primitivas atómicas; en este ejemplo usaré las funciones sync de gcc.

Tiene un error conocido: si desborda el búfer en más del 100%, no se garantiza que la cola siga siendo FIFO (aún así los procesará).

Esta aplicación se basa en la lectura/escritura de los elementos de amortiguación como una operación atómica (que está prácticamente garantizado para los punteros)

struct ringBuffer 
{ 
    void** buffer; 
    uint64_t writePosition; 
    size_t size; 
    sem_t* semaphore; 
} 

//create the ring buffer 
struct ringBuffer* buf = calloc(1, sizeof(struct ringBuffer)); 
buf->buffer = calloc(bufferSize, sizeof(void*)); 
buf->size = bufferSize; 
buf->semaphore = malloc(sizeof(sem_t)); 
sem_init(buf->semaphore, 0, 0); 

//producer 
void addToBuffer(void* newValue, struct ringBuffer* buf) 
{ 
    uint64_t writepos = __sync_fetch_and_add(&buf->writePosition, 1) % buf->size; 

    //spin lock until buffer space available 
    while(!__sync_bool_compare_and_swap(&(buf->buffer[writePosition]), NULL, newValue)); 
    sem_post(buf->semaphore); 
}  

//consumer 
void processBuffer(struct ringBuffer* buf) 
{ 
    uint64_t readPos = 0; 
    while(1) 
    { 
     sem_wait(buf->semaphore); 

     //process buf->buffer[readPos % buf->size] 
     buf->buffer[readPos % buf->size] = NULL; 
     readPos++; 
    } 
} 

Answer 2

Ver liblfds, un buffer circular PMMC sin bloqueo. No bloqueará en absoluto — las estructuras de datos sin bloqueo no tienden a hacer esto, porque el punto de estar libre de bloqueo es evitar el bloqueo; usted necesita manejar esto, cuando la estructura de datos vuelve a usted con un NULL — devuelve NULL si intenta leer en vacío, pero no coincide con su requisito al escribir lleno; aquí, tirará el elemento más antiguo y te dará eso para tu escritura.

Sin embargo, solo se necesitaría una pequeña modificación para obtener ese comportamiento.

Pero puede haber una solución mejor. La parte más complicada de un ringbuffer es cuando obtiene el elemento anterior más antiguo y lo vuelve a usar. No necesitas esto Creo que podría tomar el buffer circular SPSC con barrera de memoria solo y reescribirlo usando operaciones atómicas. Eso será un lote más eficaz que el buffer de anillo MPMC en liblfds (que es una combinación de una cola y una pila).