Usecase использования AtomicStampedReference & AtomicMarkableReference
Я ищу пример AtomicStampedReference &/или AtomicMarkableReference, который мог бы помочь мне понять эти классы и их функции.
Я не могу получить какие-либо примеры качества через Интернет.
Я могу придумать их использование в сборке мусора, но пример качества поможет мне лучше понять это.
Ответы
Ответ 1
Практические примеры (сложные)
Для AtomicMarkableReference:
https://github.com/arunmoezhi/ConcurrentKaryST
Для AtomicStampedReference
https://github.com/arunmoezhi/LockFreeBST
Простой пример:
В двоичном дереве, если вы хотите изменить дочерний элемент родительского node atomically, можно использовать compareAndSwap на AtomicMarkableReference.
В двоичном дереве можно сказать, что вы хотите помечать node атомарно. Тогда можно использовать AtomicStampedReference.
Вышеупомянутые сложные реализационные реализации используют эти два типа классов.
Ответ 2
S Kr Вот объяснение. Возьмите стек, который выглядит следующим образом: top → A → B → C.
Возьмите две нити, Th1 и Th2. Они используют не блокирующий сравнение и набор (CAS) для поп-операций.
Th1: установите return = A, next = B.. но выйдет из состояния работы
Th2:
- pop A: return = A, next = B, CAS (A, B).. так что теперь top = B
- pop B: return = B, next = C, CAS (B, C).. так что теперь top = C
- push A (тот же самый, что и раньше, удовлетворяющий ==, потому что позволяет сказать, что он был кеширован где-то):.. так что теперь top - это A, а стек выглядит так. top → A → C
Th1: вернуться в действие.. и возобновляет.. CAS (A, B).. это преуспевает!! Стек теперь выглядит так. Top → B → C.. но.. но.. B уже был удален из стека по потоку 2, и он волшебным образом возвращается! Bad.
Мораль истории: используйте AtomicStampedReference. AtomicMarkableReference - это особый случай AtomicStampedReference.
Бонус: подумайте о отсортированном связанном списке и о нескольких потоках, работающих над ним. Попробуйте вставить C в → B → D → E и выяснить аналогичную проблему ABA.
