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

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

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

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

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


multithreading optimization synchronization locking optimistic-locking
person Rodger Harris    schedule 22.07.2016    source источник
comment
Реализация всех трех методов вызывает .lock(), который может подождать. Именно поэтому они не требуют ожидания.   -  person Tsyvarev    schedule 22.07.2016

Ответы (1)


arrow_upward
2
arrow_downward

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

Почему содержит без ожидания? В отличие от оптимистической синхронизации, нам не нужно блокировать текущий узел. Напомним, что мы блокируем текущий узел, чтобы другой поток не мог его удалить, пока мы возвращаем значение 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;
}
person jbuchel    schedule 04.05.2017