Оптимистическая синхронизация без ожидания для добавления, удаления и содержит?

Question

Если вы пролистаете одну страницу вниз со страницы 205 книги «Искусство многопроцессорного программирования» (Elsevier, 2012 ISBN 978), на страницу 206 (раздел 9.6 «Оптимистическая синхронизация»): https://books.google.com/... вы увидите, как добавить/удалить/содержит методы для оптимистической синхронизации (рис. 9.11. Класс OptimisticList: метод add() обходит список, игнорируя блокировки, блокирует блокировки и проверяет перед добавлением нового узла. Рисунок 9.12. Класс OptimisticList: метод remove() перемещается, игнорируя блокировки, приобретает блокировки и проверяет удаление узла. page copy).

В следующем разделе, посвященной ленивым синхронизации, он переходит к состоянию (со ссылкой на оптимистическую синхронизацию)

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

Это, кажется, говорят о том, что содержит метод не ждать, свободным, и, следовательно, ни методы добавления, ни удаления не будут. Но я не могу понять, почему это так.

Answer 1

Ленивая синхронизация основана на оптимистичная синхронизация. При ленивой синхронизации вы переходите список только один раз, не приобретая никаких замков, в отличие от, например, ручная блокировка. Когда вы достигли пункта назначения для удаления/добавления/содержит, вам необходимо заблокировать текущий и предшествующий узел. Большая разница заключается в том, что при удалении узла сначала нужно пометить его как удаленное, а затем физически удалить его (сборщик мусора).

Почему этот файл не содержит комментариев? В отличие от оптимистической синхронизации, нам не нужно блокировать текущий узел. Напомним, что мы блокируем текущий узел, чтобы другой поток не удалял его, пока мы возвращаем true. Поскольку текущий узел был отмечен, мы можем просто проверить, если текущий узел отмечен и имеет нужный ключ. Нет необходимости в каких-либо замках. Это делает его безжизненным. Пример кода может выглядеть так:

public boolean contains(T item) { 
int key = item.hashCode(); 
Node curr = this.head; 
while (curr.key < key) { 
curr = curr.next; 
} 
return curr.key == key && !curr.marked; 
}