Rundsperrfreier Puffer

73

Ich bin dabei, ein System zu entwerfen, das eine Verbindung zu einem oder mehreren Datenfeeds herstellt und eine Analyse der Daten durchführt, um Ereignisse basierend auf dem Ergebnis auszulösen. In einem typischen Multithread-Producer / Consumer-Setup werden mehrere Producer-Threads Daten in eine Warteschlange stellen und mehrere Consumer-Threads die Daten lesen. Die Konsumenten interessieren sich nur für den neuesten Datenpunkt plus n Anzahl von Punkten. Die Producer-Threads müssen blockieren, wenn der langsame Consumer nicht mithalten kann, und natürlich werden die Consumer-Threads blockiert, wenn keine unverarbeiteten Updates vorhanden sind. Die Verwendung einer typischen gleichzeitigen Warteschlange mit Lese- / Schreibsperre funktioniert gut, aber die eingehende Datenrate kann sehr hoch sein. Daher wollte ich meinen Sperraufwand reduzieren, insbesondere die Schreibsperren für die Produzenten. Ich denke, ein kreisförmiger, sperrenfreier Puffer ist das, was ich brauchte.

Nun zwei Fragen:

  1. Ist ein kreisförmiger sperrenfreier Puffer die Antwort?

  2. Wenn ja, bevor ich meine eigenen rolle, kennen Sie eine öffentliche Implementierung, die meinen Anforderungen entspricht?

Hinweise zur Implementierung eines zirkularen sperrenfreien Puffers sind immer willkommen.

Übrigens, dies in C ++ unter Linux.

Einige zusätzliche Informationen:

Die Reaktionszeit ist für mein System entscheidend. Im Idealfall möchten die Consumer-Threads, dass Aktualisierungen so schnell wie möglich eingehen, da eine zusätzliche Verzögerung von 1 Millisekunde das System wertlos machen oder viel weniger wert sein kann.

Die Designidee, zu der ich mich neige, ist ein halbverriegelungsfreier Ringpuffer, in dem der Producer-Thread Daten so schnell wie möglich in den Puffer legt. Rufen wir den Kopf des Puffers A auf, ohne ihn zu blockieren, es sei denn, der Puffer ist voll, wenn A trifft auf das Ende des Puffers Z. Consumer-Threads enthalten jeweils zwei Zeiger auf den Kreispuffer P und P n , wobei P der lokale Pufferkopf des Threads ist und P n das n-te Element nach P ist. Jeder Consumer-Thread rückt sein P vor und P n, sobald es die Verarbeitung des Stroms P beendet hat und das Ende des Pufferzeigers Z mit dem langsamsten P n vorgerückt ist. Wenn P A erreicht, was bedeutet, dass kein neues Update mehr verarbeitet werden muss, dreht sich der Verbraucher und wartet damit, dass A wieder vorrückt. Wenn sich der Consumer-Thread zu lange dreht, kann er in den Ruhezustand versetzt werden und auf eine Bedingungsvariable warten, aber ich bin damit einverstanden, dass der Consumer den CPU-Zyklus in Anspruch nimmt und auf ein Update wartet, da dies meine Latenz nicht erhöht (ich werde mehr CPU-Kerne haben als Fäden). Stellen Sie sich vor, Sie haben eine kreisförmige Spur und der Produzent läuft vor einer Gruppe von Verbrauchern. Der Schlüssel besteht darin, das System so abzustimmen, dass der Produzent normalerweise nur ein paar Schritte vor den Verbrauchern läuft, und die meisten dieser Vorgänge können es sein erfolgt mit sperrfreien Techniken. Ich verstehe, dass es nicht einfach ist, die Details der Implementierung richtig zu machen ... okay, sehr schwer, deshalb möchte ich aus den Fehlern anderer lernen, bevor ich einige meiner eigenen mache.

Shing Yip
quelle
Ich denke, es wäre hilfreich, wenn Sie die API skizzieren, die diese Datenstruktur implementieren soll.
Dave
1
Ich habe gelernt, viel Arbeit zu leisten. Ich kenne die Größe Ihrer Arbeitselemente nicht, aber Sie können die Effizienz steigern, wenn Sie größere Stücke produzieren und größere Stücke verbrauchen können. Sie können es auch erhöhen, indem Sie Blöcke mit variabler Größe verbrauchen, damit die Verbraucher nicht alle auf einmal fertig werden und in der Datenwarteschlange kämpfen.
Zan Lynx
Eine andere Sache, an die Sie denken sollten, ist, wenn Sie einen Puffer oder eine Reihe von Puffern benötigen. Sie können Producer / Consumer-Paare haben, die sich einen Puffer teilen, und wenn ein Puffer voll ist, wechselt der Producer oder Consumer vorübergehend zu einem anderen offenen Puffer. Es ist eine Form des Arbeitsdiebstahls.
Zan Lynx
3
Effiziente sperrfreie Algorithmen sind einzigartige Schneeflocken, deren Entdeckung normalerweise einen Forschungsartikel verdient. Ich werde nicht versuchen, diese Frage zu beantworten, bis OP seine tatsächlichen Anforderungen von denen unterscheidet, von denen er glaubt, dass eine Lösung aussehen sollte.
Dave
2
Eine Millisekunde ist unter unverändertem Linux eine sehr schnelle Frist. Wenn ein anderer Prozess ausgeführt wird, können Sie ihn leicht übersehen. Sie müssten Echtzeitprioritäten verwenden, und selbst dann bin ich mir nicht sicher, ob Sie diese Fristen zuverlässig einhalten können. Sind Sie sicher, dass Sie so reaktionsschnell sein müssen? Können Sie nur die Hersteller so schnell machen, sie beispielsweise in einen Gerätetreiber implementieren und die Anforderungen an die Verbraucher lockern?
Doug

Antworten:

40

Ich habe in den letzten Jahren eine spezielle Studie über sperrenfreie Datenstrukturen durchgeführt. Ich habe die meisten Zeitungen auf dem Gebiet gelesen (es gibt nur ungefähr vierzig oder so - obwohl nur ungefähr zehn oder fünfzehn wirklich nützlich sind :-)

AFAIK, ein sperrenfreier Kreispuffer, wurde nicht erfunden. Das Problem wird darin bestehen, sich mit dem komplexen Zustand zu befassen, in dem ein Leser einen Schriftsteller überholt oder umgekehrt.

Wenn Sie nicht mindestens sechs Monate damit verbracht haben, sperrenfreie Datenstrukturen zu studieren, versuchen Sie nicht, selbst eine zu schreiben. Sie werden es falsch verstehen und es ist Ihnen möglicherweise nicht klar, dass Fehler vorliegen, bis Ihr Code nach der Bereitstellung auf neuen Plattformen fehlschlägt.

Ich glaube jedoch, dass es eine Lösung für Ihre Anforderung gibt.

Sie sollten eine Warteschlange ohne Sperre mit einer Liste ohne Sperren koppeln.

Die kostenlose Liste gibt Ihnen eine Vorabzuweisung und vermeidet so die (steuerlich teure) Anforderung eines sperrfreien Zuweisers. Wenn die freie Liste leer ist, replizieren Sie das Verhalten eines Umlaufpuffers, indem Sie ein Element sofort aus der Warteschlange entfernen und es stattdessen verwenden.

(Natürlich ist das Erhalten eines Elements in einem auf Sperren basierenden Kreispuffer nach Erreichen der Sperre sehr schnell - im Grunde genommen nur eine Zeiger-Dereferenzierung -, aber Sie werden dies in keinem sperrenfreien Algorithmus erhalten; sie müssen häufig gehen Der Aufwand für das Fehlschlagen eines Popups mit freier Liste, gefolgt von einer Warteschlange, entspricht dem Arbeitsaufwand, den ein sperrfreier Algorithmus leisten muss.

Michael und Scott haben 1996 eine wirklich gute Warteschlange ohne Sperren entwickelt. Über einen der folgenden Links erhalten Sie genügend Details, um das PDF ihres Papiers aufzuspüren. Michael und Scott, FIFO

Eine sperrenfreie freie Liste ist der einfachste sperrfreie Algorithmus, und tatsächlich glaube ich nicht, dass ich ein aktuelles Papier dafür gesehen habe.


quelle
@Blank Xavier: Das FIFO von Michael und Scott ähnelt einem, das ich unabhängig in .net implementiert habe. es schien nicht schwer zu sein. Wenn die .net-Laufzeit und der Garbage-Collector nicht garantiert hätten, dass Objekte niemals recycelt werden, solange Referenzen vorhanden sind, wäre es schwierig gewesen, das ABA-Problem zu verhindern (das oben verlinkte Papier von Michael und Scott hat dies jedoch nicht erwähnt) Der .net Garbage Collector löst dieses Problem automatisch. Wie haben Sie aus Neugier das ABA-Problem gelöst?
Supercat
@Supercat: Das M & S-Papier löst das ABA-Problem explizit, indem Zeiger-Zähler-Paare verwendet werden. "Struktur pointer_t {ptr: Zeiger auf node_t, Anzahl: vorzeichenlose Ganzzahl}". Der Zähler wird bei Bedarf erhöht, so dass es fast unmöglich ist, dass ABA auftritt.
1
@Blank Xavier: Ah, das habe ich irgendwie verpasst. Ihr CAS scheint die Existenz einer Anweisung zum Tauschen einer Struktur mit zwei Elementen anzunehmen; Ich bin für eine solche Funktion in .net nicht verfügbar.
Supercat
3
Ich kann mich irren, aber ich denke, wenn der Volatile keine Speicherbarriere durchführt, hat dies keine Auswirkungen auf das Neuordnungsverhalten des Compilers oder der CPU. Alles, was es tun wird, ist sicherzustellen, dass sein Wert aus dem Speicher gelesen wird und nicht aus einem Register oder Cache.
1
IIRC, volatileSpeicherzugriffe werden nicht mit anderen volatileZugriffen neu angeordnet. Aber in ISO C ist das alles, was Sie bekommen. In MSVC volatilegeht es weit darüber hinaus, aber heutzutage sollten Sie nur std::atomicmit memory_order_releaseoder seq_cstoder was auch immer Sie wollen verwenden.
Peter Cordes
34

Der Kunstbegriff für das, was Sie wollen, ist eine Warteschlange ohne Sperren . Es gibt eine exzellente Reihe von Notizen mit Links zu Code und Papieren von Ross Bencina. Der Typ, dessen Arbeit ich am meisten vertraue, ist Maurice Herlihy (für Amerikaner spricht er seinen Vornamen wie "Morris" aus).

Norman Ramsey
quelle
2
Eine Warteschlange ist kein Ringpuffer.
27
@Blank Xavier: Nein, aber ein Ringpuffer ist eine Warteschlange. Das Problem erfordert eine Warteschlange. Und die effizienteste Implementierung einer Warteschlange ist ... (warte darauf) ein Ringpuffer. Wenn Sie suchen möchten, suchen Sie in jedem Fall nach "sperrenfreier Warteschlange" und nicht nach "sperrenfreiem Ringpuffer".
Norman Ramsey
1
Ich sehe keinen Grund, warum ich keine Semaphoren verwenden soll. Kein Sperren / Blockieren, der Verbraucher geht nur in den Ruhezustand, wenn der Puffer leer ist, der Produzent, wenn der Puffer voll ist. Was stimmt damit nicht? Wie könnte eine Warteschlange ohne Sperre besser sein?
TMS
6
@Tomas: Die Warteschlange ohne Sperren kann besser sein, da es keine einzige Sperre gibt, die als Leistungsengpass fungiert. OP war speziell besorgt über die Reduzierung des Sperraufwands bei sehr hohen Konflikten. Semaphoren helfen nicht bei Streitigkeiten. Eine sperrenfreie Warteschlange funktioniert.
Norman Ramsey
1
liblfds.org verfügt über eine angesehene Ringpufferwarteschlange für mehrere Hersteller und mehrere Verbraucher . Es ist technisch nicht sperrenfrei : Ein Produzent, der mitten im Hinzufügen eines Eintrags schläft, kann Verbraucher daran hindern, etwas von anderen Produzenten zu sehen. Unter stackoverflow.com/questions/45907210/… finden Sie eine Analyse der Fortschrittsgarantien. Es ist sehr wenig umstritten (keine zwischen einem Produzenten und einem Konsumenten, wenn es nicht leer oder voll ist) und kann das sein, was Sie in der Praxis wollen.
Peter Cordes
12

Die Anforderung, dass Produzenten oder Konsumenten blockieren, wenn der Puffer leer oder voll ist, legt nahe, dass Sie eine normale Sperrdatenstruktur mit Semaphoren oder Bedingungsvariablen verwenden sollten, damit Produzenten und Konsumenten blockieren, bis Daten verfügbar sind. Sperrfreier Code blockiert unter solchen Bedingungen im Allgemeinen nicht - er dreht oder bricht Vorgänge ab, die nicht ausgeführt werden können, anstatt mit dem Betriebssystem zu blockieren. (Wenn Sie es sich leisten können, zu warten, bis ein anderer Thread Daten erzeugt oder verbraucht, warum dann auf eine Sperre warten, bis ein anderer Thread die Aktualisierung der Datenstruktur abgeschlossen hat?)

Unter (x86 / x64) Linux ist die Intra-Thread-Synchronisation mit Mutexen relativ kostengünstig, wenn keine Konflikte bestehen. Konzentrieren Sie sich darauf, die Zeit zu minimieren, die Hersteller und Verbraucher benötigen, um ihre Schlösser festzuhalten. Angesichts der Tatsache, dass Sie gesagt haben, dass Sie sich nur um die letzten N aufgezeichneten Datenpunkte kümmern, denke ich, dass ein kreisförmiger Puffer dies ziemlich gut tun würde. Ich verstehe jedoch nicht wirklich, wie dies zu der Blockierungsanforderung und der Idee passt, dass Verbraucher die von ihnen gelesenen Daten tatsächlich verbrauchen (entfernen). (Möchten Sie, dass die Verbraucher nur die letzten N Datenpunkte betrachten und nicht entfernen? Möchten Sie, dass es den Herstellern egal ist, ob die Verbraucher nicht mithalten können, und nur alte Daten überschreiben?)

Wie Zan Lynx kommentierte, können Sie Ihre Daten auch zu größeren Blöcken zusammenfassen / puffern, wenn viele davon eingehen. Sie können eine feste Anzahl von Punkten oder alle innerhalb einer bestimmten Zeit empfangenen Daten puffern . Dies bedeutet, dass weniger Synchronisationsvorgänge ausgeführt werden. Es führt zwar zu einer Latenz, aber wenn Sie kein Echtzeit-Linux verwenden, müssen Sie sich ohnehin bis zu einem gewissen Grad damit befassen.

Doug
quelle
stimme dem ersten Absatz absolut zu. Sehen Sie hier keinen Grund, kein Semaphor zu verwenden.
TMS
1
@TMS, Eine Anwendung mit dedizierten Producer-Threads und dedizierten Consumer-Threads (z. B. wie vom OP beschrieben) kann niemals als "sperrfrei" bezeichnet werden. In einer sperrfreien Anwendung mit N Threads sollten Sie in der Lage sein, eine beliebige Kombination von (N-1) oder weniger der Threads auf unbestimmte Zeit auszusetzen, und die Anwendung sollte weiterhin Fortschritte erzielen. Ein dedizierter Verbraucher-Thread kann jedoch nicht auf unbestimmte Zeit Fortschritte erzielen, wenn alle Hersteller suspendiert sind und wenn das Ablegen des "Produkts" auf dem Boden nicht zulässig ist, kann ein Hersteller keine Fortschritte erzielen, wenn keiner der Verbraucher ausgeführt werden darf.
Solomon Slow
@jameslarge: "lock-free" kann einen Algorithmus oder eine Datenstruktur (wie eine Warteschlange) beschreiben. en.wikipedia.org/wiki/Non-blocking_algorithm Es wird normalerweise nicht auf eine ganze Anwendung angewendet. Das Anhalten aller Producer-Threads bedeutet einfach, dass die Warteschlange leer ist. In einer Warteschlange ohne Sperren darf das Anhalten eines oder mehrerer Threads zu einem beliebigen Zeitpunkt jedoch nicht verhindern, dass die anderen Threads in die Warteschlange gestellt und aus der Warteschlange entfernt werden können. (Auch dies ist nicht einfach zu erreichen; effiziente Implementierungen haben oft einen Thread, der einen Slot "beansprucht": stackoverflow.com/questions/45907210/… )
Peter Cordes
@ Doug: Ja, ein Verbraucher / Produzent sollte schlafen, wenn er die Warteschlange leer / voll findet. Aber nein, das bedeutet nicht immer, dass Sie die Warteschlange mit herkömmlicher Sperre implementieren sollten, insbesondere nicht mit einer großen Sperre für die gesamte Datenstruktur. Diese Warteschlange (wie der vorherige Kommentar) ist im technischen Sinne nicht "sperrenfrei", ermöglicht es den Herstellern jedoch, völlig unabhängig von den Verbrauchern zu sein (kein Streit), was einen potenziell besseren Durchsatz bietet, als Sie sperren könnten. Guter Punkt zum effizienten Aufwecken auf leer-> nicht leer.
Peter Cordes
6

Die Implementierung in der Boost-Bibliothek ist eine Überlegung wert. Es ist einfach zu bedienen und ziemlich leistungsstark. Ich habe einen Test geschrieben und ihn auf einem Quad-Core-i7-Laptop (8 Threads) ausgeführt und pro Sekunde ~ 4 Millionen Enqueue / Dequeue-Vorgänge ausgeführt. Eine weitere Implementierung, die bisher nicht erwähnt wurde, ist die MPMC-Warteschlange unter http://moodycamel.com/blog/2014/detailed-design-of-a-lock-free-queue . Ich habe einige einfache Tests mit dieser Implementierung auf demselben Laptop mit 32 Herstellern und 32 Verbrauchern durchgeführt. Es ist, wie angekündigt, schneller als die Boost-Lockless-Warteschlange.

Wie die meisten anderen Antworten ist die programmlose Programmierung schwierig. Bei den meisten Implementierungen ist es schwierig, Eckfälle zu erkennen, deren Behebung viel Testen und Debuggen erfordert. Diese werden normalerweise durch sorgfältiges Platzieren von Speicherbarrieren im Code behoben. In vielen wissenschaftlichen Artikeln finden Sie auch Korrektheitsnachweise. Ich bevorzuge es, diese Implementierungen mit einem Brute-Force-Tool zu testen. Jeder sperrlose Algorithmus, den Sie in der Produktion verwenden möchten, sollte mit einem Tool wie http://research.microsoft.com/en-us/um/people/lamport/tla/tla.html auf Richtigkeit überprüft werden .

Alex
quelle
5

Es gibt eine ziemlich gute Artikelserie über DDJ . Als Zeichen dafür, wie schwierig dieses Zeug sein kann, ist es eine Korrektur eines früheren Artikels , die es falsch verstanden hat. Stellen Sie sicher, dass Sie die Fehler verstehen, bevor Sie Ihre eigenen rollen) -;

Henk Holterman
quelle
5

Ich bin kein Experte für Hardware-Speichermodelle und sperrenfreie Datenstrukturen, und ich vermeide es, diese in meinen Projekten zu verwenden, und ich gehe mit traditionellen gesperrten Datenstrukturen um.

Allerdings habe ich kürzlich das Video bemerkt: Lockless SPSC-Warteschlange basierend auf Ringpuffer

Dies basiert auf einer Open-Source-Hochleistungs-Java-Bibliothek namens LMAX Distruptor, die von einem Handelssystem verwendet wird: LMAX Distruptor

Basierend auf der obigen Darstellung machen Sie Kopf- und Schwanzzeiger atomar und prüfen atomar, ob der Kopf den Schwanz von hinten fängt oder umgekehrt.

Unten sehen Sie eine sehr grundlegende C ++ 11-Implementierung dafür:

// USING SEQUENTIAL MEMORY
#include<thread>
#include<atomic>
#include <cinttypes>
using namespace std;

#define RING_BUFFER_SIZE 1024  // power of 2 for efficient %
class lockless_ring_buffer_spsc
{
    public :

        lockless_ring_buffer_spsc()
        {
            write.store(0);
            read.store(0);
        }

        bool try_push(int64_t val)
        {
            const auto current_tail = write.load();
            const auto next_tail = increment(current_tail);
            if (next_tail != read.load())
            {
                buffer[current_tail] = val;
                write.store(next_tail);
                return true;
            }

            return false;  
        }

        void push(int64_t val)
        {
            while( ! try_push(val) );
            // TODO: exponential backoff / sleep
        }

        bool try_pop(int64_t* pval)
        {
            auto currentHead = read.load();

            if (currentHead == write.load())
            {
                return false;
            }

            *pval = buffer[currentHead];
            read.store(increment(currentHead));

            return true;
        }

        int64_t pop()
        {
            int64_t ret;
            while( ! try_pop(&ret) );
            // TODO: exponential backoff / sleep
            return ret;
        }

    private :
        std::atomic<int64_t> write;
        std::atomic<int64_t> read;
        static const int64_t size = RING_BUFFER_SIZE;
        int64_t buffer[RING_BUFFER_SIZE];

        int64_t increment(int n)
        {
            return (n + 1) % size;
        }
};

int main (int argc, char** argv)
{
    lockless_ring_buffer_spsc queue;

    std::thread write_thread( [&] () {
             for(int i = 0; i<1000000; i++)
             {
                    queue.push(i);
             }
         }  // End of lambda expression
                                                );
    std::thread read_thread( [&] () {
             for(int i = 0; i<1000000; i++)
             {
                    queue.pop();
             }
         }  // End of lambda expression
                                                );
    write_thread.join();
    read_thread.join();

     return 0;
}
Akin Ocal
quelle
Verwenden Sie eine Potenz von 2 für Ihre size, so dass das %(Modulo) nur ein bisschen bitweise UND ist. Das Speichern einer Sequenznummer in Ihren Slots würde außerdem die Konkurrenz zwischen Hersteller und Verbraucher verringern. Dabei muss der Produzent die writePosition lesen und umgekehrt, also die Cache-Zeile, die diese atomaren Variablen Ping-Pongs zwischen den Kernen enthält. Unter stackoverflow.com/questions/45907210/… finden Sie eine Slot-Sequenznummer. (Es ist eine Multi-Producer-Multi-Consumer-Warteschlange und könnte stark zu einer einzigen Producer / Consumer-Warteschlange wie dieser vereinfacht werden.)
Peter Cordes
1
Ich bin mir ziemlich sicher, dass viele der Ladungen / Geschäfte nur die Standardeinstellung benötigen memory_order_acquireoder releasenicht seq_cst. Dies ist ein großer Unterschied zu x86, wo seq_cstGeschäfte benötigt mfence(oder xchg), releaseGeschäfte jedoch nur einfache x86-Geschäfte sind. StoreLoad-Barrieren sind auch bei den meisten anderen Architekturen die teuerste Barriere. ( preshing.com/20120710/… )
Peter Cordes
1
Es wäre wahrscheinlich besser, readdanach bufferin das Klassenlayout zu setzen , also ist es in einer anderen Cache-Zeile als write. Die beiden Threads lesen also nur Cache-Zeilen, die von den anderen geschrieben wurden, und nicht beide, die in dieselbe Cache-Zeile schreiben. Außerdem sollten sie sein size_t: Es macht keinen Sinn, 64-Bit-Zähler mit 32-Bit-Zeigern zu haben. Und ein nicht signierter Typ macht Modulo viel effizienter ( godbolt.org/g/HMVL5C ). Auch uint32_twäre für fast alle Anwendungen sinnvoll. Es ist wahrscheinlich am besten, dies nach Größe zu gestalten oder den Puffer dynamisch zuzuweisen.
Peter Cordes
@PeterCordes warum ist Modulo mit einer Potenz von 2 effizienter?
Baiyan Huang
1
@BaiyanHuang: Da Computer binäre Ganzzahlen verwenden, halten Sie die niedrigen nBits einfach mit einem AND. zB x % 8= x & 7, und bitweises UND ist viel billiger als divoder sogar Tricks, die Sie mit Teilern mit konstanter Kompilierungszeit ausführen können.
Peter Cordes
4

Eine nützliche Technik, um Konflikte zu reduzieren, besteht darin, die Elemente in mehrere Warteschlangen zu stellen und jeden Verbraucher einem "Thema" zu widmen.

Für die letzte Anzahl von Artikeln, an denen Ihre Kunden interessiert sind - Sie möchten nicht die gesamte Warteschlange sperren und darüber iterieren, um einen Artikel zu finden, der überschrieben werden soll - veröffentlichen Sie einfach Artikel in N-Tupeln, dh alle N letzten Artikel. Bonuspunkte für die Implementierung, bei der der Produzent mit einem Timeout die gesamte Warteschlange blockiert (wenn die Verbraucher nicht mithalten können) und den lokalen Tupel-Cache aktualisiert. Auf diese Weise wird die Datenquelle nicht unter Druck gesetzt.

Nikolai Fetissov
quelle
Ich habe auch das Boss / Worker-Threading-Modell in Betracht gezogen, bei dem der Boss-Thread-Multicast auf die privaten Warteschlangen der Worker-Threads aktualisiert wird. Ich denke, das ist mehr oder weniger die Richtung, in die du gehst. Ich muss es zwar mehr geben, aber als ich darüber nachdachte, schien der Chef / Arbeiter zu viel Overhead zu haben, weil alle Arbeiter die gleichen Updates erhalten müssen.
Shing Yip
1
Nicht genau - ich meine im ersten Punkt, dass Sie Ihren eingehenden Stream aufteilen, damit nicht alle Threads um dieselbe Sperre / Warteschlange konkurrieren. Der zweite Punkt ist das Zwischenspeichern auf der Herstellerseite, um Spitzen im Input auszugleichen und langsamen Verbrauchern zu ermöglichen, den Erzeuger nicht aufzuhalten.
Nikolai Fetissov
Für die Geschäftslogik ist es jedoch erforderlich, dass alle Worker-Threads alle Daten kennen, die gestreamt werden. Es kommen nur ein Datentyp herein, und jeder Datenpunkt ist gleich wichtig, sodass ich meinen eingehenden Stream nicht wirklich aufteilen und unterschiedliche Daten einspeisen kann verschiedene Warteschlangen. Das Einlösen auf der Herstellerseite und das Bündeln von Aktualisierungen des Datenmodells zur Verhinderung von Hogging wurden durchgeführt, und es reichte nicht aus, um die Last zu bewältigen.
Shing Yip
Wie groß ist die Eingabedomäne? Wenn es sich um Marktdaten in der Finanzwelt handelt, haben Sie eine begrenzte, wenn auch große Anzahl von Artikeln und nur wenige Arten von Updates. Reagieren Mitarbeiter auf die Eingabeereignisse oder führen sie ihre eigene Verarbeitung durch und fragen nur bei Bedarf nach Ihren Eingaben?
Nikolai
Es ist so etwas wie Marktdaten in der Finanzwelt. Die Mitarbeiter führen ihre eigene Verarbeitung durch und haben bei Bedarf zufälligen Zugriff auf n Nummern des Aktualisierungsverlaufs (n ist eine konfigurierbare Nummer, ändert sich jedoch während der Lebensdauer des Prozesses nicht). Ich möchte ein System entwerfen, das sowohl auf großen als auch auf kleinen n gut funktioniert, damit ich eine Codebasis haben kann.
Shing Yip
4

Ich würde diesem Artikel zustimmen und davon abraten, sperrenfreie Datenstrukturen zu verwenden. Ein relativ neues Papier auf schleusenfreien FIFOWarteschlangen ist dies , vom selben Autor (en) für weitere Papiere suchen; Es gibt auch eine Doktorarbeit über Chalmers über sperrenfreie Datenstrukturen (ich habe den Link verloren). Sie haben jedoch nicht angegeben, wie groß Ihre Elemente sind. Sperrenfreie Datenstrukturen funktionieren nur mit Elementen in Wortgröße effizient. Daher müssen Sie Ihre Elemente dynamisch zuordnen, wenn sie größer als ein Maschinenwort sind (32 oder 64) Bits). Wenn Sie Elemente dynamisch zuweisen, verschieben Sie den Engpass (vermutlich, da Sie Ihr Programm nicht profiliert haben und im Grunde genommen eine vorzeitige Optimierung durchführen) auf den Speicherzuweiser, sodass Sie einen sperrfreien Speicherzuweiser benötigen, z. B. Streamflowund integrieren Sie es in Ihre Anwendung.

zvrba
quelle
3
Wenn Sie Ihre Elemente vollständig vorab zuweisen, wird der Zuweiser nicht belastet.
4

Sutters Warteschlange ist nicht optimal und er weiß es. Die Art of Multicore-Programmierung ist eine großartige Referenz, aber vertrauen Sie den Java-Leuten bei Speichermodellen nicht. Ross 'Links geben Ihnen keine eindeutige Antwort, da sie ihre Bibliotheken in solchen Problemen hatten und so weiter.

Das sperrenfreie Programmieren ist problematisch, es sei denn, Sie möchten viel Zeit mit etwas verbringen, das Sie eindeutig überarbeitet haben, bevor Sie das Problem lösen (nach der Beschreibung zu urteilen, ist es ein üblicher Wahnsinn, nach Perfektion zu suchen 'in Cache-Kohärenz). Es dauert Jahre und führt dazu, dass die Probleme nicht zuerst gelöst und später eine häufige Krankheit optimiert werden.

rama-jka toti
quelle
Würden Sie einen Link zur Analyse von Sutters Warteschlange posten?
Nikolai Fetissov
Es ist alles auf DDJ und einer der Leute, die seinen Blogs folgen, hat es profiliert. Der Punkt ist, dass heißes CAS für viele Szenarien nicht erforderlich ist und dass Sie diese Art von feiner Granularität jeden Tag selbst mit einfachen Swaps übertreffen können.
Rama-Jka Toti
Das war's, danke. Aber ich glaube, es könnte noch einige Rennen geben. Alles, was so sensibel ist wie das Erwarten impliziter Barrieren oder ein spezifisches oder vollständiges Kohärenzverständnis, ist ein Problem, das darauf wartet, in der Produktion auftreten zu können. Ich glaube einfach nicht, dass sich der Detaillierungsgrad so sehr löst, als dass man sich eher auf das Design auf Anwendungsebene als auf die Installation auf niedriger Ebene konzentriert, wenn / nur - wenn es sinnvoll ist / als identifiziert identifiziert wird. Ich begrüße die Mühe, die Bücher, alles; Aber es sind nur Artikel zu einem Touch-Thema, für die selbst MS Schwierigkeiten hat, sich für die PFX-Masse auf dem Massenmarkt gut zu behaupten.
Rama-Jka Toti
Nur eine Meinung, es gibt immer wichtigere Arbeit als sich mit Sanitär zu befassen. Parallele Bemühungen ziehen sich über die gesamte Bandbreite, nicht nur über Warteschlangen, oder tatsächlich erfinden DDJ-Artikel Mitte der neunziger Jahre immer wieder neu. Das heißt, von NT bis später übernehmen Solaris und Unix ähnliche Techniken oder neueste Arbeiten an C ++. Letzteres ist und wird wahrscheinlich Ewigkeiten dauern, um die Tatsache zu vervollständigen und immer noch zu bekämpfen, dass kein sauberer OO-Weg zum Posten eines P2-Pro-ähnlichen Universums außerhalb der Reihenfolge sinnvoll ist.
rama-jka toti
2
Dennis 'Website wurde auf landlabs.com/code/ring/ring.html verschoben. Sie verfügt über einen sperrenfreien Ringpuffer.
LanDenLabs
3

Obwohl dies eine alte Frage ist, erwähnte niemand den sperrenlosen Ringpuffer von DPDK. Es ist ein Ringpuffer mit hohem Durchsatz, der mehrere Hersteller und mehrere Verbraucher unterstützt. Es bietet auch Einzelverbraucher- und Einzelproduzenten-Modi, und der Ringpuffer ist im SPSC-Modus wartungsfrei. Es ist in C geschrieben und unterstützt mehrere Architekturen.

Darüber hinaus werden die Modi "Bulk" und "Burst" unterstützt, in denen Elemente in großen Mengen in die Warteschlange gestellt / aus der Warteschlange entfernt werden können. Mit dem Design können mehrere Konsumenten oder mehrere Produzenten gleichzeitig in die Warteschlange schreiben, indem der Speicherplatz einfach durch Bewegen eines Atomzeigers reserviert wird.

Saman Barghi
quelle
1
Ist es wirklich sperrfrei oder nur, wenn ein Produzent / Konsument nicht schläft, nachdem er einen Slot beansprucht hat, sondern bevor er die Enqueue / Dequeue beendet hat? Sehen Sie sich diese Analyse der Multi-Producer-Multi-Consumer-Warteschlange in liblfds.org an , die wahrscheinlich ziemlich ähnlich funktioniert. In der Praxis funktioniert es gut mit geringen Konflikten, ist aber technisch nicht sperrenfrei. Wie auch immer, positiv bewertet, weil der Bulk / Burst-Modus nach einer guten Idee klingt.
Peter Cordes
Ich bin damit einverstanden, es garantiert keine Terminierungssicherheit und laut [1024cores] ( 1024cores.net/home/lock-free-algorithms/introduction ) ist es ein Blockierungsalgorithmus und das System macht möglicherweise keine Fortschritte. Im SPSC-Modus wird es jedoch wartungsfrei. Ich bearbeite die Antwort, um dies widerzuspiegeln.
Saman Barghi
1
Schauen Sie sich auch Dmitrys Implementierung der Bounded MPMC-Warteschlange an: 1024cores.net/home/lock-free-algorithms/queues/… . Auch dies ist nicht sperrenfrei, aber sperrenlos und sehr einfach und effizient. In Bezug auf die Leistung kann die Warteschlange des DPDK im Bulk / Burst-Modus jedoch je nach Stapelgröße bis zu hundert Millionen Operationen pro Sekunde in Bezug auf den Durchsatz erreichen. Die Kombination von atomaren Operationen und sequentiellem Lesen / Schreiben macht es sehr effizient.
Saman Barghi
2

Der Vollständigkeit halber gibt es in OtlContainers einen gut getesteten sperrenfreien Ringpuffer , der jedoch in Delphi geschrieben ist (TOmniBaseBoundedQueue ist Kreispuffer und TOmniBaseBoundedStack ist ein begrenzter Stapel). Es gibt auch eine unbegrenzte Warteschlange in derselben Einheit (TOmniBaseQueue). Die unbegrenzte Warteschlange wird in der Warteschlange ohne dynamische Sperren beschrieben - richtig machen . Die anfängliche Implementierung der begrenzten Warteschlange (Ringpuffer) wurde schließlich in Eine Warteschlange ohne Sperren beschrieben ! aber der Code wurde seitdem aktualisiert.

gabr
quelle
2

Dies ist ein alter Thread, aber da er noch nicht erwähnt wurde, gibt es im JUCE C ++ - Framework ein sperrenfreies, zirkuläres FIFO mit 1 Hersteller und> 1 Verbraucher.

https://www.juce.com/doc/classAbstractFifo#details

Nikolay Tsenkov
quelle
2

Schauen Sie sich Disruptor ( Verwendung ) an, einen Ringpuffer, den mehrere Threads abonnieren können:

Rolf Kristensen
quelle
1

So würde ich es machen:

  • Ordnen Sie die Warteschlange einem Array zu
  • Behalten Sie den Status mit einem nächsten Lese- und einem nächsten Schreibindex bei
  • Halten Sie einen leeren Vollbitvektor herum

Das Einfügen besteht aus der Verwendung eines CAS mit einem Inkrement und einem Rollover beim nächsten Schreibvorgang. Wenn Sie einen Steckplatz haben, fügen Sie Ihren Wert hinzu und setzen Sie das entsprechende leere / volle Bit.

Das Entfernen erfordert eine Überprüfung des Bits vor dem Testen auf Unterläufe, ist jedoch anders als beim Schreiben, verwendet jedoch den Leseindex und löscht das leere / volle Bit.

Sei gewarnt,

  1. Ich bin kein Experte in diesen Dingen
  2. Atom-ASM-Operationen scheinen sehr langsam zu sein, wenn ich sie verwendet habe. Wenn Sie also mehr als einige davon haben, können Sie möglicherweise schneller Sperren verwenden, die in die Einfüge- / Entfernungsfunktionen eingebettet sind. Die Theorie ist, dass eine einzelne atomare Operation, um die Sperre zu ergreifen, gefolgt von (sehr) wenigen nichtatomaren ASM-Operationen, schneller sein kann als die gleiche Sache, die von mehreren atomaren Operationen ausgeführt wird. Damit dies funktioniert, ist jedoch manuelles oder automatisches Inlineing erforderlich, sodass nur ein kurzer ASM-Block vorhanden ist.
BCS
quelle
1
Atomoperationen sind in der Tat an und für sich langsam. Was sie nützlich macht, ist, dass sie skalieren.
Wenn die Operationen innerhalb der Sperre sehr klein sind (wie in 5-10 Zeilen ASM), können Sie möglicherweise noch eine Sperrstrategie anwenden, insbesondere wenn Sie die Sperre direkt in die kritischen Abschnitte schreiben und nicht als Funktionsaufruf.
BCS
Ich bin verwirrt. Ein kritischer Abschnitt für mich ist der Codeabschnitt, der seriell ausgeführt werden muss. Die Sperre ist der Mechanismus, der die Serialität der Ausführung sicherstellt. Können Sie mir erklären, was Sie meinen?
1

Sie können lfqueue versuchen

Es ist einfach zu bedienen, es ist kreisförmig frei von Schlössern

int *ret;

lfqueue_t results;

lfqueue_init(&results);

/** Wrap This scope in multithread testing **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
while (lfqueue_enq(&results, int_data) != 1) ;

/*Dequeue*/
while ( (ret = lfqueue_deq(&results)) == NULL);

// printf("%d\n", *(int*) ret );
free(ret);
/** End **/

lfqueue_clear(&results);
Oktaheta
quelle
1

Es gibt Situationen, in denen Sie keine Sperre benötigen, um den Rennzustand zu verhindern, insbesondere wenn Sie nur einen Hersteller und Verbraucher haben.

Betrachten Sie diesen Absatz aus LDD3:

Bei sorgfältiger Implementierung erfordert ein kreisförmiger Puffer kein Sperren, wenn nicht mehrere Hersteller oder Verbraucher vorhanden sind. Der Produzent ist der einzige Thread, der den Schreibindex und die Array-Position, auf die er verweist, ändern darf. Solange der Writer vor dem Aktualisieren des Schreibindex einen neuen Wert im Puffer speichert, wird dem Reader immer eine konsistente Ansicht angezeigt. Der Reader ist wiederum der einzige Thread, der auf den Leseindex und den Wert zugreifen kann, auf den er verweist. Mit ein wenig Sorgfalt, um sicherzustellen, dass sich die beiden Zeiger nicht überlaufen, können der Hersteller und der Verbraucher gleichzeitig ohne Rennbedingungen auf den Puffer zugreifen.

Dražen G.
quelle
LDD3? Linux-Gerätetreiber 3?
Victor Polevoy
0

Vor einiger Zeit habe ich eine gute Lösung für dieses Problem gefunden. Ich glaube, dass es das kleinste ist, das bisher gefunden wurde.

Das Repository enthält ein Beispiel dafür, wie Sie damit N Threads (Leser und Schreiber) erstellen und dann einen einzelnen Sitzplatz gemeinsam nutzen können.

Ich habe am Testbeispiel einige Benchmarks erstellt und die folgenden Ergebnisse erhalten (in Millionen Ops / Sek.):

Nach Puffergröße

Durchsatz

Nach Anzahl der Threads

Geben Sie hier die Bildbeschreibung ein

Beachten Sie, dass die Anzahl der Threads den Durchsatz nicht ändert.

Ich denke, dies ist die ultimative Lösung für dieses Problem. Es funktioniert und ist unglaublich schnell und einfach. Selbst mit Hunderten von Threads und einer Warteschlange an einer einzigen Position. Es kann als Pipeline zwischen Threads verwendet werden, um Speicherplatz in der Warteschlange zuzuweisen.

Das Repository enthält einige frühe Versionen, die in C # und Pascal geschrieben sind. Ich arbeite daran, etwas vollständiger zu polieren, um seine wahren Kräfte zu zeigen.

Ich hoffe, einige von Ihnen können die Arbeit validieren oder mit einigen Ideen helfen. Oder kannst du es zumindest brechen?

bittnkr
quelle
0

Wenn Sie davon ausgehen, dass der Puffer niemals voll wird, sollten Sie diesen sperrfreien Algorithmus verwenden:

capacity must be a power of 2
buffer = new T[capacity] - on different cache line
mask = capacity - 1
write_index - on different cache line
read_index - on different cache line

enqueue:
    write_i = write_index.fetch_add(1) & mask
    buffer[write_i] = element - release store

dequeue:
    read_i = read_index.fetch_add(1) & mask
    element
    while ((element = buffer[read_i] - acquire load) == NULL) {
        spin loop
    }
    buffer[read_i] = NULL - relaxed store
    return element

Hier ist eine Java-Implementierung:

class ConcurrentRingBuffer<T> {
    private static final VarHandle BUFFER = MethodHandles.arrayElementVarHandle(Object[].class);

    private final int mask;

    // These three should be on different cache lines
    private final Object[] buffer;
    private final AtomicInteger readIndex = new AtomicInteger();
    private final AtomicInteger writeIndex = new AtomicInteger();

    ConcurrentRingBuffer(int capacity) {
        assert isPowerOfTwo(capacity);
        mask = capacity - 1;
        buffer = new Object[capacity];
    }

    void put(T element) {
        BUFFER.setRelease(buffer, writeIndex.getAndIncrement() & mask, element);
    }

    T take() {
        Object element;
        int readIndex = this.readIndex.getAndIncrement() & mask;
        while ((element = BUFFER.getAcquire(buffer, readIndex)) == null) {
            Thread.onSpinWait();
        }
        BUFFER.setOpaque(buffer, readIndex, null);
        return (T) element;
    }
}
Francesco Menzani
quelle