Ich habe einen einzelnen Schreiber-Thread und einen einzigen Leser-Thread, um einen Pool von Arrays zu aktualisieren und zu verarbeiten (Referenzen, die in der Map gespeichert sind). Das Verhältnis der zu lesenden Schreibvorgänge beträgt fast 5: 1 (die Latenz der Schreibvorgänge ist ein Problem).
Der Writer-Thread muss basierend auf einigen Ereignissen einige Elemente eines Arrays im Pool aktualisieren. Die gesamte Schreiboperation (alle Elemente) muss atomar sein.
Ich möchte sicherstellen, dass der Leser-Thread das vorherige aktualisierte Array liest, wenn der Writer-Thread es aktualisiert (etwas wie flüchtig, aber auf das gesamte Array und nicht auf einzelne Felder). Grundsätzlich kann ich es mir leisten, veraltete Werte zu lesen, aber nicht zu blockieren.
Da die Schreibvorgänge so häufig sind, wäre es sehr teuer, neue Objekte zu erstellen oder das gesamte Array während des Lese- / Schreibvorgangs zu sperren.
Gibt es eine effizientere Datenstruktur, die verwendet werden könnte oder billigere Sperren verwenden?
Wie wäre es mit dieser Idee: Der Writer-Thread mutiert das Array nicht. Es stellt einfach die Aktualisierungen in die Warteschlange.
Wenn der Reader-Thread in eine Lesesitzung eintritt, die einen stabilen Snapshot des Arrays erfordert, wendet er die in die Warteschlange eingereihten Aktualisierungen auf das Array an und liest dann das Array.
%Vor%Gibt es eine effizientere Datenstruktur?
Ja, absolut! Sie werden persistente Datenstrukturen genannt. Sie können eine neue Version eines Vektors / einer Karte / etc lediglich durch Speichern der Unterschiede in Bezug auf eine vorherige Version darstellen. Alle Versionen sind unveränderlich, was sie für Parallelität geeignet macht (Schreiber stören nicht / blockieren Leser und umgekehrt).
Um eine Änderung auszudrücken, speichert man Referenzen auf eine persistente Datenstruktur in einem Referenztyp wie AtomicReference und ändert, worauf diese Referenzen verweisen - nicht auf die Strukturen selbst .
Clojure bietet eine erstklassige Implementierung persistenter Datenstrukturen. Sie sind in reinem, effizientem Java geschrieben.
Das folgende Programm legt dar, wie man das beschriebene Problem mit persistenten Datenstrukturen angehen würde.
%Vor%Eine andere Idee, da das Array nur 20 Doubles enthält.
Habe zwei Arrays, eins zum Schreiben, eins zum Lesen.
Reader sperrt das Lese-Array während des Lesens.
%Vor%Writer modifiziert zuerst das Write-Array, dann tryLock das gelesene Array, wenn das Sperren fehlschlägt, in Ordnung, write () gibt zurück; Wenn das Sperren erfolgreich ist, kopieren Sie das Schreib-Array in das Lese-Array und geben Sie dann die Sperre frei.
%Vor%Leser kann blockiert werden, aber nur für die Zeit, die es dauert, um die 20 Doppel zu kopieren, was kurz ist.
Der Leser sollte eine Drehsperre wie do{}while(tryLock()==false); verwenden, um zu verhindern, dass er ausgesetzt wird.
Ich würde Folgendes tun:
Synchronisieren Sie das Ganze und sehen Sie, ob die Leistung gut genug ist. Wenn Sie nur einen Autorenthread und einen Leser-Thread haben, wird der Konflikt niedrig sein und das könnte gut genug funktionieren
%Vor%Wenn es zu langsam ist, würde der Writer eine Kopie des Arrays erstellen, einige Werte ändern und das neue Array wieder in die Map einfügen. Beachten Sie, dass Array-Kopien sehr schnell sind - normalerweise würde ein Array mit 20 Elementen höchstwahrscheinlich weniger als 100 Nanosekunden benötigen
%Vor%Da die Schreibvorgänge so häufig sind, wäre es sehr teuer, neue Objekte zu erstellen oder das gesamte Array während des Lese- / Schreibvorgangs zu sperren.
Wie häufig? Es sei denn, es gibt Hunderte von ihnen jede Millisekunde, sollte es dir gut gehen.
Beachten Sie auch Folgendes:
Die folgende Variation ist sowohl von meiner meiner vorherigen Antwort als auch eines von zhong.j.yu .
Writer interferieren / blockieren keine Leser und umgekehrt, und es gibt keine Threadsicherheits- / Sichtbarkeitsprobleme oder heikle Folgerungen.
%Vor% Sie benötigen zwei statische Referenzen: readArray und writeArray und einen einfachen Mutex zum Nachverfolgen, wenn der Schreibvorgang geändert wurde.
haben eine gesperrte Funktion namens changeWriteArray Änderungen an einer deepCopy von writeArray:
synchronisierte Zeichenkette [] changeWriteArray (Zeichenkette [] writeArrayCopy, andere Parameter gehen hier) { // hier Änderungen an deepCopy von writeArray
vornehmen %Vor% Beachten Sie, dass changeWriteArray eine funktionale Programmierung mit praktisch keiner Nebenwirkung ist, da es eine Kopie zurückgibt, die weder readArray noch writeArray ist.
wer calles changeWriteArray aufruft, muss es als writeArray = changeWriteArray(writeArray.deepCopy()) nennen.
Der Mutex wird sowohl von changeWriteArray als auch von updateReadArray geändert, aber nur von updateReadArray . Wenn der Mutex gesetzt ist, zeigt updateReadArray einfach den Verweis von readArray auf den tatsächlichen Block von writeArray
BEARBEITEN:
@vemv bezüglich der Antwort, die Sie erwähnt haben. Während die Ideen die gleichen sind, ist der Unterschied signifikant: Die beiden statischen Referenzen sind static , so dass keine Zeit damit verbracht wird, die Änderungen tatsächlich in die readArray zu kopieren; Stattdessen wird der Zeiger von readArray so verschoben, dass er auf writeArray zeigt. Effektiv tauschen wir mit einem tmp-Array aus, das changeWriteArray nach Bedarf generiert. Auch das Sperren ist hier minimal, da das Lesen nicht in dem Sinne gesperrt werden muss, dass Sie mehr als ein Lesegerät gleichzeitig haben können.
Tatsächlich können Sie bei diesem Ansatz die Anzahl gleichzeitiger Leser beibehalten und den Zähler auf Null prüfen, wenn Sie readArray mit writeArray aktualisieren möchten. wieder, dass das Lesen überhaupt keine Sperre erfordert.
Bei der Verbesserung der @ zhong.j.yu-Antwort ist es wirklich eine gute Idee, die Schreibvorgänge in eine Warteschlange zu stellen, anstatt zu versuchen, sie auszuführen, wenn sie auftreten. Allerdings müssen wir das Problem angehen, wenn Updates so schnell kommen, dass der Leser ständig aktualisierte Updates erstickt. Meine Idee ist, was passiert, wenn die Lesevorgänge nur die Schreibvorgänge ausführen, die vor dem Lesen in die Warteschlange gestellt wurden, und nachfolgende Schreibvorgänge ignorieren angegangen von nächsten lesen).
Sie müssen Ihre eigene synchronisierte Warteschlange schreiben. Es basiert auf einer verknüpften Liste und würde nur zwei Methoden enthalten:
%Vor%Diese Methode fügt automatisch einen Schreibvorgang ein. Es gibt einen möglichen Deadlock, wenn die Schreibvorgänge schneller kommen würden, als es tatsächlich nötig wäre, um sie in die Warteschlange zu stellen, aber ich denke, dass es jede Sekunde Hunderttausende von Schreibvorgängen geben müsste, um das zu erreichen.
%Vor%Dadurch wird die Warteschlange automatisch leer und der Kopf (oder Schwanz) als Element-Objekt zurückgegeben. Es enthält eine Kette von anderen Elementen (Element.next, etc ..., nur die übliche verknüpfte Liste), die alle eine Kette von Schreibvorgängen seit dem letzten Lesen darstellen. Die Warteschlange wäre dann leer und bereit, neue Schreibvorgänge zu akzeptieren. Der Leser kann dann die Elementkette verfolgen (die bis dahin unabhängig von nachfolgenden Schreibvorgängen bleibt), die Schreibvorgänge ausführen und schließlich das Lesen durchführen. Während der Leser den Lesevorgang verarbeitet, werden neue Schreibvorgänge in die Warteschlange eingereiht, aber diese werden als nächstes gelesen.
Ich schrieb dies einmal, wenn auch in C ++, um einen Sounddatenpuffer darzustellen. Es gab mehr Schreibvorgänge (Treiber sendet mehr Daten), als gelesen (etwas mathematisches Zeug über die Daten), während die Schreibvorgänge so schnell wie möglich beendet werden mussten. (Die Daten kamen in Echtzeit, also musste ich sie speichern, bevor der nächste Stapel im Treiber bereit war.)
Tags und Links java performance concurrency data-structures locking