Suche nach der richtigen Ringpufferimplementierung in C

8

Ich suche nach einer Ringpuffer-Implementierung (oder Pseudocode) in C mit den folgenden Eigenschaften:

  • Multiple-Produzenten-Single-Consumer-Muster (MPSC)
  • Verbraucher blockiert auf leer
  • Produzenten blockieren vollständig
  • lock-free (ich erwarte hohe Konkurrenz)

Bisher habe ich 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 Marshalling los wird) Threads in meinem System).

Ich entwickle für Linux auf Intel Maschinen.

    
ziu 04.09.2012, 13:05
quelle

2 Antworten

3

Ich glaube, ich habe wonach Sie suchen. Es ist eine Lock-freie Ringpuffer-Implementierung, die den Producer / Consumer blockiert. Sie müssen nur auf atomare Primitive zugreifen - in diesem Beispiel verwende ich die sync -Funktionen von gcc.

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

Diese Implementierung beruht auf dem Lesen / Schreiben der Pufferelemente als eine atomare Operation (was für Zeiger ziemlich garantiert ist)

%Vor%     
charliehorse55 05.09.2012, 05:47
quelle
4

Siehe liblfds , einen lockfreien MPMC-Ringpuffer. Es wird nicht blockieren bei allen - blockierungsfreie Datenstrukturen neigen nicht dazu, dies zu tun, weil der Punkt, der frei von Sperren ist, ein Blockieren zu vermeiden ist; Sie müssen damit umgehen, wenn die Datenstruktur mit einem NULL -returns NULL an Sie zurückkehrt, wenn Sie versuchen, leer zu lesen, aber nicht Ihrer Anforderung entspricht, wenn Sie vollständig schreiben ; hier wird es das älteste Element wegwerfen und dir das für dein Schreiben geben.

Es würde jedoch nur eine kleine Modifikation benötigen, 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 eine Menge leistungsfähiger als der MPMC-Ringpuffer in liblfds (was eine Kombination aus einer Warteschlange und einem Stack ist).

    
user82238 07.09.2012 07:39
quelle