die Suche nach einer Lock-freien RT-Safe Single-Leser single-writer Struktur

Question

Ich bin für ein Lock-Free-Design suche diese Voraussetzungen entsprechen:

• einen einziger Schriftsteller schreibt in eine Struktur und ein einzelnen Leser lesen aus dieser Struktur (diese Struktur ist bereits vorhanden und ist für die gleichzeitige Lese-/Schreib-safe)
• aber irgendwann muss die Struktur den Schriftsteller, die dann initialisiert, Schalter geändert werden und schreibt in eine neue Struktur (des gleichen Typs, aber mit neuem Inhalt)
• und das nächste Mal liest der Leser, es Schalter zu dieser neuen Struktur (wenn der Schreiber zu einer neuen verriegelungsfreien Struktur multipliziert wechselt der Leser ab diese Strukturen, ihre Daten ignorierend).
• Die Strukturen müssen wiederverwendet werden, d. H. Während der Schreib-/Lese-/Schalteroperation ist keine Heap-Speicherzuweisung/frei zulässig, für RT-Zwecke.

Ich habe derzeit einen Ringpuffer implementiert, der mehrere Instanzen dieser Strukturen enthält; aber diese Implementierung leidet unter der Tatsache, dass, wenn der Schreiber alle im Ringpuffer vorhandenen Strukturen verwendet hat, es keinen Platz mehr gibt, um von der Struktur zu wechseln ... Der Rest des Ringpuffers enthält jedoch einige Daten, die nicht gelesen werden müssen vom Leser aber kann nicht vom Schreiber wiederverwendet werden. Als Konsequenz passt der Ringpuffer nicht zu diesem Zweck.

Irgendwelche Idee (Name oder Pseudo-Implementierung) eines Lock-free-Design? Vielen Dank für dieses Problem.

Answer 1

Sie sind auf dem richtigen Weg.

sperren freie Kommunikation von festen Nachrichten zwischen Fäden/Verfahren/Prozessoren alt text http://img59.imageshack.us/img59/5273/basicq.gif

fester Größe Ringpuffer können in Verriegelungsfreie Kommunikation zwischen Threads, Prozesse oder Prozessoren verwendet werden, wenn ein Hersteller gibt und man Verbraucher. Einige Überprüfungen durchzuführen:

Kopf Variable geschrieben werden nur durch Produzenten (als atomare Aktion nach dem Schreiben)

Schwanz Variable durch Verbraucher nur geschrieben (als atomare Aktion nach dem Lesen)

Fallstricke: Einführung einer Größenvariable oder Puffer voll/leer; Diese werden in der Regel sowohl von Produzenten als auch von Konsumenten geschrieben und geben Ihnen daher ein Problem.

Ich verwende in der Regel Ringpuffer für diesen Zweck. Die wichtigste Lektion, die ich gelernt habe, ist, dass ein Ringpuffer niemals mehr als Elemente enthalten kann. Auf diese Weise wird eine Kopf und Schwanz Variable vom Hersteller bzw. Verbraucher geschrieben.

Erweiterung für große/variabler Größe Blöcke um Puffer in einer Echtzeit-Umgebung verwenden, können Sie entweder Speicherpools (oft in optimierter Form in Echtzeit-Betriebssysteme) oder entkoppeln Zuteilung von Nutzungs verwenden. Letzteres passt zu der Frage, glaube ich.

extended queue http://img16.imageshack.us/img16/8725/extq.gif

Wenn Sie große Blöcke austauschen müssen, schlage ich vor, einen Pool mit Pufferblöcken zu verwenden, und Zeiger auf Puffer kommunizieren, um eine Warteschlange verwendet wird. Verwenden Sie also eine 3. Warteschlange mit Pufferzeigern. Auf diese Weise können die Zuordnungen in der Anwendung (Hintergrund) vorgenommen werden und Ihr Echtzeitabschnitt hat Zugriff auf eine variable Speichermenge.

Anwendung

while (blockQueue.full != true) 
{ 
    buf = allocate block of memory from heap or buffer pool 
    msg = { .... , buf }; 
    blockQueue.Put(msg) 
} 

Producer: 
    pBuf = blockQueue.Get() 
    pQueue.Put() 

Consumer 
    if (pQueue.Empty == false) 
    { 
     msg=pQueue.Get() 
     // use info in msg, with buf pointer 
     // optionally indicate that buf is no longer used 
    } 

Answer 2

Hier ein. Die Schlüssel sind, dass es drei Puffer gibt und der Leser reserviert den Puffer, von dem gelesen wird. Der Schreiber schreibt in einen der anderen zwei Puffer. Das Risiko einer Kollision ist minimal. Plus, das erweitert sich. Machen Sie Ihre Member-Arrays einfach um ein Element länger als die Anzahl der Leser plus die Anzahl der Writer.

Hinweis: Wie es hier geschrieben ist, gibt es zwei Kopien, um Ihre Daten zu lesen. Wenn Sie Ihre Daten mithilfe eines Referenzarguments aus der Lesefunktion übergeben, können Sie diese auf eine Kopie reduzieren.