In Java kann ich davon ausgehen, dass die Referenzzuweisung atomar ist, um eine Kopie beim Schreiben zu implementieren?

Anstatt zu versuchen, eine eigene Lösung zu rollen, warum nicht ein ConcurrentHashMap als Ihr Set und einfach alle Werte auf einen Standardwert setzen? (Eine Konstante wie Boolean.TRUE würde gut funktionieren.)

Ich denke, diese Implementierung funktioniert gut mit dem Szenario mit vielen Lesern und wenigen Autoren. Es gibt sogar ein Konstruktor Damit können Sie die erwartete "Parallelitätsebene" festlegen .

Update: Veer hat vorgeschlagen, Collections.newSetFromMap Dienstprogrammmethode, um die ConcurrentHashMap in ein Set zu verwandeln. Da die Methode ein Map<E,Boolean> verwendet, ist es wahrscheinlich, dass sie dasselbe tut, wenn sie alle Werte hinter den Kulissen auf Boolean.TRUE setzt.

Update: Adressierung des Beispiels des Posters

  

Wahrscheinlich werde ich damit enden, aber ich bin immer noch neugierig darauf, wie meine minimalistische Lösung scheitern könnte. - MilesHampson

Ihre minimalistische Lösung würde mit ein paar Optimierungen gut funktionieren. Meine Sorge ist, dass, obwohl es jetzt minimal ist, es in Zukunft komplizierter werden könnte. Es ist schwer, sich an all die Bedingungen zu erinnern, die man annimmt, wenn man etwas threadsicher macht - vor allem, wenn man Wochen / Monate / Jahre später zum Code zurückkehrt, um eine scheinbar unbedeutende Optimierung vorzunehmen. Wenn die ConcurrentHashMap alles mit einer ausreichenden Leistung macht, dann warum nicht stattdessen? All die unangenehmen Nebenläufigkeitsdetails sind verkapselt und selbst in 6 Monaten werden Sie es schwer haben, es zu vermasseln!

Sie benötigen mindestens eine Optimierung, bevor Ihre aktuelle Lösung funktioniert. Wie bereits erwähnt, sollten Sie wahrscheinlich den volatile -Modifikator zur global -Deklaration hinzufügen. Ich weiß nicht, wenn Sie einen C / C ++ Hintergrund haben, aber ich war sehr überrascht, als ich erfuhr, dass die Semantik volatile in Java sind eigentlich viel komplizierter als in C . Wenn Sie in Java planen viele gleichzeitige Programmierung auf tun, dann würde es eine gute Idee sein, sich die mit den Grundlagen von vertraut zu machen Java-Speichermodell Wenn Sie nicht über die Verweisung auf global a volatile Referenz dann ist es möglich, dass kein Thread jemals irgendwelche Änderungen an den Wert von global sehen, bis sie versuchen, es zu aktualisieren, an welchem ​​Punkt der Eingabe des synchronized Block wird den lokalen Cache leeren und den aktualisierten Referenzwert erhalten.

Aber selbst mit dem Zusatz von volatile gibt es immer noch ein großes Problem. Hier ist ein Problemszenario mit zwei Threads:

1. Wir beginnen mit der leeren Menge oder global={} . Die Threads A und B haben beide diesen Wert in ihrem Thread-lokalen Cache-Speicher.
2. Thread A erhält die synchronized Sperre für global und startet das Update, indem eine Kopie von global erstellt und der neue Schlüssel zur Menge hinzugefügt wird.
3. Während sich Thread A immer noch im Block synchronized befindet, liest der Thread B seinen lokalen Wert von global auf dem Stapel und versucht, den Block synchronized einzugeben. Seit Thread A befindet sich derzeit im Monitor Thread B blocks.
4. Thread A schließt die Aktualisierung ab, indem die Referenz gesetzt und der Monitor beendet wird, was in global={1} resultiert.
5. Thread B kann nun den Monitor aufrufen und erstellt eine Kopie von global={1} set.
6. Thread A entscheidet sich für eine weitere Aktualisierung, liest seine lokale global -Referenz ein und versucht, den synchronized -Block einzugeben. Da Thread B momentan die Sperre für {} enthält, gibt es keine Sperre für {1} und Thread A tritt erfolgreich in den Monitor ein!
7. Thread A erstellt auch eine Kopie von {1} für die Aktualisierung.

Jetzt sind die Threads A und B beide im Block synchronized und sie haben identische Kopien der global={1} Menge. Dies bedeutet, dass eines ihrer Updates verloren geht! Diese Situation wird dadurch verursacht, dass Sie ein Objekt synchronisieren, das in einer Referenz gespeichert ist, die Sie in Ihrem synchronized -Block aktualisieren. Sie sollten immer sehr vorsichtig sein, welche Objekte Sie zum Synchronisieren verwenden. Sie können dieses Problem beheben, indem Sie eine neue Variable hinzufügen, die als Sperre fungiert:

Dieser Fehler war heimtückisch genug, dass noch keine der anderen Antworten darauf eingegangen ist. Es sind diese verrückten Nebenläufigkeitsdetails, die mich dazu veranlassen, etwas aus der bereits debuggten java.util.concurrent-Bibliothek zu empfehlen, anstatt selbst etwas zusammenzusetzen. Ich denke, die obige Lösung würde funktionieren - aber wie leicht wäre es, es wieder zu vermasseln? Das wäre so viel einfacher:

Da der Verweis final ist, müssen Sie sich keine Sorgen über Threads machen, die veraltete Referenzen verwenden, und da %%_co_de% intern alle Probleme mit dem fiesen Speichermodell behandelt, müssen Sie sich nicht um all die unangenehmen Details von Monitore und Speicherbarrieren!

Laut dem entsprechenden Java-Lernprogramm

  

Wir haben bereits gesehen, dass ein Inkrement-Ausdruck wie c++ keine atomare Aktion beschreibt. Selbst sehr einfache Ausdrücke können komplexe Aktionen definieren, die in andere Aktionen zerlegt werden können. Es gibt jedoch Aktionen, die Sie atomar spezifizieren können:

     

• Lese- und Schreibvorgänge sind atomar für Referenzvariablen und für die meisten primitiven Variablen (alle Typen außer long und double ).
  
• Lese- und Schreibvorgänge sind für alle deklarierten Variablen volatile ( einschließlich long und double Variablen) atomar.
  

Dies wird von Abschnitt §17.7 der Java-Sprache bestätigt Spezifikation

  

Schreiben und Lesen von Referenzen sind immer atomar, unabhängig davon, ob sie als 32-Bit- oder als 64-Bit-Werte implementiert sind.

Es scheint, dass Sie sich tatsächlich darauf verlassen können, dass der Referenzzugriff atomar ist; Beachten Sie jedoch, dass dies nicht sicherstellt, dass alle Leser nach diesem Schreiben einen aktualisierten Wert für global lesen - d. h. hier ist keine Speicherbestellgarantie vorhanden.

Wenn Sie eine implizite Sperre über synchronized bei allen Zugriffen auf global verwenden, können Sie hier eine gewisse Speicherkonsistenz erzeugen ... aber es könnte besser sein, einen alternativen Ansatz zu verwenden.

Sie scheinen auch zu wollen, dass die Sammlung in global unveränderlich bleibt ... glücklicherweise gibt es Collections.unmodifiableSet , die Sie verwenden können, um dies zu erzwingen. Als ein Beispiel sollten Sie etwas wie das folgende tun ...

... oder mit AtomicReference ,

Sie würden dann Collections.unmodifiableSet auch für Ihre modifizierten Kopien verwenden.

Sie sollten wissen, dass eine Kopie hier redundant ist, da intern for (Object elm : global) wie folgt ein Iterator erstellt ...

Es besteht daher keine Möglichkeit, während des Lesens zu einem ganz anderen Wert für global zu wechseln.

Abgesehen davon stimme ich der von DaoWen geäußerte Meinung ... gibt es einen Grund, warum Sie Ihre eigene Datenstruktur hier rollen, wenn es eine Alternative in java.util.concurrent verfügbar? Ich habe mir gedacht, dass Sie es vielleicht mit einem älteren Java zu tun haben, da Sie rohe Typen verwenden, aber es wird nicht schaden zu fragen.

Sie finden eine Semantik zum Kopieren und Schreiben von Sammlungen, die von % bereitgestellt wird. co_de% oder sein Cousin CopyOnWriteArrayList (die ein CopyOnWriteArraySet mit dem ersteren implementiert).

Auch vorgeschlagen von DaoWen , haben Sie überlegt, ein Set ? Sie garantieren, dass die Verwendung einer ConcurrentHashMap -Schleife wie in Ihrem Beispiel konsistent ist.

  

In ähnlicher Weise geben Iteratoren und Enumerationen Elemente zurück, die den Zustand der Hash-Tabelle zu irgendeinem Zeitpunkt bei oder seit der Erstellung des Iterators / der Enumeration widerspiegeln.

Intern wird ein for für die erweiterte Iterator über einem for verwendet.

Sie können ein Iterable daraus erstellen, indem Sie Set wie folgt:

Ich denke, deine ursprüngliche Idee war solide und DaoWen hat einen guten Job gemacht, die Käfer rauszubekommen. Wenn du nicht etwas finden kannst, das alles für dich macht, ist es besser, diese Dinge zu verstehen, als zu hoffen, dass eine magische Klasse es für dich tun wird. Magische Klassen können Ihr Leben erleichtern und die Anzahl der Fehler reduzieren, aber Sie möchten verstehen, was sie tun.

ConcurrentSkipListSet könnte hier eine bessere Arbeit für Sie leisten. Es könnte alle Ihre Multithreading-Probleme loswerden.

Allerdings ist es langsamer als ein HashSet (normalerweise - HashSets und SkipLists / Trees sind schwer zu vergleichen). Wenn Sie für jeden Schreibvorgang viele Lesevorgänge durchführen, wird das, was Sie haben, schneller sein. Noch wichtiger: Wenn Sie mehr als einen Eintrag gleichzeitig aktualisieren, können Ihre Lesevorgänge zu inkonsistenten Ergebnissen führen. Wenn Sie erwarten, dass es immer einen Eintrag B gibt, wenn ein Eintrag A vorhanden ist, und umgekehrt, könnte die Sprungliste Ihnen einen ohne den anderen geben.

Mit Ihrer aktuellen Lösung für die Leser sind die Inhalte der Karte immer intern konsistent. Ein Lesevorgang kann sicherstellen, dass für jedes B ein A vorhanden ist. Es kann sichergestellt werden, dass die Methode size() die genaue Anzahl der Elemente angibt, die vom Iterator zurückgegeben werden. Zwei Iterationen geben die gleichen Elemente in der gleichen Reihenfolge zurück.

Mit anderen Worten, allUpdatesGoThroughHere und ConcurrentSkipListSet sind zwei gute Lösungen für zwei verschiedene Probleme.

Ersetze synchronized , indem du global volatile machst und du wirst in Ordnung sein, solange die Kopie beim Schreiben geht.

Obwohl die Zuweisung atomar ist, wird sie in anderen Threads nicht mit den Schreiboperationen auf das referenzierte Objekt geordnet. Es muss eine hases-before Beziehung geben, die Sie mit einem volatile erhalten, oder beide Lese- und Schreibvorgänge synchronisieren.

Das Problem, dass mehrere Aktualisierungen gleichzeitig stattfinden, ist separat - verwenden Sie einen einzelnen Thread oder was auch immer Sie dort tun möchten.

Wenn Sie synchronized sowohl für Lese- als auch für Schreibvorgänge verwendet haben, ist es korrekt, aber die Leistung ist möglicherweise bei Lesevorgängen, die übergeben werden müssen, nicht optimal. Ein ReadWriteLock mag zwar angemessen sein, aber Sie hätten immer noch blockierende Lesevorgänge.

Ein weiterer Ansatz für das Publikationsproblem besteht darin, die Semantik des letzten Felds zu verwenden, um ein Objekt zu erstellen, das (in der Theorie) sicher nicht sicher veröffentlicht werden kann.

Natürlich sind auch gleichzeitige Sammlungen verfügbar.

Können Sie die Methode Collections.synchronizedSet verwenden? Aus HashSet Javadoc Ссылка