Java-Parallelität: CAS vs Locking [geschlossen]

76

Ich lese das Buch Java Concurrency in der Praxis . In Kapitel 15 sprechen sie über die nicht blockierenden Algorithmen und die CAS-Methode ( Compare-and-Swap ).

Es steht geschrieben, dass CAS viel besser abschneidet als die Sperrmethoden. Ich möchte die Leute fragen, die bereits mit diesen beiden Konzepten gearbeitet haben, und möchte hören, wann Sie welches dieser Konzepte bevorzugen? Ist es wirklich so viel schneller?

Für mich ist die Verwendung von Schlössern viel klarer und verständlicher und vielleicht sogar besser zu warten (bitte korrigieren Sie mich, wenn ich falsch liege) . Sollten wir uns wirklich darauf konzentrieren, unseren gleichzeitigen Code in Bezug auf CAS als Sperren zu erstellen, um eine bessere Leistungssteigerung zu erzielen, oder ist Nachhaltigkeit wichtiger?

Ich weiß, dass es vielleicht keine strenge Regel gibt, wann was zu verwenden ist. Aber ich möchte nur einige Meinungen und Erfahrungen mit dem neuen Konzept von CAS hören.

Prine
quelle
Das übliche Sperren mit Monitorobjekten umfasst sowohl CAS als auch das Sperren von Kernelaufrufen. Die Kassette erleichtert das Sperren, so dass es keinen Kernelaufruf ohne Konkurrenz gibt. Und wenn es Streit gibt, könnte sich das CAS eine Zeit lang drehen und dann würde der Kernel-Aufruf stattfinden oder der Kernel-Aufruf würde sofort folgen.
Bonita Montero

Antworten:

46

CAS ist im Allgemeinen viel schneller als das Sperren, hängt jedoch vom Grad der Konkurrenz ab. Da CAS einen erneuten Versuch erzwingen kann, wenn sich der Wert zwischen Lesen und Vergleichen ändert, kann ein Thread theoretisch in einer Wartezeit stecken bleiben, wenn die betreffende Variable von vielen anderen Threads hart getroffen wird (oder wenn die Berechnung eines neuen Werts teuer ist vom alten Wert (oder beiden)).

Das Hauptproblem bei CAS ist, dass es viel schwieriger ist, richtig zu programmieren als zu sperren. Wohlgemerkt, das Sperren ist wiederum viel schwieriger korrekt zu verwenden als das Weiterleiten von Nachrichten oder STM . Nehmen Sie dies also nicht als Bestätigung für die Verwendung von Sperren.

Marcelo Cantos
quelle
1
Ich bin damit einverstanden, die Kosten für die Berechnung eines neuen Werts zu betonen . Oft ist es so groß, dass die Strategie ohne Sperren gegen die Sperrung verloren geht.
Alex Salauyou
28

Die relative Geschwindigkeit der Operationen ist weitgehend kein Problem. Relevant ist der Unterschied in der Skalierbarkeit zwischen sperrbasierten und nicht blockierenden Algorithmen. Und wenn Sie auf einem 1- oder 2-Kernsystem arbeiten, denken Sie nicht mehr über solche Dinge nach.

Nicht blockierende Algorithmen skalieren im Allgemeinen besser, da sie kürzere "kritische Abschnitte" aufweisen als sperrbasierte Algorithmen.

Brian Goetz
quelle
23

Sie können sich die Zahlen zwischen a ConcurrentLinkedQueueund a ansehen BlockingQueue. Was Sie sehen werden, ist, dass CAS bei moderaten (in realen Anwendungen realistischeren) Thread-Konflikten spürbar schneller ist.

Die attraktivste Eigenschaft von nicht blockierenden Algorithmen ist die Tatsache, dass andere Threads diesen Fehler nicht bemerken und weitermachen können , wenn ein Thread ausfällt (Cache-Fehler oder schlimmer noch Seg-Fehler). Wenn jedoch beim Erwerb einer Sperre der Thread zum Halten der Sperre einen Betriebssystemfehler aufweist, wird jeder andere Thread, der darauf wartet, dass die Sperre freigegeben wird, ebenfalls von dem Fehler betroffen.

Um Ihre Fragen zu beantworten: Ja, nicht blockierende thread-sichere Algorithmen oder Sammlungen ( ConcurrentLinkedQueue, ConcurrentSkipListMap/Set) können erheblich schneller sein als ihre blockierenden Gegenstücke. Wie Marcelo jedoch betonte, ist es sehr schwierig, nicht blockierende Algorithmen korrekt zu machen, und erfordert viel Überlegung.

Sie sollten sich über die Michael- und Scott-Warteschlange informieren . Dies ist die Warteschlangenimplementierung für ConcurrentLinkedQueueund erklärt, wie eine bidirektionale, threadsichere atomare Funktion mit einem einzigen CAS behandelt wird .

John Vint
quelle
1
Der Artikel über die "Michael and Scott Queue" ist interessant. Danke!
Prine
14

Es gibt ein gutes Buch zum Thema sperrenfreie Parallelität: "Die Kunst der Multiprozessor-Programmierung" von Maurice Herlihy

Victor Sorokin
quelle
Auch seine Präsentation Teil 1 und Teil 2 sind sehr lohnenswert.
Tamas Ionut
9

Wenn Sie nach einem Vergleich in der realen Welt suchen, finden Sie hier einen. Unsere Anwendung verfügt über zwei (2) Threads: 1) einen Reader-Thread für die Erfassung von Netzwerkpaketen und 2) einen Consumer-Thread, der das Paket entgegennimmt, zählt und Statistiken meldet.

Thread Nr. 1 tauscht jeweils ein einzelnes Paket mit Thread Nr. 2 aus

Ergebnis 1 - verwendet einen benutzerdefinierten CAS-basierten Austausch nach denselben Prinzipien wie SynchronousQueue , wobei unsere Klasse CASSynchronousQueue heißt :

30,766,538 packets in 59.999 seconds ::  500.763Kpps, 1.115Gbps 0 drops
libpcap statistics: recv=61,251,128, drop=0(0.0%), ifdrop=0

Ergebnis 2 - wenn wir unsere CAS-Implementierung durch die Standard-Java- SynchronousQueue ersetzen :

8,782,647 packets in 59.999 seconds ::  142.950Kpps, 324.957Mbps 0 drops 
libpcap statistics: recv=69,955,666, drop=52,369,516(74.9%), ifdrop=0

Ich glaube nicht, dass der Leistungsunterschied deutlicher sein könnte.

Mark Bednarczyk
quelle