Ist die optimistische Synchronisation ohne Warten auf Hinzufügen, Entfernen und Enthalten?

Question

Wenn Sie eine Seite von der Seite 205 des Buches "Die Kunst der Multiprozessor-Programmierung" (Elsevier, 2012 ISBN 978) bis Seite 206 (Abschnitt 9.6 Optimistische Synchronisation) scrollen: https://books.google.com/... sehen Sie die add/remove/contains Methoden zur optimistischen Synchronisation (Abbildung 9.11) Die OptimisticList Klasse: Die add() Methode durchläuft die Liste ohne Sperren, erwirbt Sperren und validiert vor dem Hinzufügen des neuen Knotens Abbildung 9.12 Die OptimisticList Klasse: Die remove() Methode durchläuft das Ignorieren von Sperren, erwirbt Sperren und validiert zuvor Entfernen des Knotens. page copy).

Im folgenden Abschnitt auf faule Synchronisation, geht es in dem Zustand auf (während optimistischer Synchronisation mit Bezug)

The next step is to refine this algorithm so that contains() calls are wait-free, and add() and remove() methods, while still blocking, traverse the list only once

Dies scheint zu sagen, dass die enthält Methode ist nicht frei warten, und so weder würde die hinzufügen oder entfernen Methoden sein. Aber ich kann nicht verstehen, warum das der Fall ist.

Answer 1

Lazy Synchronisation basiert auf optimistische Synchronisation. Bei einer verzögerten Synchronisation durchqueren Sie die Liste nur einmal, ohne irgendwelche Sperren zu erhalten, im Gegensatz zu z. Hand-über-Hand-Verriegelung. Wenn Sie Ihr Ziel für remove/add/contains erreicht haben, müssen Sie den aktuellen und den Vorgängerknoten sperren. Der große Unterschied ist, dass wenn Sie einen Knoten entfernen, müssen Sie es zuerst als gelöscht markieren und löschen Sie es dann (Garbage Collector).

Warum ist enthält wartefrei? Im Gegensatz zur optimistischen Synchronisation müssen wir den aktuellen Knoten nicht sperren. Erinnern wir uns, dass wir den aktuellen Knoten sperren, so dass ein anderer Thread ihn nicht löschen kann, während wir den Wert true zurückgeben. Da der aktuelle Knoten markiert worden wäre, können wir einfach prüfen, ob der aktuelle Knoten markiert ist und den gewünschten Schlüssel hat. Keine Notwendigkeit für irgendwelche Sperren. Dies macht es wartungsfrei. Ein Beispielcode könnte folgendermaßen aussehen: