für die rechte Ringpuffer Implementierung in C Suche

Question

ich für einen Ringpuffer Implementierung suchen (oder Pseudo-Code) in C mit den folgenden Eigenschaften:

• mehrere Hersteller einzelne Verbraucher Muster (MPSC)
• Blöcke Verbraucher Block auf leere
• Hersteller auf volle
• Lock-frei (ich erwarte, dass hohe Konkurrenz)

Bisher ich Ich habe nur mit SPSC-Puffern gearbeitet - einen pro Producer - aber ich möchte vermeiden, dass der Consumer ständig nach neuen Daten über alle Eingabepuffer sucht (und vielleicht einige Marshalling-Threads in meinem System loswerden könnte).

Ich entwickle für Linux auf Intel-Maschinen.

Answer 1

Ich denke, ich habe was du suchst. Es ist eine Lock-freie Ringpuffer-Implementierung, die den Producer/Consumer blockiert. Sie benötigen nur Zugriff auf atomare Primitive - in diesem Beispiel verwende ich die sync-Funktionen von gcc.

Es hat einen bekannten Fehler - wenn Sie den Puffer um mehr als 100% überlaufen, ist es nicht garantiert, dass die Warteschlange FIFO bleibt (es wird immer noch alle sie schließlich verarbeiten).

Diese Implementierung basiert auf Lesen/als eine atomare Operation die Pufferelemente zu schreiben (was ziemlich viel für Zeiger garantiert)

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

liblfds See, ein Schloss frei MPMC Ringpuffer. Es blockiert überhaupt nicht — lock-free Datenstrukturen neigen dazu, dies zu tun, weil der Punkt der Sperre frei ist, um zu blockieren; Sie müssen damit umgehen, wenn die Datenstruktur mit einer NULL — NULL zurückkommt, wenn Sie versuchen, auf leer lesen, aber nicht Ihre Anforderung beim Schreiben auf voll entspricht; hier wird es das älteste Element wegwerfen und dir das für dein Schreiben geben.

Es würde jedoch nur eine kleine Änderung erforderlich sein, um dieses Verhalten zu erhalten.

Aber es könnte eine bessere Lösung geben. Der schwierige Teil eines Ringpuffers besteht darin, das älteste vorherige Element vollständig zu laden und dieses wiederzuverwenden. Du brauchst das nicht. Ich denke, man könnte die SPSC-Speicherbarriere nur als Ringpuffer nehmen und mit atomaren Operationen umschreiben. Das wird ein Los leistungsfähiger, dass der MPMC Ringpuffer in liblfds (die eine Kombination aus einer Warteschlange und einem Stapel ist).